×

zbMATH — the first resource for mathematics

Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last. (English) Zbl 1457.90067
Summary: We present new filtering algorithms for Disjunctive and Cumulative constraints, each of which improves the complexity of the state-of-the-art algorithms by a factor of \(\log n\). We show how to perform Time-Tabling and Detectable Precedences in linear time on the Disjunctive constraint. Furthermore, we present a linear-time Overload Checking for the Disjunctive and Cumulative constraints. Finally, we show how the rule of Not-first/Not-last can be enforced in quadratic time for the Cumulative constraint. These algorithms rely on the union find data structure, from which we take advantage to introduce a new data structure that we call it time line. This data structure provides constant time operations that were previously implemented in logarithmic time by the \(\Theta\)-tree data structure. Experiments show that these new algorithms are competitive even for a small number of tasks and outperform existing algorithms as the number of tasks increases. We also show that the time line can be used to solve specific scheduling problems.
MSC:
90B35 Deterministic scheduling theory in operations research
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
BL data set
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baptiste, P; Le Pape, C, Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems, Constraints, 5, 119-139, (2000) · Zbl 0941.90030
[2] Baptiste, P., Le Pape, C., Nuijten, W. (2001). Constraint-based scheduling. Kluwer Academic Publishers. · Zbl 1094.90002
[3] Beldiceanu, N., & Carlsson, M. (2002). A new multi-resource cumulatives constraint with negative heights. In: Proceedings of the 8th international conference on principles and practice of constraint programming (CP 2002) (pp. 63-79).
[4] Beldiceanu, N., Carlsson, M., Poder, E. (2008). New filtering for the cumulative constraint in the context of non-overlapping rectangles. In: Proceedings of the 5th international conference on integration of AI and OR techniques in constraint programming for combinatorial optimisation problems (CPAIOR 2008) (pp. 21-35). · Zbl 1142.68505
[5] Belov, G., Boland, N., Savelsbergh, M.W.P., Stuckey, P.J. (2015). Exploration of models for a cargo assembly planning problem. ArXiv e-prints. · Zbl 06298790
[6] Caseau, Y., & Laburthe, F. (1996). Cumulative scheduling with task intervals. In: Proceedings of the joint international conference and symposium on logic programming (JICSLP) (pp. 369-383).
[7] Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E. (2001). Introduction to Algorithms, 2nd edn. McGraw-Hill Higher Education. · Zbl 1047.68161
[8] Fahimi, H., & Quimper, C.G. (2014). Linear-time filtering algorithms for the disjunctive constraint. In: AAAI (pp. 2637-2643).
[9] Gabow, H.N., & Tarjan, R.E. (1983). A linear-time algorithm for a special case of disjoint set union. In: Proceedings of the 15th annual ACM symposium on theory of computing (pp. 246-251).
[10] Gay, S., Hartert, R., Schaus, P. (2015). Simple and scalable time-table filtering for the cumulative constraint. In: Principles and practice of constraint programming (pp. 149-157). Springer. · Zbl 1459.90093
[11] Gay, S., Schaus, P., Smedt, V.D. (2014). Continuous casting scheduling with constraint programming. In: International conference on principles and practice of constraint programming (pp. 831-845). Springer.
[12] Guéret, C., Jussien, N., Boizumault, P., Prins, C. (1995). Building university timetables using constraint logic programming. International conference on the practice and theory of automated timetabling, (pp. 130-145). Springer.
[13] Horn, W, Some simple scheduling algorithms, Naval Research Logistics Quarterly, 21, 177-185, (1974) · Zbl 0276.90024
[14] Kameugne, R; Fotso, LP, A cumulative not-first/not-last filtering algorithm in o (n 2log (n)), Indian Journal of Pure and Applied Mathematics, 44, 95-115, (2013) · Zbl 1282.90070
[15] Letort, A., Beldiceanu, N., Carlsson, M. (2012). A scalable sweep algorithm for the cumulative constraint. In: Proceedings of the 18th international conference on principles and practice of constraint programming (CP 2012) (pp. 439-454). · Zbl 1382.68225
[16] López-Ortiz, A., Quimper, C.G., Tromp, J., van Beek, P. (2003). A fast and simple algorithm for bounds consistency of the alldifferent constraint. In: Proceedings of the 18th international joint conference on artificial intelligence (IJCAI-03) (pp. 245-250).
[17] Le Pape, C. (1988). Des systèmes d’ordonnancement flexibles et opportunistes. Ph.D. thesis Universit Paris IX.
[18] Mehlhorn, K; Thiel, S, Faster algorithms for bound-consistency of the sortedness and the alldifferent constraint, CP, 2, 306-319, (2000) · Zbl 1044.68783
[19] Nuijten, W.W. (1994). Time and resource constrained scheduling: a constraint satisfaction approach. Technische Universiteit Eindhoven: Ph.D. thesis. · Zbl 0837.90068
[20] Ouellet, P., & Quimper, C.G. (2013). Time-table-extended-edge-finding for the cumulative constraint. In: Proceedings of the 19th international conference on principles and practice of constraint programming (CP 2013) (pp. 562-577).
[21] Puget, J.F. (1998). A fast algorithm for the bound consistency of alldiff constraints. In: Proceedings of the 15th national conference on artificiel intelligence (AAAI-98) and the 10th conference on innovation applications of artificial intelligence (IAAI-98) (pp. 359-366).
[22] Quimper, C.G., López-Ortiz, A., Pesant, G. (2006). A quadratic propagator for the inter-distance constraint. In: Proc. of the 21st nat. conf. on artificial intelligence (AAAI 06) (pp. 123-128).
[23] Schutt, A., Feydy, T., Stuckey, P.J. (2013). Explaining time-table-edge-finding propagation for the cumulative resource constraint. In: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR 2013) (pp. 234-250). · Zbl 1382.68232
[24] Schutt, A; Feydy, T; Stuckey, PJ; Wallace, MG, Solving rcpsp/MAX by lazy clause generation, Journal of Scheduling, 16, 273-289, (2013) · Zbl 1280.90067
[25] Schutt, A., Stuckey, P., Verden, A. (2011). Optimal carpet cutting, pp. 69-84.
[26] Schutt, A., Wolf, A., Schrader, G. (2006). Not-first and not-last detection for cumulative scheduling in \(\mathcal{O}(n^{3}\log n)\). In: Declarative programming for knowledge management (INAP 2005) (pp. 66-80).
[27] Taillard, E, Benchmarks for basic scheduling problems, European Journal Opererational Research, 64, 278-285, (1993) · Zbl 0769.90052
[28] Vilím, P. (2002). Batch processing with sequence dependent setup times: New results. In: Proceedings of the 4th workshop of constraint programming for decision and control (CPDC’02).
[29] Vilím, P. (2004). \(O\)(\(n\) log \(n\)) filtering algorithms for unary resource constraint. In: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR 2004) (pp. 335-347). · Zbl 1094.90566
[30] Vilím, P. (2007). Global constraints in scheduling. Ph.D. thesis: Charles University in Prague.
[31] Vilím, P.E. (2009). Finding filtering algorithm for discrete cumulative resources in \(O\)(\(k\)\(n\) log \(n\)). In: Principles and Practice of Constraint Programming (CP 2009) (pp. 802-816).
[32] Vilím, P. (2009). Max energy filtering algorithm for discrete cumulative resources. In: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 294-308). Springer. · Zbl 1241.90125
[33] Vilím, P. (2011). Timetable edge finding filtering algorithm for discrete cumulative resources. In: Proceedings of the 8th international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR 2011) (pp. 230-245).
[34] Vilím, P., Barták, R., Čepek, O. (2004). Unary resource constraint with optional activities. In: Proceedings of the 10th international conference on principles and practice of constraint programming (pp. 62-76). · Zbl 1152.68590
[35] Wolf, A., & Schrader, G. (2006). \(O\)(\(n\) log \(n\)) overload checking for the cumulative constraint and its application. In: Declarative programming for knowledge management (INAP 2005) (pp. 88-101).
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.