Minimizing Total Weighted Tardiness on Parallel Batch Process Machines Using Genetic Algorithms
Recently, the electronics industry has become the largest industry in the world. A key aspect of this industry is the manufacturing of integrated circuits. In the past, sources of reducing costs were decreasing the size of the chips, increasing the wafer
- PDF / 1,288,748 Bytes
- 6 Pages / 439 x 666 pts Page_size
- 73 Downloads / 195 Views
1
Introduction
Recently, the electron ics industry has become the largest industry in the world. A key aspect of this industry is the manufacturing of integrated circuits. In the past, sources of reducing costs were decreasing the size of the chips, increasing the wafer sizes and improving the yield, simultaneously with efforts to improve operational processes inside the wafer fabrication facilities (wafer fab). Currently, it seems that the improvement of operational processes creates the best opportunity to realize the necessary cost reductions [6]. This research is motivated by a scheduling problem found in the area of diffusion in a wafer fab. In the diffusion area, there are several diffusion furnaces which can be operated in parallel and can process several jobs simultaneously. However, due to the different chemical nature of the processes, only jobs of the same job family can be processed together. Carefully choosing which products to batch together and which order these jobs should be sequenced is of high importance as the process ing times in the diffusion furnaces can take up to 10 hours, versus a 1 hour processing time in other wafer fab processes . Therefore, a proper scheduling of the machines dedicated to the diffusion process steps has a great impact on the performance of the entire wafer fab. Given that many wafer fabs are driven by on-time delivery, the performance measure of interest is the total weighted tardiness . This performance measure is given as
LW ij Tij , where we
denote by w ij the weight or priority for the job j of family i . The tardiness of job j offamily i is given by Tij := max(c j -dij'O), where we denote by Cjj the completion time for job j of family i in the schedule and d ij represents the due date for job j of family i . In this paper, we extend previous research on single batch process machines [2,3,4] to the more general case of parallel machines . We use a genetic algorithm in order to assign batches to the parallel machines. We reduce the problem to single machine sequencing problems after performing this decomposition step. For * To whom correspondence should be addressed.
U. Leopold-Wildburger et al. (eds.), Operations Research Proceedings 2002 © Springer-Verlag Berlin Heidelberg 2003
230 the efficient solution of the single machine problems we use the same techniques as suggested in [2,4], The paper is organized as follows. In the next section, we describe the problem under consideration in detail. Then we describe a four-phase-scheduling algorithm for obtaining the solution of the problem. We present results of computational experiments in the last section of this paper.
2
Problem Description
By Pinedo (2002), scheduling problems can be represented in the form
a I ~ I 'Y.
The a field describes the machine environment (single machine, parallel machine , job shop, etc.), the ~ field describes the process characteristics , restrictions, constraints (such as release dates, batch, set up dependent operations), and the 'Y field contains the information on the per
Data Loading...
