Abstract
This paper demonstrates that complex job shop scheduling problems can be solved more efficiently by focusing on the ordering of operations rather than their specific start times. By utilizing local measures of "temporal slack" to guide search decisions, the authors achieve performance comparable to state-of-the-art global contention models at a fraction of the computational cost.
Introduction
The Job Shop Scheduling Problem (JSSP) with non-relaxable time windows is a classic challenge in combinatorial optimization. Traditionally, researchers have treated this as a "start-time assignment" problem, which often results in brittle solutions and massive search spaces. While previous high-performing solutions relied on "contention-based" metrics—requiring complex probabilistic profiles of resource demand—this paper proposes a simpler approach using local temporal information.
The Precedence Constraint Posting (PCP) Framework
The core of the proposed method is the Precedence Constraint Posting (PCP) framework. Instead of assigning exact clock times, the algorithm sequences pairs of operations competing for the same machine.
The framework consists of several key components:
- Constraint-Based Analysis (CBA): A pruning technique that uses dominance conditions to automatically post "must-precede" constraints, narrowing the search space.
- Min-Slack (Variable Ordering): To decide which pair of operations to sequence next, the algorithm identifies the "most critical" decision—the pair with the minimum temporal slack.
- Max-Slack (Value Ordering): Once a pair is chosen, the algorithm selects the ordering ($i \to j$ or $j \to i$) that leaves the most remaining slack, preserving flexibility for future decisions.
As illustrated in Figure 2, slack represents the remaining window of time available for an operation after its predecessor is scheduled. By prioritizing the most constrained decisions (Min-Slack) and choosing the most liberating outcomes (Max-Slack), the algorithm effectively avoids dead ends in the search tree.
Experimental Results
The authors evaluated their heuristics using a standard suite of 60 benchmark problems involving 10 jobs and 5 resources. These problems were categorized by deadline tightness and the presence of bottleneck resources.
The results were compelling:
- Success Rate: While the basic Min-Slack heuristic solved 56 out of 60 problems, a refined "Biased Slack" heuristic achieved a 100% success rate (60/60).
- Efficiency: The PCP approach was significantly faster than contemporary methods, averaging 0.2 to 0.3 seconds per problem. In contrast, contention-based methods like ORR/FSS and CPS required more computational resources to achieve similar results.
- Robustness: The heuristics performed remarkably well even on "tight" deadline problems that typically cause priority-rule-based dispatchers to fail.
Conclusion
The primary insight of this work is that the search space of operation orderings is often more manageable than the space of fixed start times. Local slack metrics provide sufficient "look-ahead" to navigate the search space effectively without the need for expensive global calculations. Future research will focus on adapting the PCP approach for optimization objectives, such as minimizing weighted tardiness, by replacing slack-based metrics with cost-based heuristics.
Summary updated