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

Solving Project Scheduling Problems by Minimum Cut Computations

Author

Listed:
  • Rolf H. Möhring

    () (Fakultät II, Institut für Mathematik, Technische Universität Berlin, Sekr. MA 6-1, Stra\beta e des 17. Juni 136, D-10623 Berlin, Germany)

  • Andreas S. Schulz

    () (Sloan School of Management, E53-361, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139)

  • Frederik Stork

    () (ILOG Deutschland GmbH, Ober-Eschbacher Stra\beta e 109, D-61352 Bad Homburg, Germany)

  • Marc Uetz

    () (Faculty of Economics and Business Administration, Quantitative Economics, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands)

Abstract

In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for scarce resources. Due to its universality, the latter problem has a variety of applications in manufacturing, production planning, project management, and elsewhere. It is one of the most intractable problems in operations research, and has therefore become a popular playground for the latest optimization techniques, including virtually all local search paradigms. We show that a somewhat more classical mathematical programming approach leads to both competitive feasible solutions and strong lower bounds, within reasonable computation times. The basic ingredients of our approach are the Lagrangian relaxation of a time-indexed integer programming formulation and relaxation-based list scheduling, enriched with a useful idea from recent approximation algorithms for machine scheduling problems. The efficiency of the algorithm results from the insight that the relaxed problem can be solved by computing a minimum cut in an appropriately defined directed graph. Our computational study covers different types of resource-constrained project scheduling problems, based on several notoriously hard test sets, including practical problem instances from chemical production planning.

Suggested Citation

  • Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
  • Handle: RePEc:inm:ormnsc:v:49:y:2003:i:3:p:330-350
    as

    Download full text from publisher

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

    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. 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.
    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. Brucker, Peter & Knust, Sigrid, 2000. "A linear programming and constraint propagation-based lower bound for the RCPSP," European Journal of Operational Research, Elsevier, vol. 127(2), pages 355-362, December.
    5. A. Kimms, 2001. "Maximizing the Net Present Value of a Project Under Resource Constraints Using a Lagrangian Relaxation Based Heuristic with Tight Upper Bounds," Annals of Operations Research, Springer, vol. 102(1), pages 221-236, February.
    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. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    8. 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.
    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. Estévez-Fernández, Arantza, 2012. "A game theoretical approach to sharing penalties and rewards in projects," European Journal of Operational Research, Elsevier, vol. 216(3), pages 647-657.
    2. Kedad-Sidhoum, Safia & Solis, Yasmin Rios & Sourd, Francis, 2008. "Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1305-1316, September.
    3. Nurre, Sarah G. & Cavdaroglu, Burak & Mitchell, John E. & Sharkey, Thomas C. & Wallace, William A., 2012. "Restoring infrastructure systems: An integrated network design and scheduling (INDS) problem," European Journal of Operational Research, Elsevier, vol. 223(3), pages 794-806.
    4. 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.
    5. repec:spr:coopap:v:69:y:2018:i:2:d:10.1007_s10589-017-9946-1 is not listed on IDEAS
    6. Túlio A. M. Toffolo & Haroldo G. Santos & Marco A. M. Carvalho & Janniele A. Soares, 2016. "An integer programming approach to the multimode resource-constrained multiproject scheduling problem," Journal of Scheduling, Springer, vol. 19(3), pages 295-307, June.
    7. Damay, Jean & Quilliot, Alain & Sanlaville, Eric, 2007. "Linear programming based algorithms for preemptive and non-preemptive RCPSP," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1012-1022, November.
    8. Konstantinos G. Zografos & Michael A. Madas & Konstantinos N. Androutsopoulos, 2017. "Increasing airport capacity utilisation through optimum slot scheduling: review of current developments and identification of future needs," Journal of Scheduling, Springer, vol. 20(1), pages 3-24, February.
    9. 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.
    10. 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.
    11. Tseng, Lin-Yu & Chen, Shih-Chieh, 2006. "A hybrid metaheuristic for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 175(2), pages 707-721, December.
    12. repec:pal:jorsoc:v:56:y:2005:i:4:d:10.1057_palgrave.jors.2601860 is not listed on IDEAS
    13. 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.
    14. repec:spr:annopr:v:249:y:2017:i:1:d:10.1007_s10479-014-1776-2 is not listed on IDEAS
    15. 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.
    16. 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.
    17. Patricio Lamas & Erik Demeulemeester, 2016. "A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations," Journal of Scheduling, Springer, vol. 19(4), pages 409-428, August.
    18. Joseph G. Szmerekovsky, 2005. "The Impact of Contractor Behavior on the Client's Payment-Scheduling Problem," Management Science, INFORMS, vol. 51(4), pages 629-640, April.
    19. 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.
    20. Kerkhove, L.-P. & Vanhoucke, M., 2017. "Optimised scheduling for weather sensitive offshore construction projects," Omega, Elsevier, vol. 66(PA), pages 58-78.

    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:49:y:2003:i:3:p:330-350. 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.