IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v23y2020i1d10.1007_s10951-019-00621-x.html
   My bibliography  Save this article

Maximizing the number of jobs scheduled at their baseline starting times in case of machine failures

Author

Listed:
  • Philippe Chrétienne

    (Sorbonne Université, Université Pierre et Marie Curie)

Abstract

We investigate the problem of keeping the maximum number of starting times of a baseline schedule if some machines happen to be out of order when the baseline schedule is to be implemented. If the machines are identical, we show that the problem is polynomially solved when no deadline is imposed on the reactive schedule and is strongly NP-hard otherwise. If the number of unrelated machines is fixed and if no deadline is imposed on the reactive schedule, a polynomial algorithm, based on a state graph, has been developed. We conclude with an open complexity question and some further research directions for this class of problems.

Suggested Citation

  • Philippe Chrétienne, 2020. "Maximizing the number of jobs scheduled at their baseline starting times in case of machine failures," Journal of Scheduling, Springer, vol. 23(1), pages 135-143, February.
    • Handle: RePEc:spr:jsched:v:23:y:2020:i:1:d:10.1007_s10951-019-00621-x
    DOI: 10.1007/s10951-019-00621-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-019-00621-x
    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/s10951-019-00621-x?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. HazIr, Öncü & Haouari, Mohamed & Erel, Erdal, 2010. "Robust scheduling and robustness measures for the discrete time/cost trade-off problem," European Journal of Operational Research, Elsevier, vol. 207(2), pages 633-643, December.
    2. Bendotti, Pascale & Chrétienne, Philippe & Fouilhoux, Pierre & Quilliot, Alain, 2017. "Anchored reactive and proactive solutions to the CPM-scheduling problem," European Journal of Operational Research, Elsevier, vol. 261(1), pages 67-74.
    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.
    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. Bendotti, Pascale & Chrétienne, Philippe & Fouilhoux, Pierre & Pass-Lanneau, Adèle, 2021. "Dominance-based linear formulation for the Anchor-Robust Project Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 22-33.
    2. Hazır, Öncü & Ulusoy, Gündüz, 2020. "A classification and review of approaches and methods for modeling uncertainty in projects," International Journal of Production Economics, Elsevier, vol. 223(C).
    3. Philippe Chrétienne, 2021. "Reactive and proactive single-machine scheduling to maintain a maximum number of starting times," Annals of Operations Research, Springer, vol. 298(1), pages 111-124, March.
    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. Ö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.
    6. 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.
    7. Shichang Xiao & Zigao Wu & Hongyan Dui, 2022. "Resilience-Based Surrogate Robustness Measure and Optimization Method for Robust Job-Shop Scheduling," Mathematics, MDPI, vol. 10(21), pages 1-22, October.
    8. 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.
    9. Yan Zhao & Nanfang Cui & Wendi Tian, 2020. "A two-stage approach for the critical chain project rescheduling," Annals of Operations Research, Springer, vol. 285(1), pages 67-95, February.
    10. Junguang Zhang & Dan Wan, 2021. "Determination of early warning time window for bottleneck resource buffer," Annals of Operations Research, Springer, vol. 300(1), pages 289-305, May.
    11. Song, Jie & Martens, Annelies & Vanhoucke, Mario, 2022. "Using Earned Value Management and Schedule Risk Analysis with resource constraints for project control," European Journal of Operational Research, Elsevier, vol. 297(2), pages 451-466.
    12. Xiang Chu & Qiu-Yan Zhong & Shahid G. Khokhar, 2015. "Triage Scheduling Optimization for Mass Casualty and Disaster Response," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(06), pages 1-20, December.
    13. 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.
    14. Bendotti, Pascale & Chrétienne, Philippe & Fouilhoux, Pierre & Quilliot, Alain, 2017. "Anchored reactive and proactive solutions to the CPM-scheduling problem," European Journal of Operational Research, Elsevier, vol. 261(1), pages 67-74.
    15. Elmaghraby, Salah E., 2005. "On the fallacy of averages in project risk management," European Journal of Operational Research, Elsevier, vol. 165(2), pages 307-313, September.
    16. 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.
    17. Can Akkan & Ayla Gülcü & Zeki Kuş, 2022. "Bi-criteria simulated annealing for the curriculum-based course timetabling problem with robustness approximation," Journal of Scheduling, Springer, vol. 25(4), pages 477-501, August.
    18. Bowman, R. Alan, 2006. "Developing activity duration specification limits for effective project control," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1191-1204, October.
    19. 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.
    20. Shichang Xiao & Shudong Sun & Jionghua (Judy) Jin, 2017. "Surrogate Measures for the Robust Scheduling of Stochastic Job Shop Scheduling Problems," Energies, MDPI, vol. 10(4), pages 1-26, April.

    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:jsched:v:23:y:2020:i:1:d:10.1007_s10951-019-00621-x. 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.