Implementing Cumulative Functions with Generalized Cumulative Constraints
This work addresses a gap in open-source constraint programming solvers for modeling producer and consumer scheduling problems, though it appears incremental as it implements an existing paradigm from commercial solvers.
The authors tackled the problem of implementing cumulative functions with conditional time intervals for scheduling problems, which was previously unavailable in open-source solvers, by developing a Generalized Cumulative constraint and a novel time-table filtering algorithm. Their approach performs competitively with existing solvers and scales effectively to large problems.
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 time-table filtering algorithm 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 problems.