Improved Filtering of Scheduling Problems using Redundant Table Constraints
(2021) Workshop ModRef2021 of CP2021 — Location: Montpellier, France (Online) (25.October.2021)
Files
Improved_Filtering_of_the_Cumulative_constraint_using_Table_Constraint__ModRef21_finalVersion.pdf
Open Access - Adobe PDF
- 443.08 KB
Details
- Authors
- Abstract
- Scheduling problems have been studied for a long time in Constraint Programming (CP). As the constraints used to model such scheduling problems are often NP-hard to filter, various relaxation mech- anisms (typically, to prune time interval variables) have been imagined and still continue to be proposed. An example of such constraint is the cumulative constraint, for which fast and strong filtering algorithms have been conceived during the last two decades, which has permitted to greatly improve constraint-based scheduling solvers [23]. In this paper, we introduce a simple approach to further enhance the filtering process of scheduling problems, in general, by relying on redundant table con- straints. The idea is to compile all solutions of an abstract version of the problem to be solved as a redundant table constraint. To cope with the possibly prohibitive size of the generated table, solutions are collected on task views at a coarser temporal granularity. Another important in- gredient to control the size of the redundant table is to only consider a subset of the tasks, for instance, those that are critical according to a heuristic criterion such as the energy. Interestingly, this approach can be easily integrated in constraint solvers and is totally compatible with any existing filtering technique (propagators of the cumulative constraint, lazy-clause reasoning, . . . ). Our experiments on Resource-Constrained Project Scheduling Problem (RCPSP) show that this simple approach can effectively reduce time solving despite the preprocessing stage needed to build the redundant table constraint.
- Affiliations
Citations
Verhaeghe, H., Kameugne, R., Lecoutre, C., & Schaus, P. (2021). Improved Filtering of Scheduling Problems using Redundant Table Constraints. Workshop ModRef2021 of CP2021, Montpellier, France (Online). https://hdl.handle.net/2078.5/269939