×

zbMATH — the first resource for mathematics

An efficient filtering algorithm for the unary resource constraint with transition times and optional activities. (English) Zbl 1446.90085
Summary: This paper describes a unified global constraint to model scheduling problems with unary resources, i.e., each resource can process only a single activity at a time. In addition, the constraint enforces sequence-dependent transition times between activities. It often happens that activities are grouped into families with zero transition times within a family. Moreover, some of the activities might be optional from the resource viewpoint (typically in the case of alternative resources). The global constraint unifies reasoning with both optional activities and families of activities. The scalable filtering algorithms we discuss keep a low time complexity of \(\mathcal{O}(n \cdot \log (n) \cdot \log (f))\), where \(n\) is the number of tasks on the resource and \(f\) is the number of families. This results from the fact that we extend the \(\varTheta \)-tree data structure used for the Unary Resource constraint without transition times. Our experiments demonstrate that our global constraint strengthens the pruning of domains as compared with existing approaches, leading to important speedups. Moreover, our low time complexity allows maintaining a small overhead, even for large instances. These conclusions are particularly true when optional activities are present in the problem.
MSC:
90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Software:
ILOG SCHEDULE; OscaR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allahverdi, A.; Ng, C.; Cheng, TE; Kovalyov, MY, A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187, 3, 985-1032 (2008) · Zbl 1137.90474
[2] Artigues, C., Belmokhtar, S., & Feillet, D. (2004). A new exact solution algorithm for the job shop problem with sequence-dependent setup times. In J. C. Régin, & M. Rueher (Eds.), Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 37-49). Springer. · Zbl 1094.90553
[3] Artigues, C.; Feillet, D., A branch and bound method for the job-shop problem with sequence-dependent setup times, Annals of Operations Research, 159, 1, 135-159 (2008) · Zbl 1152.90424
[4] Baptiste, P.; Laborie, P.; Le Pape, C.; Nuijten, W.; Rossi, F.; van Beek, P.; Walsh, T., Constraint-based scheduling and planning, Handbook of constraint programming, Chap. 22, 759-797 (2006), Amsterdam: Elsevier, Amsterdam
[5] Baptiste, P.; Le Pape, C.; Nuijten, W., Constraint-based scheduling: Applying constraint programming to scheduling problems, International Series in Operations Research & Management Science (2001), Berlin: Springer, Berlin · Zbl 1094.90002
[6] Barták, R. (2008). Search strategies for scheduling problems with optional activities. In Proceedings of CSCLP 2008 annual ERCIM workshop on constraint solving and constraint logic programming, Rome.
[7] Barták, R.; Čepek, O., Incremental propagation rules for a precedence graph with optional activities and time windows, Transactions of the Institute of Measurement and Control, 32, 1, 73-96 (2010)
[8] Bellman, R., On a routing problem (1956), DTIC Document: Technical report, DTIC Document
[9] Brucker, P. (1999). Complex scheduling problems. Zeitschrift Operations Research. 30, 99.
[10] Brucker, P.; Thiele, O., A branch & bound method for the general-shop problem with sequence dependent setup-times, Operations-Research-Spektrum, 18, 3, 145-161 (1996) · Zbl 0852.90087
[11] Cappart, Q., Thomas, C., Schaus, P., & Rousseau, L. M. (2018). A constraint programming approach for solving patient transportation problems. In International conference on principles and practice of constraint programming (pp. 490-506). Springer.
[12] Christofides, N.; Mingozzi, A.; Toth, P., State-space relaxation procedures for the computation of bounds to routing problems, Networks, 11, 2, 145-164 (1981) · Zbl 0458.90071
[13] Dejemeppe, C. (2016). Constraint programming algorithms and models for scheduling applications. Ph.D. thesis, Université catholique de Louvain, Louvain-la-Neuve
[14] Dejemeppe, C., Van Cauwelaert, S., & Schaus, P. (2015). The unary resource with transition times. In International conference on principles and practice of constraint programming (pp. 89-104). Springer
[15] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Mathematical programming, 91, 2, 201-213 (2002) · Zbl 1049.90004
[16] Focacci, F., Laborie, P., & Nuijten, W. (2000). Solving scheduling problems with setup times and alternative resources. In AIPS (pp. 92-101).
[17] Gay, S., Hartert, R., Lecoutre, C., & Schaus, P.(2015). Conflict ordering search for scheduling problems. In International conference on principles and practice of constraint programming (pp. 140-148). Springer.
[18] Gay, S., Schaus, P., & De Smedt, V. (2014). Continuous casting scheduling with constraint programming. In B. O’Sullivan (Ed.), Principles and practice of constraint programming (pp. 831-845). Springer.
[19] Grimes, D., & Hebrard, E. (2010). Job shop scheduling with setup times and maximal time-lags: A simple constraint programming approach. In Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 147-161). Springer. · Zbl 1285.68157
[20] Kruskal, JB, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical society, 7, 1, 48-50 (1956) · Zbl 0070.18404
[21] Laborie, P. (2018). An update on the comparison of MIP, CP and hybrid approaches for mixed resource allocation and scheduling. In International conference on the integration of constraint programming, artificial intelligence, and operations research (pp. 403-411). Springer. · Zbl 06982407
[22] Laborie, P., & Rogerie, J. (2008). Reasoning with conditional time-intervals. In FLAIRS conference (pp. 555-560).
[23] Laborie, P.; Rogerie, J.; Shaw, P.; Vilím, P., IBM ILOG CP optimizer for scheduling, Constraints, 23, 2, 210-250 (2018) · Zbl 1400.90169
[24] Moore, E. (1959). The shortest path through a maze. In Proceedings international symposium on switching theory.
[25] Team, Osca R. (2012). OscaR: Scala in OR. Retrieved from https://bitbucket.org/oscarlib/oscar.
[26] Ozolins, A., Bounded dynamic programming algorithm for the job shop problem with sequence dependent setup times, Operational Research (2018)
[27] Van Cauwelaert, S., Lombardi, M., & Schaus, P. (2015) Understanding the potential of propagators. In International conference on integration of artificial intelligence (AI) and operations research (OR) techniques in constraint programming (pp. 427-436). Springer. · Zbl 06605772
[28] Van Cauwelaert, S., Lombardi, M., & Schaus, P. (2016). A visual web tool to perform what-if analysis of optimization approaches. Technical report, UCLouvain.
[29] Van Cauwelaert, S.; Lombardi, M.; Schaus, P., How efficient is a global constraint in practice?, Constraints, 23, 210-250 (2017)
[30] Vilım, P. (2007). Global constraints in scheduling. Ph.D. thesis, Charles University in Prague, Faculty of Mathematics and Physics, Department of Theoretical Computer Science and Mathematical Logic, KTIML MFF, Universita Karlova, Malostranské námestı 2/25, 118 00 Praha 1, Czech Republic.
[31] Vilım, P. (2009a). Edge finding filtering algorithm for discrete cumulative resources in o (kn log n). In I. P. Gent (Ed.), Principles and practice of constraint programming-CP (Vol. 5732, pp. 802-816). Springer.
[32] Vilím, P. (2009b). Max energy filtering algorithm for discrete cumulative resources. In International conference on AI and OR techniques in constriant programming for combinatorial optimization problems (pp. 294-308). Springer. · Zbl 1241.90125
[33] Vilım, P., & Barták, R. (2012). Filtering algorithms for batch processing with sequence dependent setup times. In Proceedings of the 6th international conference on AI planning and scheduling, AIPS.
[34] Warren, HS, Hacker’s delight (2013), London: Pearson Education, London
[35] Wolf, A., Constraint-based task scheduling with sequence dependent setup times, time windows and breaks, GI Jahrestagung, 154, 3205-3219 (2009)
[36] Zampelli, S., Vergados, Y., Van Schaeren, R., Dullaert, W., & Raa, B. (2013). The berth allocation and quay crane assignment problem using a CP approach. In C. Schulte (Ed.), Principles and practice of constraint programming (pp. 880-896). Springer.
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.