Algorithms and Heuristics for Scheduling Semiconductor Burn-in Operations



Abstract

This paper addresses a problem of batch scheduling which arises in the burn-in stage of semiconductor manufacturing. Burn-in ovens are modeled as batch-processing machines which can handle up to B jobs simultaneously. The processing time of a batch is equal to the longest processing time among the jobs in the batch. The scheduling problem involves assigning jobs to batches and determining the batch sequence so as to minimize the total flowtime. In practice, there is a small number m of distinct job types.
Previously, the only solution techniques known for the single-machine version of this problem were an O(m^3 B^m^+^1) pseudo-polynomial algorithm, and a branch-and-bound procedure. We present an algorithm with a running time of O(m^23^m), which is independent of B, the maximum batch size. We also present a polynomial heuristic for the general problem (when m is not fixed), which is a 2-approximation algorithm. For any problem instance, this heuristic provides a solution at least as good as that given by previously known heuristics. Finally, we address the m-type problem on parallel machines, providing an exact pseudo-polynomial algorithm and a polynomial approximation algorithm with a performance guarantee of (1 + 2^0.5)/2.

Download Information

Click on the following title to view and download the paper in PostScript format.

Algorithms and Heuristics for Scheduling Semiconductor Burn-in Operations (35 pages, 180 KB)
Dorit S. Hochbaum and D. Landy. Operations Research, 45:6, 874-885, (1997).
dorit@hochbaum.ieor.berkeley.edu
7/28/98