IDEAS home Printed from https://ideas.repec.org/p/zbw/cauman/639.html
   My bibliography  Save this paper

Robust scheduling on a single machine usinge time buffers

Author

Listed:
  • Briskorn, Dirk
  • Leung, Joseph
  • Pinedo, Michael

Abstract

This paper studies the allocation of buffer times in a single machine environment. Buffer times are a common tool to protect the schedule against disruptions such as machine failures. We introduce new classes of robust machine scheduling problems. For an arbitrary scheduling problem 1|ß|y, prmt ∉ ß, we obtain three corresponding robust problems: maximize overall (weighted) buffer time while ensuring a given schedule's performance (regarding y), optimize the schedule's performance (regarding y) while ensuring a given minimum overall (weighted) buffer time, and finding the trade off curve regarding both objectives. We outline the relationships between the different classes of problems and the corresponding underlying problem. Furthermore, we analyze the robust counterparts of three fundamental problems.

Suggested Citation

  • Briskorn, Dirk & Leung, Joseph & Pinedo, Michael, 2008. "Robust scheduling on a single machine usinge time buffers," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 639, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    • Handle: RePEc:zbw:cauman:639
    as

    Download full text from publisher

    File URL: https://www.econstor.eu/bitstream/10419/147557/1/manuskript_639.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Van de Vonder, Stijn & Demeulemeester, Erik & Herroelen, Willy & Leus, Roel, 2005. "The use of buffers in project management: The trade-off between stability and makespan," International Journal of Production Economics, Elsevier, vol. 97(2), pages 227-240, August.
    2. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    3. 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.
    4. Aytug, Haldun & Lawley, Mark A. & McKay, Kenneth & Mohan, Shantha & Uzsoy, Reha, 2005. "Executing production schedules in the face of uncertainties: A review and some future directions," European Journal of Operational Research, Elsevier, vol. 161(1), pages 86-110, February.
    5. Richard L. Daniels & Panagiotis Kouvelis, 1995. "Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production," Management Science, INFORMS, vol. 41(2), pages 363-376, February.
    6. S. David Wu & Eui-Seok Byeon & Robert H. Storer, 1999. "A Graph-Theoretic Decomposition of the Job Shop Scheduling Problem to Achieve Scheduling Robustness," Operations Research, INFORMS, vol. 47(1), pages 113-124, February.
    7. Kobylanski, Przemyslaw & Kuchta, Dorota, 2007. "A note on the paper by M. A. Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling," International Journal of Production Economics, Elsevier, vol. 107(2), pages 496-501, June.
    Full references (including those not matched with items on IDEAS)

    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. Xiong, Jian & Xing, Li-ning & Chen, Ying-wu, 2013. "Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns," International Journal of Production Economics, Elsevier, vol. 141(1), pages 112-126.
    2. Al-Hinai, Nasr & ElMekkawy, T.Y., 2011. "Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm," International Journal of Production Economics, Elsevier, vol. 132(2), pages 279-291, August.
    3. Dmitry Ivanov & Alexandre Dolgui & Boris Sokolov & Frank Werner, 2016. "Schedule robustness analysis with the help of attainable sets in continuous flow problem under capacity disruptions," International Journal of Production Research, Taylor & Francis Journals, vol. 54(11), pages 3397-3413, June.
    4. Said, Samer S. & Haouari, Mohamed, 2015. "A hybrid simulation-optimization approach for the robust Discrete Time/Cost Trade-off Problem," Applied Mathematics and Computation, Elsevier, vol. 259(C), pages 628-636.
    5. Morteza Davari & Erik Demeulemeester, 2019. "The proactive and reactive resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 22(2), pages 211-237, April.
    6. Lamas, Patricio & Goycoolea, Marcos & Pagnoncelli, Bernardo & Newman, Alexandra, 2024. "A target-time-windows technique for project scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 314(2), pages 792-806.
    7. Gang Xuan & Win-Chin Lin & Shuenn-Ren Cheng & Wei-Lun Shen & Po-An Pan & Chih-Ling Kuo & Chin-Chia Wu, 2022. "A Robust Single-Machine Scheduling Problem with Two Job Parameter Scenarios," Mathematics, MDPI, vol. 10(13), pages 1-17, June.
    8. Silva, Marco & Poss, Michael & Maculan, Nelson, 2020. "Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty," European Journal of Operational Research, Elsevier, vol. 283(1), pages 70-82.
    9. Lin, Jun & Ng, Tsan Sheng, 2011. "Robust multi-market newsvendor models with interval demand data," European Journal of Operational Research, Elsevier, vol. 212(2), pages 361-373, July.
    10. Balouka, Noemie & Cohen, Izack, 2021. "A robust optimization approach for the multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 291(2), pages 457-470.
    11. Wei Chen & Ying Zhao & Yangqing Yu & Kaiman Chen & Mehrdad Arashpour, 2020. "Collaborative Scheduling of On-Site and Off-Site Operations in Prefabrication," Sustainability, MDPI, vol. 12(21), pages 1-21, November.
    12. Olivier Lambrechts & Erik Demeulemeester & Willy Herroelen, 2011. "Time slack-based techniques for robust project scheduling subject to resource uncertainty," Annals of Operations Research, Springer, vol. 186(1), pages 443-464, June.
    13. Yuli Zhang & Zuo-Jun Max Shen & Shiji Song, 2018. "Exact Algorithms for Distributionally β -Robust Machine Scheduling with Uncertain Processing Times," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 662-676, November.
    14. Nikulin, Yury, 2006. "Robustness in combinatorial optimization and scheduling theory: An extended annotated bibliography," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 606, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    15. Yin, Yunqiang & Luo, Zunhao & Wang, Dujuan & Cheng, T.C.E., 2023. "Wasserstein distance‐based distributionally robust parallel‐machine scheduling," Omega, Elsevier, vol. 120(C).
    16. Öncü Hazir & Gündüz Ulusoy, 2020. "A classification and review of approaches and methods for modeling uncertainty in projects," Post-Print hal-02898162, HAL.
    17. Song, Jie & Martens, Annelies & Vanhoucke, Mario, 2021. "Using Schedule Risk Analysis with resource constraints for project control," European Journal of Operational Research, Elsevier, vol. 288(3), pages 736-752.
    18. Abdelhamid Boudjelida, 2019. "On the robustness of joint production and maintenance scheduling in presence of uncertainties," Journal of Intelligent Manufacturing, Springer, vol. 30(4), pages 1515-1530, April.
    19. Laslo, Zohar & Golenko-Ginzburg, Dimitri & Keren, Baruch, 2008. "Optimal booking of machines in a virtual job-shop with stochastic processing times to minimize total machine rental and job tardiness costs," International Journal of Production Economics, Elsevier, vol. 111(2), pages 812-821, February.
    20. Wendi Tian & Erik Demeulemeester, 2014. "Railway scheduling reduces the expected project makespan over roadrunner scheduling in a multi-mode project scheduling environment," Annals of Operations Research, Springer, vol. 213(1), pages 271-291, February.

    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:zbw:cauman:639. 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: ZBW - Leibniz Information Centre for Economics (email available below). General contact details of provider: https://edirc.repec.org/data/ibkiede.html .

    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.