IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v337y2024i2d10.1007_s10479-023-05537-6.html
   My bibliography  Save this article

Exact and heuristic methods for Anchor-Robust and Adjustable-Robust RCPSP

Author

Listed:
  • Adèle Pass-Lanneau

    (EDF R &D
    Sorbonne Université, CNRS)

  • Pascale Bendotti

    (EDF R &D
    Sorbonne Université, CNRS)

  • Luca Brunod-Indrigo

    (EDF R &D
    Sorbonne Université, CNRS)

Abstract

The concept of anchored solutions is proposed as a new robust optimization approach to the Resource-Constrained Project Scheduling Problem (RCPSP) under processing times uncertainty. The Anchor-Robust RCPSP is defined, to compute a baseline schedule with bounded makespan, sequencing decisions, and a max-size subset of jobs with guaranteed starting times, called anchored set. It is shown that the Adjustable-Robust RCPSP from the literature fits within the framework of anchored solutions. The Anchor-Robust RCPSP and the Adjustable-Robust RCPSP can benefit from each other to find both a worst-case makespan, and a baseline schedule with an anchored set. A dedicated graph model for anchored solutions is reviewed for budgeted uncertainty. Compact MIP reformulations are derived for both the Adjustable-Robust RCPSP and the Anchor-Robust RCPSP. Dedicated heuristics are designed based on the graph model. For both problems, the efficiency of the proposed MIP reformulations and heuristic approaches is assessed through numerical experiments on benchmark instances.

Suggested Citation

  • Adèle Pass-Lanneau & Pascale Bendotti & Luca Brunod-Indrigo, 2024. "Exact and heuristic methods for Anchor-Robust and Adjustable-Robust RCPSP," Annals of Operations Research, Springer, vol. 337(2), pages 649-682, June.
    • Handle: RePEc:spr:annopr:v:337:y:2024:i:2:d:10.1007_s10479-023-05537-6
    DOI: 10.1007/s10479-023-05537-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-023-05537-6
    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/s10479-023-05537-6?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. 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).
    2. Rainer Kolisch & Arno Sprecher & Andreas Drexl, 1995. "Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems," Management Science, INFORMS, vol. 41(10), pages 1693-1703, October.
    3. Artigues, Christian & Michelon, Philippe & Reusser, Stephane, 2003. "Insertion techniques for static and dynamic resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 149(2), pages 249-267, September.
    4. Ö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.
    5. A. L. Soyster, 1973. "Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming," Operations Research, INFORMS, vol. 21(5), pages 1154-1157, October.
    6. 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.
    7. 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. Ilia Tarasov & Alain Haït & Alexander Lazarev & Olga Battaïa, 2024. "Metric estimation approach for managing uncertainty in resource leveling problem," Annals of Operations Research, Springer, vol. 338(1), pages 645-673, July.
    2. Chunlai Yu & Xiaoming Wang & Qingxin Chen, 2025. "Efficient Rollout Algorithms for Resource-Constrained Project Scheduling with a Flexible Project Structure and Uncertain Activity Durations," Mathematics, MDPI, vol. 13(9), pages 1-25, April.
    3. 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.
    4. Orlando Durán & Paulo Afonso & Víctor Jiménez & Katty Carvajal, 2023. "Cost of Ownership of Spare Parts under Uncertainty: Integrating Reliability and Costs," Mathematics, MDPI, vol. 11(15), pages 1-23, July.
    5. Tritschler, Martin & Naber, Anulark & Kolisch, Rainer, 2017. "A hybrid metaheuristic for resource-constrained project scheduling with flexible resource profiles," European Journal of Operational Research, Elsevier, vol. 262(1), pages 262-273.
    6. 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.
    7. Krüger, Doreen & Scholl, Armin, 2009. "A heuristic solution framework for the resource constrained (multi-)project scheduling problem with sequence-dependent transfer times," European Journal of Operational Research, Elsevier, vol. 197(2), pages 492-508, September.
    8. Alya J. Abuseem & Udechukwu Ojiako & Fikri T. Dweiri, 2024. "Overcoming ignorance and the unknown in UAE projects: the role of improvisation," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 15(3), pages 871-897, March.
    9. Mohammed M. Alhaider & Ziad M. Ali & Mostafa H. Mostafa & Shady H. E. Abdel Aleem, 2023. "Economic Viability of NaS Batteries for Optimal Microgrid Operation and Hosting Capacity Enhancement under Uncertain Conditions," Sustainability, MDPI, vol. 15(20), pages 1-24, October.
    10. Kolisch, Rainer & Hartmann, Sonke, 2006. "Experimental investigation of heuristics for resource-constrained project scheduling: An update," European Journal of Operational Research, Elsevier, vol. 174(1), pages 23-37, October.
    11. Valls, Vicente & Ballestin, Francisco & Quintanilla, Sacramento, 2008. "A hybrid genetic algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 185(2), pages 495-508, March.
    12. Ö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.
    13. 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.
    14. Bruni, Maria Elena & Hazır, Öncü, 2024. "A risk-averse distributionally robust project scheduling model to address payment delays," European Journal of Operational Research, Elsevier, vol. 318(2), pages 398-407.
    15. Liu, Zhixue & Ding, Ronggui & Wang, Lei & Song, Rui & Song, Xinyi, 2023. "Cooperation in an uncertain environment: The impact of stakeholders' concerted action on collaborative innovation projects risk management," Technological Forecasting and Social Change, Elsevier, vol. 196(C).
    16. Ang Yang & Ang Li & Zongxing Li & Yuhui Sun & Jing Gao, 2025. "Investment Analysis of Low-Carbon Yard Cranes: Integrating Monte Carlo Simulation and Jump Diffusion Processes with a Hybrid American–European Real Options Approach," Energies, MDPI, vol. 18(8), pages 1-30, April.
    17. Jürgen Kuster & Dietmar Jannach & Gerhard Friedrich, 2010. "Applying Local Rescheduling in response to schedule disruptions," Annals of Operations Research, Springer, vol. 180(1), pages 265-282, November.
    18. Shahsavar, Aria & Sadeghi, J. Kiarash & Shockley, Jeff & Ojha, Divesh, 2021. "On the relationship between lean scheduling and economic performance in shipbuilding: A proposed model and comparative evaluation," International Journal of Production Economics, Elsevier, vol. 239(C).
    19. 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).
    20. 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.

    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:annopr:v:337:y:2024:i:2:d:10.1007_s10479-023-05537-6. 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.