Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime

Dorit S. Hochbaum and Dan Landy
Additional contact information
Dorit S. Hochbaum: University of California, Berkeley, California
Dan Landy: University of California, Berkeley, California

Operations Research, 1997, vol. 45, issue 6, 874-885

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 2 3 B m +1 ) pseudopolynomial algorithm, and a branch-and-bound procedure. We present an algorithm with a running time of O ( m 2 3 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 two-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 pseudopolynomial algorithm and a polynomial approximation algorithm with a performance guarantee of (1 + √2)/2.

Keywords: production/scheduling; applications; semiconductor burn-in operations; dynamic programming; applications; scheduling semiconductor burn-in operations (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.6.874 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:6:p:874-885

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().