Abstract
In this article, we study compact Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP). Compared to the classical time-indexed formulation, the size of compact models is strongly polynomial in the number of jobs. In addition to two compact models from the literature, we propose a new compact model. We can show that all three compact models are equivalent by successive linear transformations. For their LP-relaxations, however, we state a full inclusion hierarchy where our new model dominates the previous models in terms of polyhedral strength. Moreover, we reveal a polyhedral relationship to the common time-indexed model. Furthermore, a general class of valid cutting planes for the compact models is introduced and finally all models are evaluated by computational experiments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Artigues, C., Michelon, P., Reusser, S.: Insertion techniques for static and dynamic resource-constrained project scheduling. Eur. J. Oper. Res. 149(2), 249–267 (2003)
Brucker, P., Knust, S.: Lower bounds for resource-constrained project scheduling problems. Eur. J. Oper. Res. 149(2), 302–313 (2003)
Carlier, J., Néron, E.: On linear lower bounds for the resource constrained project scheduling problem. Eur. J. Oper. Res. 149(2), 314–324 (2003)
Cavalcante, C.C., De Souza, C.C., Savelsbergh, M.W., Wang, Y., Wolsey, L.A.: Scheduling projects with labor constraints. Discrete Appl. Math. 112(1), 27–52 (2001)
Christofides, N., Alvarez-Valdés, R., Tamarit, J.M.: Project scheduling with resource constraints: a branch and bound approach. Eur. J. Oper. Res. 29(3), 262–273 (1987)
Haouari, M., Kooli, A., Néron, E., Carlier, J.: A preemptive bound for the resource constrained project scheduling problem. J. Scheduling 17(3), 237–248 (2014)
Kolisch, R., Sprecher, A.: PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program. Eur. J. Oper. Res. 96(1), 205–216 (1997)
Koné, O., Artigues, C., Lopez, P., Mongeau, M.: Event-based MILP models for resource-constrained project scheduling problems. Comput. Oper. Res. 38(1), 3–13 (2011)
Möhring, R.H., Schulz, A.S., Stork, F., Uetz, M.: Solving project scheduling problems by minimum cut computations. Manage. Sci. 49(3), 330–350 (2003)
Pritsker, A.A.B., Waiters, L.J., Wolfe, P.M.: Multiproject scheduling with limited resources: a zero-one programming approach. Manage. Sci. 16(1), 93–108 (1969)
Schrijver, A.: Combinatorial Optimization, vol. A (2003)
Tesch, A.: Compact MIP models for the resource-constrained project scheduling problem. Master’s Thesis, TU-Berlin (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Tesch, A. (2018). Improved Compact Models for the Resource-Constrained Project Scheduling Problem. In: Fink, A., Fügenschuh, A., Geiger, M. (eds) Operations Research Proceedings 2016. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-55702-1_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-55702-1_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55701-4
Online ISBN: 978-3-319-55702-1
eBook Packages: Business and ManagementBusiness and Management (R0)