×

zbMATH — the first resource for mathematics

Strong bounds for resource constrained project scheduling: preprocessing and cutting planes. (English) Zbl 1458.90247
Summary: Resource Constrained Project Scheduling Problems (RCPSPs) without preemption are well-known \(\mathcal{NP}\)-hard combinatorial optimization problems. A feasible RCPSP solution consists of a time-ordered schedule of jobs with corresponding execution modes, respecting precedence and resources constraints. In this paper, we propose a cutting plane algorithm to separate five different cut families, as well as a new preprocessing routine to strengthen resource-related constraints. New lifted versions of the well-known precedence and cover inequalities are employed. At each iteration, a dense conflict graph is built considering feasibility and optimality conditions to separate cliques, odd-holes and strengthened Chvátal-Gomory cuts. The proposed strategies considerably improve the linear relaxation bounds, allowing a state-of-the-art mixed-integer linear programming solver to find provably optimal solutions for 754 previously open instances of different variants of the RCPSPs, which was not possible using the original linear programming formulations.

MSC:
90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
Software:
Gurobi; JOBSHOP; PSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Applegate, D.; Cook, W., A computational study of the job-shop scheduling problem, ORSA J. Comput., 3, 149-1556 (1991) · Zbl 0755.90039
[2] Artigues, C., On the strength of time-indexed formulations for the resource-constrained project scheduling problem, Oper. Res. Lett., 45, 154-159 (2017) · Zbl 1409.90085
[3] Artigues, C.; Demassey, S.; Néon, E., Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications (2008), ISTE Ltd and John Wiley & Sons, Inc
[4] Atamtürk, A.; Nemhauser, G. L.; Savelsbergh, M. W.P., Conflict graphs in solving integer programming problems, Eur. J. Oper. Res., 121, 1, 40-55 (2000) · Zbl 0959.90034
[5] Balas, E., Facets of the knapsack polytope, Math. Program., 8, 1, 146-164 (1975) · Zbl 0316.90046
[6] Balas, E.; Zemel, E., Facets of the knapsack polytope from minimal covers, SIAM J. Appl. Math., 34, 1, 119-148 (1978) · Zbl 0385.90083
[7] Baptiste, P.; Demassey, S., Tight lp bounds for resource constrained project scheduling, OR Spectr., 26, 2, 251-262 (2004) · Zbl 1072.90012
[8] Blazewicz, J.; Lenstra, J.; Rinnooy Kan, A., Scheduling subject to resource constraints: classification and complexity, Discrete Appl. Math, 5, 11-24 (1983) · Zbl 0516.68037
[9] Boyd, E., Fenchel cutting planes for integer programming, Oper. Res., 42, 53-64 (1992) · Zbl 0809.90104
[10] Boyd, E., Solving 0/1 integer programs with enumeration cutting planes, Ann. Oper. Res., 50, 61-72 (1994) · Zbl 0815.90115
[11] Brito, S. S.; Santos, H. G.; Poggi, M., A computational study of conflict graphs and aggressive cut separation in integer programming, Electron. Notes Discrete Math., 50, 355-360 (2015) · Zbl 1356.90085
[12] Brucker, P.; Knust, S.; Schoo, A.; Thiele, O., A branch and bound algorithm for the resource-constrained project scheduling problem, Eur. J. Oper. Res., 107, 272-288 (1998) · Zbl 0970.90030
[13] Cavalcante, C.; de Souza, C.; Savelsbergh, M.; Y, W.; Wolsey, L. A., Scheduling projects with labor constraints, Discrete Appl. Math., 112, 1, 27-52 (2001) · Zbl 0984.90012
[14] Chakrabortty, R. K.; Sarker, R. A.; Essam, D. L., Resource constrained project scheduling: a branch and cut approach, International Conference on Computers and Industrial Engineering, Vol. 45, 552-559 (2015)
[15] Christofides, N.; Alvarez-Valdes, R.; Tamarit, J., Project scheduling with resource constraints: a branch and bound approach, Eur. J. Oper. Res., 29, 262-273 (1987) · Zbl 0614.90056
[16] Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 305-337 (1973) · Zbl 0253.05131
[17] de Souza, C. C.; Wolsey, L. A., Scheduling Projects with Labour Constraints, Technical report (1997), Instituto de Computação, Universidade Estadual de Campinas
[18] Demassey, S.; Artigues, C.; Michelon, P., Constraint propagation based cutting planes : an application to the resource-constrained project scheduling problem, INFORMS J. Comput., 17, 52-65 (2005) · Zbl 1239.90062
[19] Demeulemeester, E.; Herroelen, W., Recent advances in branch-and-bound procedures for resource-constrained project scheduling problems, Paper Presented at the Summer School on Scheduling Theory and its Applications, 1-32 (1992)
[20] Demeulemeester, E. L.; Herroelen, W. S., Project Scheduling: A Research Handbook (2002), Kluwer Academic Publishers · Zbl 1059.90068
[21] Fischetti, M.; Lodi, A., Optimizing over the first Chvátal closure, Math. Program., 110, 1, 3-20 (2007) · Zbl 1192.90125
[22] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman & Co.: W. H. Freeman & Co. New York, NY, USA · Zbl 0411.68039
[23] Gu, Z.; Nemhauser, G.; Savelsbergh, M., Sequence independent lifting in mixed integer programming, J. Comb. Optim., 4, 1, 109-129 (2000) · Zbl 0964.90030
[24] Gurobi Optimization, I., 2016. Gurobi Optimizer: Reference Manual.
[25] Hardin, J. R.; Nemhauser, G. L.; Savelsbergh, M. W., Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements, Discrete Optim., 5, 19-35 (2008) · Zbl 1134.90016
[26] Johnson, E.; Kostreva, M.; Suhl, U., Solving 0-1 integer programming problems arising from large scale planning models, Oper. Res., 33, 803-819 (1985) · Zbl 0569.90056
[27] Kelley Jr, J.; Walker, M. R., Critical-path planning and scheduling, Eastern Joint IRE-AIEE-ACM Computer Conference, 160-173 (1959), ACM
[28] Kolisch, R., Project Scheduling under Resource Constraints: Efficient Heuristics for Several Problem Classes. Number IX, 212, Production and Logistics (1995), Physica-Verlag Heidelberg
[29] Kolisch, R.; Sprecher, A., PSPLIB - a project scheduling problem library, Eur. J. Oper. Res., 96, 205-216 (1996) · Zbl 0947.90587
[30] Kone, O.; Artigues, C.; Lopez, P.; Mongeau, M., Event-based MILP models for resource-constrained project scheduling problems, Comput. Oper. Res., 38, 3-13 (2011) · Zbl 1231.90202
[31] Land, A. H.; Doig, A. G., An Automatic Method for Solving Discrete Programming Problems, 105-132 (2010), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg · Zbl 1187.90016
[32] Letchford, A. N.; Marzi, F.; Rossi, F.; Smriglio, S., Strengthening Chvátal-Gomory cuts for the stable set problem, Combinatorial Optimization, 201-212 (2016), Springer International Publishing · Zbl 1452.90272
[33] Article ID 652135, 7 pages, doi:10.1155/2014/652135.
[34] Liu, S.-S.; Wang, C.-J., Resource-constrained construction project scheduling model for profit maximization considering cash flow, Autom. Constr., 17, 8, 966-974 (2008)
[35] Mingozzi, A.; Maniezzo, V.; Ricciardelli, S.; Bianco, L., An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation, Manage. Sci., 44, 5, 714-729 (1998) · Zbl 1004.90036
[36] Nemhauser, G. L.; Vance, P. H., Lifted cover facets of the 0-1 knapsack polytope with GUB constraints, Oper. Res. Lett., 16, 5, 255-263 (1994) · Zbl 0826.90093
[37] Padberg, M. W., On the facial structure of set packing polyhedra, Math. Program., 5, 1, 199-215 (1973) · Zbl 0272.90041
[38] Patterson, J.; Huber, W., A horizon-varying zero-one approach to project scheduling, Manage. Sci., 20, 990-998 (1974) · Zbl 0303.90026
[39] Pritsker, A.; Watters, L.; Wolfe, P., Multi project scheduling with limited resources: a zero-one programming approach, Manage. Sci., 3416, 93-108 (1969)
[40] Riedler, M.; Jatschka, T.; Maschler, J.; Raidl, G. R., An iterative time-bucket refinement algorithm for a high resolution resource-constrained project scheduling problem, Int. Trans. Oper. Res., 27, 573-613 (2020)
[41] Sankaran, J. K.; Bricker, D. L.; Juang, S., A strong fractional cutting plane algorithm for resource-constrained project scheduling, Int. J. Ind. Eng., 6, 99-111 (1999)
[42] Santos, H. G.; Toffolo, T. A.M.; Gomes, R. A.M.; Ribas, S., Integer programming techniques for the nurse rostering problem, Ann. Oper. Res., 239, 1, 225-251 (2016) · Zbl 1336.90063
[43] Schnell, A.; Hartl, R. F., On the generalization of constraint programming and boolean satisfiability solving techniques to schedule a resource-constrained project consisting of multi-mode jobs, Oper. Res. Perspect.s, 4, 1-11 (2017)
[44] Schwindt, C.; Zimmermann, J., Handbook on project management and scheduling, International Handbooks on Information Systems, Vol. 1 (2015), Springer International Publishing
[45] Toffolo, T.; Santos, H.; Carvalho, M.; Soares, J., An integer programming approach to the multimode resource-constrained multiproject scheduling problem, J. Scheduling, 19, 295-307 (2016) · Zbl 1347.90051
[46] Van Peteghem, V.; Vanhoucke, M., An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances, Eur. J. Oper. Res., 235, 1, 62-72 (2014) · Zbl 1305.90203
[47] Wauters, T.; Kinable, J.; Smet, P.; Vancroonenburg, W.; Vanden Berghe, G.; Verstichel, J., The multi-mode resource-constrained multi-project scheduling problem, J. Scheduling, 19, 271-283 (2016) · Zbl 1347.90052
[48] Wolsey, L., Integer Programming (1998), Wiley - Interscience Series in Discrete Mathematics and Optimization · Zbl 0930.90072
[49] Zhu, G.; Bard, J.; Yu, G., A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem, INFORMS J. Comput., 18, 3, 377-390 (2006) · Zbl 1241.90168
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.