This dissertation address dynamic deterministic job shop scheduling, a problem that occurs in many manufacturing environments. The problem is among the most difficult scheduling problems, and few solution procedures have been implemented. The approach in this research is to consider specific subproblems that are motivated by semiconductor test operations and to develop genetic algorithms that exploit alternative search spaces.
The research includes new analytical and empirical results for previously unstudied one-machine class scheduling and three-machine look-ahead problems. The one-machine problems include sequence-dependent setup times. In the three-machine problems, two groups of jobs are processed on separate second-stage machines. Testing shows that a new type of genetic algorithm can find good schedules for the one-machine problems by adjusting the problem data while using an appropriate heuristic. An approximation algorithm for the three-machine problem is able to find near-optimal schedules.
Moreover, this dissertation describes the development and application of a global job shop scheduling system for the semiconductor test area. This system uses a detailed deterministic simulation model of the shop floor, data about the current status of the shop, and a genetic algorithm to search over combinations of dispatching rules in order to create a good shift schedule. These rules include those motivated by the research into the one-machine and three-machine problems. The scheduling system is able to adapt to changing conditions each shift.
The benefits of this work consist of the identification of dominance properties for the one-machine class scheduling and three-machine look-ahead problems, the development of a problem space genetic algorithm, the definition of new look-ahead heuristics, the creation of a new genetic algorithm for global scheduling, and the implementation of these results to the actual semiconductor test floor that is the motivation for this work.
For further information, please contact Jeffrey W. Herrmann at jwh2@eng.umd.edu.