基于问题分解与蚁群算法的半导体晶圆制造系统调度方法的研究
|
摘要
半导体晶圆制造系统是半导体制造过程中最为复杂和昂贵的环节，晶圆制造系统的调度问题是一类复杂的车间调度问题。尽管目前晶圆制造系统求解调度问题最常见的方法是启发式调度规则，但是智能算法在未来的晶圆制造系统中应用的潜力非常大，这是因为智能算法具有自组织与自调整能力，可以适应调度问题的变化，并在可接受的时间内获得高质量的解。蚁群算法是一类产生不久但发展迅速的智能算法，它不仅具有一般智能算法的优点，而且具有并发多线程搜索机制与正反馈特点，可以更迅速地获得满意的可行解，因而近年来被逐渐应用于解决生产调度问题。但是到目前为止，应用蚁群算法求解晶圆制造系统调度问题的研究还很不深入，这是因为传统蚁群算法不能很好地应对晶圆制造系统的复杂性，特别是其大规模、多重入、混合型生产的特征。
基于以上的原因，本文提出基于问题分解的蚁群算法，有针对性地对传统蚁群算法进行改造，并结合问题分解方法，以期获得晶圆制造系统调度问题的高质量解。本文所取得的主要工作成果包括：
1）建立应用蚁群算法调度晶圆制造系统的问题分解框架。
元启发算法可解决较大规模的调度问题，但是当其用于解决晶圆制造调度这样的大规模调度问题时，随着问题规模急剧扩大，元启发算法的应用会受到制约。为此，应用问题分解方法将大规模问题分解为小规模的子问题，再用蚁群算法分别求解，就成为一条可行的解决途径。本论文提出两类适合晶圆制造系统特征的问题分解方法，包括基于时间的问题分解方法与基于机器类型的问题分解方法。前者用来应对晶圆制造系统的大规模特征。通过对调度时间的分割，在每个时间区间内只需要处理部分机器与工件，降低了问题的规模与难度；后者用来应对混合型生产的特征，通过对机器按照类型进行分解，针对每一类型采用相应的蚁群算法进行处理，使得调度问题更易于解决。在此基础上，建立应用蚁群算法调度晶圆制造系统的问题分解框架，以有效处理大规模晶圆制造系统调度问题。
2）提出调度问题分解协调机制。
问题分解是一个将各子问题解耦的过程，在各子问题单独求解完成后，这些解合成原问题的解又面临如何协调的问题，这两个问题如何处理是问题分解方法最需要考虑的问题。本文提出三类协调机制，首先针对基于时间的问题分解方法，提出基于重叠区间的协调机制，保证了原问题调度方案的可行性；其次提出了基于工件上下游的协调机制，通过上下游机器的加工信息，决定当前机器的调度策略，以提供调度方案的精度；最后采用蚁群算法的信息素更新机制作为隐性协调机制，针对基于机器的分解方法，采用蚁群算法的信息素保证分解后的机器间信息的沟通。
3）针对晶圆制造系统与问题分解方法特征对现有蚁群算法进行改进。
为了应对晶圆制造系统的复杂性特征，以及适应前述问题分解方法，对现有蚁群算法进行了改进：首先，针对晶圆制造系统的多重入特征，开发基于重入的蚁群算法，针对加工目标对不同加工阶段的工件赋以不同的信息权重，使其可以获得更好的调度方案。其次，应对基于类型的分解方法，当将子问题分解为若干单机调度问题后，针对其中较难调度且经常为系统瓶颈的批处理设备开发专门的蚁群算法，以保证整个调度问题的顺利求解。最后，提出分类蚁群算法，使得多种类型设备的调度问题可以在一个算法构架下共存。
最后，采用仿真实验对所提出的问题分解方法、协调机制与蚁群算法进行验证，实验分别针对单台设备调度问题、子问题调度、大规模调度问题而进行，实验结果证明了本文所提出方法的可以有效地处理晶圆制造系统的复杂特征，并获得高质量的调度方案。
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 algorithm
The 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-problems
After 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 method
In 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.
基于以上的原因，本文提出基于问题分解的蚁群算法，有针对性地对传统蚁群算法进行改造，并结合问题分解方法，以期获得晶圆制造系统调度问题的高质量解。本文所取得的主要工作成果包括：
1）建立应用蚁群算法调度晶圆制造系统的问题分解框架。
元启发算法可解决较大规模的调度问题，但是当其用于解决晶圆制造调度这样的大规模调度问题时，随着问题规模急剧扩大，元启发算法的应用会受到制约。为此，应用问题分解方法将大规模问题分解为小规模的子问题，再用蚁群算法分别求解，就成为一条可行的解决途径。本论文提出两类适合晶圆制造系统特征的问题分解方法，包括基于时间的问题分解方法与基于机器类型的问题分解方法。前者用来应对晶圆制造系统的大规模特征。通过对调度时间的分割，在每个时间区间内只需要处理部分机器与工件，降低了问题的规模与难度；后者用来应对混合型生产的特征，通过对机器按照类型进行分解，针对每一类型采用相应的蚁群算法进行处理，使得调度问题更易于解决。在此基础上，建立应用蚁群算法调度晶圆制造系统的问题分解框架，以有效处理大规模晶圆制造系统调度问题。
2）提出调度问题分解协调机制。
问题分解是一个将各子问题解耦的过程，在各子问题单独求解完成后，这些解合成原问题的解又面临如何协调的问题，这两个问题如何处理是问题分解方法最需要考虑的问题。本文提出三类协调机制，首先针对基于时间的问题分解方法，提出基于重叠区间的协调机制，保证了原问题调度方案的可行性；其次提出了基于工件上下游的协调机制，通过上下游机器的加工信息，决定当前机器的调度策略，以提供调度方案的精度；最后采用蚁群算法的信息素更新机制作为隐性协调机制，针对基于机器的分解方法，采用蚁群算法的信息素保证分解后的机器间信息的沟通。
3）针对晶圆制造系统与问题分解方法特征对现有蚁群算法进行改进。
为了应对晶圆制造系统的复杂性特征，以及适应前述问题分解方法，对现有蚁群算法进行了改进：首先，针对晶圆制造系统的多重入特征，开发基于重入的蚁群算法，针对加工目标对不同加工阶段的工件赋以不同的信息权重，使其可以获得更好的调度方案。其次，应对基于类型的分解方法，当将子问题分解为若干单机调度问题后，针对其中较难调度且经常为系统瓶颈的批处理设备开发专门的蚁群算法，以保证整个调度问题的顺利求解。最后，提出分类蚁群算法，使得多种类型设备的调度问题可以在一个算法构架下共存。
最后，采用仿真实验对所提出的问题分解方法、协调机制与蚁群算法进行验证，实验分别针对单台设备调度问题、子问题调度、大规模调度问题而进行，实验结果证明了本文所提出方法的可以有效地处理晶圆制造系统的复杂特征，并获得高质量的调度方案。
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 algorithm
The 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-problems
After 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 method
In 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.
引文
[1]环咨公司,2011年中国集成电路行业分析研究报告.2011:北京.
[2]王阳元, et al.,面向产业需求的21世纪微电子技术的发展（上）.物理,2004.33(6):p.407-413.
[3] Kumar, P.R., Scheduling Semiconductor Manufacturing Plants. IEEE Control SystemsMagazine,1994.14(6): p.33-40.
[4] Narahari, Y. and Khan, L.M., Performance analysis of scheduling polices in re-entrantmanufacturing system. Computer Operations Research,1996.23(1): p.37-51.
[5] Hung, A.C., et al., Modeling, scheduling, and Prediction for Wafer Fabrication:Queueing Colored Petri-Net and GA Based Approach, in Proceedings of the2002IEEE International Conference on Robotics&Automation.2002. p.3187-3192.
[6] Bachrach, R., et al. Comparative analysis of300mm FAB architectures impact ofequipment sets on wafer cost and dynamic performance. in SemiconductorManufacturing Symposium,2001IEEE International.2001.
[7] Leachman, R.C., Kang, J., and Lin, V., SLIM: Short cycle time and low inventory inmanufacturing at Samsung electronics. Interfaces, Informs,2002.32(1): p.61-77.
[8] Zant, P.V.,芯片制造—半导体工艺制程实用教程（第四版）.2004,北京:电子工业出版社.
[9] Quirk, M.,半导体制造技术.2004,北京:电子工业出版社.
[10] McKay, K.N. and Wiers, V.C.S., Unifying the theory and practice of productionscheduling. Journal of Manufacturing System,1999.18(4): p.241～255.
[11]徐俊刚,戴国忠, and王宏安,生产调度理论和方法研究综述.计算机研究与发展,2004.41(2): p.257-267.
[12]陈荣秋,排序的理论和方法.1987,武汉:华中科技大学出版社.
[13] Wein, L.M., Scheduling Semiconductor Wafer Fabrication. IEEE Transactions onSemiconductor Manufacturing,1988.1(3).
[14] Chung, S.H. and Huang, H.W., The design of production activity control policy.Journal of the Chinese Institute of Industrial Engineering,1999.16(1): p.93–113.
[15] Lee, C.E. and Chen, C.W., A dispatching scheme involving move control andweighted due date for wafer foundries. IEEE Transaction on Component, Packaging,and Manufacturing Technology Part C,1997.20(4): p.268–277.
[16] Glassey, C.R. and Resende, M.G.C., Closed-loop job release control for VLSI circuitmanufacturing. IEEE Transaction on Semiconductor Manufacturing,1988.1(1): p.36–46.
[17] Fowler, J.W., et al., Measurable improvements in cycle-time-constrained capacity, inIEEE International Symposium on Semiconductor Manufacturing ConferenceProceedings.1997. p. A21-A24.
[18] Lu, S.C.H., Ramaswamy, D., and Kumar, P.R., Efficient scheduling policies to reducemean and variance of cycle-time in semiconductor manufacturing plants. IEEETransaction on Semiconductor Manufacturing,1994.7(3): p.374–388.
[19] Glassey, C.R. and Weng, W.W., Dynamic batching heuristic for simultaneousprocessing. Semiconductor Manufacturing, IEEE Transactions on,1991.4(2): p.77-82.
[20] Lee, L.H., Tang, L.C., and Chan, S.C., Dispatching Heuristic for Wafer Fabrication, inProceedings of the2001Winter Simulation Conference.2001. p.1215-1219.
[21] Uzsoy, R., Church, L., and Ovacik, I., Dispatching rules for semiconductor testingoperations: a computational study, in IEEE/CHMT International ElectronicsManufacturing Technology Symposium.1992. p.272–276.
[22] Holthaus, O. and Rajendran, C., Efficient dispatching rules for scheduling in a jobshop. International Journal Production Economy,1997.48: p.87–105.
[23] Dessouky, M.M. and R.C., L., Dynamic Models of Production with MultipleOperation General Processing Times. Journal of the Operational Research Society,1997.48(6): p.647-654.
[24] Kumar, S. and Kumar, P.R., Queueing Network Models in the Design and Analysis ofSemiconductor Wafer Fabs. IEEE Transactions on Robotics and Automation,2001.17(5): p.548-561.
[25] Morton, T. and Pentico, D., Heuristic scheduling systems.1993, New York: Wiley.
[26] Sung, C. and Choung, Y., Minimizing makespan on a single burn-in oven insemiconductor manufacturing. European Journal Operation Research,2000.120: p.559-574.
[27] Chen, T.-R., Chen, C.-W., and Kao, J., Due windows scheduling for ic sort and testfacilities with precedence constrains via Lagrangian relaxation, in IEEE/SEMIInternational Semiconductor Manufacturing Science Symposium.1993. p.110–114.
[28] Chen, T.-R. and Hsia, T., Job shop scheduling with multiple resources and anapplication to a semiconductor testing facility, in Proceedings of the33rd IEEEConference on Decision and Control.1994. p.1564–1570.
[29] Chen, T.-R. and Hsia, T., Scheduling for IC sort and test facilities with precedenceconstrains via Lagrangian relaxation. Journal Manufacturing System,1997.16(2): p.117–128.
[30] Kaskavelis, C. and Caramanis, M. Application of a Lagrangian relaxation basedscheduling algorithm to a semiconductor testing facility. in Proceedings of the FourthInternational Conference on Computer Integrated Manufacturing and AutomationTechnology, IEEE.1994.
[31] Kaskavelis, C. and Caramanis, M., Efficient Lagrangian relaxation algorithms forindustrial size job-shop scheduling problems. IIE Transactions,1998.30: p.1085–1097.
[32] Sun, X., James, S., and Klein, C., Single-machine scheduling with sequence dependentsetup to minimize total weighted squared tardiness. IIE Transactions,1999.31: p.113–124.
[33] De, S. and Lee, A., Towards a knowledge-based scheduling system for semiconductortesting. International Journal Production Research,1998.36(4): p.1045–1073.
[34] Connors, D., Feigin, G., and Yao, D., Scheduling semiconductor lines using a fluidnetwork model. IIE Trans Robot Autom,1994.10(2): p.88–98.
[35] Neuts, M.F., A general class of bulk queues with Poisson input. The Annals ofMathematical Statistics,1967.38: p.759-770.
[36] Medhi, J., Waiting time distribution in a Poisson queue with a general bulk servicerule. Management Science,1975.21(7): p.777-782.
[37] Hopp, W., et al., Using an optimized queuing network model to support wafer fabdesign. IIE Solutions,2002.34: p.119–130.
[38] Huang, M.G., Chang, P.L., and Chou, Y.C., Analytic Approximations for MultiserverBatch-Service Work-Stations with Multiple Process Recipes in Semiconductor WaferFabrication. IEEE Transactions on Semiconductor Manufacturing,2001.14(4): p.395-405.
[39] Li, C.-L. and Lee, C.-Y., Scheduling with aggreable release time and due dates on abatch processing machine. European Jounal of Operational Research,1997.96: p.564-569.
[40] Sung, C.S., et al., Minimizing makespan on a single burn-in oven with job familiesand dynamics job arrivals. Computers&Operations Research,2002.29: p.995-1007.
[41] Burdick, R.G.A., A cost effective expert system for semiconductor manufacturing.Computer&Operations Research,1987.
[42] Aytug, H., et al., A review of machine learning in scheduling. IEEE Trans Eng Manage,1994.41(2): p.165–171.
[43] Huang, C.L., et al., Construction of production performance prediction system forsemiconductor manufacturing with artificial neural networks. International Journal ofProduction Research,1999.37(6): p.1387-1402.
[44] Liao, D.Y. and Wang, C.N., Neural-network-based delivery time estimates forprioritized300-mm automatic material handling operations. IEEE Transactions onSemiconductor Manufacturing,2004.17(3): p.324-332.
[45] Zhang, J., et al., Fuzzy neural networks based rescheduling strategies optimization ofsemiconductor fabrication line. Chinese Journal of Mechanical Engineering,2005.41(10): p.75-79.
[46] Azzaro-Pantel, C., et al., A fuzzy approach for performance modeling in a batch plant:application to semiconductor manufacturing. IEEE Transactions on Fuzzy System,1997.5(3): p.338-357.
[47] Zhou, M.C. and Jeng, M.D., Modeling, Analysis, Simulation, scheduling, and Controlof Semiconductor Manufacturing Systems: A Petri Net Approach. IEEE Transactionson Semiconductor Manufacturing,1998.11(3): p.333-357.
[48] Xiong, H. and Zhou, M., Scheduling of semiconductor test facility via petri nets andhybrid heuristic search. IEEE Trans Semicond Manuf,1998.11(3): p.384–393.
[49] Cerny, V., Thermodynamical approach to the traveling salesman problem: An efficientsimulation algorithm. Journal of Optimization Theory and Applications,1985.45(1): p.41-52.
[50] Yim, S. and Lee, D., Scheduling cluster tools in wafer fabrication using candidate listand simulated annealing. Journal Intelligent Manufacturing,1999.10(6): p.531–540.
[51] Erramilli, V. and Mason, S.J., Multiple Orders Per Job Compatible Batch Scheduling.Electronics Packaging Manufacturing, IEEE Transactions on,2006.29(4): p.285-296.
[52] Glover, F., Tabu Search-Part I. ORSA JOURNAL ON COMPUTING,1989.1(3): p.190-206.
[53] Glover, F., Tabu Search-Part II. ORSA JOURNAL ON COMPUTING,1990.2(1): p.4-32.
[54] Geiger, C., Kempf, K., and Uzsoy, R., A Tabu search approach to scheduling anautomated wet etch station. Journal of Manufacturing System,1997.16(2): p.102–116.
[55] Schwefel, H., Numerical optimization of computer models.1981, New York: JohnWiley&Sons, Inc.
[56] Fogel, L., Artificial intelligence through simulated evolution.1966, New York: JohnWiley&Sons.
[57] Holland, J., Adaptation in natural and artificial systems.1992: MIT Press Cambridge.
[58] Goldberg, D., Genetic algorithms in search, optimization and machine learning.1989,Boston: Wesley Longman Publishing.
[59] Liu, M. and Wu, C., Genetic algorithm using sequence rule chain for multi-objectiveoptimization in re-entrant micro-electronic production line. Robotics andComputer-Integrated Manufacturing,2004.20(3): p.225-236.
[60] Wang, C.S. and Uzsoy, R., A genetic algorithm to minimize maximum lateness on abatch processing machine. Computers and Operations Research,2002.29(12): p.1621-1640.
[61] Melouk, S., Damodaranb, P., and Chang, P.-Y., Minimizing makespan for singlemachine batch processing with non-identical job sizes using simulated annealingInternational journal of production economics,2004.87(2): p.141-147.
[62] M nch, L., et al., Heuristic scheduling of jobs on parallel batch machines withincompatible job families and unequal ready times. Computers&Operations Research,2005.32(11): p.2731-2750.
[63] SG, K., et al., Scheduling a single batch processing machine with arbitrary job sizesand incompatible job families. International Journal of Production Economics,2005.98: p.81–96.
[64] Dantzig, G.B. and Wolfe, P., Decomposition principle for linear programs. OperationsResearch,1960.8(1): p.101-111.
[65] Akker, J.M.v.d., Hurkens, C.A.J., and Savelsbergh, M.W.P., Time-indexedformulations for machine scheduling problems:column generation. INFORMS Journalon Computing,1998.12: p.111-124.
[66] Barnhart, C., et al., Brach-and-Price: column generation for huge integer programs.Operations Research,1998.36: p.316-329.
[67] Vanderbeck, F. and Savelsbergh, M.W.P., A generic view of Dantzig-Wolfedecomposition for integer programming. Operations Research Letters,2006.34: p.294-306.
[68] FISHER, M.L., The lagrangian relaxation met hod for solving integer programmingproblems. Management Science,1981.27(1): p.1-18.
[69] FISHER, M.L., An applications oriented guide to lagrangian relaxation. Interfaces,1985.15(2): p.10-21.
[70] Held, M. and Karp, R.M., The traveling salesman and minimum spanning trees.Operation Research,1970.18: p.1138-1162.
[71] Held, M. and Karp, R.M., The traveling salesman and minimum spanning trees:Part II.Mathematic Programming,1971.1: p.6-25.
[72] Fisher, M.L., Optimal solution of scheduling problems using Lagrange multipliers:PartI. Operation Research,1973.21: p.1114-1127.
[73] Fisher, M.L., et al., Surrogate duality relaxation for job shop scheduling. DiscreteApplied Mathematics,1983.5: p.65-75.
[74] Luh, P.B. and Hoitornt, D.J., Scheduling of manufacturing system using the lagrangianrelaxation technique. IEEE Transactions on Automatic Control,1993.38: p.1066-1079.
[75] Luh, P.B., et al., Lagrangian relaxation neural networks for job shop scheduling. IEEETransactions on Robotics and Automation,2000.16: p.78-88.
[76] Zhao, X., A new generation of optimization algorithms within the lagrangianrelaxation approach for job shop scheduling, in Ph.D.1999, University of Connecticut.
[77] Fisher, M.L., The lagrangian relaxation method for solving integer programmingproblems. Management Science,2004.50: p.1861-1871.
[78] GUIGNARD, M. and KIM, S., Lagrangian decomposition: a model yielding st rongerLagrangian bounds. Mathematical Programming,1987.39(2): p.215-228.
[79]吴清烈and徐南荣,大规模含整变量优化问题的一种分解方法.东南大学学报,1996.26(3): p.119-125.
[80] Benders, J.F., Partitioning procedure for solving mixed-variables programmingproblems. Numerische Mathematik,1962.4: p.238-252.
[81] Bassett, M., et al., Perspectives on model based integration of process operations.Computers and Chemical Engineering,1996.20(6-7): p.821-844.
[82] Bassett, M., Pekny, J., and Reklaitis, G., Decomposition techniques for the solution oflarge-scale scheduling problems. AIChE Journal,1996.42(12): p.3373-3387.
[83] Ovacik, I.M. and Uzsoy, R., Rolling horizon algorithms for a single-machine dynamicscheduling problem with sequence-dependent setup times. International Journal ofProduction Research,1994.32(6): p.1243.
[84] Ovacik, I.M. and Uzsoy, R., Rolling horizon procedures for dynamic parallel machinescheduling with sequence-dependent setup times. International Journal of ProductionResearch,1995.33(11): p.3173-3192.
[85] Upasani, A.A., Uzsoy, R., and Sourirajan, K., A Problem Reduction Approach forScheduling Semiconductor Wafer Fabrication Facilities. SemiconductorManufacturing, IEEE Transactions on2006.19(2): p.216-225
[86] Sourirajan, K. and Uzsoy, R., Hybrid decomposition heuristics for solving large-scalescheduling problems in semiconductor wafer fabrication. Journal of Scheduling,2007.10(1): p.41-65.
[87] Sannomiya, N. and Iima, H. Genetic algorithm approach to an optimal schedulingproblem for a large-scale complex manufacturing system. in IEEE SMC '99Conference Proceedings..1999. Tokyo.
[88] Rosl f, J., et al., A Short-Term Scheduling Problem in the Paper-Converting Industry.Computers&Chemical Engineering,1999.23(S): p. S861-S874.
[89] Rosl f, J., et al., Solving a large-scale industrial scheduling problem using MILPcombined with a heuristic procedure. European Journal of Operational Research2002.138(1): p.29-42.
[90] Fox, M.S., Constraint-directed search: A case study of job-shop scheduling.1983,Pittsburgh: Carnegie Mellon University.
[91] Chu, C., Portmann, M.C., and Proth, J.M., A splitting-up approach to simplifyjob-shop scheduling problems. International Journal of Production Research,1992.30(4): p.859-870.
[92] Sun, D. and Batta, R., Scheduling larger job shops: a decomposition approach.International Journal of Production Research,1996.34(7): p.2019-2033.
[93] Adams, J., Balas, E., and Zawack, D., The Shifting Bottleneck Procedure for Job ShopScheduling. Management Science,1988.34(3): p.11.
[94] Wang, C.-S., Decomposition heuristics for complex job shop scheduling.2000, PurdueUniversity.
[95] Dauzere-Peres, S. and Lasserre, J.B., A modified shifting bottleneck procedure forjob-shop scheduling. International Journal of Production Research,1993.31: p.923-932.
[96] Balas, E., Lenstra, J.K., and Vazacopoulos, A., The one-machine problem with delayedprecedence constraints and its use in job shop scheduling. Management Science,1995.41: p.94-109.
[97] Demirkol, E., Mehta, S., and Uzsoy, R., A computational study of shifting bottleneckprocedures for shop scheduling problems. Journal of Heuristic,1997.3: p.111-137.
[98] Luh, P.B. and Chen, H.X., An alterative framework to lagrangian relaxation approachfor job shop cheduling, in the38th Conference on Decision&Control.1999.
[99] Merkle, D. and Middendorf, M., Ant Colony Optimization with Global PheromoneEvaluation for Scheduling a Single Machine. Applied Intelligence,2003.18(1): p.105-111.
[100] Blum, C., ACO Applied to Group Shop Scheduling: A Case Study on Intensificationand Diversification, in Ant Algorithms: Third International Workshop, ANTS2002,Brussels, Belgium, September12-14,2002. Proceedings2002, Springer Berlin/Heidelberg. p.149-180.
[101]梁静,钱省三, and马良,基于双层蚂蚁算法的半导体炉管制程批调度研究.系统工程理论与实践,2005.12(25): p.96-101.
[102] Song, Y., et al., Bottleneck Station Scheduling in Semiconductor Assembly and TestManufacturing Using Ant Colony Optimization. Automation Science and Engineering,IEEE Transactions on,2007.4(4): p.569-578
[103]尹文君,刘民, and吴澄,进化计算在生产线调度研究中的现状与展望.计算机集成制造系统,2001.7(12): p.1-6.
[104] Dorigo, M., Optimization, learning and natural algorithms.1992, Politecnico diMilano.
[105] Dorigo, M., Bonabeau, E., and Theraulaz, G., Ant algorithms and stigmergy. FutureGeneration Computer Systems,2000.16: p.851-871.
[106] Dorigo, M. and Di Caro, G. The Ant Colony Optimization: a new meta-heuristic. inProeeedings of the IEEE International Conference on Evolutionary Computation.1999:IEEE Press.
[107] Dorigo, M., Di Caro, G., and Gambardella, L.M., Ant algorithms for disereteoptimization. Artificial Life,1999.5(2): p.137-172.
[108] Dorigo, M., Maniezzo, V., and Colorni, A., Ant system: optimization by a colony ofcooperating agents. Systems, Man and Cybernetics, Part B, IEEE Transactions on,1996.26(1): p.29-41.
[109] Maniezzo, V. and Colorni, A., The Ant System applied to the quadratic assignmentProblem. IEEE Trans. Knowledge Data Eng,1999.11(5): p.769-778.
[110] Gambardella, L.M. and Dorigo, M. Ant-Q: A reinforCement learning apProach to thetraveling salesman problem. in Proceedings of the Twelfth International Conferenceon Machine Learning(ML-95).1995: Morgan Kaufimann Publishers.
[111] Gambardella, L.M. and Dorigo, M. Solving symmetric and asymmetric TSPs by antcolonies. in Proeeedings of the IEEE International Conference on EvolutionaryComputation.1996: IEEE Press.
[112] Sutton, R. and Barto, A., Reinforcement Learning: An Introduction.1998, Cambridge,MA: MIT Press.
[113] Watkins, J.C.H., Q-learning. Machine Learning,1992.8: p.279-292.
[114] Dorigo, M. and Gambardella, L.M., Ant Colony System: A cooperative learningapproach to the traveling salesman Problem. IEEE Transactions on EvolutionaryComputation,1997.1(1): p.53-66.
[115] Stutzle, T. and Hoos, H.H. The MAX-MIN ant system and local search for thetraveling salesman problem. in IEEE4th International Conference on EvolutionaryComputation.1997: IEEE Press.
[116] Stutzle, T., An ant approach to the flow shop problem in Technical report AIDA-97-07.1997. p.7.
[117] Stützle, T. and Hoos, H.H., MAX-MIN Ant System. Future Generation ComputerSystems,2000(16): p.889-914.
[118] Bullnheimer, B., Hartl, R.F., and Stranss, C., A New Rank Based Version of the AntSystem: A Computational Study. Central European Journal for Operations Researehand Eeonomics,1999.7(1): p.25-38.
[119] Gutjahr, W.J., A graph-based ant system and its convergence. Future Gener.Comput.Syst.,2000.16(8): p.873-888.
[120] Blum, C., Roli, A., and Dorigo, M., HC-ACO: The Hyper-Cube Framework for AntColony Optimization, in MIC'2001-4th Metaheuristics International Conference.2001.
[121]覃刚力and杨家本,自适应调整信息素的蚁群算法.信息与控制,2002.31(3): p.198-201.
[122]谢剑英and王颖,一种自适应蚁群算法及其仿真研究.系统仿真学报,2002.14(1): p.31-33.
[123]吴斌and史忠植,一种基于蚁群算法的TSP问题分段求解算法.计算机学报,2002.24(12): p.1328-1333.
[124] Dorigo, M., Maniezzo, V., and Colorni, A., The Ant System: An autocatalyticoptimizing Process. Technical RePort91-016Revised.1991, Dipartimento diElettronica, Politecnico di Milano: Milan, Italy.
[125]张纪会,高齐圣, and徐心和,自适应蚁群算法.控制理论与应用,2000.17(1): p.1-3.
[126] Stutzle, T. and Dorigo, M., ACO algorithms for the quadratic assignment Problem.New Ideas in Optimization,1999: p.33-50.
[127] Di Caro, G. and Dorigo, M., AntNet: Distributed stigmergetic control forcommunications networks. Journal of Artificial Intelligence Research,1998.9: p.317-365.
[128] Roli, A., Blum, C., and Dorigo, M., ACO for maximal constraint satisfaction Problems.Proeeedings of MIC'2001,2001.1: p.187-191.
[129] Solnon, C., Ants can solve constraint satisfaction problems. IEEE Transactions onEvolutionary Computation,2002.6(4): p.347-357.
[130] Merkle, D., Middendorf, M., and Schmeck, H. Ant colony optimization forresource-constrained project scheduling. in Proceedings of the Genetic andEvolutionary Computation Conference.2000.
[131] Wodrich, M. and Bilchev, G., Cooperative distributed search: the ants way.Control andCybernetics.26,1997.3(413-445).
[132] Jayaraman, V.K., et al., Ant colony framework for optimal design and scheduling ofbatch Plants. Computers&Chemical Engineering,2000.24: p.1901-1912.
[133] Mathur, M., et al., Ant colony approach to continuous function optimization.Ind.Eng.Chem.Res,2000.39: p.3814-3822.
[134] Bauer, A., et al., An ant colony optimization approach for the single machinetotaltardiness problem, in Evolutionary Computation,1999. CEC99.1999:Washington, DC, USA.
[135] Bauer, A., et al., Minimizing Total Tardiness on a Single Machine Using Ant ColonyOptimization. Central European Journal for Operations Research and Economics,2000.8(2): p.17.
[136] Merkle, D. and Middendorf, M., An Ant Algorithm with a new Pheromone EvaluationRule for Total Tardiness Problems. Computer Science,2000.1803.
[137] Besten, M.d., Stutzle, T., and Dorigo, M., Ant Colony Optimization for the TotalWeighted Tardiness Problem, in Conference on Parallel Problem Solving from Nature.2000.
[138]陈义保, et al.,基于蚁群系统的工件排序问题的一种新算法.系统工程学报,2002.17(5): p.476-480.
[139] Stutzle, T., An ant approach to the flow shop problem, in proceedings of EuropeanCongress on IntelligentTechniques and Soft ComPuting.1998. p.1560-1564.
[140] Colorni, A., et al., Ant system for job-shop scheduling. Belgian Journal OperationResearch (JORBEL),1994.34(1): p.39-53.
[141] Zwaan, S.v.d. and Marques, C., Ant Colony Optimisation for Job Shop Scheduling.1999.
[142]邢文训and谢金星,现代优化计算方法.2000:清华大学出版社.
[143]郑大钟and赵千川,离散事件动态系统.2001:清华大学出版社.
[144] Blum, C. and Sampels, M. Ant colony optimization for FOP shop scheduling: a casestudy on different pheromone representations. in Evolutionary Computation,2002.CEC '02. Proceedings of the2002Congress on.2002.
[145] Blum, C. and Sampels, M. When Model Bias Is Stronger than Selection Pressure inParallel Problem Solving from Nature-PPSN VII:7th International Conference.2002.Granada, Spain: Springer Berlin/Heidelberg.
[146] Balas, E., Machine Sequencing via Disjunctive Graphs: An Implicit EnumerationAlgorithm. Operations Research,1969.17(6): p.941-957.
[147] Pinedo, M.L., Scheduling: Theory, Algorithms, and Systems.2000, New Jersey:Prentice-Hall.
[148] Singer, M., Decomposition methods for large job shops. Computers&OperationsResearch,2001.28(3): p.193-207.
[149] Nowicki, E. and Smutnicki, C., A fast taboo search algorithm for the job shop problem.Management Science,1996.42(6): p.797-813.
[150] Ikura, Y. and Gimple, M., Efficient scheduling algorithms for a single batch processingmachine. Operations Research Letters,1986.5(2): p.61-65.
[151] Lee, C.-Y., Uzsoy, R., and Martin-Vega, L.A., Efficient algorithms for schedulingsemiconductor burn-in operations. Operations Research,1992.40(4): p.764-775.
[152] Ahmadi, J.H., et al., Batching and scheduling jobs on batch and discrete processors.Operations Research,1992.40: p.750-763.
[153] Fowler, J.W., Phillips, D.T., and Hogg, G.L., Real-time control of multiproductbulk-service semiconductor manufacturing processes. Semiconductor Manufacturing,IEEE Transactions on,1992.5(2): p.158-163.
[154] Ham, M. and Fowler, J.W., Scheduling of wet etch and furnace operations with nextarrival control heuristic. International Journal of Advanced Manufacturing Technology,2008.38(9-10): p.1006-1017.
[155] Weng, W.W. and Leachman, R.C., An improved methodology for real-time productiondecision at batch-process work station. IEEE Transactions on SemiconductorManufacturing,1993.6(3): p.219-225.
[156] Chandra, P. and Gupta, S., An analysis of a last-station-bottleneck semiconductorpackaging line.1992, Faculty of Management, McGill University.
[157] Uzsoy, R. and Yang, Y., Minimizing total weighted completion time on a single batchprocessing machine. Production and Operations Management,1997.6: p.57-73.
[158] Lee, C.Y. and Uzsoy, R., Minimizing makespan on a single batch processing machinewith dynamic job arrivals.1996, School of Industrial Engineering, Purdue University.
[159] Chandru, V., Lee, C.Y., and Uzsoy, R., Minimizing total completion time on batchprocessing machines. International Journal of Producton Research,1993.31: p.2097-2121.
[160] Chandru, V., Lee, C.Y., and Uzsoy, R., Minimizing total completion time on a batchprocessing machine with job families. Operations Research Letters,1993.13: p.61-65.
[161] Brucker, P., et al., Scheduling a batching machine. Journal of Scheduling,1998.1: p.31–54.
[162] Li, L., Qiao, F., and Wu, Q.D., ACO-based multi-objective scheduling of parallelbatch processing machines with advanced process control constraints TheInternational Journal of Advanced Manufacturing Technology,2009.
[163] Dobson, G. and Nambimadom, R.S., The batch loading and scheduling problem.Operations Research,2001.49(1): p.52-65.
[164] Hochbaum, D.S. and Landy, D., Algorithms and heuristics for schedulingsemiconductor burn-in operations.1994, Department of Industrial Engineering andOperations Research, University of California, Berkeley.
[165] Uzsoy, R., Scheduling a single batch processing machine with nonidentical job sizes.International Journal of Production Research,1994.32: p.1615-1635.
[166] Azizoglu, M. and Webster, S., Scheduling a batch processing machine withincompatible job families. Computers and Industrial Engineering,2001.39(3-4): p.325-335.
[167] Sevaux, M. and Peres, S.D., Genetic algorithms to minimize the weighted number oflate jobs on a single machine. European Journal of Operational Research,2003.151(2):p.296-306.
[168] Koksalan, M. and Keha, A.B., Using genetic algorithms for single machine bicriteriascheduling problems. European Journal of Operational Research,2003.145(3): p.543-556.
[169] Koh, S.G., et al., Scheduling a single batch processing machine with arbitrary jobsizes and incompatible job families. International Journal of Production Economics,2005.98(1): p.81-96.
[170] Cheng, B.-Y., et al. A chaotic Ant Colony Optimization method for scheduling a singlebatch-processing machine with non-identical job sizes. in Evolutionary Computation.2008.
[171] Akturk, M.S. and Ozdemir, D., A new dominance rule to minimize total weightedtardiness with unequal release dates. European Journal of Operational Research,2001.135(2): p.394-412.
[172] El Adl, M.K., Rodriguez, A.A., and Tsakalis, K.S. Hierarchical modeling and controlof re-entrant semiconductor manufacturing facilities. in Proceedings of the35th IEEEConference on Decision and Control.1996. Kobe, Jpn.
[173] Liu, H., Fung, R.Y.K., and Jiang, Z., Modeling of semiconductor wafer fabricationsystems by extended object-oriented Petri nets. International Journal of ProductionResearch,2005.43(3): p.471-495.
[174] Zhang, H., et al., An EOPN-based real-time scheduling simulation platform of waferfabrication system. Journal of Shanghai Jiao Tong University,2006.40(11): p.1857-1863.
[175] Mason, S.J., Minimizing total weighted tardiness in complex job shops.2000, ArizonaState University.
[2]王阳元, et al.,面向产业需求的21世纪微电子技术的发展（上）.物理,2004.33(6):p.407-413.
[3] Kumar, P.R., Scheduling Semiconductor Manufacturing Plants. IEEE Control SystemsMagazine,1994.14(6): p.33-40.
[4] Narahari, Y. and Khan, L.M., Performance analysis of scheduling polices in re-entrantmanufacturing system. Computer Operations Research,1996.23(1): p.37-51.
[5] Hung, A.C., et al., Modeling, scheduling, and Prediction for Wafer Fabrication:Queueing Colored Petri-Net and GA Based Approach, in Proceedings of the2002IEEE International Conference on Robotics&Automation.2002. p.3187-3192.
[6] Bachrach, R., et al. Comparative analysis of300mm FAB architectures impact ofequipment sets on wafer cost and dynamic performance. in SemiconductorManufacturing Symposium,2001IEEE International.2001.
[7] Leachman, R.C., Kang, J., and Lin, V., SLIM: Short cycle time and low inventory inmanufacturing at Samsung electronics. Interfaces, Informs,2002.32(1): p.61-77.
[8] Zant, P.V.,芯片制造—半导体工艺制程实用教程（第四版）.2004,北京:电子工业出版社.
[9] Quirk, M.,半导体制造技术.2004,北京:电子工业出版社.
[10] McKay, K.N. and Wiers, V.C.S., Unifying the theory and practice of productionscheduling. Journal of Manufacturing System,1999.18(4): p.241～255.
[11]徐俊刚,戴国忠, and王宏安,生产调度理论和方法研究综述.计算机研究与发展,2004.41(2): p.257-267.
[12]陈荣秋,排序的理论和方法.1987,武汉:华中科技大学出版社.
[13] Wein, L.M., Scheduling Semiconductor Wafer Fabrication. IEEE Transactions onSemiconductor Manufacturing,1988.1(3).
[14] Chung, S.H. and Huang, H.W., The design of production activity control policy.Journal of the Chinese Institute of Industrial Engineering,1999.16(1): p.93–113.
[15] Lee, C.E. and Chen, C.W., A dispatching scheme involving move control andweighted due date for wafer foundries. IEEE Transaction on Component, Packaging,and Manufacturing Technology Part C,1997.20(4): p.268–277.
[16] Glassey, C.R. and Resende, M.G.C., Closed-loop job release control for VLSI circuitmanufacturing. IEEE Transaction on Semiconductor Manufacturing,1988.1(1): p.36–46.
[17] Fowler, J.W., et al., Measurable improvements in cycle-time-constrained capacity, inIEEE International Symposium on Semiconductor Manufacturing ConferenceProceedings.1997. p. A21-A24.
[18] Lu, S.C.H., Ramaswamy, D., and Kumar, P.R., Efficient scheduling policies to reducemean and variance of cycle-time in semiconductor manufacturing plants. IEEETransaction on Semiconductor Manufacturing,1994.7(3): p.374–388.
[19] Glassey, C.R. and Weng, W.W., Dynamic batching heuristic for simultaneousprocessing. Semiconductor Manufacturing, IEEE Transactions on,1991.4(2): p.77-82.
[20] Lee, L.H., Tang, L.C., and Chan, S.C., Dispatching Heuristic for Wafer Fabrication, inProceedings of the2001Winter Simulation Conference.2001. p.1215-1219.
[21] Uzsoy, R., Church, L., and Ovacik, I., Dispatching rules for semiconductor testingoperations: a computational study, in IEEE/CHMT International ElectronicsManufacturing Technology Symposium.1992. p.272–276.
[22] Holthaus, O. and Rajendran, C., Efficient dispatching rules for scheduling in a jobshop. International Journal Production Economy,1997.48: p.87–105.
[23] Dessouky, M.M. and R.C., L., Dynamic Models of Production with MultipleOperation General Processing Times. Journal of the Operational Research Society,1997.48(6): p.647-654.
[24] Kumar, S. and Kumar, P.R., Queueing Network Models in the Design and Analysis ofSemiconductor Wafer Fabs. IEEE Transactions on Robotics and Automation,2001.17(5): p.548-561.
[25] Morton, T. and Pentico, D., Heuristic scheduling systems.1993, New York: Wiley.
[26] Sung, C. and Choung, Y., Minimizing makespan on a single burn-in oven insemiconductor manufacturing. European Journal Operation Research,2000.120: p.559-574.
[27] Chen, T.-R., Chen, C.-W., and Kao, J., Due windows scheduling for ic sort and testfacilities with precedence constrains via Lagrangian relaxation, in IEEE/SEMIInternational Semiconductor Manufacturing Science Symposium.1993. p.110–114.
[28] Chen, T.-R. and Hsia, T., Job shop scheduling with multiple resources and anapplication to a semiconductor testing facility, in Proceedings of the33rd IEEEConference on Decision and Control.1994. p.1564–1570.
[29] Chen, T.-R. and Hsia, T., Scheduling for IC sort and test facilities with precedenceconstrains via Lagrangian relaxation. Journal Manufacturing System,1997.16(2): p.117–128.
[30] Kaskavelis, C. and Caramanis, M. Application of a Lagrangian relaxation basedscheduling algorithm to a semiconductor testing facility. in Proceedings of the FourthInternational Conference on Computer Integrated Manufacturing and AutomationTechnology, IEEE.1994.
[31] Kaskavelis, C. and Caramanis, M., Efficient Lagrangian relaxation algorithms forindustrial size job-shop scheduling problems. IIE Transactions,1998.30: p.1085–1097.
[32] Sun, X., James, S., and Klein, C., Single-machine scheduling with sequence dependentsetup to minimize total weighted squared tardiness. IIE Transactions,1999.31: p.113–124.
[33] De, S. and Lee, A., Towards a knowledge-based scheduling system for semiconductortesting. International Journal Production Research,1998.36(4): p.1045–1073.
[34] Connors, D., Feigin, G., and Yao, D., Scheduling semiconductor lines using a fluidnetwork model. IIE Trans Robot Autom,1994.10(2): p.88–98.
[35] Neuts, M.F., A general class of bulk queues with Poisson input. The Annals ofMathematical Statistics,1967.38: p.759-770.
[36] Medhi, J., Waiting time distribution in a Poisson queue with a general bulk servicerule. Management Science,1975.21(7): p.777-782.
[37] Hopp, W., et al., Using an optimized queuing network model to support wafer fabdesign. IIE Solutions,2002.34: p.119–130.
[38] Huang, M.G., Chang, P.L., and Chou, Y.C., Analytic Approximations for MultiserverBatch-Service Work-Stations with Multiple Process Recipes in Semiconductor WaferFabrication. IEEE Transactions on Semiconductor Manufacturing,2001.14(4): p.395-405.
[39] Li, C.-L. and Lee, C.-Y., Scheduling with aggreable release time and due dates on abatch processing machine. European Jounal of Operational Research,1997.96: p.564-569.
[40] Sung, C.S., et al., Minimizing makespan on a single burn-in oven with job familiesand dynamics job arrivals. Computers&Operations Research,2002.29: p.995-1007.
[41] Burdick, R.G.A., A cost effective expert system for semiconductor manufacturing.Computer&Operations Research,1987.
[42] Aytug, H., et al., A review of machine learning in scheduling. IEEE Trans Eng Manage,1994.41(2): p.165–171.
[43] Huang, C.L., et al., Construction of production performance prediction system forsemiconductor manufacturing with artificial neural networks. International Journal ofProduction Research,1999.37(6): p.1387-1402.
[44] Liao, D.Y. and Wang, C.N., Neural-network-based delivery time estimates forprioritized300-mm automatic material handling operations. IEEE Transactions onSemiconductor Manufacturing,2004.17(3): p.324-332.
[45] Zhang, J., et al., Fuzzy neural networks based rescheduling strategies optimization ofsemiconductor fabrication line. Chinese Journal of Mechanical Engineering,2005.41(10): p.75-79.
[46] Azzaro-Pantel, C., et al., A fuzzy approach for performance modeling in a batch plant:application to semiconductor manufacturing. IEEE Transactions on Fuzzy System,1997.5(3): p.338-357.
[47] Zhou, M.C. and Jeng, M.D., Modeling, Analysis, Simulation, scheduling, and Controlof Semiconductor Manufacturing Systems: A Petri Net Approach. IEEE Transactionson Semiconductor Manufacturing,1998.11(3): p.333-357.
[48] Xiong, H. and Zhou, M., Scheduling of semiconductor test facility via petri nets andhybrid heuristic search. IEEE Trans Semicond Manuf,1998.11(3): p.384–393.
[49] Cerny, V., Thermodynamical approach to the traveling salesman problem: An efficientsimulation algorithm. Journal of Optimization Theory and Applications,1985.45(1): p.41-52.
[50] Yim, S. and Lee, D., Scheduling cluster tools in wafer fabrication using candidate listand simulated annealing. Journal Intelligent Manufacturing,1999.10(6): p.531–540.
[51] Erramilli, V. and Mason, S.J., Multiple Orders Per Job Compatible Batch Scheduling.Electronics Packaging Manufacturing, IEEE Transactions on,2006.29(4): p.285-296.
[52] Glover, F., Tabu Search-Part I. ORSA JOURNAL ON COMPUTING,1989.1(3): p.190-206.
[53] Glover, F., Tabu Search-Part II. ORSA JOURNAL ON COMPUTING,1990.2(1): p.4-32.
[54] Geiger, C., Kempf, K., and Uzsoy, R., A Tabu search approach to scheduling anautomated wet etch station. Journal of Manufacturing System,1997.16(2): p.102–116.
[55] Schwefel, H., Numerical optimization of computer models.1981, New York: JohnWiley&Sons, Inc.
[56] Fogel, L., Artificial intelligence through simulated evolution.1966, New York: JohnWiley&Sons.
[57] Holland, J., Adaptation in natural and artificial systems.1992: MIT Press Cambridge.
[58] Goldberg, D., Genetic algorithms in search, optimization and machine learning.1989,Boston: Wesley Longman Publishing.
[59] Liu, M. and Wu, C., Genetic algorithm using sequence rule chain for multi-objectiveoptimization in re-entrant micro-electronic production line. Robotics andComputer-Integrated Manufacturing,2004.20(3): p.225-236.
[60] Wang, C.S. and Uzsoy, R., A genetic algorithm to minimize maximum lateness on abatch processing machine. Computers and Operations Research,2002.29(12): p.1621-1640.
[61] Melouk, S., Damodaranb, P., and Chang, P.-Y., Minimizing makespan for singlemachine batch processing with non-identical job sizes using simulated annealingInternational journal of production economics,2004.87(2): p.141-147.
[62] M nch, L., et al., Heuristic scheduling of jobs on parallel batch machines withincompatible job families and unequal ready times. Computers&Operations Research,2005.32(11): p.2731-2750.
[63] SG, K., et al., Scheduling a single batch processing machine with arbitrary job sizesand incompatible job families. International Journal of Production Economics,2005.98: p.81–96.
[64] Dantzig, G.B. and Wolfe, P., Decomposition principle for linear programs. OperationsResearch,1960.8(1): p.101-111.
[65] Akker, J.M.v.d., Hurkens, C.A.J., and Savelsbergh, M.W.P., Time-indexedformulations for machine scheduling problems:column generation. INFORMS Journalon Computing,1998.12: p.111-124.
[66] Barnhart, C., et al., Brach-and-Price: column generation for huge integer programs.Operations Research,1998.36: p.316-329.
[67] Vanderbeck, F. and Savelsbergh, M.W.P., A generic view of Dantzig-Wolfedecomposition for integer programming. Operations Research Letters,2006.34: p.294-306.
[68] FISHER, M.L., The lagrangian relaxation met hod for solving integer programmingproblems. Management Science,1981.27(1): p.1-18.
[69] FISHER, M.L., An applications oriented guide to lagrangian relaxation. Interfaces,1985.15(2): p.10-21.
[70] Held, M. and Karp, R.M., The traveling salesman and minimum spanning trees.Operation Research,1970.18: p.1138-1162.
[71] Held, M. and Karp, R.M., The traveling salesman and minimum spanning trees:Part II.Mathematic Programming,1971.1: p.6-25.
[72] Fisher, M.L., Optimal solution of scheduling problems using Lagrange multipliers:PartI. Operation Research,1973.21: p.1114-1127.
[73] Fisher, M.L., et al., Surrogate duality relaxation for job shop scheduling. DiscreteApplied Mathematics,1983.5: p.65-75.
[74] Luh, P.B. and Hoitornt, D.J., Scheduling of manufacturing system using the lagrangianrelaxation technique. IEEE Transactions on Automatic Control,1993.38: p.1066-1079.
[75] Luh, P.B., et al., Lagrangian relaxation neural networks for job shop scheduling. IEEETransactions on Robotics and Automation,2000.16: p.78-88.
[76] Zhao, X., A new generation of optimization algorithms within the lagrangianrelaxation approach for job shop scheduling, in Ph.D.1999, University of Connecticut.
[77] Fisher, M.L., The lagrangian relaxation method for solving integer programmingproblems. Management Science,2004.50: p.1861-1871.
[78] GUIGNARD, M. and KIM, S., Lagrangian decomposition: a model yielding st rongerLagrangian bounds. Mathematical Programming,1987.39(2): p.215-228.
[79]吴清烈and徐南荣,大规模含整变量优化问题的一种分解方法.东南大学学报,1996.26(3): p.119-125.
[80] Benders, J.F., Partitioning procedure for solving mixed-variables programmingproblems. Numerische Mathematik,1962.4: p.238-252.
[81] Bassett, M., et al., Perspectives on model based integration of process operations.Computers and Chemical Engineering,1996.20(6-7): p.821-844.
[82] Bassett, M., Pekny, J., and Reklaitis, G., Decomposition techniques for the solution oflarge-scale scheduling problems. AIChE Journal,1996.42(12): p.3373-3387.
[83] Ovacik, I.M. and Uzsoy, R., Rolling horizon algorithms for a single-machine dynamicscheduling problem with sequence-dependent setup times. International Journal ofProduction Research,1994.32(6): p.1243.
[84] Ovacik, I.M. and Uzsoy, R., Rolling horizon procedures for dynamic parallel machinescheduling with sequence-dependent setup times. International Journal of ProductionResearch,1995.33(11): p.3173-3192.
[85] Upasani, A.A., Uzsoy, R., and Sourirajan, K., A Problem Reduction Approach forScheduling Semiconductor Wafer Fabrication Facilities. SemiconductorManufacturing, IEEE Transactions on2006.19(2): p.216-225
[86] Sourirajan, K. and Uzsoy, R., Hybrid decomposition heuristics for solving large-scalescheduling problems in semiconductor wafer fabrication. Journal of Scheduling,2007.10(1): p.41-65.
[87] Sannomiya, N. and Iima, H. Genetic algorithm approach to an optimal schedulingproblem for a large-scale complex manufacturing system. in IEEE SMC '99Conference Proceedings..1999. Tokyo.
[88] Rosl f, J., et al., A Short-Term Scheduling Problem in the Paper-Converting Industry.Computers&Chemical Engineering,1999.23(S): p. S861-S874.
[89] Rosl f, J., et al., Solving a large-scale industrial scheduling problem using MILPcombined with a heuristic procedure. European Journal of Operational Research2002.138(1): p.29-42.
[90] Fox, M.S., Constraint-directed search: A case study of job-shop scheduling.1983,Pittsburgh: Carnegie Mellon University.
[91] Chu, C., Portmann, M.C., and Proth, J.M., A splitting-up approach to simplifyjob-shop scheduling problems. International Journal of Production Research,1992.30(4): p.859-870.
[92] Sun, D. and Batta, R., Scheduling larger job shops: a decomposition approach.International Journal of Production Research,1996.34(7): p.2019-2033.
[93] Adams, J., Balas, E., and Zawack, D., The Shifting Bottleneck Procedure for Job ShopScheduling. Management Science,1988.34(3): p.11.
[94] Wang, C.-S., Decomposition heuristics for complex job shop scheduling.2000, PurdueUniversity.
[95] Dauzere-Peres, S. and Lasserre, J.B., A modified shifting bottleneck procedure forjob-shop scheduling. International Journal of Production Research,1993.31: p.923-932.
[96] Balas, E., Lenstra, J.K., and Vazacopoulos, A., The one-machine problem with delayedprecedence constraints and its use in job shop scheduling. Management Science,1995.41: p.94-109.
[97] Demirkol, E., Mehta, S., and Uzsoy, R., A computational study of shifting bottleneckprocedures for shop scheduling problems. Journal of Heuristic,1997.3: p.111-137.
[98] Luh, P.B. and Chen, H.X., An alterative framework to lagrangian relaxation approachfor job shop cheduling, in the38th Conference on Decision&Control.1999.
[99] Merkle, D. and Middendorf, M., Ant Colony Optimization with Global PheromoneEvaluation for Scheduling a Single Machine. Applied Intelligence,2003.18(1): p.105-111.
[100] Blum, C., ACO Applied to Group Shop Scheduling: A Case Study on Intensificationand Diversification, in Ant Algorithms: Third International Workshop, ANTS2002,Brussels, Belgium, September12-14,2002. Proceedings2002, Springer Berlin/Heidelberg. p.149-180.
[101]梁静,钱省三, and马良,基于双层蚂蚁算法的半导体炉管制程批调度研究.系统工程理论与实践,2005.12(25): p.96-101.
[102] Song, Y., et al., Bottleneck Station Scheduling in Semiconductor Assembly and TestManufacturing Using Ant Colony Optimization. Automation Science and Engineering,IEEE Transactions on,2007.4(4): p.569-578
[103]尹文君,刘民, and吴澄,进化计算在生产线调度研究中的现状与展望.计算机集成制造系统,2001.7(12): p.1-6.
[104] Dorigo, M., Optimization, learning and natural algorithms.1992, Politecnico diMilano.
[105] Dorigo, M., Bonabeau, E., and Theraulaz, G., Ant algorithms and stigmergy. FutureGeneration Computer Systems,2000.16: p.851-871.
[106] Dorigo, M. and Di Caro, G. The Ant Colony Optimization: a new meta-heuristic. inProeeedings of the IEEE International Conference on Evolutionary Computation.1999:IEEE Press.
[107] Dorigo, M., Di Caro, G., and Gambardella, L.M., Ant algorithms for disereteoptimization. Artificial Life,1999.5(2): p.137-172.
[108] Dorigo, M., Maniezzo, V., and Colorni, A., Ant system: optimization by a colony ofcooperating agents. Systems, Man and Cybernetics, Part B, IEEE Transactions on,1996.26(1): p.29-41.
[109] Maniezzo, V. and Colorni, A., The Ant System applied to the quadratic assignmentProblem. IEEE Trans. Knowledge Data Eng,1999.11(5): p.769-778.
[110] Gambardella, L.M. and Dorigo, M. Ant-Q: A reinforCement learning apProach to thetraveling salesman problem. in Proceedings of the Twelfth International Conferenceon Machine Learning(ML-95).1995: Morgan Kaufimann Publishers.
[111] Gambardella, L.M. and Dorigo, M. Solving symmetric and asymmetric TSPs by antcolonies. in Proeeedings of the IEEE International Conference on EvolutionaryComputation.1996: IEEE Press.
[112] Sutton, R. and Barto, A., Reinforcement Learning: An Introduction.1998, Cambridge,MA: MIT Press.
[113] Watkins, J.C.H., Q-learning. Machine Learning,1992.8: p.279-292.
[114] Dorigo, M. and Gambardella, L.M., Ant Colony System: A cooperative learningapproach to the traveling salesman Problem. IEEE Transactions on EvolutionaryComputation,1997.1(1): p.53-66.
[115] Stutzle, T. and Hoos, H.H. The MAX-MIN ant system and local search for thetraveling salesman problem. in IEEE4th International Conference on EvolutionaryComputation.1997: IEEE Press.
[116] Stutzle, T., An ant approach to the flow shop problem in Technical report AIDA-97-07.1997. p.7.
[117] Stützle, T. and Hoos, H.H., MAX-MIN Ant System. Future Generation ComputerSystems,2000(16): p.889-914.
[118] Bullnheimer, B., Hartl, R.F., and Stranss, C., A New Rank Based Version of the AntSystem: A Computational Study. Central European Journal for Operations Researehand Eeonomics,1999.7(1): p.25-38.
[119] Gutjahr, W.J., A graph-based ant system and its convergence. Future Gener.Comput.Syst.,2000.16(8): p.873-888.
[120] Blum, C., Roli, A., and Dorigo, M., HC-ACO: The Hyper-Cube Framework for AntColony Optimization, in MIC'2001-4th Metaheuristics International Conference.2001.
[121]覃刚力and杨家本,自适应调整信息素的蚁群算法.信息与控制,2002.31(3): p.198-201.
[122]谢剑英and王颖,一种自适应蚁群算法及其仿真研究.系统仿真学报,2002.14(1): p.31-33.
[123]吴斌and史忠植,一种基于蚁群算法的TSP问题分段求解算法.计算机学报,2002.24(12): p.1328-1333.
[124] Dorigo, M., Maniezzo, V., and Colorni, A., The Ant System: An autocatalyticoptimizing Process. Technical RePort91-016Revised.1991, Dipartimento diElettronica, Politecnico di Milano: Milan, Italy.
[125]张纪会,高齐圣, and徐心和,自适应蚁群算法.控制理论与应用,2000.17(1): p.1-3.
[126] Stutzle, T. and Dorigo, M., ACO algorithms for the quadratic assignment Problem.New Ideas in Optimization,1999: p.33-50.
[127] Di Caro, G. and Dorigo, M., AntNet: Distributed stigmergetic control forcommunications networks. Journal of Artificial Intelligence Research,1998.9: p.317-365.
[128] Roli, A., Blum, C., and Dorigo, M., ACO for maximal constraint satisfaction Problems.Proeeedings of MIC'2001,2001.1: p.187-191.
[129] Solnon, C., Ants can solve constraint satisfaction problems. IEEE Transactions onEvolutionary Computation,2002.6(4): p.347-357.
[130] Merkle, D., Middendorf, M., and Schmeck, H. Ant colony optimization forresource-constrained project scheduling. in Proceedings of the Genetic andEvolutionary Computation Conference.2000.
[131] Wodrich, M. and Bilchev, G., Cooperative distributed search: the ants way.Control andCybernetics.26,1997.3(413-445).
[132] Jayaraman, V.K., et al., Ant colony framework for optimal design and scheduling ofbatch Plants. Computers&Chemical Engineering,2000.24: p.1901-1912.
[133] Mathur, M., et al., Ant colony approach to continuous function optimization.Ind.Eng.Chem.Res,2000.39: p.3814-3822.
[134] Bauer, A., et al., An ant colony optimization approach for the single machinetotaltardiness problem, in Evolutionary Computation,1999. CEC99.1999:Washington, DC, USA.
[135] Bauer, A., et al., Minimizing Total Tardiness on a Single Machine Using Ant ColonyOptimization. Central European Journal for Operations Research and Economics,2000.8(2): p.17.
[136] Merkle, D. and Middendorf, M., An Ant Algorithm with a new Pheromone EvaluationRule for Total Tardiness Problems. Computer Science,2000.1803.
[137] Besten, M.d., Stutzle, T., and Dorigo, M., Ant Colony Optimization for the TotalWeighted Tardiness Problem, in Conference on Parallel Problem Solving from Nature.2000.
[138]陈义保, et al.,基于蚁群系统的工件排序问题的一种新算法.系统工程学报,2002.17(5): p.476-480.
[139] Stutzle, T., An ant approach to the flow shop problem, in proceedings of EuropeanCongress on IntelligentTechniques and Soft ComPuting.1998. p.1560-1564.
[140] Colorni, A., et al., Ant system for job-shop scheduling. Belgian Journal OperationResearch (JORBEL),1994.34(1): p.39-53.
[141] Zwaan, S.v.d. and Marques, C., Ant Colony Optimisation for Job Shop Scheduling.1999.
[142]邢文训and谢金星,现代优化计算方法.2000:清华大学出版社.
[143]郑大钟and赵千川,离散事件动态系统.2001:清华大学出版社.
[144] Blum, C. and Sampels, M. Ant colony optimization for FOP shop scheduling: a casestudy on different pheromone representations. in Evolutionary Computation,2002.CEC '02. Proceedings of the2002Congress on.2002.
[145] Blum, C. and Sampels, M. When Model Bias Is Stronger than Selection Pressure inParallel Problem Solving from Nature-PPSN VII:7th International Conference.2002.Granada, Spain: Springer Berlin/Heidelberg.
[146] Balas, E., Machine Sequencing via Disjunctive Graphs: An Implicit EnumerationAlgorithm. Operations Research,1969.17(6): p.941-957.
[147] Pinedo, M.L., Scheduling: Theory, Algorithms, and Systems.2000, New Jersey:Prentice-Hall.
[148] Singer, M., Decomposition methods for large job shops. Computers&OperationsResearch,2001.28(3): p.193-207.
[149] Nowicki, E. and Smutnicki, C., A fast taboo search algorithm for the job shop problem.Management Science,1996.42(6): p.797-813.
[150] Ikura, Y. and Gimple, M., Efficient scheduling algorithms for a single batch processingmachine. Operations Research Letters,1986.5(2): p.61-65.
[151] Lee, C.-Y., Uzsoy, R., and Martin-Vega, L.A., Efficient algorithms for schedulingsemiconductor burn-in operations. Operations Research,1992.40(4): p.764-775.
[152] Ahmadi, J.H., et al., Batching and scheduling jobs on batch and discrete processors.Operations Research,1992.40: p.750-763.
[153] Fowler, J.W., Phillips, D.T., and Hogg, G.L., Real-time control of multiproductbulk-service semiconductor manufacturing processes. Semiconductor Manufacturing,IEEE Transactions on,1992.5(2): p.158-163.
[154] Ham, M. and Fowler, J.W., Scheduling of wet etch and furnace operations with nextarrival control heuristic. International Journal of Advanced Manufacturing Technology,2008.38(9-10): p.1006-1017.
[155] Weng, W.W. and Leachman, R.C., An improved methodology for real-time productiondecision at batch-process work station. IEEE Transactions on SemiconductorManufacturing,1993.6(3): p.219-225.
[156] Chandra, P. and Gupta, S., An analysis of a last-station-bottleneck semiconductorpackaging line.1992, Faculty of Management, McGill University.
[157] Uzsoy, R. and Yang, Y., Minimizing total weighted completion time on a single batchprocessing machine. Production and Operations Management,1997.6: p.57-73.
[158] Lee, C.Y. and Uzsoy, R., Minimizing makespan on a single batch processing machinewith dynamic job arrivals.1996, School of Industrial Engineering, Purdue University.
[159] Chandru, V., Lee, C.Y., and Uzsoy, R., Minimizing total completion time on batchprocessing machines. International Journal of Producton Research,1993.31: p.2097-2121.
[160] Chandru, V., Lee, C.Y., and Uzsoy, R., Minimizing total completion time on a batchprocessing machine with job families. Operations Research Letters,1993.13: p.61-65.
[161] Brucker, P., et al., Scheduling a batching machine. Journal of Scheduling,1998.1: p.31–54.
[162] Li, L., Qiao, F., and Wu, Q.D., ACO-based multi-objective scheduling of parallelbatch processing machines with advanced process control constraints TheInternational Journal of Advanced Manufacturing Technology,2009.
[163] Dobson, G. and Nambimadom, R.S., The batch loading and scheduling problem.Operations Research,2001.49(1): p.52-65.
[164] Hochbaum, D.S. and Landy, D., Algorithms and heuristics for schedulingsemiconductor burn-in operations.1994, Department of Industrial Engineering andOperations Research, University of California, Berkeley.
[165] Uzsoy, R., Scheduling a single batch processing machine with nonidentical job sizes.International Journal of Production Research,1994.32: p.1615-1635.
[166] Azizoglu, M. and Webster, S., Scheduling a batch processing machine withincompatible job families. Computers and Industrial Engineering,2001.39(3-4): p.325-335.
[167] Sevaux, M. and Peres, S.D., Genetic algorithms to minimize the weighted number oflate jobs on a single machine. European Journal of Operational Research,2003.151(2):p.296-306.
[168] Koksalan, M. and Keha, A.B., Using genetic algorithms for single machine bicriteriascheduling problems. European Journal of Operational Research,2003.145(3): p.543-556.
[169] Koh, S.G., et al., Scheduling a single batch processing machine with arbitrary jobsizes and incompatible job families. International Journal of Production Economics,2005.98(1): p.81-96.
[170] Cheng, B.-Y., et al. A chaotic Ant Colony Optimization method for scheduling a singlebatch-processing machine with non-identical job sizes. in Evolutionary Computation.2008.
[171] Akturk, M.S. and Ozdemir, D., A new dominance rule to minimize total weightedtardiness with unequal release dates. European Journal of Operational Research,2001.135(2): p.394-412.
[172] El Adl, M.K., Rodriguez, A.A., and Tsakalis, K.S. Hierarchical modeling and controlof re-entrant semiconductor manufacturing facilities. in Proceedings of the35th IEEEConference on Decision and Control.1996. Kobe, Jpn.
[173] Liu, H., Fung, R.Y.K., and Jiang, Z., Modeling of semiconductor wafer fabricationsystems by extended object-oriented Petri nets. International Journal of ProductionResearch,2005.43(3): p.471-495.
[174] Zhang, H., et al., An EOPN-based real-time scheduling simulation platform of waferfabrication system. Journal of Shanghai Jiao Tong University,2006.40(11): p.1857-1863.
[175] Mason, S.J., Minimizing total weighted tardiness in complex job shops.2000, ArizonaState University.