Look-Ahead Techniques for Micro-Opportunistic Job Shop Scheduling
Abstract
Scheduling deals with the allocation of resources over time to perform a collection of tasks. Scheduling problems arise in domains as diverse as manufacturing, computer processing, transportation, health care, space exploration, education, etc. Scheduling problems are conveniently formulated as Constraint Satisfaction Problems (CSPs) or Constrained Optimization Problems (COPs). A general paradigm for solving CSPs and COPs relies on the use of backtrack search. Within this paradigm, the scheduling problem is solved through the iterative selection of a subproblem and the tentative assignment of a solution to that subproblem. Because most scheduling problems are NP-complete, even finding a solution that simply satisfies the problem constraints could require exponential time in the worst case. This dissertation demonstrates that the granularity of the subproblems selected by the backtrack search procedure critically affects both the efficiency of the procedure and the quality of the resulting solution. A so-called microopportunistic search procedure is developed, in which subproblems can be as small as a single operation. Look-ahead techniques are presented that constantly track the evolution of so-called bottleneck resources. These look-ahead techniques enable the scheduler to take advantage of the fine granularity of its search procedure by opportunistically revising its scheduling strategy as bottlenecks shift from one part of the problem space to another. More specifically, two variations of the job shop scheduling problem are successively studied: (1) The first variation is one in which operations have to be performed within non-relaxable time windows. Heuristics to guide a micro-opportunistic scheduler are presented that are shown to outperform both generic CSP heuristics as well as specialized heuristics developed for similar scheduling problems; and (2) The second part of this work deals with the factory scheduling problem.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1991
- Accession Number
- ADA596791
Entities
People
- Norman Sadeh
Organizations
- Carnegie Mellon University