Generating Feasible Schedules under Complex Metric Constraints

Cheng-Chung Cheng, Stephen F. SmithAAAI 1994

Introduction

The Job Shop Scheduling Problem (JSSP) is a fundamental challenge in manufacturing and operations research. While traditional models focus on simple precedence constraints, real-world scenarios often involve complex metric separation constraints—minimum and maximum time intervals between tasks. This paper introduces SP-PCP (Shortest Path Precedence Constraint Posting), an algorithm designed to navigate these intricate timing requirements by leveraging shortest-path information within a temporal constraint network.

Methodology: Temporal Constraint Networks

The authors model the scheduling problem as a General Temporal Constraint Network (GTCN). In this framework, nodes represent the start and end times of operations, while edges define the allowed temporal intervals between them. This global view is essential because local "slack" measures often fail to account for the ripple effects of interdependent timing intervals.

A General Temporal Constraint Network (GTCN) representation of two jobs with metric separation constraints.

The SP-PCP algorithm enhances traditional scheduling in two primary ways:

  1. Dominance Conditions: By calculating shortest paths (using the Floyd-Warshall algorithm), the system can identify "forced" sequencing decisions. If one operation must precede another to prevent an impossible timeline (a negative cycle), the algorithm commits to that order immediately, significantly pruning the search space.
  2. Biased Shortest-Path Heuristic: Rather than relying on simple slack, SP-PCP uses a biased shortest-path metric to estimate sequencing flexibility. It prioritizes the "most constrained" pairs—those with the least amount of "wiggle room" in the temporal network—to ensure that critical decisions are made before the search space becomes overly restricted.

Experimental Evaluation

The algorithm was tested against a suite of 250 randomly generated scheduling problems, ranging from 30 to 100 operations. These problems featured five resources, variable task durations, and mandatory separation intervals. SP-PCP was compared against traditional chronological backtracking (CB) and the original slack-based PCP algorithm.

Results and Discussion

The experimental results highlight a dramatic improvement in both robustness and efficiency. As problem complexity increased, traditional methods like slack-based PCP and basic backtracking failed to find solutions for larger instances.

Performance comparison showing the number of problems solved by various algorithms as the number of operations increases.

Key findings include:

  • Scalability: On the largest 100-operation problems, the original PCP solved zero instances, whereas SP-PCP (integrated with backtracking) solved 46 out of 50.
  • Efficiency: SP-PCP proved remarkably fast, typically finding feasible schedules for 100-operation problems in under 10 seconds. This is a massive performance boost over traditional methods that find such problems impossible.
  • Global Perspective: The success of SP-PCP demonstrates that shortest-path distances serve as superior proxies for flexibility compared to local slack measures, which are easily "fooled" by complex constraints.

Conclusion

SP-PCP represents a significant advancement in solving scheduling problems with complex metric constraints. By shifting from local heuristics to global temporal reasoning, the algorithm enables the efficient generation of feasible schedules in environments that were previously computationally intractable. While the current focus is on feasibility, future work may explore extending this framework to optimization goals, such as minimizing total makespan.

Summary updated

BibTeX
@inproceedings{cheng1994generating,
  author = {Cheng-Chung Cheng and Stephen F. Smith},
  title = {{Generating Feasible Schedules under Complex Metric Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure