Implementing Cumulative Functions with Generalized Cumulative Constraints
Organizations: UCLouvain, ICTEAM, Louvain-la-Neuve, Belgium · University of Maroua, Maroua, Cameroon
Abstract
Modeling scheduling problems with conditional time intervals and cumulative functions has become a common approach when using modern commercial constraint programming solvers. This paradigm enables the modeling of a wide range of scheduling problems, including those involving producers and consumers. However, it is unavailable in existing open-source solvers and practical implementation details remain undocumented. In this work, we present an implementation of this modeling approach using a single, generic global constraint called the Generalized Cumulative. We also introduce a novel timetabling filtering algorithm specifically designed to handle tasks defined on conditional time-intervals. Experimental results demonstrate that this approach, combined with the new filtering algorithm, performs competitively with existing solvers enabling the modeling of producer and consumer scheduling problems and effectively scales to large-scale problems.
Figures & tables
| time | event(s) | |||
|---|---|---|---|---|
| 0 | 0 | 2 | 0 | |
| 1 | 1 | 2 | 1 | |
| 2 | 1 | 4 | 1 | |
| 3 | -2 | 5 | 0 | |
| 4 | 0 | 3 | 1 | |
| 5 | -2 | 3 | 0 |
| Feature / Aspect | Beldiceanu and Carlsson (2002) | This Work |
|---|---|---|
| Data structure | Event array sweep | Doubly-linked Profile with boundary pointers |
| Backward adjustment | Single adjustment per propagation call | Chained adjustments in a single pass (Ex. 1 ) |
| Consumption pruning | Restricted to single-event span | Minimum overlapping interval (Ex. 2 ) |
| Duration pruning | Measured from single conflicting point | Longest conflict-free sub-interval (Ex. 3 ) |
| Optional tasks | Indirect via dummy resource | Native conditional intervals with direct presence pruning |