In industrial sequencing and economic modeling, the Cumulative Scheduling Problem (CuSP) is a fundamental challenge. It involves scheduling multiple tasks on a resource with a fixed capacity (e.g., power or floor space), where each task consumes a specific "height" of that resource. Finding an optimal schedule is NP-Hard, requiring constraint solvers to use filtering algorithms to prune impossible branches of the search tree early.
Traditionally, these algorithms rely on a "fully-elastic" (FE) relaxation. This model simplifies tasks by assuming they can be reshaped into any configuration as long as their total energy (height $\times$ time) is preserved. However, this relaxation is often too loose, allowing "impossible" task shapes that ignore individual height limits and leading solvers to waste time exploring dead ends.
The Horizontally-Elastic Relaxation
Presented at IJCAI 2016, this research introduces a more powerful horizontally-elastic (HE) relaxation. Unlike the FE model, the HE relaxation enforces that a task $i$ can never consume more than its original height $h_i$ at any given moment. While it still allows tasks to be interrupted or fluctuate in height (between 0 and $h_i$), it prevents them from "stacking" their own energy vertically beyond their physical capacity.
By capping the height of each task in the relaxation, the authors obtain a much tighter estimate of the earliest completion time ($ect$) for a group of tasks. To make this computationally feasible, they introduced a Profile data structure that tracks resource utilization over time as a series of rectangles, allowing $ect$ calculations in $O(n)$ time.
Generalized Filtering Rules
The authors redefined two critical filtering rules using this tighter HE relaxation:
- Overload Check: Detects if a set of tasks is impossible to complete within a given deadline.
- Edge-Finder: Determines if a specific task must finish after a set of other tasks.
Mathematically, the paper proves that these new HE-based rules dominate traditional FE rules. Any inconsistency detected by the old rules will be caught by the new ones, but the HE rules will also identify many impossible schedules that the FE rules miss.
Experimental Results
The algorithms were evaluated using the Choco 2 solver on standard Resource-Constrained Project Scheduling Problem (RCPSP) benchmarks, including the highly cumulative BL benchmarks and the PSPLib library.
The results demonstrated significant performance gains:
- Speedups: On BL benchmarks, the HE method achieved run-time reductions of 63% to 85% depending on the search heuristic.
- Search Efficiency: The number of backtracks (failed scheduling attempts) was significantly lower, confirming that the tighter relaxation prunes the search space more effectively.
- Broad Applicability: Even on the easier PSPLib benchmarks, the HE method provided speedups in 75% of the instances.
Conclusion
By moving from a fully-elastic to a horizontally-elastic relaxation, this work provides a more realistic and powerful tool for cumulative scheduling. While the improvements are most dramatic for highly cumulative problems where resource height is a major bottleneck, the efficiency of the Profile data structure ensures that the added pruning power does not come at a prohibitive computational cost. Future work may involve extending this relaxation to other scheduling constraints, such as Not-First/Not-Last rules.
Summary updated