Simple CP for Complex JSP: Trading Inference for Adaptive Search

TL;DR

In the world of Job Shop Scheduling (JSP), the prevailing wisdom often dictates using heavy-duty global constraints and domain-specific propagators. This paper by Grimes and Hebrard flips the script. By using a minimalist "naive" model combined with powerful generic search heuristics—specifically weighted degree and geometric restarts—they managed to outperform complex state-of-the-art methods on sequence-dependent setup times and maximum time-lag variants, even proving optimality for long-standing open problems.

Background: The Limits of Specialized Inference

Standard JSP is hard enough, but industrial reality adds layers like setup times (where a machine needs cleaning/tuning between different tasks) and time-lags (where a task must start shortly after another, common in chemical or steel processing).

The traditional CP approach relies on "Edge-finding" algorithms. However, these are specialized: adding setup times or maximum lags often breaks the mathematical assumptions of these global constraints. This forces researchers to decompose the problem into sub-problems (like TSP), which leads to a "modeling debt" where the system becomes too rigid to handle varied constraints efficiently.

Methodology: The Power of Minimalism

The authors' approach is elegantly simple. Instead of treating a machine as a complex global resource, they decompose it into a set of primitive disjunctive constraints. For every pair of tasks sharing a machine, a Boolean variable $b_{ij}$ decides which comes first.

The Core Strategy: Weighted Degree Heuristic

The "secret sauce" isn't in the propagation, but in the variable selection. They use the tdom/wdeg (Task Domain / Weighted Degree) heuristic.

1. Weighting: Every time a constraint causes a failure (conflict) during search, its weight is incremented.
2. Bottleneck Discovery: As search progresses, the "hardest" constraints naturally accumulate weight. The heuristic directs the solver to resolve these bottlenecks first.
3. Solution Guidance: They maintain an "elite set" of previous best solutions to guide value selection, ensuring the search stays in high-quality regions of the search space.

The model uses simple Booleans to represent relative ordering, which allows for constant-time bounds consistency (BC) propagation.

Experiments: Breaking New Ground

The authors tested their approach on two major variants:

1. SDST-JSP (Setup Times): Competitive with specialized Metaheuristics (GA/Tabu Search), providing the first optimality proofs for instances like t2-ps09.
2. JTL-JSP (Time Lags): Significantly more efficient than previous Genetic Algorithms. In the "No-Wait" variant (lag = 0), they further optimized the model by collapsing job tasks into single "blocks," drastically reducing the variable count.

Table 1 highlights several new upper bounds () and proofs of optimality (underlined) achieved by the simple CP model.*

A Surprising Insight: When Weights Fail

One of the paper's most fascinating contributions is the Weight Learning Analysis. The authors used the Gini Coefficient (a measure of inequality typically used in economics) to analyze how "concentrated" the constraint weights were.

They discovered a paradox: while weighting is vital for SDST-JSP, it can actually be detrimental for No-Wait JSP. In no-wait scenarios, the functional dependencies between tasks are so strong that the search space is highly structured; here, the weights can sometimes "distract" the solver from the natural structural flow of the problem.

The Gini analysis (Fig 1) shows how quickly search focuses on a small subset of "bottleneck" variables in different problem types.

Conclusion & Takeaways

The success of this "minimalist" approach suggests a paradigm shift in combinatorial optimization:

• Search over Inference: In complex variants, fast, adaptive search beats localized, complex propagation.
• Adaptive Learning: Heuristics that learn from failure (like weighted degree) are essential for industrial problems where the "bottlenecks" aren't obvious from the start.
• Model Flexibility: Because the model is made of simple components, it can be extended to handle setup times or time-lags with just a few lines of modification to the basic disjunctive logic.

For practitioners, this is a call to focus more on adaptive search strategies and less on handcrafted algorithmic shortcuts.