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

Mixed-integer linear programming for resource leveling problems

Author

Listed:
  • Rieck, Julia
  • Zimmermann, Jürgen
  • Gather, Thorsten

Abstract

We consider project scheduling problems subject to general temporal constraints, where the utilization of a set of renewable resources has to be smoothed over a prescribed planning horizon. In particular, we consider the classical resource leveling problem, where the variation in resource utilization during project execution is to be minimized, and the so-called “overload problem”, where costs are incurred if a given resource-utilization threshold is exceeded. For both problems, we present new mixed-integer linear model formulations and domain-reducing preprocessing techniques. In order to strengthen the models, lower and upper bounds for resource requirements at particular points in time, as well as effective cutting planes, are outlined. We use CPLEX 12.1 to solve medium-scale instances, as well as instances of the well-known test set devised by Kolisch et al. (1999). Instances with up to 50 activities and tight project deadlines are solved to optimality for the first time.

Suggested Citation

  • Rieck, Julia & Zimmermann, Jürgen & Gather, Thorsten, 2012. "Mixed-integer linear programming for resource leveling problems," European Journal of Operational Research, Elsevier, vol. 221(1), pages 27-37.
    • Handle: RePEc:eee:ejores:v:221:y:2012:i:1:p:27-37
    DOI: 10.1016/j.ejor.2012.03.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712001968
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.03.003?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. 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.
    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. Bandelloni, M. & Tucci, M. & Rinaldi, R., 1994. "Optimal resource leveling using non-serial dyanamic programming," European Journal of Operational Research, Elsevier, vol. 78(2), pages 162-177, October.
    4. Neumann, K. & Zimmermann, J., 2000. "Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints," European Journal of Operational Research, Elsevier, vol. 127(2), pages 425-443, December.
    5. 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.
    6. 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.
    7. Kolisch, Rainer & Schwindt, Christoph & Sprecher, Arno, 1999. "Benchmark instances for project scheduling problems," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 9500, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    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. Freeman, Nickolas & Zhao, Ming & Melouk, Sharif, 2018. "An iterative approach for case mix planning under uncertainty," Omega, Elsevier, vol. 76(C), pages 160-173.
    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. Atan, Tankut & Eren, Elif, 2018. "Optimal project duration for resource leveling," European Journal of Operational Research, Elsevier, vol. 266(2), pages 508-520.
    4. Carvalho, Andréa Nunes & Oliveira, Fabricio & Scavarda, Luiz Felipe, 2016. "Tactical capacity planning in a real-world ETO industry case: A robust optimization approach," International Journal of Production Economics, Elsevier, vol. 180(C), pages 158-171.
    5. Hongbo Li & Linwen Zheng & Hanyu Zhu, 2023. "Resource leveling in projects with flexible structures," Annals of Operations Research, Springer, vol. 321(1), pages 311-342, February.
    6. Markus Frey & Rainer Kolisch & Christian Artigues, 2017. "Column Generation for Outbound Baggage Handling at Airports," Transportation Science, INFORMS, vol. 51(4), pages 1226-1241, November.
    7. 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.
    8. Simon Emde & Hamid Abedinnia & Anne Lange & Christoph H. Glock, 2020. "Scheduling personnel for the build-up of unit load devices at an air cargo terminal with limited space," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 397-426, June.
    9. Carvalho, Andréa Nunes & Oliveira, Fabricio & Scavarda, Luiz Felipe, 2015. "Tactical capacity planning in a real-world ETO industry case: An action research," International Journal of Production Economics, Elsevier, vol. 167(C), pages 187-203.
    10. Lena Sophie Wohlert & Jürgen Zimmermann, 2024. "Resource overload problems with tardiness penalty: structural properties and solution approaches," Annals of Operations Research, Springer, vol. 338(1), pages 151-172, July.
    11. Milička, P. & Šůcha, P. & Vanhoucke, M. & Maenhout, B., 2022. "The bilevel optimisation of a multi-agent project scheduling and staffing problem," European Journal of Operational Research, Elsevier, vol. 296(1), pages 72-86.
    12. Cédric Verbeeck & Vincent Peteghem & Mario Vanhoucke & Pieter Vansteenwegen & El-Houssaine Aghezzaf, 2017. "A metaheuristic solution approach for the time-constrained project scheduling problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(2), pages 353-371, March.
    13. Hübner, Felix & Schellenbaum, Uli & Stürck, Christian & Gerhards, Patrick & Schultmann, Frank, 2017. "Evaluation von Schedulingproblemen für die Projektplanung von Großprojekten am Beispiel des kerntechnischen Rückbaus," Working Paper Series in Production and Energy 22, Karlsruhe Institute of Technology (KIT), Institute for Industrial Production (IIP).
    14. Lucio Bianco & Massimiliano Caramia & Stefano Giordani, 2016. "Resource levelling in project scheduling with generalized precedence relationships and variable execution intensities," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(2), pages 405-425, March.
    15. Guopeng Song & Tamás Kis & Roel Leus, 2021. "Polyhedral Results and Branch-and-Cut for the Resource Loading Problem," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 105-119, January.
    16. Qingyou Yan & Qian Zhang & Xin Zou, 2016. "A Cost Optimization Model for Multiresource Leveling Problem without Project Duration Constraint," Discrete Dynamics in Nature and Society, Hindawi, vol. 2016, pages 1-8, July.
    17. Bersch, Christopher V. & Akkerman, Renzo & Kolisch, Rainer, 2021. "Strategic planning of new product introductions: Integrated planning of products and modules in the automotive industry," Omega, Elsevier, vol. 105(C).
    18. Ilia Tarasov & Alain Haït & Alexander Lazarev & Olga Battaïa, 2024. "Metric estimation approach for managing uncertainty in resource leveling problem," Annals of Operations Research, Springer, vol. 338(1), pages 645-673, July.
    19. Györgyi, Péter & Kis, Tamás, 2020. "A common approximation framework for early work, late work, and resource leveling problems," European Journal of Operational Research, Elsevier, vol. 286(1), pages 129-137.
    20. Hongbo Li & Erik Demeulemeester, 2016. "A genetic algorithm for the robust resource leveling problem," Journal of Scheduling, Springer, vol. 19(1), pages 43-60, February.
    21. Gahm, Christian & Dünnwald, Bastian & Sahamie, Ramin, 2014. "A multi-criteria master production scheduling approach for special purpose machinery," International Journal of Production Economics, Elsevier, vol. 149(C), pages 89-101.

    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. 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.
    2. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    3. 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.
    4. Thomas Selle & Jürgen Zimmermann, 2003. "A bidirectional heuristic for maximizing the net present value of large‐scale projects subject to limited resources," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(2), pages 130-148, March.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Bartels, J.-H. & Zimmermann, J., 2009. "Scheduling tests in automotive R&D projects," European Journal of Operational Research, Elsevier, vol. 193(3), pages 805-819, March.
    10. Nicole Megow & Rolf H. Möhring & Jens Schulz, 2011. "Decision Support and Optimization in Shutdown and Turnaround Scheduling," INFORMS Journal on Computing, INFORMS, vol. 23(2), pages 189-204, May.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. Sciau, Jean-Baptiste & Goyon, Agathe & Sarazin, Alexandre & Bascans, Jérémy & Prud’homme, Charles & Lorca, Xavier, 2024. "Using constraint programming to address the operational aircraft line maintenance scheduling problem," Journal of Air Transport Management, Elsevier, vol. 115(C).
    17. 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.
    18. Hongbo Li & Linwen Zheng & Hanyu Zhu, 2023. "Resource leveling in projects with flexible structures," Annals of Operations Research, Springer, vol. 321(1), pages 311-342, February.
    19. Gonzalo Muñoz & Daniel Espinoza & Marcos Goycoolea & Eduardo Moreno & Maurice Queyranne & Orlando Rivera Letelier, 2018. "A study of the Bienstock–Zuckerberg algorithm: applications in mining and resource constrained project scheduling," Computational Optimization and Applications, Springer, vol. 69(2), pages 501-534, March.
    20. 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.

    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:221:y:2012:i:1:p:27-37. 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.