Introduction
In industrial scheduling, disjunctive resources—machines or workers capable of handling only one task at a time—are a fundamental constraint. Constraint Programming (CP) solvers manage these resources using filtering algorithms that prune the search space by identifying impossible start times based on earliest start times ($est$), latest completion times ($lct$), and task durations ($p$). Historically, state-of-the-art filters like the "overload check" or "detectable precedences" have relied on balanced tree structures (specifically $\Theta$-trees), resulting in $O(n \log n)$ complexity. This paper introduces a novel "Time Line" data structure that enables these filters to achieve linear time complexity ($O(n)$), significantly improving solver scalability.
The Time Line Data Structure
The core innovation of this work is the replacement of logarithmic-time balanced trees with a structure based on Union-Find. While $\Theta$-trees allow for both task insertion and removal in $O(\log n)$ time, the authors observed that many scheduling filters do not require the removal operation. By sacrificing this flexibility, they developed the Time Line, which uses Union-Find to "fill" time intervals and "skip" over contiguous blocks of occupied time in nearly constant time. This turns potentially expensive searches for available slots into a series of $O(1)$ jumps.
Linear-Time Filtering Suite
The authors developed three primary algorithms utilizing the Time Line structure:
- Time-Tabling: This filter identifies "compulsory parts"—intervals where a task must execute regardless of its exact start time. The linear-time version uses Union-Find to glue these intervals together, facilitating rapid identification of available slots for other tasks.
- Overload Check: This determines if a set of tasks is physically impossible to complete before a collective deadline. The Time Line allows the algorithm to greedily schedule tasks and detect deadline violations in $O(n)$.
- Detectable Precedences: This rule discovers if one task must precede another. The authors' version handles "blocking tasks" by postponing filtering until the blocking task is processed, avoiding the need for complex tree deletions.
Experimental Evaluation
The algorithms were evaluated using Taillard’s Benchmarks and large-scale random instances with up to 100 tasks. The results confirm that the theoretical $O(n)$ complexity translates to significant practical speedups over the $O(n \log n)$ state-of-the-art.
As shown in the performance data, the Time Line-based approach consistently outperforms $\Theta$-tree implementations across all tested filters. The performance gap widens as the number of tasks ($n$) increases, validating the scalability of the linear-time approach. In job-shop and open-shop scheduling tests, the new algorithms allowed solvers to explore search trees much faster, with some configurations showing a 2x speedup in execution time.
Conclusion
By trading the flexibility of task removal for the efficiency of Union-Find, this research achieves a significant milestone in scheduling optimization. While the current Time Line structure does not yet support edge-finding algorithms—which require task removal—it provides a robust foundation for faster CP solvers. Future work will focus on adapting these linear-time techniques to more complex constraints, such as those involving optional tasks.
Summary updated