The Research On Scheduling Of Wafer Fabrication System Based On Decomposition Method And Ant Colony Optimization Algorithm

Semiconductor wafer fabrication system (SWFS) is the most complicatedand expensive part of the semiconductor manufacture system and the schedulingproblem of wafer fabrication system is a type of complex job shop schedulingproblem. The most extensive used scheduling method in SWFS is the heuristicrules. However, the intelligent algorithms are more potential to broadly apply inSWFS in the future, because they have the ability of self-organization andself-adjustment, which can adapt the change of the scheduling problem andobtain the high quality solution in reasonable calculation time. The Ant colonyoptimization (ACO) method is a new but developed very fast intelligentalgorithm. It has the features of concurrent multi-thread calculation ability,positive feedback and self-organization, which can help the algorithm obtain thesolution much faster. Due to the above reasons, the ACO algorithm is applied tosolve the scheduling problem in many fields recently. However, it is notsuccessful applied to solve the scheduling problem of SWFS up to now becausethe traditional ACO algorithm cannot cope with the complexity of SWFS,especially the features of large scale, multi-reentrant and mixed production.This paper proposed the decomposition based ant colony optimizationmethod to handle the problem stated above. The proposed method modified thetradition ACO algorithm and combined with the decomposition method to findhigh quality solution for the scheduling problem of SWFS. The major contributions are stated as follows.1. Construct the decomposition framework on scheduling wafer fabricationsystem with ACO algorithmThe meta-heuristic algorithm can be used to solve the large scalescheduling problem. However, its application will be restricted when the size ofproblem increased rapidly. As a result, the large scale problem needs to bedecomposed into several sub-problems with smaller size and then be scheduledby ACO algorithms. In the thesis, two type of decomposition are presented tocope with the features of wafer fabrication system, including the time-based andmachine-type-based decomposition methods. The former method is used to copewith the feature of large scale of SWFS. It divided the scheduling period, andonly a part of machines and jobs need to be scheduled in a small period, whichdecreases the size and difficulty of scheduling problem. The latter one is used tocope with the feature of mixed production. It decomposes the schedulingproblem according to the machine-type, and every type of machine is solved bythe according ACO algorithm, which make the scheduling problem is solvedeasily. The decomposition framework is constructed based on these twodecomposition methods and ACO algorithms.2. Develop the coordination mechanisms for the decomposed sub-problemsAfter the sub-problems have been decomposed and scheduled, theschedules of the sub-problems need to be combined to the solution of originalproblems, and the coordination mechanisms are needed to adjust thesesub-problem schedules. In this thesis, three type of coordination mechanism arepresented. The first type was based on overlapping area which is constructedbetween two neighbor sub-problems and a part of operations were belongs tothese two sub-problems. This coordination mechanism can ensure the continuityof the schedule obtained. The second one considered the up and down stream ofthe process. After the scheduling problem was decomposed into several single machine scheduling problems by the machine-type decomposition method, theinformation of the up and down stream of the job should be considered when thecurrent operation was processed. The third coordination mechanism is based onthe pheromone updating rule. Different type of machine can run in the samescheduling framework according to the delivery of pheromone.3. Improve the traditional ACO algorithm to cope with the features of waferfabrication system and decomposition methodIn order to cope with the complicated features of wafer fabrication systemand the decomposition method stated above, the traditional ACO algorithm needto be modified. This paper proposed three type of modified ACO algorithm.First, the ACO algorithm based on re-entrant feature is proposed to cope withthe multi re-entrant feature of SWFS. The algorithm places different weights tothe job at different processing stage to find better solution. Second, two newhybrid-ACO algorithms were proposed to schedule the batch machine, which ishard to schedule and is always the bottleneck of the system. Finally, theclassified ACO algorithm is proposed to schedule different type of machine inthe same framework.In the end, the simulation experiments are conducted to testify the proposeddecomposition methods, the coordination mechanisms and the modified ACOalgorithms. The experiments are executed on single machine schedulingproblem, the sub-problem scheduling and the large scale scheduling problemrespectively. The results show that the proposed methods can handle thecomplicated features of the wafer fabrication system and obtain the high qualitysolution.