Minimizing Makespan on a Single Burn-in Oven in Semiconductor Manufacturing

Abstract

This paper considers a scheduling problem for a single burn-in oven in semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. The objective measure of the problem is the maximum completion time (makespan) of all jobs. This paper investigates a static case in which all jobs are available to process at time zero, and also analyzes a dynamic case with different job-release times, for which a branch-and-bound algorithm and several heuristics are exploited. The worst case error performance ratios of the heuristics are also derived. (C) 2000 Elsevier Science B.V. All rights reserved.