Generalizing the Edge-Finder Rule for the Cumulative Constraint

Vincent Gingras, Claude-Guy QuimperIJCAI 2016

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.

Illustration of the cumulative constraint and the profile-based calculation of earliest completion times.

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:

  1. Overload Check: Detects if a set of tasks is impossible to complete within a given deadline.
  2. 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.

Comparison of FE vs HE runtime (s) using the DomOverWDeg heuristic. Points above the diagonal indicate instances where the HE relaxation is faster.

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

BibTeX
@inproceedings{gingras2016generalizing,
  author = {Vincent Gingras and Claude-Guy Quimper},
  title = {{Generalizing the Edge-Finder Rule for the Cumulative Constraint}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure