IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v45y1999i4p543-559.html
   My bibliography  Save this article

Project Scheduling Under Partially Renewable Resource Constraints

Author

Listed:
  • Jan Böttcher

    (Institut für Betriebswirtschaftslehre, Christian-Albrechts-Universität zu Kiel, Olshausenstr, 40, 24118 Kiel, Germany)

  • Andreas Drexl

    (Institut für Betriebswirtschaftslehre, Christian-Albrechts-Universität zu Kiel, Olshausenstr, 40, 24118 Kiel, Germany)

  • Rainer Kolisch

    (Institut für Betriebswirtschaftlehre, Technische Universität Darmstadt, Hochschulstr, 1, 64289 Darmstadt, Germany)

  • Frank Salewski

    (Institut für Betriebswirtschaftslehre, Christian-Albrechts-Universität zu Kiel, Olshausenstr, 40, 24118 Kiel, Germany)

Abstract

We consider a generalization of the classical resource constrained project scheduling problem. We introduce so-called partially renewable resources by assuming for each resource a capacity on subsets of periods. The concept of partially renewable resources is a fundamental tool in order to make, e.g., timetabling and shift scheduling aspects, amenable to project scheduling. In addition, partially renewable resources serve to model complicated labor regulations. Furthermore, they cover traditional renewable and nonrenewable resource constraints as special cases. We consider makespan minimization as objective. For the exact solution of the problem we employ a basic enumeration scheme. In order to speed up convergence, we formulate bounds which take into account future resource consumption of partially renewable resources. Moreover, we generalize the serial scheduling scheme in order to get fast approximation methods. A rigorous assessment of the procedures is provided by solving ProGen instances generated under a full factorial test design. Besides the well-known problem parameters we employ additionally three parameters which control the generation of partially renewable resources.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:ormnsc:v:45:y:1999:i:4:p:543-559
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.45.4.543
    Download Restriction: no

    References listed on IDEAS

    as
    1. Oguz, Osman & Bala, Hasan, 1994. "A comparative study of computational procedures for the resource constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 72(2), pages 406-416, January.
    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. 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.
    4. 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.
    5. Brucker, Peter & Knust, Sigrid & Schoo, Arno & Thiele, Olaf, 1998. "A branch and bound algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 107(2), pages 272-288, June.
    6. Dale F. Cooper, 1976. "Heuristics for Scheduling Resource-Constrained Projects: An Experimental Investigation," Management Science, INFORMS, vol. 22(11), pages 1186-1194, July.
    7. Erik L. Demeulemeester & Willy S. Herroelen, 1997. "New Benchmark Results for the Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 43(11), pages 1485-1492, November.
    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. Li, K. Y. & Willis, R. J., 1992. "An iterative scheduling technique for resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 56(3), pages 370-379, February.
    10. Boctor, Fayer F., 1990. "Some efficient multi-heuristic procedures for resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 49(1), pages 3-13, November.
    11. Edward W. Davis & George E. Heidorn, 1971. "An Algorithm for Optimal Project Scheduling under Multiple Resource Constraints," Management Science, INFORMS, vol. 17(12), pages 803-816, August.
    12. 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.
    13. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.
    2. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    3. 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.
    4. 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.
    5. Schirmer, Andreas & Potzahr, Kathrin, 2001. "Lehrgangsplanung für die Ausbildung von Verkehrsflugzeugführern: Ergebnisse einer Studie bei Lufthansa Flight Training," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 538, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    6. Karen Puttkammer & Rainer Kleber & Tobias Schulz & Karl Inderfurth, 2011. "Simultane Maschinenbelegungs- und Personaleinsatzplanung in KMUs anhand eines Fallbeispiels aus der Druckereibranche," FEMM Working Papers 110010, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    7. repec:spr:compst:v:75:y:2012:i:3:p:305-326 is not listed on IDEAS
    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. Nissen, Rüdiger & Haase, Knut, 2004. "Duty-period-based network model for airline crew rescheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 581, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    10. Bartsch, Thomas & Drexl, Andreas & Kröger, Stefan, 2002. "Schedulung European soccer leagues: Models, methods, and applications," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 557, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    11. Bodenstein, Christian & Schryen, Guido & Neumann, Dirk, 2012. "Energy-aware workload management models for operation cost reduction in data centers," European Journal of Operational Research, Elsevier, vol. 222(1), pages 157-167.
    12. repec:pal:jorsoc:v:56:y:2005:i:4:d:10.1057_palgrave.jors.2601860 is not listed on IDEAS
    13. 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.
    14. Knust, Sigrid, 2010. "Scheduling non-professional table-tennis leagues," European Journal of Operational Research, Elsevier, vol. 200(2), pages 358-367, January.
    15. 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.
    16. Chatterjee A K & Mukherjee, Saral, 2006. "Unified Concept of Bottleneck," IIMA Working Papers WP2006-05-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    17. 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.
    18. 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.
    19. Colvin, Matthew & Maravelias, Christos T., 2011. "R&D pipeline management: Task interdependencies and risk management," European Journal of Operational Research, Elsevier, vol. 215(3), pages 616-628, December.
    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:inm:ormnsc:v:45:y:1999:i:4:p:543-559. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc). General contact details of provider: http://edirc.repec.org/data/inforea.html .

    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 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.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.