IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v26y2023i1d10.1007_s10951-022-00735-9.html
   My bibliography  Save this article

A constructive branch-and-bound algorithm for the project duration problem with partially renewable resources and general temporal constraints

Author

Listed:
  • Kai Watermeyer

    (Clausthal University of Technology)

  • Jürgen Zimmermann

    (Clausthal University of Technology)

Abstract

This paper deals with the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints with the objective to minimize the project duration. The consideration of partially renewable resources allows to integrate the decision about the availability of a resource for a specific time period into the scheduling process. Together with general temporal constraints, which permit to establish minimum and maximum time lags between activities, even more aspects of real-life projects can be taken into account. We present a branch-and-bound algorithm for the stated problem that is based on a serial schedule-generation scheme. For the first time it is shown how a dominance criterion can be applied on the associated generation scheme to reduce the start times in each scheduling step. To improve the performance of the solution procedure, we integrate consistency tests and lower bounds from the literature and devise new pruning techniques. In a comprehensive experimental performance analysis we compare our exact solution procedure with all available branch-and-bound algorithms for partially renewable resources. Additionally, we investigate a directly derived priority rule-based approximation method from our new enumeration scheme. The results of the computational study demonstrate the efficiency of our branch-and-bound algorithm and reveal that the derived approximation method is only suited to solve small- and medium-sized instances.

Suggested Citation

  • Kai Watermeyer & Jürgen Zimmermann, 2023. "A constructive branch-and-bound algorithm for the project duration problem with partially renewable resources and general temporal constraints," Journal of Scheduling, Springer, vol. 26(1), pages 95-111, February.
    • Handle: RePEc:spr:jsched:v:26:y:2023:i:1:d:10.1007_s10951-022-00735-9
    DOI: 10.1007/s10951-022-00735-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-022-00735-9
    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-022-00735-9?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. Ramon Alvarez-Valdes & Jose Manuel Tamarit & Fulgencia Villa, 2015. "Partially Renewable Resources," 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 203-227, Springer.
    2. Brucker, Peter & Knust, Sigrid, 2003. "Lower bounds for resource-constrained project scheduling problems," European Journal of Operational Research, Elsevier, vol. 149(2), pages 302-313, September.
    3. Ulrich Dorndorf & Erwin Pesch & Toàn Phan-Huy, 2000. "A Time-Oriented Branch-and-Bound Algorithm for Resource-Constrained Project Scheduling with Generalised Precedence Constraints," Management Science, INFORMS, vol. 46(10), pages 1365-1384, October.
    4. 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.
    5. Böttcher, Jan & Drexl, A. & Kolisch, R. & Salewski, F., 1999. "Project scheduling under partially renewable resource constraints," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 345, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    6. Kolisch, Rainer, 1996. "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation," European Journal of Operational Research, Elsevier, vol. 90(2), pages 320-333, April.
    7. K. Neumann & H. Nübel & C. Schwindt, 2000. "Active and stable project scheduling," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 52(3), pages 441-465, December.
    8. Jan Böttcher & Andreas Drexl & Rainer Kolisch & Frank Salewski, 1999. "Project Scheduling Under Partially Renewable Resource Constraints," Management Science, INFORMS, vol. 45(4), pages 543-559, April.
    9. Erik Demeulemeester & Willy Herroelen, 1992. "A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 38(12), pages 1803-1818, December.
    10. Alvarez-Valdes, R. & Crespo, E. & Tamarit, J.M. & Villa, F., 2008. "GRASP and path relinking for project scheduling under partially renewable resources," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1153-1170, September.
    11. 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.
    12. Andreas Drexl, 1991. "Scheduling of Project Networks by Job Assignment," Management Science, INFORMS, vol. 37(12), pages 1590-1602, December.
    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. Abdollah Arasteh, 2020. "Considering Project Management Activities for Engineering Design Groups," SN Operations Research Forum, Springer, vol. 1(4), pages 1-29, December.
    2. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    3. Chen, Jiaqiong & Askin, Ronald G., 2009. "Project selection, scheduling and resource allocation with time dependent returns," European Journal of Operational Research, Elsevier, vol. 193(1), pages 23-34, February.
    4. 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.
    5. Kai Watermeyer & Jürgen Zimmermann, 2022. "A partition-based branch-and-bound algorithm for the project duration problem with partially renewable resources and general temporal constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 575-602, June.
    6. 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.
    7. Schirmer, Andreas, 1999. "Adaptive control schemes applied to project scheduling with partially renewable resources," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 520, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    8. Böttcher, Jan & Drexl, Andreas & Kolisch, Rainer & Salewski, Frank, 1996. "Project scheduling under partially renewable resource constraints," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 398, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    9. 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.
    10. Ramírez Palencia, Alberto E. & Mejía Delgadillo, Gonzalo E., 2012. "A computer application for a bus body assembly line using Genetic Algorithms," International Journal of Production Economics, Elsevier, vol. 140(1), pages 431-438.
    11. Schirmer, Andreas & Riesenberg, Sven, 1997. "Parameterized heuristics for project scheduling: Biased random sampling methods," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 456, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    12. 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.
    13. Sprecher, Arno, 1996. "Solving the RCPSP efficiently at modest memory requirements," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 425, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    14. Andreas Schirmer, 2000. "Case‐based reasoning and improved adaptive search for project scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(3), pages 201-222, April.
    15. Jan Böttcher & Andreas Drexl & Rainer Kolisch & Frank Salewski, 1999. "Project Scheduling Under Partially Renewable Resource Constraints," Management Science, INFORMS, vol. 45(4), pages 543-559, April.
    16. Kolisch, Rainer, 1994. "Serial and parallel resource-constrained projekt scheduling methodes revisited: Theory and computation," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 344, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    17. Berghman, Lotte & Leus, Roel, 2015. "Practical solutions for a dock assignment problem with trailer transportation," European Journal of Operational Research, Elsevier, vol. 246(3), pages 787-799.
    18. Klein, Robert & Scholl, Armin, 1999. "Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 112(2), pages 322-346, January.
    19. Sprecher, Arno & Drexl, Andreas, 1998. "Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm," European Journal of Operational Research, Elsevier, vol. 107(2), pages 431-450, June.
    20. Guidong Zhu & Jonathan F. Bard & Gang Yu, 2006. "A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 377-390, August.

    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:26:y:2023:i:1:d:10.1007_s10951-022-00735-9. 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.