|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 consists in using depth-first backtrack search. Our earlier work focused on developing efficient consistency enforcing techniques and efficient variable/value ordering heuristics to 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 From Failure dynamically modifies the order in which variables are instantiated based on earlier conflicts, and (3) Heuristic Backjumping gives up searching areas of the search space that appear too difficult. These schemes are shown to (1) further reduce the average complexity of the search procedure, (2) enable our system to efficiently solve problems that could not be solved otherwise due to excessive computational cost, and (3) be more effective at solving job shop scheduling problems than other look-back schemes advocated in the literature.
Sponsor: DARPA, McDonnell Aircraft Co., Digital Equipment Corp.
Grant ID: F30602-88-C-0001
|Norman Sadeh-Koniecpol, Katia Sycara, and Yalin Xiong, "Backtracking Techniques for Hard Scheduling Problems," tech. report CMU-RI-TR-93-08 (CMU-RI-TR-92-06), Robotics Institute, Carnegie Mellon University, 1993|
author = "Norman Sadeh-Koniecpol and Katia Sycara and Yalin Xiong",
title = "Backtracking Techniques for Hard Scheduling Problems",
booktitle = "",
institution = "Robotics Institute",
year = "1993",
number= "CMU-RI-TR-93-08 (CMU-RI-TR-92-06)",
address= "Pittsburgh, PA",
|The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.|
Contact Us | Update Instructions