(475c) A New MILP/Discrete-Event Simulation Algorithm for Scheduling Automated Wet-Etching Stations

The efficient operation of complex semiconductor manufacturing facilities has attracted an increasing research interest in recent years. Industry is currently in a growth expansion, immersed in a series of highly competitive global markets that are characterized for being intensely technological and dynamic. This forces the wafer fabrication facilities to focus their efforts on providing to their customers, high-quality of affordable products with minimum delivery times and lower processing times. As a consequence, the development of efficient short-term scheduling strategies becomes a potential alternative to increase competitiveness, answering agilely to the requirements of highly demanding markets and customers.

The automated wet-etching station (AWS) is a key part of a modern semiconductor production system and has to deal with many complex constraints and limited resources. It consists of a series of chemical and water baths coupled with an automated lot transfer system, in which mixed intermediate storage policies must be strictly followed in order to avoid very expensive wafer contamination. The efficient operation of this stage will offer a substantial reduction of the processing time required to complete all the jobs, providing at the same time a better utilization of the critical transportation resources.

Previous works addressing this problem [1-3] have reported that the complexity lies with the sequencing of the transportation tasks that are performed by one or more robots and have proposed two-stage algorithms to reduce combinatorial complexity and hence allow the solution of larger problems. Unlimited robot availability was assumed in the first step and a relaxed MILP model was solved to find the optimal processing sequence. This was then fixed in the second step and a constrained MILP model was solved to find the optimal sequence of transportation tasks. Unfortunately, only problems featuring an extra few orders could still be tackled showing that other approaches are needed for sizes beyond 12 lots in 12 baths. Of the three conceptually different continuous-time models, the one by Castro et al. [1] exhibited the best performance.

In this work, we propose a new algorithm that combines mathematical programming and discrete-event simulation. The concern is no longer finding the optimal solution but very good solutions in a reasonable amount of time (e.g. 1 hour). The decomposition strategy involves three stages: (i) finding a near optimal processing sequence under unlimited robot availability by applying neighborhood search procedures [4-6] to an initial sequence, using the relaxed MILP model. Such rescheduling procedures use the ideas from our previous work [7-9] dealing with just a few lots per iteration but now lot selection is done randomly instead of using preordering heuristics. The best found sequence is then the input to (ii) the discrete-event simulation model that is able to generate a good feasible schedule to the one robot problem. This will be the starting point of the (iii) rescheduling procedure applied to the more complex MILP from [1], featuring the robot sequencing constraints. Note that the balance between solution quality and total computational effort can easily be shifted by changing the number of lots rescheduled per iteration.

Several examples are used to illustrate the capabilities of the proposed method, which is compared to the full-space model and to a constraint programming approach featuring a problem specific search strategy [10]. The results show significantly better solutions in about the same computational time. In particular, for the original  25 lots in 12 baths problem [2], the best found solution features a makespan that is 14.2% better than the A2’ heuristic algorithm from [11] and 7.4% better than the constraint programming approach.

[1] Castro, P. M.; Zeballos, L. J.; Méndez, C. A. Hybrid Time Slots Sequencing Model for a Class of Scheduling Problems. AIChE J. doi: 10.1002/aic.12609.

[2] Bhushan S.; Karimi, I. A. An MILP Approach to Automated Wet-Etch Station Scheduling. Ind. Eng. Chem. Res. 2003, 42, 1391.

[3] Aguirre, A. M.; Méndez, C. A.; Castro, P. M. A Novel Optimization Method to Automated Wet-Etch Station Scheduling in Semiconductor Manufacturing Systems. Comput. Chem. Eng. 2011, doi:10.1016/j.compchemeng.2011.02.14.

[4] Danna, E.; Rothberg, E.; Le Pape, C. Exploring relaxation induced neighborhoods to improve MIP solutions. Mathematical Programming, 2005, 102, 7.

[5] Rothberg, E. An evolutionary algorithm for polishing Mixed Integer Programming Solutions. INFORMS Journal On Computing, 2007, 19, 534.

[6] Fischetti, M.; Lodi, A. Local branching. Mathematical Programming, 2005, 98, 23.

[7] Méndez, C.; Cerdá, J. Dynamic scheduling in multiproduct batch plants. Comp. Chem. Eng. 2003, 27, 1247.

[8] Castro, P. M.; Harjunkoski, I.; Grossmann, I. E. Optimal Short-Term Scheduling of Large-Scale Multistage Batch Plants. Ind. Eng. Chem. Res. 2009, 48, 11002.

[9] Castro, P. M.; Harjunkoski, I.; Grossmann, I. E. Greedy Algorithm for Scheduling Batch Plants with Sequence-Dependent Changeovers. AIChE J. 2011, 57, 373.

[10] Zeballos, L. J.; Castro, P. M.; Méndez, C. A. Integrated Constraint Programming Scheduling Approach for Automated Wet-Etch Stations in Semiconductor Manufacturing. Ind. Eng. Chem. Res. 2011, 50, 1705.

[11] Bhushan, S.; Karimi, I. A. Heuristic Algorithms for Scheduling an Automated Wet-Etch Station. Comput. Chem. Eng. 2004, 28, 363.