IDEAS home Printed from https://ideas.repec.org/a/spr/orspec/v42y2020i2d10.1007_s00291-020-00583-z.html
   My bibliography  Save this article

A branch-and-bound procedure for the resource-constrained project scheduling 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

In this paper, we consider the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints. For the first time, the concept of partially renewable resources is embedded in the context of projects with general temporal constraints. While partially renewable resources have already broadened the area of applications for project scheduling, the extension by general temporal constraints allows to consider even more relevant aspects of real projects. We present a branch-and-bound procedure for the problem with the objective to minimize the project duration. To improve the performance of the solution procedure, new consistency tests, lower bounds, and dominance rules are developed. Furthermore, new temporal planning procedures, based on forbidden start times of activities, are presented which can be used for any project scheduling problem with general temporal constraints independent on the considered resource type. In a performance analysis, we compare our branch-and-bound procedure with the mixed-integer linear programming solver IBM CPLEX 12.8.0 on adaptations of benchmark instances from the literature. In addition, we compare our solution procedure with the only available branch-and-bound procedure for partially renewable resources. The results of the computational experiments prove the efficiency of our branch-and-bound procedure.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:orspec:v:42:y:2020:i:2:d:10.1007_s00291-020-00583-z
    DOI: 10.1007/s00291-020-00583-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00291-020-00583-z
    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/s00291-020-00583-z?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. Klein, Robert, 1999. "Computing lower bounds by destructive improvement - an application to resource-constrained project scheduling," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 10913, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    2. Bianco, Lucio & Caramia, Massimiliano, 2012. "An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations," European Journal of Operational Research, Elsevier, vol. 219(1), pages 73-85.
    3. 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.
    4. 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.
    5. Katta G. Murty, 1968. "Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost," Operations Research, INFORMS, vol. 16(3), pages 682-687, June.
    6. Dirk Briskorn & Malte Fliedner, 2012. "Packing chained items in aligned bins with applications to container transshipment and project scheduling," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 75(3), pages 305-326, June.
    7. Drexl, Andreas & Juretzka, Jan & Salewski, Frank, 1993. "Academic course scheduling under workload and changeover constraints," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 337, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    8. 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.
    9. 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).
    10. Drexl, Andreas & Salewski, Frank, 1997. "Distribution requirements and compactness constraints in school timetabling," European Journal of Operational Research, Elsevier, vol. 102(1), pages 193-214, October.
    11. Knust, Sigrid, 2010. "Scheduling non-professional table-tennis leagues," European Journal of Operational Research, Elsevier, vol. 200(2), pages 358-367, January.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. De Reyck, Bert & Herroelen, willy, 1998. "A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations," European Journal of Operational Research, Elsevier, vol. 111(1), pages 152-174, November.
    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. 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.
    2. Andrey I. Kibzun & Varvara A. Rasskazova, 2023. "On Propeties of the LIP Model in the Class of RCPSPs," Mathematics, MDPI, vol. 11(9), pages 1-10, April.
    3. Patoghi, Amirhosein & Mousavi, Seyed Meysam, 2021. "A new approach for material ordering and multi-mode resource constraint project scheduling problem in a multi-site context under interval-valued fuzzy uncertainty," Technological Forecasting and Social Change, Elsevier, vol. 173(C).
    4. Hua Wang & Jon Dieringer & Steve Guntz & Shankarraman Vaidyaraman & Shekhar Viswanath & Nikolaos H. Lappas & Sal Garcia-Munoz & Chrysanthos E. Gounaris, 2021. "Portfolio-Wide Optimization of Pharmaceutical R&D Activities Using Mathematical Programming," Interfaces, INFORMS, vol. 51(4), pages 262-279, July.
    5. 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.
    6. Mareike Karnebogen & Jürgen Zimmermann, 2024. "Generation schemes for the resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints," Annals of Operations Research, Springer, vol. 338(1), pages 173-192, July.

    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. 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.
    2. Drexl, Andreas & Nissen, Rudiger & Patterson, James H. & Salewski, Frank, 2000. "ProGen/[pi]x - An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions," European Journal of Operational Research, Elsevier, vol. 125(1), pages 59-72, August.
    3. 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.
    4. Hartmann, Sönke & Briskorn, Dirk, 2008. "A survey of variants and extensions of the resource-constrained project scheduling problem," Working Paper Series 02/2008, Hamburg School of Business Administration (HSBA).
    5. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    6. 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.
    7. 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.
    8. 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.
    9. Mareike Karnebogen & Jürgen Zimmermann, 2024. "Generation schemes for the resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints," Annals of Operations Research, Springer, vol. 338(1), pages 173-192, July.
    10. 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.
    11. Abdollah Arasteh, 2020. "Considering Project Management Activities for Engineering Design Groups," SN Operations Research Forum, Springer, vol. 1(4), pages 1-29, December.
    12. 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.
    13. Bianco, Lucio & Caramia, Massimiliano, 2012. "An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations," European Journal of Operational Research, Elsevier, vol. 219(1), pages 73-85.
    14. 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.
    15. Andrei Horbach, 2010. "A Boolean satisfiability approach to the resource-constrained project scheduling problem," Annals of Operations Research, Springer, vol. 181(1), pages 89-107, December.
    16. Sophie Demassey & Christian Artigues & Philippe Michelon, 2005. "Constraint-Propagation-Based Cutting Planes: An Application to the Resource-Constrained Project Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 52-65, February.
    17. 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.
    18. 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.
    19. Salewski, Frank & Schirmer, Andreas & Drexl, Andreas, 1997. "Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application," European Journal of Operational Research, Elsevier, vol. 102(1), pages 88-110, October.
    20. 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.

    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:orspec:v:42:y:2020:i:2:d:10.1007_s00291-020-00583-z. 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.