{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T20:55:24Z","timestamp":1774644924145,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,4,11]],"date-time":"2018-04-11T00:00:00Z","timestamp":1523404800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2016-05953"],"award-info":[{"award-number":["RGPIN-2016-05953"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s10601-018-9282-9","type":"journal-article","created":{"date-parts":[[2018,4,11]],"date-time":"2018-04-11T00:05:46Z","timestamp":1523405146000},"page":"272-293","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last"],"prefix":"10.1007","volume":"23","author":[{"given":"Hamed","family":"Fahimi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanick","family":"Ouellet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5899-0217","authenticated-orcid":false,"given":"Claude-Guy","family":"Quimper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,4,11]]},"reference":[{"issue":"1-2","key":"9282_CR1","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1023\/A:1009822502231","volume":"5","author":"P Baptiste","year":"2000","unstructured":"Baptiste, P., & Le Pape, C. (2000). Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. Constraints, 5(1-2), 119\u2013139.","journal-title":"Constraints"},{"key":"9282_CR2","doi-asserted-by":"crossref","unstructured":"Baptiste, P., Le Pape, C., Nuijten, W. (2001). Constraint-based scheduling. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-1479-4"},{"key":"9282_CR3","doi-asserted-by":"crossref","unstructured":"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\u201379).","DOI":"10.1007\/3-540-46135-3_5"},{"key":"9282_CR4","doi-asserted-by":"crossref","unstructured":"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\u201335).","DOI":"10.1007\/978-3-540-68155-7_5"},{"key":"9282_CR5","unstructured":"Belov, G., Boland, N., Savelsbergh, M.W.P., Stuckey, P.J. (2015). Exploration of models for a cargo assembly planning problem. ArXiv e-prints."},{"key":"9282_CR6","unstructured":"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\u2013383)."},{"key":"9282_CR7","unstructured":"Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E. (2001). Introduction to Algorithms, 2nd edn. McGraw-Hill Higher Education."},{"key":"9282_CR8","unstructured":"Fahimi, H., & Quimper, C.G. (2014). Linear-time filtering algorithms for the disjunctive constraint. In: AAAI (pp. 2637\u20132643)."},{"key":"9282_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013251).","DOI":"10.1145\/800061.808753"},{"key":"9282_CR10","unstructured":"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\u2013157). Springer."},{"key":"9282_CR11","doi-asserted-by":"crossref","unstructured":"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\u2013845). Springer.","DOI":"10.1007\/978-3-319-10428-7_59"},{"key":"9282_CR12","unstructured":"Gu\u00e9ret, 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\u2013145). Springer."},{"issue":"1","key":"9282_CR13","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/nav.3800210113","volume":"21","author":"W Horn","year":"1974","unstructured":"Horn, W. (1974). Some simple scheduling algorithms. Naval Research Logistics Quarterly, 21(1), 177\u2013185.","journal-title":"Naval Research Logistics Quarterly"},{"issue":"1","key":"9282_CR14","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s13226-013-0005-z","volume":"44","author":"R Kameugne","year":"2013","unstructured":"Kameugne, R., & Fotso, L.P. (2013). A cumulative not-first\/not-last filtering algorithm in o (n 2log (n)). Indian Journal of Pure and Applied Mathematics, 44(1), 95\u2013115.","journal-title":"Indian Journal of Pure and Applied Mathematics"},{"key":"9282_CR15","doi-asserted-by":"crossref","unstructured":"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\u2013454).","DOI":"10.1007\/978-3-642-33558-7_33"},{"key":"9282_CR16","unstructured":"L\u00f3pez-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\u2013250)."},{"key":"9282_CR17","unstructured":"Le Pape, C. (1988). Des syst\u00e8mes d\u2019ordonnancement flexibles et opportunistes. Ph.D. thesis Universit Paris IX."},{"key":"9282_CR18","first-page":"306","volume":"2","author":"K Mehlhorn","year":"2000","unstructured":"Mehlhorn, K., & Thiel, S. (2000). Faster algorithms for bound-consistency of the sortedness and the alldifferent constraint. CP, 2, 306\u2013319.","journal-title":"CP"},{"key":"9282_CR19","volume-title":"Time and resource constrained scheduling: a constraint satisfaction approach","author":"WW Nuijten","year":"1994","unstructured":"Nuijten, W.W. (1994). Time and resource constrained scheduling: a constraint satisfaction approach. Technische Universiteit Eindhoven: Ph.D. thesis."},{"key":"9282_CR20","doi-asserted-by":"crossref","unstructured":"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\u2013577).","DOI":"10.1007\/978-3-642-40627-0_42"},{"key":"9282_CR21","unstructured":"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\u2013366)."},{"key":"9282_CR22","unstructured":"Quimper, C.G., L\u00f3pez-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\u2013128)."},{"key":"9282_CR23","doi-asserted-by":"crossref","unstructured":"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\u2013250).","DOI":"10.1007\/978-3-642-38171-3_16"},{"issue":"3","key":"9282_CR24","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s10951-012-0285-x","volume":"16","author":"A Schutt","year":"2013","unstructured":"Schutt, A., Feydy, T., Stuckey, P.J., Wallace, M.G. (2013). Solving rcpsp\/max by lazy clause generation. Journal of Scheduling, 16(3), 273\u2013289.","journal-title":"Journal of Scheduling"},{"key":"9282_CR25","doi-asserted-by":"crossref","unstructured":"Schutt, A., Stuckey, P., Verden, A. (2011). Optimal carpet cutting, pp. 69\u201384.","DOI":"10.1007\/978-3-642-23786-7_8"},{"key":"9282_CR26","unstructured":"Schutt, A., Wolf, A., Schrader, G. (2006). Not-first and not-last detection for cumulative scheduling in \n                    \n                      \n                    \n                    \n                      \n                        O\n                        (\n                        \n                          \n                            n\n                          \n                          \n                            3\n                          \n                        \n                        log\n                        n\n                        )\n                      \n                    \n                    $\\mathcal {O}(n^{3}\\log n)$\n                  . In: Declarative programming for knowledge management (INAP 2005) (pp. 66\u201380)."},{"issue":"2","key":"9282_CR27","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/0377-2217(93)90182-M","volume":"64","author":"E Taillard","year":"1993","unstructured":"Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal Opererational Research, 64(2), 278\u2013285.","journal-title":"European Journal Opererational Research"},{"key":"9282_CR28","unstructured":"Vil\u00edm, 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\u201902)."},{"key":"9282_CR29","unstructured":"Vil\u00edm, 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\u2013347)."},{"key":"9282_CR30","volume-title":"Global constraints in scheduling","author":"P Vil\u00edm","year":"2007","unstructured":"Vil\u00edm, P. (2007). Global constraints in scheduling. Ph.D. thesis: Charles University in Prague."},{"key":"#cr-split#-9282_CR31.1","unstructured":"23. Vil??m, P.E. (2009). Finding filtering algorithm for discrete cumulative resources in O(k"},{"key":"#cr-split#-9282_CR31.2","unstructured":"24.  n log n). In: Principles and Practice of Constraint Programming (CP 2009) (pp. 802-816)."},{"key":"9282_CR32","unstructured":"Vil\u00edm, 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\u2013308). Springer."},{"key":"9282_CR33","unstructured":"Vil\u00edm, 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\u2013245)."},{"key":"9282_CR34","unstructured":"Vil\u00edm, P., Bart\u00e1k, R., \u010cepek, O. (2004). Unary resource constraint with optional activities. In: Proceedings of the 10th international conference on principles and practice of constraint programming (pp. 62\u201376)."},{"key":"9282_CR35","unstructured":"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\u2013101)."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-018-9282-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9282-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9282-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,10]],"date-time":"2019-04-10T19:52:37Z","timestamp":1554925957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-018-9282-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,11]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9282"],"URL":"https:\/\/doi.org\/10.1007\/s10601-018-9282-9","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,11]]},"assertion":[{"value":"11 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}