zbMATH — the first resource for mathematics

Time-table disjunctive reasoning for the cumulative constraint. (English) Zbl 1459.90093
Michel, Laurent (ed.), Integration of AI and OR techniques in constraint programming. 12th international conference, CPAIOR 2015, Barcelona, Spain, May 18–22, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9075, 157-172 (2015).
Summary: 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.
For the entire collection see [Zbl 1337.68015].

90B35 Deterministic scheduling theory in operations research
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W40 Analysis of algorithms
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI