Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime

Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime 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(m23Bm+1) pseudopolynomial algorithm, and a branch-and-bound procedure. We present an algorithm with a running time of O(m23m), 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Operations Research INFORMS

Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime

Operations Research , Volume 45 (6): 12 – Dec 1, 1997
12 pages

Loading next page...
 
/lp/informs/scheduling-semiconductor-burn-in-operations-to-minimize-total-flowtime-UZla7DhcBK

References (20)

Publisher
INFORMS
Copyright
Copyright © INFORMS
Subject
Research Article
ISSN
0030-364X
eISSN
1526-5463
DOI
10.1287/opre.45.6.874
Publisher site
See Article on Publisher Site

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(m23Bm+1) pseudopolynomial algorithm, and a branch-and-bound procedure. We present an algorithm with a running time of O(m23m), 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.

Journal

Operations ResearchINFORMS

Published: Dec 1, 1997

Keywords: Keywords : production/scheduling ; applications ; semiconductor burn-in operations ; dynamic programming ; applications ; scheduling semiconductor burn-in operations

There are no references for this article.