The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

This paper studies a version of the job shop scheduling problem in which some operations have to be scheduled within non-relaxable time windows (i.e. earliest/latest possible start time windows). This problem is a well-known NP-complete Constraint Satisfaction Problem (CSP). A popular method for solving this type of problems involves using depth-first backtrack search. In our earlier work, we focused on the development of consistency enforcing techniques and variable/value ordering heuristics that improve the efficiency of this search procedure. In this paper, we combine these techniques with new look-back schemes that help the search procedure recover from so-called deadend search states (i.e. partial solutions that cannot be completed without violating some constraints). More specifically, we successively describe three "intelligent" backtracking schemes: (1) Dynamic Consistency Enforcement dynamically identifies critical subproblems and determines how far to backtrack by selectively enforcing higher levels of consistency among variables participating in these critical subproblems, (2) Learning Ordering From Failure dynamically modifies the order in which variables are instantiated based on earlier conflicts, and (3) Incomplete Backjumping Heuristic abandons areas of the search space that appear to require excessive computational efforts. These schemes are shown to (1) further reduce the average complexity of the backtrack search procedure, (2) enable our system to efficiently solve problems that could not be solved otherwise due to excessive computation cost, and (3) be more effective at solving job shop scheduling problems that other look-back schemes advocated in the literature.

Notes

Sponsor: DARPA

Grant ID: #F30602-91-F-0016

Number of pages: 26

Text Reference

Norman Sadeh-Koniecpol, Katia Sycara, and Yalin Xiong, "Backtracking Techniques for the Job Shop Scheduling Constraint Satisfaction Problem," tech. report CMU-RI-TR-94-31, Robotics Institute, Carnegie Mellon University, October, 1994

BibTeX Reference

@techreport{Sadeh-Koniecpol_1994_350,
   author = "Norman Sadeh-Koniecpol and Katia Sycara and Yalin Xiong",
   title = "Backtracking Techniques for the Job Shop Scheduling Constraint Satisfaction Problem",
   booktitle = "",
   institution = "Robotics Institute",
   month = "October",
   year = "1994",
   number= "CMU-RI-TR-94-31",
   address= "Pittsburgh, PA",
}

The Robotics Institute

Menu