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

Due to its typical features, such as large-scale, multiple re-entrant flows, and hybrid machine types, the semiconductor wafer fabrication system (SWFS) is extremely difficult to schedule. In order to cope with this difficulty, the decomposition-based classified ant colony optimization (D-CACO) method is proposed and analyzed in this paper. The D-CACO method comprises decomposition procedure and classified ant colony optimization algorithm. In the decomposition procedure, a large and complicate scheduling problem is decomposed into several subproblems and these subproblems are scheduled in sequence. The classified ACO algorithm then groups all of the operations of the subproblems and schedules them according to machine type. To test the effect of the method, a set of simulations are conducted on a virtual fab simulation platform. The test results show that the proposed D-CACO algorithm works efficiently in scheduling SWFS.

Semiconductor manufacturing process comprises four phases: wafer fabrication, wafer probe, assembly, and final testing (Uzsoy, Church, Ovacik, & Hinchman, 1992), while wafer fabrication is the most complicated, expensive and time consuming part. In semiconductor wafer fabrication system (SWFS), there are hundreds of machines working together under various constraints, and following numerous processing steps, to build multiple layers of chemical patterns on a silicon wafer (Kumar, 1994 and Mason et al., 2002). Every layer needs to be processed in a similar manner, so wafers have to visit a certain machine for several times, each time for a layer of circuitry, and this is known as re-entrant product flow (Toktay & Uzsoy, 1998). In addition, wafer fabrication is also characterized by hybrid machine types. Several types of equipment (e.g. single wafer processing machine, single lot processing machine, and batch-type processing machine) work simultaneously in the SWFS. Due to these features, the scheduling problem of SWFS is a generalization of job shop problem that is strongly NP-hard (Garey & Johnson, 1979). This implies that the SWFS problem with the Cmax criterion considered in this paper is strongly NP-hard as well. In view of the complexity of SWFS, dispatching policies are commonly used for the production scheduling problems because these policies can provide approximate solutions for large problems within reasonable computation time (Pinedo, 2000). Dispatching policies usually used in SWFS were reviewed in detail by Lee, Tang, and Chan (2001). Wein (1988) studied the influence of scheduling rules on the performance of SWFS. Under these policies, the priority of jobs waiting for processing on a machine is evaluated. Once a machine is free, the job with the highest priority is picked from currently available jobs that are queuing for processing. It has been shown that a good dispatching policy may significantly improve the performance of SWFS (Kumar, 1994). However, there is no single dispatching rule that can work perfectly for all measures of performance (Holthausa and Rajendran, 1997 and Uzsoy et al., 1992). Furthermore, these dispatching policies are myopic and usually cannot lead to optimal solutions as they work well on one machine but may ignore influences among different machines, thus result in poor system performance (Hung & Chang, 2002). In order to use global shop information, some non-myopic algorithms were developed. One class of such algorithms is based on decomposition, which is used to divide large scheduling problems into smaller ones. There are two major decomposition methods, which are either time-sequence based or machine based. These methods are commonly adopted in decomposing large-scale scheduling problems into smaller ones. Rolling horizon procedures (RHPs), a kind of time-sequence decomposition method, was developed for dynamic scheduling problems (Ovacik and Uzsoy, 1994 and Ovacik and Uzsoy, 1995). According to RHPs, a scheduling problem is divided into several subproblems along time-axis. Each subproblem corresponds to a time window of the whole schedule, which is solved by branch-and-bound algorithm or other mathematical programming methods. This approach was improved and applied to schedule SWFS (Sourirajan & Uzsoy, 2007). Among the machine-based decomposition methods, one of the most successful approaches is the Shifting Bottleneck (SB) proposed by Adams, Balas, and Zawack (1988). In SB procedure, one critical unscheduled machine is identified at every iteration and scheduled by a branch-and-bound approach. This process is repeated until all machines will have been scheduled (Singer, 2001). Based on the SB heuristic, Revised Shifting Bottleneck procedure was developed for the scheduling of wafer fabrication environment (Wang, 2000). Later, another modification of the SB heuristic has been proposed in (Mason et al., 2002) for the minimization of the total weighted tardiness in a semiconductor wafer fabrication facility. Both RHPs and SB combine decomposition procedures with exact methods, such as branch-and-bound algorithm, which can obtain high-quality schedules but requires large computer memory and long computation time. In recent years, some intelligent heuristic algorithms, called metaheuristics, were applied to scheduling problems in SWFS. Compared with traditional heuristics, these algorithms may provide better solutions using a local search procedure. Popular metaheuristics used in SWFS include tabu search method (Geiger et al., 1997 and Mazumdar et al., 2008), simulated annealing (Chou et al., 2008 and Yim and Lee, 1999), and genetic algorithm (Chien and Chen, 2007 and Mönch et al., 2007). The Ant Colony Optimization (ACO) algorithm (Dorigo, 1992, Dorigo and Blum, 2005 and Dorigo and Stützle, 2004) is a metaheuristic algorithm and it was originally inspired by the behavior of ants. Ants are capable of finding the shortest route from a food source to their nest. They communicate via pheromone that they use in variable quantities to mark their trails. An ant’s tendency to choose a certain route is positively correlated to the pheromone intensity of that trail. Since pheromone evaporates over time, its intensity decreases if no more pheromone is laid down. If many ants choose a certain route and all lay down pheromone, the pheromone intensity of this trail increases and will attract more ants. Compared with other methods used for the SWFS scheduling problem, ACO has two advantages. Firstly, ACO can effectively combine some problem-specific information with business rules during solution search. Secondly, ACO is a model-based algorithm, which is different from an instance-based genetic algorithm. The learning process of ACO is distributed in each element of the model, and normally this can lead to high-quality results. The ACO algorithm has been used successfully in solving production scheduling problems (Dorigo & Stützle, 2004), such as job shop problem (Colorni et al., 1994 and Huang and Liao, 2008), flow shop problem (Benbouzid-Sitayeb et al., 2008 and Stützle, 1998), group shop problem (Blum, 2002), and open shop problem (Blum, 2005). Recently, ACO algorithm was used to solve scheduling problems in semiconductor manufacturing system. It was used to solve scheduling problem of single batch processing machine (Kashan & Karimi, 2008) and parallel batch processing machines (Li, Qiao, & Wu, 2009) in SWFS, and was also used to solve bottleneck station scheduling problem in semiconductor assembly and test manufacturing system (Song, Zhang, Yi, Zhang, & Zheng, 2007). However, to our best knowledge, there is no previous work on the application of ACO algorithm for scheduling large-scale problem with hybrid machine types. The metaheuristics have some advantages. They can obtain near-optimal solutions that are much better than those gained by dispatching rules, and need less computation time compared with mathematical programming. However, it is not appropriate to apply a metaheuristic method alone to the SWFS scheduling because of two reasons. First, although the computation time for the metaheuristics is not a significant factor as in mathematical programming techniques, it is still impossible to schedule large-scale complex problems within a reasonable time. Second, traditional metaheuristic approaches usually cope with one specific type of equipment well but are difficult to deal with hybrid machine types in SWFS. In this paper, we introduce a new heuristic – decomposition-based classified ACO algorithm (D-CACO), an improved ACO algorithm that shows efficacy on SWFS scheduling. The D-CACO divides large-scale scheduling problem into several small subproblems, and then solves these subproblems in sequence using classified ACO algorithm (CACO). Different from traditional ACO algorithm, CACO algorithm can schedule various types of equipment under a single scheduling framework. On a virtual fab simulation platform, the application of D-CACO method can lead to 10–20% reduction of makespan compared to traditional dispatching rule. The remaining sections of this paper are organized as follows. Section 2 discusses the scheduling model and disjunctive graph of SWFS. Section 3 describes the proposed decomposition-based classified ant colony optimization (D-CACO) algorithm. Two simulation models are introduced in Section 4, and D-CACO algorithm is tested by numerical experiments on simulation models in Section 5. Finally, some concluding remarks and a discussion of potential directions for future research are presented in Section 6.

This paper presented a D-CACO algorithm in solving the SWFS scheduling problem. The D-CACO is composed of decomposition and classified ant colony optimization algorithm. The scheduling problems were decomposed into smaller subproblems, and then ACO algorithm was used to find high quality solutions. By applying corresponding scheduling method to different types of machines, D-CACO algorithm coped with hybrid machine types quite well. Simulation was conducted on a mini-fab and virtual fab simulation models. The results show that the classified ACO algorithm can obtain high-quality schedule for small problems, while the D-CACO algorithm has clear efficiency improvement on large one. With the increase of the subproblem size, the quality of solution found by D-CACO algorithm became better while the computation time also increased. However, the computation time was still reasonable and relatively shorter compared with the long processing time of SWFS equipment. Future research is planned along two lines. First, the proposed algorithm should be tested in more realistic or complicate environment. Some factors from the factory, such as different release policies, multiple products, and equipment maintenance, should be considered. Second, parallel decomposition mode should be studied in the future. As mentioned in Section 3.1, there are difficulties on coordination of subproblems in parallel decomposition method. However, less computation time of this method makes it attractive, though a better coordination mechanism is needed before it can be used in practice.