الگوریتم های هیوریستیک برای برنامه ریزی یک ایستگاه مرطوب خودکار

Wet-etching is a key step in wafer fabrication. A wet-etch station is a chemical batch process involving a complex interplay of mixed intermediate storage (MIS) policies and a shared robot for wafer transfers. Its operation poses a challenging resource-constrained scheduling problem that is crucial for enhancing productivity, improving yield and minimizing contamination. In this paper, we develop three new algorithms for scheduling wafer jobs for a given sequence, which comfortably outperform a literature algorithm in terms of solution quality without requiring excessive effort. Furthermore, we propose a simulated annealing (SA) algorithm for sequencing the wafer jobs. Using this SA algorithm, an existing sequencing algorithm based on tabu search (TS), two job-scheduling algorithms and two algorithms for initial job sequence, we identify eight complete algorithms for scheduling operations in an automated wet-etch station (AWS). After a thorough numerical evaluation, we conclude that the TS sequencing strategy combined with two of our three job-scheduling algorithms is the best option that yields up to 25–30% lower makespans than a literature algorithm, and requires acceptable computing times for industrial-scale problems.

In a previous paper (Bhushan & Karimi, 2003), we developed a novel continuous-time mixed integer linear programming (MILP) formulation for scheduling production in an automated wet-etch station (AWS) and reviewed relevant literature in detail. As discussed there, an AWS performs a key step of wet-etching in wafer fabrication; it removes the exposed or unmasked areas of a wafer. In the AWS, a series of chemical and de-ionizing baths process carriers (jobs) of wafers, while a single robot moves the carriers from bath to bath. These automated movements sharing the single robot and strict requirements on the exposure times of wafers in various baths make the AWS operation complex from a scheduling perspective. For most scheduling problems, MILP solutions become prohibitive for large problems. Besides, the solution times for MILP algorithms are notoriously sensitive to problem data and unpredictable. Therefore, heuristic methods have been widely reported in the scheduling literature. Although the heuristic methods cannot guarantee optimal solutions, they take much less CPU times and are insensitive to problem data, thus are more reliable and robust for practical application. These factors make them very attractive for solving real-life, large-size, scheduling problems. For the problem at hand, Geiger, Kempf, and Uzsoy (1997) reported a heuristic algorithm based on tabu search (TS). With the objective of minimizing makespan, they developed an approximate algorithm for scheduling lot transfers by the robot for a given sequence of carriers or jobs on baths. Then, they used this inside a tabu search algorithm to obtain a near-optimal sequence of jobs on the baths. Earlier, Hertz, Mottet, and Rochat (1996) addressed a similar problem occurring in the robotized sample preparation of membrane fatty acid esters for the identification of bacteria. They considered a single product system with ‘implicit’ and ‘explicit’ activations of resources. An implicit activation means that a task starts as soon as it enters the resource, while an explicit resource must be turned ‘on’ to process a job and has to be turned ‘off’ after the job exits. They took into consideration shelf-life constraints and permitted hold-up on the robot. They stressed that defining even a set of feasible schedules and its neighborhood was non-trivial due to the NP-hard nature of the problem. Hence, they used a constraints graph technique to solve this scheduling problem with the objective of minimizing the makespan. The problem addressed in this paper is more complex than that of Hertz et al. (1996), because it involves a multi-product system in which the robot must ensure zero-wait (ZW) and no intermediate storage (NIS) policies (Ku & Karimi, 1990) at alternate baths. For its solution, we employ a two-level strategy in which the outer or sequencing algorithm examines many job sequences to arrive at the best and the inner or scheduling algorithm computes the makespan for a given sequence by scheduling the movements of jobs among the baths. We present a simulated annealing (SA) (Kalivas, 1995) algorithm for the former and three new algorithms for the latter. Then, we thoroughly evaluate six combinations of algorithms proposed in this paper and those existing in the literature to identify the best two-level algorithm for optimizing operations in the AWS. Finally, we illustrate the application of our algorithms using an example.

A typical multi-product AWS may process hundreds of wafer-carriers and the ability to solve such large problems is crucial in real-life operations. To complement our earlier MILP formulation (Bhushan & Karimi, 2003) for scheduling production in the AWS, we developed several heuristic approaches suited for large problems in this work and evaluated them thoroughly to identify the best complete algorithm. We found that a TS-based sequencing strategy was superior to a SA-based strategy for this problem, provided the initial job sequence and robot logics were the same. This, we believe, is primarily due to the more random nature of SA in contrast to TS. The best complete algorithm for this problem is the TS implementation of Geiger et al. (1997) combined with our efficient and powerful robot-scheduling algorithms (II or JAT). It performed much better than Geiger’s algorithm mainly due to our significantly superior robot-scheduling algorithms. We demonstrated that Geiger’s algorithm might yield makespans as much as 28.81% worse than other algorithms for big, complex problems. Besides, we also observed that multiple sequences might result in the same makespan, making the robot-scheduling a major consideration in this problem. By developing near-optimal algorithms that are able to solve large scheduling problems arising in the AWS in reasonable times, this work makes a significant contribution towards improving the productivity and yields in the key step of wet-etching in wafer fabrication.