Abstract
In automated scheduling, the CUMULATIVE constraint ensures resource demands stay within fixed limits. However, real-world scenarios often require flexibility, allowing for overloads at a cost. This paper introduces a novel approach to the SOFTCUMULATIVE constraint that supports both linear and quadratic penalty functions. By utilizing energetic reasoning and lazy clause generation (LCG), the authors develop efficient checker and filtering algorithms. Experimental results on Resource Constrained Project Scheduling Problem (RCPSP) benchmarks demonstrate that this global constraint significantly outperforms traditional decomposition methods, offering substantial speedups and solving complex instances to optimality where previous methods failed.
Introduction
In Constraint Programming, the CUMULATIVE constraint is a fundamental tool for managing resource allocation. It ensures that the total resource demand of active tasks does not exceed a fixed capacity. However, rigid constraints often fail to capture the nuances of real-world scheduling, where paying for overtime or additional resources might be preferable to missing a deadline.
This paper explores "soft" versions of the CUMULATIVE constraint. While linear penalties (where cost is proportional to overload) are common, the authors focus on the more realistic scenario of quadratic penalties. Quadratic models naturally encourage "load smoothing," as a single large overload becomes significantly more expensive than several smaller ones spread over time. Prior to this work, efficient global constraints for such load-balancing logic were lacking.
Methodology
The authors base their solution on Energetic Reasoning, a powerful scheduling rule. To maintain efficiency, they focus on a linear-sized subset of "critical time points" rather than checking every possible interval, which would be computationally prohibitive ($O(n^4)$). The approach involves three primary components:
- Overcost Calculation: The algorithm determines the "minimum intersection" of tasks within specific time intervals. If the required energy exceeds capacity, an overcost is calculated based on the penalty function ($f(x) = x$ or $f(x) = x^2$).
- The Checker: To find the total penalty, the problem is modeled as a directed acyclic graph (DAG) where nodes represent time points and edges represent the overcost of intervals. Finding the longest path in this graph provides the maximum possible lower bound on the total penalty.
- Filtering and Lazy Clause Generation (LCG): The filtering algorithm prunes the search space by identifying task start times that would inevitably exceed the allowed budget. By integrating LCG, the solver generates logical "explanations" for these failures, allowing a SAT solver to avoid repeating unsuccessful search paths.
Experimental Evaluation
The researchers evaluated their approach using an adapted version of the KSD15_D benchmark for Resource Constrained Project Scheduling (RCPSP). To simulate the need for soft constraints, resource capacities were reduced by four units and project deadlines were fixed to the original optimal times, forcing the solver to find the most cost-effective way to exceed capacity.
Results and Discussion
The experimental results highlight the superiority of the dedicated global constraint over traditional decomposition methods.
Key findings include:
- Significant Speedups: For linear penalties, the new filtering algorithm was more than 10 times faster than decomposition in 68% of instances. In the quadratic case, it remained 10x faster in 60% of cases.
- Improved Optimality: Many instances that the decomposition method failed to solve within a 20-minute timeout were solved to optimality by the
SOFTCUMULATIVEconstraint in just a few seconds. - Load Smoothing: The move to quadratic penalties successfully pushed the solver toward more balanced resource usage, preferring distributed overloads over concentrated ones.
Conclusion
This work demonstrates that a global SOFTCUMULATIVE constraint using energetic reasoning and LCG is highly effective for scheduling problems with resource overloads. While the current energetic reasoning assumes task preemption—potentially leading to slightly weaker filtering in non-preemptive scenarios—the performance gains are substantial. Future research may extend these methods to more complex cost functions and further optimize the algorithms for large-scale industrial applications.
Summary updated