A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling

IJCAI 1995

TL;DR

This paper investigates advanced techniques for disjunctive scheduling, a crucial problem in operations research and AI. The authors compare different constraint propagation methods, demonstrating that more sophisticated techniques significantly improve efficiency for complex scheduling problems, often outperforming traditional methods.

What Problem Does This Paper Address?

Disjunctive constraints are fundamental in scheduling to ensure that activities requiring the same resource don't overlap. For example, if two tasks, A and B, need a specific machine, a disjunctive constraint enforces that either A must finish before B starts, or B must finish before A starts. "Constraint propagation" is the process of using these constraints to deduce new information, like tightening the possible start and end times of activities. While basic propagation (arc-B-consistency) is standard, it often isn't powerful enough for complex real-world problems. This paper addresses the need for more effective propagation techniques to prune the search space more aggressively, leading to faster and more efficient scheduling solutions.

Methods

The paper compares three main categories of constraint propagation techniques for disjunctive scheduling:

  • Arc-B-Consistency: This is the standard, basic method. It enforces consistency on the bounds of variables representing start and end times.
  • Edge-Finding: This is a more advanced technique that looks beyond just pairs of activities. It considers an activity's position relative to a set of other activities that share a resource. The paper discusses two main variants:
  • Jackson's Preemptive Schedule (JPS) based: This method uses a preemptive schedule to derive temporal constraints.
  • Direct Edge-Finding: This variant, described by Nuijten et al., is simpler as it doesn't require computing JPS.
  • Energy-Based Reasoning: This approach compares the "resource energy" (amount of work) required over a time interval to the available energy. It can detect conflicts or deduce new bounds by analyzing resource consumption patterns. The paper discusses two implementations:
  • Habograph: A data structure for analyzing energy consumption over time.
  • Energetic Resources: A more abstract representation used in ILOG SCHEDULE, focusing on the amount of work performed over regular intervals.

The authors implement and compare three specific algorithms: ERA (Energetic Reasoning), EFJ (Edge-Finding based on JPS), and EFN (Edge-Finding based on Nuijten et al.).

Datasets

The paper evaluates the proposed techniques on several benchmark problems:

  • Bridge Construction Scheduling Problem: A well-known benchmark in constraint programming.
  • 10x10 Job-Shop Scheduling Problems: Ten instances considered particularly hard to solve to optimality. These are standard benchmarks from the operations research community.
  • Industrial Project Scheduling Problem: A real-world problem involving scheduling two projects with common resources, described as very difficult.

Key Insights and Ideas

  • Beyond Pairs: The most significant insight is that moving beyond pairwise disjunctive constraints (like A before B) to consider an activity's relationship with a set of other activities (edge-finding) or its resource consumption over time (energy-based reasoning) dramatically improves propagation power.
  • Trade-off Between Propagation and Search: While advanced propagation techniques require more computation per step, they drastically reduce the number of search steps (backtracks) needed to find a solution, especially for complex problems. This is a crucial trade-off in constraint programming.
  • "Unique Fixpoint Semantics" is Important: The paper highlights that some techniques, particularly when applied only to specific "task intervals," can break the "unique fixpoint semantics." This means the final solution might depend on the order in which constraints are processed, which can be problematic for users of generic constraint programming tools.
  • Edge-Finding Dominates for Hard Problems: For complex job-shop and industrial scheduling problems, edge-finding techniques (EFJ and EFN) consistently outperform basic arc-B-consistency and even energetic reasoning in terms of both backtracks and CPU time.

Key Results

  • Performance on Job-Shop Problems: For the 10x10 job-shop problems, the edge-finding algorithms (EFJ and EFN) significantly reduced the number of backtracks and CPU time compared to arc-B-consistency, which was often too slow to solve these instances. For example, for the MT10 problem, EFN required 51980 backtracks and 2194 seconds, while ARC was not even tested due to its inefficiency.
  • Industrial Project Scheduling: On a difficult industrial project scheduling problem, edge-finding algorithms (EFJ and EFN) strongly outperformed other methods, achieving solutions within reasonable time limits where others failed.
  • Bridge Construction: For the simpler bridge construction problem, basic arc-B-consistency was surprisingly efficient in terms of CPU time, suggesting that the overhead of more complex propagation might not always be justified for simpler problems.
  • EFN's Edge: The EFN algorithm, based on Nuijten et al.'s method, was found to deduce slightly more information than pure edge-finding, specifically identifying when an activity cannot be the first to execute, which can further prune the search.

Limitations and Future Work

  • "Unique Fixpoint" Issue: The paper notes that some methods, like the task interval rules of Caseau and Laburthe, can break "unique fixpoint semantics," making them potentially less predictable in a generic constraint programming context. This is a limitation for tool developers.
  • Algorithm Complexity: While theoretical complexities are analyzed, the practical performance also depends on factors like the number of iterations to reach a fixpoint and the "pruning power" of the propagation, which are harder to quantify a priori.
  • Future Work: The paper suggests that the implementation of the edge-finding algorithm of Nuijten et al. (EFN) in ILOG SCHEDULE 1.1, along with improved search strategies, is a promising direction. They also mention the need to study a new algorithm by Carlier and Pinson (0(n log n)) in more detail. The experimental results also inform the development of more efficient constraint propagation systems.

Summary updated

BibTeX
@inproceedings{1995theoretical,
  title = {{A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure