×

Mixed-integer linear programming for resource leveling problems. (English) Zbl 1253.90116

Summary: 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 R. Kolisch et al. [“Benchmark instances for project scheduling problems. in: Project scheduling: recent models, algorithms, and applications. (Kluwer, Boston) (1999)]. Instances with up to 50 activities and tight project deadlines are solved to optimality for the first time.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
90C35 Programming involving graphs or networks

Software:

CPLEX; PSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, H. N., Construction Performance Control by Networks (1976), Wiley: Wiley New York
[2] Ahuja, R.; Magnanti, T.; Orlin, J., Network Flows (1993), Prentice Hall: Prentice Hall Englewood Cliffs · Zbl 1201.90001
[3] Artigues, C.; Michelon, P.; Reusser, S., Insertion techniques for static and dynamic resource-constraint project scheduling, European Journal of Operational Research, 149, 2, 249-267 (2003) · Zbl 1040.90013
[4] Ballestin, F.; Schwindt, C.; Zimmermann, J., Resource leveling in make-to-order production: modeling and heuristic solution method, International Journal of Operations Research, 13, 2, 76-83 (2007)
[5] Bandelloni, M.; Tucci, M.; Rinaldi, R., Optimal resource leveling using non-serial dynamic programming, European Journal of Operational Research, 78, 162-177 (1994) · Zbl 0812.90062
[6] Bartusch, M.; Möhring, R.; Radermacher, F., Scheduling project networks with resource constraints and time windows, Annals of Operations Research, 16, 201-240 (1988) · Zbl 0693.90047
[7] Burgess, A.; Killebrew, J., Variation in activity level on a cyclical arrow diagram, Journal of Industrial Engineering, 13, 76-83 (1962)
[8] Christofides, N.; Alvarez-ValdFs, R.; Tamarit, J. M., Project scheduling with resource constraints: a branch and bound approach, European Journal of Operations Research, 29, 3, 262-273 (1987) · Zbl 0614.90056
[9] Das Gupta, O., 2009. Alte Atomkraftwerke - Die Gelddruckmaschinen. Süddeutsche Zeitung 06.07.2009.; Das Gupta, O., 2009. Alte Atomkraftwerke - Die Gelddruckmaschinen. Süddeutsche Zeitung 06.07.2009.
[10] Demeulemeester, E.; Herroelen, W., Project Scheduling: A Research Handbook (2002), Kluwer: Kluwer Bosten · Zbl 1059.90068
[11] Easa, S. M., Resource leveling in construction by optimization, Journal of Construction Engineering and Management, 115, 302-316 (1989)
[12] Eidgenössisches Nuklearsicherheitsinspektorat, E., 2009. Revision von Kernkraftwerken. ENSI Newsletter 4 (Themenheft).; Eidgenössisches Nuklearsicherheitsinspektorat, E., 2009. Revision von Kernkraftwerken. ENSI Newsletter 4 (Themenheft).
[13] Gabow, H.; Myers, E., Finding all spanning trees of directed and undirected graphs, SIAM Journal on Computing, 7, 208-287 (1978) · Zbl 0379.68031
[14] Gather, T., Exakte Verfahren für das Ressourcennivellierungsproblem (2011), Gabler: Gabler Wiesbaden
[15] Gather, T.; Zimmermann, J.; Bartels, J.-H., Exact methods for the resource levelling problem, Journal of Scheduling, 14, 6, 557-569 (2011) · Zbl 1280.90046
[16] Habib, M.; Morvan, M.; Rampon, J. X., On the calculation of transitive reduction-closure of orders, Discrete Mathematics, 111, 289-303 (1993) · Zbl 0782.68089
[17] Hagmayer, S., Struktur von Projektplanungsproblemen aus polyedertheoretischer Sicht (2006), Shaker: Shaker Aachen
[18] Harris, R. B., Packing method for resource leveling (pack), Journal of Construction Engineering and Management, 116, 39-43 (1990)
[19] Ilg, P., 2009. Wie Atomkraftwerke in Deutschland geprüft werden. Financial Times Deutschland 20.10.2009.; Ilg, P., 2009. Wie Atomkraftwerke in Deutschland geprüft werden. Financial Times Deutschland 20.10.2009.
[20] Józefowska, J.; We¸glarz, J., Perspectives in Modern Project Scheduling (2006), Springer: Springer New York · Zbl 1094.90003
[21] Kelly, J. E., Critical-path planning and scheduling: mathematical basis, Operations Research, 9, 296-320 (1961) · Zbl 0098.12103
[22] Kolisch, R.; Schwindt, C.; Sprecher, A., Benchmark instances for project scheduling problems, (We¸glarz, J., Project Scheduling: Recent Models, Algorithms, and Applications (1999), Kluwer: Kluwer Boston), 197-212
[23] Koné, O.; Artigues, C.; Lopeza, P.; Mongeauc, M., Event-based milp models for resource-constrained project scheduling problems, Computers and Operations Research, 38, 3-13 (2011) · Zbl 1231.90202
[24] Möhring, R. H., Minimizing costs of resource requirements in project networks subject to a fixed completion time, Operations Research, 32, 89-120 (1984) · Zbl 0531.90049
[25] Neumann, K.; Zimmermann, J., Methods for resource-constrained project scheduling with regular and nonregular objective functions and schedule-dependent time windows, (We¸glarz, J., Project Scheduling: Recent Models, Algorithms, and Applications (1999), Kluwer: Kluwer Boston), 261-287
[26] Neumann, K.; Zimmermann, J., Procedures for resource levelling and net present value problems in project scheduling with general temporal and resource constraints, European Journal of Operations Research, 127, 425443 (2000) · Zbl 0990.90058
[27] Neumann, K.; Nübel, H.; Schwindt, C., Active and stable project scheduling, Mathematical Methods of Operations Research, 52, 441-465 (2000) · Zbl 1023.90029
[28] Neumann, K.; Schwindt, C.; Zimmermann, J., Project Scheduling with Time Windows and Scarce Resources (2003), Springer: Springer Berlin · Zbl 1059.90001
[29] Nübel, H., Minimierung der Ressourcenkosten für Projekte mit planungsabhängigen Zeitfenstern (1999), Gabler: Gabler Wiesbaden
[30] Pritsker, A. A.B.; Watters, L. J.; Wolfe, P. M., Multi-project scheduling with limited resources: a zero-one programming approach, Management Science, 16, 93-108 (1969)
[31] Schreiber, H., 2007. Eine Revision der Rekorde im Kernkraftwerk. Augsburger Allgemeine Zeitung 26.10.2007.; Schreiber, H., 2007. Eine Revision der Rekorde im Kernkraftwerk. Augsburger Allgemeine Zeitung 26.10.2007.
[32] Schwindt, C., 1998. Generation of resource-constrained project scheduling problems subject to temporal constraints. Technical report wior-543, Institute for Economic Theory and Operations Research, University Karlsruhe.; Schwindt, C., 1998. Generation of resource-constrained project scheduling problems subject to temporal constraints. Technical report wior-543, Institute for Economic Theory and Operations Research, University Karlsruhe.
[33] Schwindt, C., Resource Allocation in Project Management (2005), Springer: Springer Berlin
[34] Selle, T., Untere Schranken für Projektplanungsprobleme (2002), Shaker: Shaker Aachen
[35] Younis, M. A.; Saad, B., Optimal resource leveling of multi-resource projects, Computers and Industrial Engineering, 31, 1-4 (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.