Beyond Contention: Extending Texture-Based Scheduling Heuristics

AAAI 1997

TL;DR

This paper introduces new methods for estimating the "probability of breakage" for scheduling constraints, moving beyond traditional "contention" measures. These new heuristics, particularly VarHeight and TriangleHeight, prove competitive with existing methods on job shop scheduling problems and offer a more extensible framework for tackling complex real-world scheduling challenges.

What Problem Does This Paper Address?

Scheduling complex real-world problems, like those found in manufacturing, often involves more than just simple resource contention. Constraints can include cumulative resources, alternative resources, and inventory capacities. Existing heuristic scheduling techniques, particularly those based on "texture measurements" (which analyze the structure of the constraint graph), often struggle to extend beyond basic resource contention. The core challenge is to find a unified way to measure the "criticality" of different types of constraints so that a heuristic can effectively prioritize which constraint to address next in a search. The authors aim to bridge this gap by recasting constraint criticality in terms of probability theory.

Methods

The paper builds upon the concept of "texture measurements" for scheduling heuristics. Instead of just measuring contention (how much activities compete for a resource), they propose estimating the probability that a constraint will be broken. They introduce three new techniques for this estimation, all based on analyzing the "demand" of activities for resources over time:

  • SumHeight: This method aggregates individual activity "demand curves" for a resource to estimate overall contention. It uses an event-based representation for efficiency.
  • JointHeight: This technique directly estimates the probability of breakage for a unary resource constraint by considering pairs of activities that might conflict. It relies on multiplying individual activity demands, but has a higher time complexity and is less easily extensible to complex constraints.
  • TriangleHeight: This method estimates breakage probability by assuming a triangular distribution around the expected demand. It's noted for its extensibility to non-unary capacity resources and inventory constraints.
  • VarHeight: Similar to TriangleHeight, but uses variance in addition to expected value to estimate the distribution. It also offers good extensibility but relies on some "egregious assumptions" about independence and normality.

These criticality estimates are then used within a heuristic search framework. The heuristic identifies the most critical constraint and time point, selects two conflicting activities, and then uses one of three sequencing heuristics (MinimizeMax, Centroid, Random) to decide their order.

Datasets

The paper uses two main sources for evaluation:

  • Job shop scheduling problems from the Operations Research library: A set of 21 benchmark problems.
  • Taillard's generator of job shop scheduling problems: Used to create larger problem sets of varying sizes (10x10 to 20x20) to test scalability and performance across different difficulty levels.

Key Insights and Ideas

  • Probability as a Unifying Measure: Framing constraint criticality as "probability of breakage" offers a more general and mathematically grounded approach than simple contention, allowing for comparisons across diverse constraint types.
  • Extensibility is Key: VarHeight and TriangleHeight stand out for their potential to be adapted to more complex scheduling scenarios like inventory management, which is crucial for real-world applicability.
  • Texture Heuristics Identify Critical Decisions: The experiments suggest that texture-based heuristics are better at identifying the truly critical decisions in a search state, leading to better solutions. This is supported by a higher ratio of "implied commitments" (from propagators) to "heuristic commitments."
  • Backtracking Matters: The choice of backtracking strategy (chronological vs. Limited Discrepancy Search - LDS) significantly impacts performance, with LDS generally yielding better results for most heuristics.

Key Results

  • Competitive Performance: The proposed heuristics (VarHeight, SumHeight, TriangleHeight, JointHeight) perform competitively with, and in some cases outperform, existing heuristics like CBASlack on job shop scheduling problems.
  • VarHeight Outperforms: VarHeight, in particular, showed strong performance, solving more problems and achieving better schedule quality than other heuristics when using chronological backtracking.
  • LDS Benefits: Using LDS generally led to better schedule quality across most heuristics, though it required more heuristic commitments.
  • Commitment Ratio: Texture-based heuristics consistently showed a higher ratio of implied to heuristic commitments, supporting the idea that they are better at identifying critical constraints.

Limitations and Future Work

  • Assumptions in VarHeight/TriangleHeight: The authors acknowledge that VarHeight relies on "egregious assumptions" about independence and normality, which may limit its theoretical purity but still yields practical benefits. TriangleHeight's assumption of a triangular distribution is also noted as lacking strong justification.
  • JointHeight Complexity: JointHeight's high time complexity and limited extensibility are noted as drawbacks.
  • Further Investigation Needed: The authors express curiosity about the performance of JointHeight and plan further investigation.
  • Extending to More Constraints: The paper outlines future work in extending these methods to more complex constraints like full inventory problems (with varying rates), scheduling with changeovers, and options for production/consumption.
  • Dynamic Programming for Inventory: While exponential in the worst case, a dynamic programming formulation for inventory constraints shows promise for average-case performance.

Summary updated

BibTeX
@inproceedings{1997beyond,
  title = {{Beyond Contention: Extending Texture-Based Scheduling Heuristics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1997},
}

Loading related content...

Figure