×

zbMATH — the first resource for mathematics

On the efficient modeling and solution of the multi-mode resource-constrained project scheduling problem with generalized precedence relations. (English) Zbl 1339.90151
Summary: For variants of the single-mode resource-constrained project scheduling problem, state-of-the-art exact algorithms combine a Branch and Bound algorithm with principles from Constraint Programming and Boolean Satisfiability Solving. In our paper, we propose new exact approaches extending the above principles to the multi-mode RCPSP (MRCPSP) with generalized precedence relations (GPRs). More precisely, we implemented two constraint handlers cumulativemm and gprecedencemm for the optimization framework SCIP. With the latter, one can model renewable resource constraints and GPRs in the context of multi-mode activities, respectively. Moreover, they integrate domain propagation and explanation generation techniques for the above problem characteristics. We formulate three SCIP-models for the MRCPSP with GPRs, two without and one with our constraint handler gprecedencemm. Our computational results on instances from the literature with \(30\), \(50\) and \(100\) activities show that the addition of this constraint handler significantly strengthens the SCIP-model. Moreover, we outperform the state-of-the-art exact approach on instances with \(50\) activities when imposing time limits of \(27\) s. In addition, we close (find the optimal solution and prove its optimality for) \(289\) open instances and improve the best known makespan for \(271\) instances from the literature.

MSC:
90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg T (2004) SCIP-a framework to integrate constraint and mixed integer programming. Konrad-Zuse-Zentrum für Informationstechnik Berlin, Berlin
[2] Achterberg, T, SCIP: solving constraint integer programs, Math Program Comput, 1, 1-41, (2009) · Zbl 1171.90476
[3] Apt KR (2003) Principles of constraint programming. Cambridge University Press, Cambridge · Zbl 1187.68132
[4] Ballestín, F; Barrios, A; Valls, V, Looking for the best modes helps solving the MRCPSP/MAX, Int J Prod Res, 51, 813-827, (2013)
[5] Bartusch, M; Möhring, RH; Radermacher, FJ, Scheduling project networks with resource constraints and time windows, Ann Oper Res, 16, 199-240, (1988) · Zbl 0693.90047
[6] Blazewicz, J; Lenstra, JK; Rinnooy Kan, AHG, Scheduling subject to resource constraints: classification and complexity, Discrete Appl Math, 5, 11-24, (1983) · Zbl 0516.68037
[7] Brucker, P; Knust, S, Lower bounds for resource-constrained project scheduling problems, Eur J Oper Res, 149, 302-313, (2003) · Zbl 1036.90038
[8] Brucker P, Knust S (2006) Complex scheduling. Springer, Berlin (ISBN 3540295453) · Zbl 1154.90002
[9] CPU benchmark (2014) Passmark CPU benchmark. https://www.cpubenchmark.net/cpu_list.php. Accessed 27 Jan 2015
[10] Reyck, B; Herroelen, W, The multi-mode resource-constrained project scheduling problem with generalized precedence relations, Eur J Oper Res, 119, 538-556, (1999) · Zbl 0934.90040
[11] Elmaghraby SE (1977) Activity networks: project planning and control by network models. Wiley, New York · Zbl 0385.90076
[12] Fischetti, M; Monaci, M, Exploiting erraticism in search, Oper Res, 62, 114-122, (2014) · Zbl 1291.90148
[13] Hartmann, S; Briskorn, D, A survey of variants and extensions of the resource-constrained project scheduling problem, Eur J Oper Res, 207, 1-14, (2010) · Zbl 1205.90123
[14] Heilmann, R, A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags, Eur J Oper Res, 144, 348-365, (2003) · Zbl 1012.90513
[15] Horbach, A, A Boolean satisfiability approach to the resource-constrained project scheduling problem, Ann Oper Res, 181, 89-107, (2010) · Zbl 1209.90170
[16] Kolisch, R; Drexl, A, Local search for nonpreemptive multi-mode resource-constrained project scheduling, IIE Trans, 29, 987-999, (1997)
[17] Kolisch, R; Sprecher, A, PSPLIB-a project scheduling problem library, Eur J Oper Res, 96, 205-216, (1997) · Zbl 0947.90587
[18] Kolisch, R; Sprecher, A; Drexl, A, Characterization and generation of a general class of resource-constrained project scheduling problems, Manag Sci, 41, 1693-1703, (1995) · Zbl 0870.90070
[19] Marques-Silva, JP; Sakallah, KA, GRASP: a search algorithm for propositional satisfiability, IEEE Trans Comput, 48, 506-521, (1999) · Zbl 1392.68388
[20] Moskewicz MW, Madigan CF, Zhao Y, Zhang L, Malik S (2001) Chaff: engineering an efficient SAT solver. In: Proceedings of the 38th annual design automation conference, DAC ’01, New York, NY, USA. ACM, pp 530-535 (ISBN 1-58113-297-2). doi:10.1145/378239.379017 · Zbl 1171.90476
[21] Nonobe K, Ibaraki T (2003) A tabu search algorithm for a generalized resource constrained project scheduling problem. In: MIC2003: the fifth metaheuristics international conference, pp 55-1 · Zbl 1171.90476
[22] Ohrimenko, O; Stuckey, PJ; Codish, M, Propagation via lazy clause generation, Constraints, 14, 357-391, (2009) · Zbl 1192.68654
[23] Online (2014) Operations Management Group of the TU Clausthal. http://www.wiwi.tu-clausthal.de/en/chairs/produktion/research/research-areas/project-generator/mrcpspmax/. Accessed 1 Feb 2015 · Zbl 1036.90038
[24] Schnell A, Hartl RF (2012) The effect of the predefined search space on recent exact algorithms for the resource-constrained project scheduling problem. In: Working paper · Zbl 1192.68654
[25] Schnell A, Hartl RF (2013) On the generalization of constraint programming and boolean satisfiability solving techniques to schedule a resource-constrained project consisting of multi-mode jobs. In: Working paper (under review) · Zbl 1226.68099
[26] Schutt, A; Feydy, T; Stuckey, PJ; Wallace, MG, Explaining the cumulative propagator, Constraints, 16, 250-282, (2011) · Zbl 1226.68099
[27] Schutt A, Chu G, Stuckey PJ, Wallace MG (2012) Maximising the net present value for resource-constrained project scheduling. In: Beldiceanu N, Jussien N, Pinson E (eds) Integration of AI and OR techniques in constraint programming for combinatorial optimzation problems, Lecture notes in computer science, vol 7298. Springer, Berlin, pp 362-378 (ISBN 978-3-642-29827-1)
[28] Schutt, A; Feydy, T; Stuckey, PJ; Wallace, MG, Solving RCPSP/MAX by lazy clause generation, J Sched, 16, 273-289, (2013) · Zbl 1280.90067
[29] Schwindt C (1998) Generation of resource constrained project scheduling problems subject to temporal constraints. In: Report WIOR-543. Institut für Wirtschaftstheorie und Operations Research, Universität Karlsruhe · Zbl 1241.90168
[30] Zhu, G; Bard, JF; Yu, G, A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem, Informs J Comput, 18, 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.