【作者】 郭乘涛；

【导师】 江志斌；

【作者基本信息】 上海交通大学 ， 机械工程， 2012， 博士

【摘要】 半导体晶圆制造系统是半导体制造过程中最为复杂和昂贵的环节，晶圆制造系统的调度问题是一类复杂的车间调度问题。尽管目前晶圆制造系统求解调度问题最常见的方法是启发式调度规则，但是智能算法在未来的晶圆制造系统中应用的潜力非常大，这是因为智能算法具有自组织与自调整能力，可以适应调度问题的变化，并在可接受的时间内获得高质量的解。蚁群算法是一类产生不久但发展迅速的智能算法，它不仅具有一般智能算法的优点，而且具有并发多线程搜索机制与正反馈特点，可以更迅速地获得满意的可行解，因而近年来被逐渐应用于解决生产调度问题。但是到目前为止，应用蚁群算法求解晶圆制造系统调度问题的研究还很不深入，这是因为传统蚁群算法不能很好地应对晶圆制造系统的复杂性，特别是其大规模、多重入、混合型生产的特征。基于以上的原因，本文提出基于问题分解的蚁群算法，有针对性地对传统蚁群算法进行改造，并结合问题分解方法，以期获得晶圆制造系统调度问题的高质量解。本文所取得的主要工作成果包括：1）建立应用蚁群算法调度晶圆制造系统的问题分解框架。元启发算法可解决较大规模的调度问题，但是当其用于解决晶圆制造调度这样的大规模调度问题时，随着问题规模急剧扩大，元启发算法的应用会受到制约。为此，应用问题分解方法将大规模问题分解为小规模的子问题，再用蚁群算法分别求解，就成为一条可行的解决途径。本论文提出两类适合晶圆制造系统特征的问题分解方法，包括基于时间的问题分解方法与基于机器类型的问题分解方法。前者用来应对晶圆制造系统的大规模特征。通过对调度时间的分割，在每个时间区间内只需要处理部分机器与工件，降低了问题的规模与难度；后者用来应对混合型生产的特征，通过对机器按照类型进行分解，针对每一类型采用相应的蚁群算法进行处理，使得调度问题更易于解决。在此基础上，建立应用蚁群算法调度晶圆制造系统的问题分解框架，以有效处理大规模晶圆制造系统调度问题。2）提出调度问题分解协调机制。问题分解是一个将各子问题解耦的过程，在各子问题单独求解完成后，这些解合成原问题的解又面临如何协调的问题，这两个问题如何处理是问题分解方法最需要考虑的问题。本文提出三类协调机制，首先针对基于时间的问题分解方法，提出基于重叠区间的协调机制，保证了原问题调度方案的可行性；其次提出了基于工件上下游的协调机制，通过上下游机器的加工信息，决定当前机器的调度策略，以提供调度方案的精度；最后采用蚁群算法的信息素更新机制作为隐性协调机制，针对基于机器的分解方法，采用蚁群算法的信息素保证分解后的机器间信息的沟通。3）针对晶圆制造系统与问题分解方法特征对现有蚁群算法进行改进。为了应对晶圆制造系统的复杂性特征，以及适应前述问题分解方法，对现有蚁群算法进行了改进：首先，针对晶圆制造系统的多重入特征，开发基于重入的蚁群算法，针对加工目标对不同加工阶段的工件赋以不同的信息权重，使其可以获得更好的调度方案。其次，应对基于类型的分解方法，当将子问题分解为若干单机调度问题后，针对其中较难调度且经常为系统瓶颈的批处理设备开发专门的蚁群算法，以保证整个调度问题的顺利求解。最后，提出分类蚁群算法，使得多种类型设备的调度问题可以在一个算法构架下共存。最后，采用仿真实验对所提出的问题分解方法、协调机制与蚁群算法进行验证，实验分别针对单台设备调度问题、子问题调度、大规模调度问题而进行，实验结果证明了本文所提出方法的可以有效地处理晶圆制造系统的复杂特征，并获得高质量的调度方案。更多还原

【Abstract】 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.更多还原