The University of Maryland

Institute for Systems Research

Jeffrey W. Herrmann

An investigation of production scheduling problems motivated by semiconductor manufacturing

An abstract of the dissertation of Jeffrey W. Herrmann. The dissertation was completed in December, 1993, at the University of Florida under the guidance of Chung-Yee Lee. This research was also supported by Harris Semiconductor, Palm Bay, Florida.


Manufacturing and service organizations frequently face the challenge of making high-quality products quickly and of delivering those products to their customers on time. Improvements in the scheduling of their operations can often contribute to their success in meeting these goals. However, as manufacturing processes become more complex, the difficulty of finding good production schedules increases.

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

Author: JWH