Abstract
Scheduling has been a successful domain of application for constraint programming since its beginnings. The cumulative constraint – which enforces the usage of a limited resource by several tasks – is one of the core components that are surely responsible of this success. Unfortunately, ensuring bound-consistency for the cumulative constraint is already NP-Hard. Therefore, several relaxations were proposed to reduce domains in polynomial time such as Time-Tabling, Edge-Finding, Energetic Reasoning, and Not-First-Not-Last. Recently, Vilim introduced the Time-Table Edge-Finding reasoning which strengthens Edge-Finding by considering the time-table of the resource. We pursue the idea of exploiting the time-table to detect disjunctive pairs of tasks dynamically during the search. This new type of filtering – which we call time-table disjunctive reasoning – is not dominated by existing filtering rules. We propose a simple algorithm that implements this filtering rule with a \(\mathcal {O}(n^2)\) time complexity (where \(n\) is the number of tasks) without relying on complex data structures. Our results on well known benchmarks highlight that using this new algorithm can substantially improve the solving process for some instances and only adds a marginally low computation overhead for the other ones.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aggoun, A., Beldiceanu, N.: Extending chip in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling 17(7), 57–73 (1993)
Baptiste, P., Le Pape, C.: Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. Constraints 5(1–2), 119–139 (2000)
Baptiste, P., Le Pape, C., Nuijten, W.: Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems, vol. 39. Springer (2001)
Beldiceanu, N., Carlsson, M.: A new multi-resource \(cumulatives\) constraint with negative heights. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 63–79. Springer, Heidelberg (2002)
Derrien, A., Petit, T.: A new characterization of relevant intervals for energetic reasoning. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 289–297. Springer, Heidelberg (2014)
Kameugne, R., Fotso, L.P., Scott, J., Ngo-Kateu, Y.: A quadratic edge-finding filtering algorithm for cumulative resource constraints. Constraints 19(3), 243–269 (2014)
Kolisch, R., Schwindt, C., Sprecher, A.: Benchmark instances for project scheduling problems. In: Project Scheduling, pp. 197–212. Springer (1999)
Le Pape, C., Couronné, P., Vergamini, D., Gosselin, V.: Time-Versus-Capacity Compromises in Project Scheduling (1994)
Letort, A., Beldiceanu, N., Carlsson, M.: A scalable sweep algorithm for the cumulative constraint. In: Milano, M. (ed.) Principles and Practice of Constraint Programming. LNCS, pp. 439–454. Springer, Heidelberg (2012)
Lopez, P., Erschler, J., Esquirol, P.: Ordonnancement de tâches sous contraintes: une approche énergétique. Automatique-productique informatique industrielle 26(5–6), 453–481 (1992)
Nuijten, W.P.M.: Time and resource constrained scheduling: a constraint satisfaction approach. PhD thesis, Technische Universiteit Eindhoven (1994)
OscaR Team. OscaR: Scala in OR (2012). https://bitbucket.org/oscarlib/oscar
Ouellet, P., Quimper, C.-G.: Time-table extended-edge-finding for the cumulative constraint. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 562–577. Springer, Heidelberg (2013)
Schutt, A., Wolf, A.: A new O\((n^{2}\) log \(n\)) not-first/not-last pruning algorithm for cumulative resource constraints. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 445–459. Springer, Heidelberg (2010)
Vilím, P.: Edge finding filtering algorithm for discrete cumulative resources in O(kn log n). In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 802–816. Springer, Heidelberg (2009)
Vilím, P.: Timetable edge finding filtering algorithm for discrete cumulative resources. In: Achterberg, T., Beck, J.C. (eds.) CPAIOR 2011. LNCS, vol. 6697, pp. 230–245. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Gay, S., Hartert, R., Schaus, P. (2015). Time-Table Disjunctive Reasoning for the Cumulative Constraint. In: Michel, L. (eds) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015. Lecture Notes in Computer Science(), vol 9075. Springer, Cham. https://doi.org/10.1007/978-3-319-18008-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-18008-3_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18007-6
Online ISBN: 978-3-319-18008-3
eBook Packages: Computer ScienceComputer Science (R0)