×

zbMATH — the first resource for mathematics

Solving RCPSP/max by lazy clause generation. (English) Zbl 1280.90067
Summary: We present a generic exact method for minimizing the project duration of the resource-constrained project scheduling problem with generalized precedence relations (Rcpsp/max). This is a very general scheduling model with applications areas such as project management and production planning. Our method uses lazy clause generation, i.e., a hybrid of finite domain and Boolean satisfiability solving, in order to apply no-good learning and conflict-driven search to the solution generation. Our experiments show the benefit of lazy clause generation for finding an optimal solution and proving its optimality in comparison to other state-of-the-art exact and non-exact methods. In comparison to other methods, our method is able to find better solutions faster on the Rcpsp/max benchmarks. Indeed, our method closes 573 open problem instances and generates better solutions in most of the remaining instances. Surprisingly, although ours is an exact method, it outperforms the published non-exact methods on these benchmarks in terms of the quality of solutions.

MSC:
90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C09 Boolean programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aggoun, A.; Beldiceanu, N., Extending CHIP in order to solve complex scheduling and placement problems, Mathematical and Computer Modelling, 17, 57-73, (1993)
[2] Ballestín, F.; Barrios, A.; Valls, V., An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time lags, Journal of Scheduling, 14, 391-406, (2011) · Zbl 1230.90085
[3] Bartusch, M.; Möhring, R. H.; Radermacher, F. J., Scheduling project networks with resource constraints and time windows, Annals of Operations Research, 16, 199-240, (1988) · Zbl 0693.90047
[4] Bellman, R., On a routing problem, Quarterly of Applied Mathematics, 16, 87-90, (1958) · Zbl 0081.14403
[5] Blazewicz, J.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Scheduling subject to resource constraints: classification and complexity, Discrete Applied Mathematics, 5, 11-24, (1983) · Zbl 0516.68037
[6] Brucker, P.; Drexl, A.; Möhring, R.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: notation, classification, models, and methods, European Journal of Operational Research, 112, 3-41, (1999) · Zbl 0937.90030
[7] Cesta, A.; Oddi, A.; Smith, S. F., A constraint-based method for project scheduling with time windows, Journal of Heuristics, 8, 109-136, (2002) · Zbl 1048.90103
[8] Davis, M.; Putnam, H., A computing procedure for quantification theory, Journal of the ACM, 7, 201-215, (1960) · Zbl 0212.34203
[9] Davis, M.; Logemann, G.; Loveland, D., A machine program for theorem proving, Communications of the ACM, 5, 394-397, (1962) · Zbl 0217.54002
[10] Reyck, B.; Herroelen, W., A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations, European Journal of Operational Research, 111, 152-174, (1998) · Zbl 0948.90077
[11] Dorndorf, U.; Pesch, E.; Phan-Huy, T., A time-oriented branch-and-bound algorithm for resource-constrained project scheduling with generalised precedence constraints, Management Science, 46, 1365-1384, (2000) · Zbl 1232.90208
[12] Fest, A., Möhring, R. H., Stork, F., & Uetz, M. (1999). Resource-constrained project scheduling with time windows: a branching scheme based on dynamic release dates (Technical Report 596). Technische Universität Berlin. · Zbl 1165.68517
[13] Feydy, T. (2010). Constraint programming: improving propagation. PhD thesis, The University of Melbourne.
[14] Feydy, T.; Schutt, A.; Stuckey, P. J.; Antoy, S. (ed.); Albert, E. (ed.), Global difference constraint propagation for finite domain solvers, 226-235, (2008), New York
[15] Feydy, T.; Somogyi, Z.; Stuckey, P. J.; Lee, J. H. M. (ed.), Half reification and flattening, No. 6876, 286-301, (2011), Berlin
[16] Ford, L. R., & Fulkerson, D. R. (1962). Flows in networks. Princeton: Princeton University Press. · Zbl 0106.34802
[17] Franck, B.; Neumann, K.; Schwindt, C., Truncated branch-and-bound, schedule-construction, and schedule-improvement procedures for resource-constrained project scheduling, OR Spektrum, 23, 297-324, (2001) · Zbl 0989.90060
[18] Herroelen, W.; Reyck, B.; Demeulemeester, E., Resource-constrained project scheduling: a survey of recent developments, Computers & Operations Research, 25, 279-302, (1998) · Zbl 1040.90525
[19] Horbach, A., A Boolean satisfiability approach to the resource-constrained project scheduling problem, Annals of Operations Research, 181, 89-107, (2010) · Zbl 1209.90170
[20] Huang, J.; Veloso, M. M. (ed.), The effect of restarts on the efficiency of clause learning, 2318-2323, (2007)
[21] Kolisch, R.; Schwindt, C.; Sprecher, A., Publishers, chap benchmark instances for project scheduling problems, 197-212, (1998), Dordrecht
[22] Le Pape, C., Implementation of resource constraints in ILOG schedule: a library for the development of constraint-based scheduling systems, Intelligent Systems Engineering, 3, 55-66, (1994)
[23] Marriott, K., & Stuckey, P. J. (1998). Programming with constraints: an introduction. Cambridge: MIT Press. · Zbl 0935.68098
[24] Moskewicz, M. W.; Madigan, C. F.; Zhao, Y.; Zhang, L.; Malik, S., Chaff: engineering an efficient SAT solver, 530-535, (2001), New York
[25] Neumann, K.; Schwindt, C., Activity-on-node networks with minimal and maximal time lags and their application to make-to-order production, OR Spektrum, 19, 205-217, (1997) · Zbl 0885.90058
[26] Oddi, A.; Rasconi, R.; Oddi, A. (ed.); Fages, F. (ed.); Rossi, F. (ed.), Iterative flattening search on RCPSP/MAX problems: recent developments, No. 5655, 99-115, (2009), Berlin · Zbl 1248.68460
[27] Ohrimenko, O.; Stuckey, P. J.; Codish, M., Propagation via lazy clause generation, Constraints, 14, 357-391, (2009) · Zbl 1192.68654
[28] Project duration problem RCPSP/max (2010). http://www.wior.uni-karlsruhe.de/LS_Neumann/Forschung/ProGenMax/rcpspmax.html. · Zbl 0693.90047
[29] PSPLib (2010). Project scheduling problem library. http://129.187.106.231/psplib/. · Zbl 1230.90085
[30] Schutt, A.; Feydy, T.; Stuckey, P. J.; Wallace, M. G.; Gent, I. P. (ed.), Why cumulative decomposition is not as bad as it sounds, No. 5732, 746-761, (2009), Berlin
[31] Schutt, A.; Feydy, T.; Stuckey, P. J.; Wallace, M. G., Explaining the cumulative propagator, Constraints, 16, 250-282, (2011) · Zbl 1226.68099
[32] Schwindt, C. (1995). ProGen/max: a new problem generator for different resource-constrained project scheduling problems with minimal and maximal time lags (WIOR 449). Universität Karlsruhe, Germany · Zbl 1232.90208
[33] Schwindt, C. (1998a). A branch-and-bound algorithm for the resource-constrained project duration problem subject to temporal constraints (WIOR 544). Universität Karlsruhe, Germany
[34] Schwindt, C. (1998b). Verfahren zur lösung des ressourcenbeschränkten projektdauerminimierungsproblems mit planungsabhängigen zeitfenstern. Aachen: Shaker.
[35] Smith, T. B.; Pyle, J. M.; McGuinness, D. L. (ed.); Ferguson, G. (ed.), An effective algorithm for project scheduling with arbitrary temporal constraints, 544-549, (2004), Cambridge
[36] Stuckey, P. J.; García de la Banda, M. J.; Maher, M. J.; Marriott, K.; Slaney, J. K.; Somogyi, Z.; Wallace, M. G.; Walsh, T.; Gabbrielli, M. (ed.); Gupta, G. (ed.), The G12 project: mapping solver independent models to efficient solutions, No. 3668, 9-13, (2005), Berlin · Zbl 1165.68517
[37] Tsang, E. (1993). Foundations of constraint satisfaction. San Diego: Academic Press.
[38] Walsh, T., Search in a small world, 1172-1177, (1999), San Mateo
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.