A linear time–cost tradeoff problem with multiple milestones under a comb graph

Byung-Cheon Choi () and Changmuk Kang ()
Additional contact information
Byung-Cheon Choi: Chungnam National University
Changmuk Kang: Soongsil University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 2, No 2, 361 pages

Abstract: Abstract We consider a linear time–cost tradeoff problem (LTCTP) with multiple milestones under a comb graph. A time–cost tradeoff problem decides whether and how much to spend a cost to compress processing time of a job in order to meet promised due dates. This is common in managing a project because additional labors or resources are expensive. It is called linear where the compression cost linearly increases with reduced time. An objective of the LTCTP that this study addresses is to minimize the weighted number of tardy milestones plus the total compression cost. This study considers a special precedence structure, which is called a comb graph. A chain of jobs that sequentially precede each other forms a main process of a project, and other chains of jobs, corresponding to sub processes, precede each job in the main process. For this structure, we developed a strongly-polynomial-time algorithm. This is the first result of unveiling complexity of the multi-milestone LTCTP under a non-chain structure.

Keywords: Project scheduling; Time–cost tradeoff; Multiple milestones; Comb graph (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00385-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00385-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00385-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().