Decomposition algorithms for scheduling semiconductor testing facilities

The research described in this paper began in 1988 and is directed at developing effective computerized scheduling procedures for a semiconductor testing facility. To this end we first give a brief overview of the testing process and management goals. We then discuss the performance of a series of different scheduling techniques for this problem, beginning with local dispatching rules that use very limited information through more complex dispatching procedures incorporating local optimization and look-ahead capabilities, culminating in a series of decomposition procedures that take a global view of the test area while making scheduling decisions. Our computational experiments indicate that exploiting the real-time factory status information available in existing factory automation systems can result in significant improvements in shop performance. We conclude the paper with a summary and a discussion of future research directions.