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 result...