Abstract
We study the problem of levelling resources in a project with generalized precedence relationships, given a deadline for the completion of all the activities and variable execution intensities and flexible durations of the activities. Variable execution intensities have been taken into account firstly by Kis (Math Program 103(3):515–539, 2005) applied to a real world scenario in which, due to the physical characteristics of some manufacturing processes, the effort associated with a certain activity for its execution may vary over time. Generalized precedence relationships and variable intensity execution and duration have not been dealt with together to the best of our knowledge. For this novel problem we propose a mixed-integer linear programming formulation, a lower bound based on Lagrangian relaxation, and a branch and bound algorithm. Computational results on known benchmarks are provided.
Similar content being viewed by others
References
Ahuja HN (1976) Construction performance control by networks. Wiley, New York
Bartusch M, Möhring RH, Radermacher FJ (1988) Scheduling project networks with resource constraints and time windows. Ann Oper Res 16(1–4):201–240
Bianco L, Caramia M (2011) Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound. 4OR 9:371–389
Bianco L, Caramia M (2012) An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations. Eur J Oper Res 219(1):73–85
Burgess AR, Killebrew JB (1962) Variation in activity level on a cyclical arrow diagram. Int J Ind Eng 2:76–83
Easa SM (1989) Resource levelling in construction by optimization. J Constr Eng Manag 115:302–316
Engelhardt H, Zimmermann J (1998) Lower Bounds and exact methods for resource levelling problems. Technical Report WIOR (Universität Karlsruhe), vol 517
Fündeling C, Trautmann N (2010) A priority-rule method for project scheduling with work-content constraints. Eur J Oper Res 203:568–574
Gabow HN, Myers EW (1978) Finding all spanning trees of directed and undirected graphs. SIAM J Comput 7:280–287
Gather T, Zimmermann J (2009) Exact methods for the resource levelling problem. Proc MISTA Conf 2009:811–820
Gather T, Zimmermann J, Bartels J-H (2011) Exact methods for the resource levelling problem. J Sched 14(6):557–569
Kis T (2005) A branch-and-cut algorithm for scheduling of projects with variable-intensity activities. Math Program 103(3):515–539
Kolisch R, Schwindt C, Sprecher A (1999) Benchmark instances for project scheduling problems. In: Weglarz J (ed) Project scheduling: recent models, algorithms, and applications, vol 9. Kluwer, Boston, pp 197–212
Kreter S, Rieck J, Zimmermann J (2014) The total adjustment cost problem: applications, models, and solution algorithms. J Sched 17:145–160
Neumann K, Schwindt C, Zimmerman J (2003) Project scheduling with time windows and scarce resources. In: Lecture notes in economics and mathematical systems, vol 508, 2nd edn. Springer, Berlin
Nübel H (2001) The resource renting problem subject to temporal constraints. OR Spektrum 23:359–381
Petrovic R (1969) On optimization of resource leveling in project plans. In: Lombaers HJ (ed) Project planning by network analysis. North-Holland, Amsterdam, pp 268–273
Rieck J, Zimmerman J (2015) Exact methods for resource leveling problems. In: Schwindt C, Zimmerman J (eds) Handbook on project management and scheduling, vol 1. Springer, Berlin, pp 361–387
Rieck J, Zimmerman J, Gather T (2012) Mixed-integer linear programming for resource levelling problems. Eur J Oper Res 221:27–37
Schwindt C (1998) Verfahren zur Lösung des ressourcenbeschränkten Projektdauerminimierungsproblems mit planungsabhängigen Zeitfenstern. Shaker, Aachen
Schwindt C, Zimmerman J (2015) Handbook on project management and scheduling, vol 1. Springer, Berlin
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bianco, L., Caramia, M. & Giordani, S. Resource levelling in project scheduling with generalized precedence relationships and variable execution intensities. OR Spectrum 38, 405–425 (2016). https://doi.org/10.1007/s00291-016-0435-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-016-0435-1