IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v251y2016i2p387-403.html
   My bibliography  Save this article

Models and solution procedures for the resource-constrained project scheduling problem with general temporal constraints and calendars

Author

Listed:
  • Kreter, Stefan
  • Rieck, Julia
  • Zimmermann, Jürgen

Abstract

In this paper, the resource-constrained project scheduling problem with general temporal constraints is extended by the concept of break-calendars in order to incorporate the possible absence of renewable resources. Three binary linear model formulations are presented that use either start-based or changeover-based or execution-based binary decision variables. In addition, a priority-rule method as well as three different versions of a scatter search procedure are proposed in order to solve the problem heuristically. All exact and heuristic solution procedures use a new and powerful time planning method, which identifies all time- and calendar-feasible start times for activities as well as all corresponding absolute time lags between activities. In a comprehensive performance analysis, small- and medium-scale instances are solved with CPLEX 12.6. Furthermore, large-scale instances of the problem are tackled with scatter search, where the results of the three versions are compared to each other and to the priority-rule method.

Suggested Citation

  • Kreter, Stefan & Rieck, Julia & Zimmermann, Jürgen, 2016. "Models and solution procedures for the resource-constrained project scheduling problem with general temporal constraints and calendars," European Journal of Operational Research, Elsevier, vol. 251(2), pages 387-403.
    • Handle: RePEc:eee:ejores:v:251:y:2016:i:2:p:387-403
    DOI: 10.1016/j.ejor.2015.11.021
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171501070X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.11.021?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. Buddhakulsomsiri, Jirachai & Kim, David S., 2006. "Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting," European Journal of Operational Research, Elsevier, vol. 175(1), pages 279-295, November.
    2. A. Alan B. Pritsker & Lawrence J. Waiters & Philip M. Wolfe, 1969. "Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach," Management Science, INFORMS, vol. 16(1), pages 93-108, September.
    3. Buddhakulsomsiri, Jirachai & Kim, David S., 2007. "Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting," European Journal of Operational Research, Elsevier, vol. 178(2), pages 374-390, April.
    4. Christofides, Nicos & Alvarez-Valdes, R. & Tamarit, J. M., 1987. "Project scheduling with resource constraints: A branch and bound approach," European Journal of Operational Research, Elsevier, vol. 29(3), pages 262-273, June.
    5. Valls, Vicente & Ballestin, Francisco & Quintanilla, Sacramento, 2005. "Justification and RCPSP: A technique that pays," European Journal of Operational Research, Elsevier, vol. 165(2), pages 375-386, September.
    6. Christian Artigues & Oumar Koné & Pierre Lopez & Marcel Mongeau, 2015. "Mixed-Integer Linear Programming Formulations," International Handbooks on Information Systems, in: Christoph Schwindt & Jürgen Zimmermann (ed.), Handbook on Project Management and Scheduling Vol.1, edition 127, chapter 0, pages 17-41, Springer.
    7. Coviello, Decio & Ichino, Andrea & Persico, Nicola, 2010. "Don't Spread Yourself Too Thin: The Impact of Task Juggling on Workers' Speed of Job Completion," IZA Discussion Papers 5280, Institute of Labor Economics (IZA).
    8. Neumann, K. & Schwindt, C. & Zimmermann, J., 2003. "Order-based neighborhoods for project scheduling with nonregular objective functions," European Journal of Operational Research, Elsevier, vol. 149(2), pages 325-343, September.
    9. Debels, Dieter & De Reyck, Bert & Leus, Roel & Vanhoucke, Mario, 2006. "A hybrid scatter search/electromagnetism meta-heuristic for project scheduling," European Journal of Operational Research, Elsevier, vol. 169(2), pages 638-653, March.
    10. Sönke Hartmann, 2015. "Time-Varying Resource Requirements and Capacities," International Handbooks on Information Systems, in: Christoph Schwindt & Jürgen Zimmermann (ed.), Handbook on Project Management and Scheduling Vol.1, edition 127, chapter 0, pages 163-176, Springer.
    11. Gabriella Budai & Rommert Dekker & Robin P. Nicolai, 2008. "Maintenance and Production: A Review of Planning Models," Springer Series in Reliability Engineering, in: Complex System Maintenance Handbook, chapter 13, pages 321-344, Springer.
    12. Aristide Mingozzi & Vittorio Maniezzo & Salvatore Ricciardelli & Lucio Bianco, 1998. "An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation," Management Science, INFORMS, vol. 44(5), pages 714-729, May.
    13. Ranjbar, Mohammad & De Reyck, Bert & Kianfar, Fereydoon, 2009. "A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling," European Journal of Operational Research, Elsevier, vol. 193(1), pages 35-48, February.
    14. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    15. 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.
    16. Andreas Schutt & Thibaut Feydy & Peter J. Stuckey & Mark G. Wallace, 2015. "A Satisfiability Solving Approach," International Handbooks on Information Systems, in: Christoph Schwindt & Jürgen Zimmermann (ed.), Handbook on Project Management and Scheduling Vol.1, edition 127, chapter 0, pages 135-160, Springer.
    17. Kolisch, Rainer & Sprecher, Arno, 1996. "PSPLIB - a project scheduling problem library," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 396, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    18. F. Brian Talbot & James H. Patterson, 1978. "An Efficient Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling Problems," Management Science, INFORMS, vol. 24(11), pages 1163-1174, July.
    19. Valls, Vicente & Pérez, Ángeles & Quintanilla, Sacramento, 2009. "Skilled workforce scheduling in Service Centres," European Journal of Operational Research, Elsevier, vol. 193(3), pages 791-804, March.
    20. Pilar Tormos & Antonio Lova, 2001. "A Competitive Heuristic Solution Technique for Resource-Constrained Project Scheduling," Annals of Operations Research, Springer, vol. 102(1), pages 65-81, February.
    21. 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.
    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. Kai Watermeyer & Jürgen Zimmermann, 2020. "A branch-and-bound procedure for the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 427-460, June.
    2. Hartmann, Sönke & Briskorn, Dirk, 2022. "An updated survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 1-14.
    3. Hongbo Li & Hanyu Zhu & Linwen Zheng & Fang Xie, 2024. "Software project scheduling under activity duration uncertainty," Annals of Operations Research, Springer, vol. 338(1), pages 477-512, July.
    4. Nataliia Dotsenko & Dmytro Chumachenko & Yuliia Husieva & Nataliia Kosenko & Igor Chumachenko, 2022. "Sustainable Management of Healthcare Settings’ Personnel Based on Intelligent Project-Oriented Approach for Post-War Development," Energies, MDPI, vol. 15(22), pages 1-18, November.
    5. Kreter, Stefan & Schutt, Andreas & Stuckey, Peter J. & Zimmermann, Jürgen, 2018. "Mixed-integer linear programming and constraint programming formulations for solving resource availability cost problems," European Journal of Operational Research, Elsevier, vol. 266(2), pages 472-486.
    6. Philippe Lacomme & Aziz Moukrim & Alain Quilliot & Marina Vinot, 2019. "Integration of routing into a resource-constrained project scheduling problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(4), pages 421-464, December.
    7. Nataliia Dotsenko & Dmytro Chumachenko & Igor Chumachenko & Andrii Galkin & Tomasz Lis & Marek Lis, 2021. "Conceptual Framework of Sustainable Management of the Process of Forming a Project Team with Functional Redundancy," Energies, MDPI, vol. 14(24), pages 1-22, December.

    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. André Schnabel & Carolin Kellenbrink & Stefan Helber, 2018. "Profit-oriented scheduling of resource-constrained projects with flexible capacity constraints," Business Research, Springer;German Academic Association for Business Research, vol. 11(2), pages 329-356, September.
    2. 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.
    3. Luis F. Machado-Domínguez & Carlos D. Paternina-Arboleda & Jorge I. Vélez & Agustin Barrios-Sarmiento, 2021. "A memetic algorithm to address the multi-node resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 24(4), pages 413-429, August.
    4. Xabier A. Martin & Rosa Herrero & Angel A. Juan & Javier Panadero, 2024. "An Agile Adaptive Biased-Randomized Discrete-Event Heuristic for the Resource-Constrained Project Scheduling Problem," Mathematics, MDPI, vol. 12(12), pages 1-21, June.
    5. Peteghem, Vincent Van & Vanhoucke, Mario, 2010. "A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 201(2), pages 409-418, March.
    6. Alexander Tesch, 2020. "A polyhedral study of event-based models for the resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 23(2), pages 233-251, April.
    7. Alireza Etminaniesfahani & Hanyu Gu & Leila Moslemi Naeni & Amir Salehipour, 2024. "An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem," Annals of Operations Research, Springer, vol. 338(1), pages 41-68, July.
    8. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    9. Guo, Weikang & Vanhoucke, Mario & Coelho, José, 2023. "A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 579-595.
    10. 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.
    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. R. Christopher L. Riley & Cesar Rego, 2019. "Intensification, diversification, and learning via relaxation adaptive memory programming: a case study on resource constrained project scheduling," Journal of Heuristics, Springer, vol. 25(4), pages 793-807, October.
    13. Coelho, José & Vanhoucke, Mario, 2011. "Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers," European Journal of Operational Research, Elsevier, vol. 213(1), pages 73-82, August.
    14. Tom Rihm & Norbert Trautmann & Adrian Zimmermann, 2018. "MIP formulations for an application of project scheduling in human resource management," Flexible Services and Manufacturing Journal, Springer, vol. 30(4), pages 609-639, December.
    15. Hartmann, Sönke & Briskorn, Dirk, 2022. "An updated survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 1-14.
    16. Amadeu A. Coco & Christophe Duhamel & Andréa Cynthia Santos, 2020. "Modeling and solving the multi-period disruptions scheduling problem on urban networks," Annals of Operations Research, Springer, vol. 285(1), pages 427-443, February.
    17. Ranjbar, Mohammad & De Reyck, Bert & Kianfar, Fereydoon, 2009. "A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling," European Journal of Operational Research, Elsevier, vol. 193(1), pages 35-48, February.
    18. 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.
    19. Sepehr Proon & Mingzhou Jin, 2011. "A genetic algorithm with neighborhood search for the resource‐constrained project scheduling problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(2), pages 73-82, March.
    20. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.

    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:eee:ejores:v:251:y:2016:i:2:p:387-403. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.