IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v38y2019i2d10.1007_s10878-019-00385-2.html
   My bibliography  Save this article

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

Author

Listed:
  • Byung-Cheon Choi

    (Chungnam National University)

  • Changmuk Kang

    (Soongsil University)

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.

Suggested Citation

  • Byung-Cheon Choi & Changmuk Kang, 2019. "A linear time–cost tradeoff problem with multiple milestones under a comb graph," Journal of Combinatorial Optimization, Springer, vol. 38(2), pages 341-361, August.
    • Handle: RePEc:spr:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00385-2
    DOI: 10.1007/s10878-019-00385-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-019-00385-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-019-00385-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Choi, Byung-Cheon & Chung, Jibok, 2014. "Complexity results for the linear time–cost tradeoff problem with multiple milestones and completely ordered jobs," European Journal of Operational Research, Elsevier, vol. 236(1), pages 61-68.
    2. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    3. Weglarz, Jan & Józefowska, Joanna & Mika, Marek & Waligóra, Grzegorz, 2011. "Project scheduling with finite or infinite number of activity processing modes - A survey," European Journal of Operational Research, Elsevier, vol. 208(3), pages 177-205, February.
    4. James E. Kelley, 1961. "Critical-Path Planning and Scheduling: Mathematical Basis," Operations Research, INFORMS, vol. 9(3), pages 296-320, June.
    5. Choi, Byung-Cheon & Park, Myoung-Ju, 2015. "A continuous time–cost tradeoff problem with multiple milestones and completely ordered jobs," European Journal of Operational Research, Elsevier, vol. 244(3), pages 748-752.
    6. D. R. Fulkerson, 1961. "A Network Flow Computation for Project Cost Curves," Management Science, INFORMS, vol. 7(2), pages 167-178, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Xue Li & Zhengwen He & Nengmin Wang & Mario Vanhoucke, 2022. "Multimode time-cost-robustness trade-off project scheduling problem under uncertainty," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1173-1202, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Choi, Byung-Cheon & Park, Myoung-Ju, 2015. "A continuous time–cost tradeoff problem with multiple milestones and completely ordered jobs," European Journal of Operational Research, Elsevier, vol. 244(3), pages 748-752.
    2. Geng, Zhichao & Yuan, Jinjiang, 2023. "Single-machine scheduling of multiple projects with controllable processing times," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1074-1090.
    3. Choi, Byung-Cheon & Chung, Jibok, 2014. "Complexity results for the linear time–cost tradeoff problem with multiple milestones and completely ordered jobs," European Journal of Operational Research, Elsevier, vol. 236(1), pages 61-68.
    4. Byung-Cheon Choi & Myoung-Ju Park, 2020. "Scheduling two projects with controllable processing times in a single-machine environment," Journal of Scheduling, Springer, vol. 23(5), pages 619-628, October.
    5. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    6. Nicole Megow & Rolf H. Möhring & Jens Schulz, 2011. "Decision Support and Optimization in Shutdown and Turnaround Scheduling," INFORMS Journal on Computing, INFORMS, vol. 23(2), pages 189-204, May.
    7. Zhao, Mingxuan & Zhou, Jian & Wang, Ke & Pantelous, Athanasios A., 2023. "Project scheduling problem with fuzzy activity durations: A novel operational law based solution framework," European Journal of Operational Research, Elsevier, vol. 306(2), pages 519-534.
    8. A B Hafızoğlu & M Azizoğlu, 2010. "Linear programming based approaches for the discrete time/cost trade-off problem in project networks," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(4), pages 676-685, April.
    9. Herroelen, Willy & Leus, Roel, 2004. "The construction of stable project baseline schedules," European Journal of Operational Research, Elsevier, vol. 156(3), pages 550-565, August.
    10. Roland Braune & Karl F. Doerner, 2017. "Real-world flexible resource profile scheduling with multiple criteria: learning scalarization functions for MIP and heuristic approaches," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 952-972, August.
    11. Gehring, Marco & Volk, Rebekka & Schultmann, Frank, 2022. "On the integration of diverging material flows into resource‐constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1071-1087.
    12. Siqian Shen & J. Cole Smith & Shabbir Ahmed, 2010. "Expectation and Chance-Constrained Models and Algorithms for Insuring Critical Paths," Management Science, INFORMS, vol. 56(10), pages 1794-1814, October.
    13. Luise-Sophie Hoffmann & Carolin Kellenbrink & Stefan Helber, 2020. "Simultaneous structuring and scheduling of multiple projects with flexible project structures," Journal of Business Economics, Springer, vol. 90(5), pages 679-711, June.
    14. Perrone, G. & Roma, P. & Lo Nigro, G., 2010. "Designing multi-attribute auctions for engineering services procurement in new product development in the automotive context," International Journal of Production Economics, Elsevier, vol. 124(1), pages 20-31, March.
    15. Servranckx, Tom & Vanhoucke, Mario, 2019. "A tabu search procedure for the resource-constrained project scheduling problem with alternative subgraphs," European Journal of Operational Research, Elsevier, vol. 273(3), pages 841-860.
    16. Kellenbrink, Carolin & Helber, Stefan, 2015. "Scheduling resource-constrained projects with a flexible project structure," European Journal of Operational Research, Elsevier, vol. 246(2), pages 379-391.
    17. Zhengwen He & Nengmin Wang & Pengxiang Li, 2014. "Simulated annealing for financing cost distribution based project payment scheduling from a joint perspective," Annals of Operations Research, Springer, vol. 213(1), pages 203-220, February.
    18. Xue Li & Zhengwen He & Nengmin Wang & Mario Vanhoucke, 2022. "Multimode time-cost-robustness trade-off project scheduling problem under uncertainty," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1173-1202, July.
    19. Van Peteghem, Vincent & Vanhoucke, Mario, 2014. "An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances," European Journal of Operational Research, Elsevier, vol. 235(1), pages 62-72.
    20. Marcin Anholcer & Helena Gaspars-Wieloch, 2011. "Efficiency analysis of the Kaufmann and Dezbazeille algorithm for the deadline problem," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 21(1), pages 5-18.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00385-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.