差异工件单机批调度问题的优化算法研究
|
摘要
差异工件的单机批调度问题,具有古典调度和批调度的双重性质,在实际生产中有着广泛的应用;在计算复杂性方面,单机的制造跨度最小化问题为强NP-hard,加权完工时间最小化问题为NP-hard,单机问题的高复杂性对优化算法提出了挑战。因此对差异工件单机批调度问题的研究具有重要的现实意义和理论价值。本文首先对确定性单机问题进行求解,针对单机问题复杂度高、可行解数量大的特点,设计了有效的优化算法。然后将单机问题扩展到更接近现实情形的模糊环境中,建立模糊调度模型,并设计了求解模糊问题的优化算法。本文的主要工作和创新点如下:
(1)研究了蚁群算法(Ant Colony Optimization,ACO)在差异工件单机批调度问题中的应用。设计了高效的编码和解码方法;为了解决蚁群算法易陷入局部最优的问题,本文引入了Metropolis准则的概率选择机制作为路径激励策略,避免了由于路径重复而造成的局部最优;仿真实验验证了改进算法的有效性。另一方面,本文采用了混沌优化算子,将混沌优化的全局性能嵌入蚁群算法中,有效改进了解的质量。
(2)研究了微粒群算法(Particle Swarm Optimization,PSO)在差异工件单机批调度问题中的应用。首先设计了微粒的编码方法;然后采用了基于优先值向量的排序方法对微粒进行解码,有效的利用了微粒群算法在离散优化中的优势;最后利用批调度策略进行分批处理,获得优秀的可行解。
(3)研究了DNA进化算法(DNA Evolution Algorithm,DEA)在差异工件单机批调度问题中的应用。引入了分裂、水平选择、变异、垂直选择四种算子,对垂直选择算子进行了重新设计。充分利用了DNA进化算法实现简单、时间性能好的优势;同时,设计了随机选择机制对变异个体进行选择,使得求解过程能够跳出局部极值,实现全局优化。仿真实验的结果表明改进的DNA进化算法是有效的。
(4)研究了在模糊环境下的差异工件单机批调度问题。在现实生产过程中,加工信息的不确定性存在于两个方面:工件在批中的加工时间和批的间隔时间。因此本文将NSBM问题从上述研究的理想环境拓展到更接近现实情况的模糊环境中,建立了基于模糊数的制造跨度模型。在此基础上,设计了基于微粒群算法和差异演化的混合优化算法,获得了满意的实验结果。
The scheduling of a single batch-processing machine with non-identical job sizes is widely used in the real manufacturing and the problems of this kind are integrated with the characteristics of the classical scheduling and the batch scheduling.The problems of minimizing the makespan and the weighted completion time of a single machine are respectively strongly NP-hard and NP-hard.The optimization of a single batch-processing machine with non-identical job sizes has an influence on the industry and theoretical research.In this paper,intelligent algorithms are applied to solve the problems on a single batch-processing machine with non-identical job sizes and then,the deterministic problems are extended to fuzzy environment and algorithms are designed for the optimization of the fuzzy problems.The main innovations of this paper are listed as follows.
(1) The ant colony optimization(ACO) method is studied and designed for a single batch-processing machine with non-identical job sizes(NSBM).The coding and decoding mechanism of ACO is improved and in order to conquer the local optimum of ACO,the Metropolis criterion is adopted as the selection method of the paths to solve the problem.The simulation results demonstrate the efficiency of the algorithm.Additionally,the chaotic optimizer is introduced to improve the quality of ACO.
(2) The particle swarm optimization method(PSO) is applied to NSBM.Firstly the coding approach is designed and then the particles are sequenced using the priority value vectors which make PSO appropriate for the discrete optimization problem.In the decoding section,the feasible solutions are produced with batch scheduling mechanism.
(3) DNA evolutionary algorithm(DEA) is applied to the problem.The operators of division,level selection,mutation and vertical selection are introduced.DEA has a simple implementation and an outstanding time performance.Additionally,the vertical selection operator is improved by integrating a random selection method. An effective global optimization is achieved by jumping from the local optimum. The numerical results demonstrate the efficiency of DEA.
(4) The NSBM in fuzzy manufacturing system is studied in this paper.In the real industry,the uncertainty lies in two factors which consist of the processing time of the batches and the intemals between the batches.The NSBM is extended from the current ideal environment to fuzzy environment and the fuzzy model of minimizing the makespan is established.A hybrid algorithm based on different evolution(DE) and PSO is proposed for the optimization.The simulation results show the good performance of the method.
(1)研究了蚁群算法(Ant Colony Optimization,ACO)在差异工件单机批调度问题中的应用。设计了高效的编码和解码方法;为了解决蚁群算法易陷入局部最优的问题,本文引入了Metropolis准则的概率选择机制作为路径激励策略,避免了由于路径重复而造成的局部最优;仿真实验验证了改进算法的有效性。另一方面,本文采用了混沌优化算子,将混沌优化的全局性能嵌入蚁群算法中,有效改进了解的质量。
(2)研究了微粒群算法(Particle Swarm Optimization,PSO)在差异工件单机批调度问题中的应用。首先设计了微粒的编码方法;然后采用了基于优先值向量的排序方法对微粒进行解码,有效的利用了微粒群算法在离散优化中的优势;最后利用批调度策略进行分批处理,获得优秀的可行解。
(3)研究了DNA进化算法(DNA Evolution Algorithm,DEA)在差异工件单机批调度问题中的应用。引入了分裂、水平选择、变异、垂直选择四种算子,对垂直选择算子进行了重新设计。充分利用了DNA进化算法实现简单、时间性能好的优势;同时,设计了随机选择机制对变异个体进行选择,使得求解过程能够跳出局部极值,实现全局优化。仿真实验的结果表明改进的DNA进化算法是有效的。
(4)研究了在模糊环境下的差异工件单机批调度问题。在现实生产过程中,加工信息的不确定性存在于两个方面:工件在批中的加工时间和批的间隔时间。因此本文将NSBM问题从上述研究的理想环境拓展到更接近现实情况的模糊环境中,建立了基于模糊数的制造跨度模型。在此基础上,设计了基于微粒群算法和差异演化的混合优化算法,获得了满意的实验结果。
The scheduling of a single batch-processing machine with non-identical job sizes is widely used in the real manufacturing and the problems of this kind are integrated with the characteristics of the classical scheduling and the batch scheduling.The problems of minimizing the makespan and the weighted completion time of a single machine are respectively strongly NP-hard and NP-hard.The optimization of a single batch-processing machine with non-identical job sizes has an influence on the industry and theoretical research.In this paper,intelligent algorithms are applied to solve the problems on a single batch-processing machine with non-identical job sizes and then,the deterministic problems are extended to fuzzy environment and algorithms are designed for the optimization of the fuzzy problems.The main innovations of this paper are listed as follows.
(1) The ant colony optimization(ACO) method is studied and designed for a single batch-processing machine with non-identical job sizes(NSBM).The coding and decoding mechanism of ACO is improved and in order to conquer the local optimum of ACO,the Metropolis criterion is adopted as the selection method of the paths to solve the problem.The simulation results demonstrate the efficiency of the algorithm.Additionally,the chaotic optimizer is introduced to improve the quality of ACO.
(2) The particle swarm optimization method(PSO) is applied to NSBM.Firstly the coding approach is designed and then the particles are sequenced using the priority value vectors which make PSO appropriate for the discrete optimization problem.In the decoding section,the feasible solutions are produced with batch scheduling mechanism.
(3) DNA evolutionary algorithm(DEA) is applied to the problem.The operators of division,level selection,mutation and vertical selection are introduced.DEA has a simple implementation and an outstanding time performance.Additionally,the vertical selection operator is improved by integrating a random selection method. An effective global optimization is achieved by jumping from the local optimum. The numerical results demonstrate the efficiency of DEA.
(4) The NSBM in fuzzy manufacturing system is studied in this paper.In the real industry,the uncertainty lies in two factors which consist of the processing time of the batches and the intemals between the batches.The NSBM is extended from the current ideal environment to fuzzy environment and the fuzzy model of minimizing the makespan is established.A hybrid algorithm based on different evolution(DE) and PSO is proposed for the optimization.The simulation results show the good performance of the method.
引文
陈烨.带杂交算子的蚁群算法[J].计算机工程,2001,27(12):74-76.
丁永生,任立红,邵世煌。采用新的DNA进化算法自动谁Takagi-Sugeno模糊控制器[J].自动化学报,2001,27(4):510-520.
马建辉,牛海军.提前/拖期惩罚的单机批调度优化问题研究[J].制造业自动化,2002,24(7),65-67.
潘峰,陈杰,甘明刚,蔡涛,涂青彦。粒子群优化算法模型分析[J].自动化学报,2006,32(3):368-377.
吴超超,顾幸生.最优公共交货期单机提前/拖期调度和对应的批次送货[J].华东理工大学学报,2004,30(2):211-215.
吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
肖扬.2002.动态系统分析[M].北方交大出版社.
颜晨阳,张友鹏,熊伟清。一种新的蚁群优化算法信息素更新策略及其性能分析[J].计算机应用研究,2007,24(7):86-91.
张海刚,顾幸生。基于DNA进化算法的车辆调度问题[J].华东理工大学学报(自然科学版),2006,32(12):1463-1467.
张虹,李歧强,郭庆强,张鹏,高远。生产调度的模糊建模方法研究综述[J].中国工程科学,2005,7(12):92-97.
张玉忠,柏庆国,徐健腾.工件有尺寸且分两批到达的单机分批排序[J]运筹学学报,2006,10(4):99-105.
赵传立,张庆灵,唐恒永.极小化加权完成时间和的flowshop问题的算法[J].运筹学学报,2002,6(4):50-56.
赵玉芳,唐立新.极小化最大完工时间的单机连续型批调度问题[J]自动化学报,2006,32(5):730-737.
Afrati F.,Bampis E.,Chekuri C.,Karger D.,Kenyon C.,Khanna S.,Milis I.,Queyranne M.,Skutella M.,Stein C.,Sviridenko M.Approximation schemes for minimizing average weighted completion time with release dates[C].Proceeding of the FOCS'99,1999,32-43.
Ahmadi J.H.,Ahmadi R.H.,Dasu S.,Tang C.S.Batching and scheduling jobs on Batch and discrete processors[J].Operations Research,1992,39(4):750-763.
Allet S.Handling flexibility in a “generalized job shop” with a fuzzy approach[J].European Journal of Operation Research,2003,147(2):312-333.
Andreas C.Nearchou A differential evolution approach for the common due date early/tardy job scheduling problem[J].Computers & Operations Research,2008,35(4):1329-1343.
Atighehchian A.,Bijari M.,Tarkesh H.A novel hybrid algorithm for scheduling steel-making continuous casting production[J].Computers & Operations Research,2009,36(8):2450-2461.
Blum C.Beam-ACO—hybridizing ant colony optimization with beam search:an application to open shop scheduling[J].Computers & Operations Research,2005,32(6):1565-1591.
Blum C,Sampels M.An ant colony optimization algorithm for shop scheduling problems[J].Journal of Mathematical Modeling and Algorithms,2004,3(3):285-308.
Brucker P.,Gladky A.,Hoogeveen J.A.,Kovalyov M.Y.,Potts C.N.,Tautenhahn T.,Velde S.Scheduling a batching machine[J].Journal of Scheduling,1998,1(1):31-54.
Bullnheimer B.,Haiti R.R,Strauss C.A new rank based version of the ant system-a computational study[J].Central European Journal of Operational Research,1999,7(1):25-38.
Chandru V.,Lee C.Y.,Uzsoy R.Minimizing total completion time on batch processing machine with job families[J].Operations Research Letters,1993a:61-65.
Chanas S.,Kasperski.On two single machine scheduling problems with fuzzy processing times and fuzzy due dates[J].European Journal of Operational Research,2003,147(2):281-296.
Chanas S.,Kasperski A.Possible and necessary optimality of solutions in the single machine scheduling problem with fuzzy parameters[J].Fuzzy Sets and Systems,2004,142(3):359-371.
Chandru V.,Lee C.Y.,Uzsoy R.Minimizing total completion time on batch processing machine with job families[J].Operations Research Letters,1993a:61-65.
ClercM.The swarm and the queen:Towards a deterministic and adaptive particle swarm optimization[A].Proceeding of the Congress on Evolutionary Computation[C].Washington DC,1999:1951-1957.
Cynthia S.McCahon,E.Stanley Lee.Fuzzy job sequencing for a flow shop[J].European Journal of Operational Research,1992,62(3):294-301.
Damodaran P.,Chang P.Y.Heuristics to minimize makespan of parallel batch processing machines[J].International Journal of Manufacturing Technology,2008,37(10):1005-1013.
Damodaran P.,Manjeshwar P.K.,Srihari K.Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms[J].International Journal of Production Economics,2006,103(2):882-891.
Deng X.,Poon C.K.,Zhang Y.Approximation algorithms in batch processing[J].Lecture Notes in Computer Science,1999,1741:153-162.
Dorigo M.,Maniezzo V.,Colorni A.The Ant System:Optimization by a olony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41.
Dupont L.,Flipo C.D.Minimizing the makespan on a batch machine with nonidentical job sizes:an exact procedure[J].Computers & Operations Research,2002,29(7):807-819.
Fishkin A.V.,Jansen K.,Mastrolilli M.On minimizing average weighted completion time:a PTAS for the job shop problem with release dates.Lecture Notes in Computer Science 2906,2003,319-328.
Garey M.R.,Johnson D.S.Complexity results for multiprocessor scheduling under resource constraints[J].SLAM Journal on Computing,1975,4(4):397-411.
Garey M.R.,Johnson D.S.,Sethi R.The complexity of flowshop and jobshop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
Goemans M.X.,Queyranne M.,Schulz A.S.,Skutella M.,Wang Y..Single machine scheduling with release dates[J].SI AM Journal on Discrete Mathematics,2001,15(2):165-192.
Gonzalez T.,Sahni S.Open shop scheduling to minimize finish time[J].Journal of the Association for Computing Machinery,1976,23(4):665-680.
Gonzalez T.,Sahni S.Flowshop and jobshop schedules:complexity and approximation[J].Operations Research,1978,26(1):36-52.
Hall L.A..A polynomial approximation scheme for a constrained flow-shop scheduling problem[J].Mathematics of Operations Research,1994,19(1):68-85.
Hall L.A.Approximability of flow shop scheduling[J].Mathematical Programming,1998,82(1-2):175-190.
Hall L.A.,Schulz A.S.,Shmoys D.B.,and Wein J.Scheduling to minimize average completion time[J]:Off-line and On-line Approximation Algorithms.Mathematics of Operations Research,1997,22(3):513-544.
Heinonen J.,Pettersson F.Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem[J].Applied Mathematics and Computation,2007,187(2):989-998.
Hochbaum D.S.Approximation Algorithms for NP-hard Problems[M].PWS Publishing Company,1995.
Hochbaum D.S.,Landy D.Scheduling semiconductor burn-in operations to minimize total flow time[J],Operations Research,1997,45(6):874-885.
Hochbaum D.S.,Shmoys D.B.Using dual approximation algorithms for scheduling problems:Theoretical and practical results[J].Journal of the ACM,1987,34(1):144-162.
Hoogeveen J.A.,Kawaguchi T.Minimizing total completion time in a two-machine flowshop:Analysis of special cases.Mathematics of Operations Research,1999, 24(4):887-910.
Hoogeveen H.,Velde S.Scheduling by positional completion times:analysis of a two-stage flow shop problem with a batching machine[J].Mathematical Programming,1998,82(1-2):273-289.
Horn W.A.Minimizing average flow time on parallel machines.[J].Operations Research,1973,21(3):846-847.
Huang K.L.,Liao C.J.Ant colony optimization combined with taboo search for the job shop scheduling problem[J].Computers & Operations Research,2008,35(4):1030-1046.
Ikura Y.,Gimple M.Efficient scheduling algorithms for a single batch processing machine[J].Operations Research Letters,1986,5(2):61-65.
Jansen K.,Solis-Oba R.,Sviridenko M.Makespan minimization in job shops:a linear time approximation scheme[J].SLAM Journal on Discrete Mathematics,2003,16(2):288-300.
Jackson J.R.An extension of Johnson's results on job lot scheduling[J].Naval Research Logistics Quarterly,1956,3:201-203.
Javadi B.,Mehrabad M.S.,Haji A.,Mahdavi I.,Jolai R,Amiri N.M.No-wait flow shop scheduling using fuzzy multi-objective linear programming[J].Journal of the Franklin Institute,2008,345(5):452-467.
Johnson S.M.Optimal two-and three-stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1(1):61-68.
Kacem I.,Hammadi S.,Borne R Pareto-optimality approach for flexible job-shop scheduling problems:hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation,2002,60(3-5):245-376.
Kashan A.H.,Karimi B.,Jolai R Minimizing makespan on a single batch processing machine with non-identical job sizes:a hybrid genetic approach[C]Proc.Evolutionary Computation in Combinatorial Optimization—6th European Conference,2006,Lecture Notes in Computer Science 3906:135-146.
Kennedy J,Eberhart R C.Particle swarm optimization[A].Proc.IEEE International Conference on Neural Networks,IV[C].Piscataway,NJ:IEEE Service Center, 1995:1942-1948.
Kokaslan M.,Keha A.B.Using genetic algorithms for single machine bicriteria scheduling problems[J].European Journal of Operational Research,2003,145(3):543-556.
Konno T.,Ishii H.An open shop scheduling problem with fuzzy allowable time and fuzzy resource constraint[J].Fuzzy Sets and Systems,2000,109(1):141-147.
Kuo I.H.,Horng S.J.,Kao T.W.,Liu T.L.,Lee C.L.,Terano T.,Pan Y.An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model[J].Expert Systems with Applications,2009,36(3)part 2:7027-7032.
Kuroda M.,Wang Z.Fuzzy job shop scheduling[J].International Journal of Production Economics,1996,44(1-2):45-51.
Lee C.Y.,Uzsoy R.Minimizing makespan on a single batch processing machine with dynamic job arrivals[J].International Journal of Production Research,1999,37(1):219-236.
Lei D.A Pareto archive particle swarm optimization for multi-objective job shop scheduling[J].Computers & Industrial Engineering,2008,54(4):960-971,
Kuo I.H.,Horng S.J.,Kao T.W.,Liu T.L.,Lee C.L.,Terano T.,Pan Y An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model[J].Expert Systems with Applications,2009,36(3)part 2:7027-7032.
Lenstra J.K.,Kan A.R.,Brucker P.Complexity of machine scheduling problems[J].Annals of Discrete Math.1977,1:343-362.
Li T.Y,Yorke J.A.Period three implies chaos[J].Am Math Monthly,1975,82(10):982-992.
Liao G,Tsao T.Using chaos search immune genetic and fuzzy system for short-term unit commitment algorithm[J].International Journal of Electrical Power and Energy Systems,2006,28(1):1-12.
Lian Z.,Gu X.,Jiao B.A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan[J].Chaos,Solitons & Fractals,2008,35(5):851-861.
Lei D.A Pareto archive particle swarm optimization for multi-objective job shop scheduling[J].Computers & Industrial Engineering,2008,54(4):960-971,
Liu Z.,Yu W.Scheduling one batch processor subject to job release dates[J].Discrete Applied Mathematics.2000,105(1):129-136.
Marcin L.P.,Tony W.Using genetic algorithms to optimize ACS-TSP[C].Proceeding of 3rd International workshop ANTS.Brussels,2002:282-287.
Masaya O.Chaotic neural networks with reinforced self-feedbacks and its application to N-Queen problem[J].Mathematics and Computers in Simulation,2002,59(4):305-317.
Melouk S.,Damodaran P.,Chang P.Y.Minimizing makespan for single machine batch processing with nonidentical job sizes using simulated annealing[J].International Journal of Production Economics,2004,87(2):141-147.
Nezhad S.S.,Assadi R.G.Preference ratio-based maximum operator approximation and its application in fuzzy flow shop scheduling[J].Applied Soft Computing,2008,8(1):759-766.
Niu Q.,Jiao B.,Gu X.Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time[J].Applied Mathematics and Computation,2008,205(1):148-158.
Onwubolu G,Davendra D.Scheduling flow shops using differential evolution algorithm[J].European Journal of Operational Research,2006,171(2):674-692.
Ott E.,Grebogi C,Yorke J.A.Controlling Chaos[J].Physical Review Letters,1990,64(11):1196-1199.
Pan Q.K.,Tasgetiren M.R,Liang Y.C.A discrete differential evolution algorithm for the permutation flowshop scheduling problem[J].Computers & Industrial Engineering,2008,55(4):795-816.
Pan Q.K.,Wang L.,Qian B.A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J].Computers & Operations Research,2009,36(8):2498-2511.
Poon C.K.,Zhang P.Minimizing makespan in batch machine scheduling[J].Lecture Notes in Computer Science,1999,37(1):219-236..
Potts C.N.Analysis of heuristics for two-machine flow-shop sequencing subject to selease dates[J].Mathematics of Operations Research,1985,10(4):576-584.
Potts C.N.,Strusevich V.A.,Tautenhahn T.Scheduling batches with simultaneous job processing for two-machine shop problems[J].Journal of Scheduling,2001,4(1):25-51.
Ridouard R,Richard P.,Martneau P.On-line scheduling on a batch processing machine with unbounded batch size to minimize the makespan[J].European Journal of Operational Research,2008,189(3):1327-1342.
Rossi A.,Dini G.Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method[J].Robotics and Computer-Integrated Manufacturing,2007,23(5):503-516.
Ruelle D.,Takens F.On the nature of turbulence[J].Communications of Mathematical Physics,1971,20(3):167-192.
Sakawa M.,Kubota R.Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms[J].European Journal of Operational Research,2000,120(2):393-407.
Sakawa M.,Mori T.An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate[J].Computers & Industrial Engineering,36(2):325-341.
Sevastianov S.,Woeginger G.Makespan minimization in open shops:a polynomial time approximation scheme[J],Mathematical Programming,1998,82(1):191-198.
Sevaux M.,Peres S.D.Genetic algorithms to minimize the weighted number of late jobs on a single machine[J].European Journal of Operational Research,2003,151(2):296-306.
Sha D.Y.,Hsu C.Y.A hybrid particle swarm optimization for job shop scheduling problem[J].Computers & Industrial Engineering,2006,51(4):791-808.
Sha D.Y.,Hsu C.Y.A new particle swarm optimization for the open shop scheduling problem[J].Computers & Operations Research,2008,35(10):3243-3261.
Shi Yuhui,Eberhart R.A modified particle swarm optimizer[A].Proceeding IEEE International Conference on Evolutionary Computation[C].Anchorage,1998:69-73.
Shi Yuhui,Eberhart R.Empirical study of particle swarm optimization[A].Proceeding of the Congress on Evolutionary Computation[C].Washington DC,1999:1945-1950.
Shi Yuhui,Eberhart R.Parameter select ion in particle swarm optimization[A].Proceeding of the 7th Annual Conference on Evolutionary Programming[C].Washington DC,1998:591-600.
Sinha S.C,Henrichs J.T.A general approach in the design of active controllers for nonlinear systems exhibiting chaos[J].International Journal of Bifurcation and Chaos,2000,10(1):165-178.
Skutella M.Convex quadratic and semi-definite programming relaxations in scheduling[J].Journal of the ACM,2001,48(2):206-242.
Smutnicki C.Some results of the worst-case analysis for flow sShop scheduling[J].European Journal of Operational Research,1998,109(1):66-87.
Stiitzle T.,Hoos H.H.Max-min ant system[J].Future Generation Computer System,12000,16:889-914.
Suganthan P N.Particle swarm optimiser with neighborhood operator[A].Proceeding of the Congress on Evolutionary Computation[C].Washington DC,1999:1958-1962.
Sung C.S.,Choung Y.I.Minimizing makespan on a single burn-in oven in semiconductor manufacturing[J].European Journal of Operation Research,2000,120(3):559-574.
Uzsoy R.Scheduling a single batch processing machine with non-identical job sizes[J].International Journal of Production Research,1994,32(7):1615-1635.
Van den Bergh R,Engelbrecht A.P.A study of particle swarm optimization particle trajectories[J].Information Sciences,2006,176(8):937-971.
Wang C,Wang D.,Ip W H.,Yuen D.W.The single machine ready time scheduling problem with fuzzy processing times[J].Fuzzy Sets and Systems,2002,127(2):117-129.
Wang J.A fuzzy robust scheduling approach for product development projects[J].European Journal of Operation Research,2004,152(1):180-194.
Yagmahan B.,Yenisey M.M.Ant colony optimization for multi-objective flow shop scheduling problem[J].Computers & Industrial Engineering,2008,54(3):411-420.
Yao J.S.,Lin F.T.Constructing a fuzzy flow-shop sequencing model based on statistical data[J].International Journal of Approximate Reasoning,2002,29(3):215-234.
Yu W,Li R H.An effective bidirectional evolutionary algorithm[J].Mini-Micro Computer Systems,2003,24(3):527-530.
Yuan X.,Cao B.,Yang B.,Yuan Y Hydrothermal scheduling using chaotic hybrid differential evolution[J].Energy Conversion and Management,2008,49(12):3627-3633.
Zhang C,Sun J.An alternate two phases particle swarm optimization algorithm for flow shop scheduling problem[J].Expert Systems with Applications,2009,36(3),part 1:5162-5167.
Zhang Y,Cao Z.An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan.Journal of combinatorial optimization,2008 16(2):119-126
丁永生,任立红,邵世煌。采用新的DNA进化算法自动谁Takagi-Sugeno模糊控制器[J].自动化学报,2001,27(4):510-520.
马建辉,牛海军.提前/拖期惩罚的单机批调度优化问题研究[J].制造业自动化,2002,24(7),65-67.
潘峰,陈杰,甘明刚,蔡涛,涂青彦。粒子群优化算法模型分析[J].自动化学报,2006,32(3):368-377.
吴超超,顾幸生.最优公共交货期单机提前/拖期调度和对应的批次送货[J].华东理工大学学报,2004,30(2):211-215.
吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
肖扬.2002.动态系统分析[M].北方交大出版社.
颜晨阳,张友鹏,熊伟清。一种新的蚁群优化算法信息素更新策略及其性能分析[J].计算机应用研究,2007,24(7):86-91.
张海刚,顾幸生。基于DNA进化算法的车辆调度问题[J].华东理工大学学报(自然科学版),2006,32(12):1463-1467.
张虹,李歧强,郭庆强,张鹏,高远。生产调度的模糊建模方法研究综述[J].中国工程科学,2005,7(12):92-97.
张玉忠,柏庆国,徐健腾.工件有尺寸且分两批到达的单机分批排序[J]运筹学学报,2006,10(4):99-105.
赵传立,张庆灵,唐恒永.极小化加权完成时间和的flowshop问题的算法[J].运筹学学报,2002,6(4):50-56.
赵玉芳,唐立新.极小化最大完工时间的单机连续型批调度问题[J]自动化学报,2006,32(5):730-737.
Afrati F.,Bampis E.,Chekuri C.,Karger D.,Kenyon C.,Khanna S.,Milis I.,Queyranne M.,Skutella M.,Stein C.,Sviridenko M.Approximation schemes for minimizing average weighted completion time with release dates[C].Proceeding of the FOCS'99,1999,32-43.
Ahmadi J.H.,Ahmadi R.H.,Dasu S.,Tang C.S.Batching and scheduling jobs on Batch and discrete processors[J].Operations Research,1992,39(4):750-763.
Allet S.Handling flexibility in a “generalized job shop” with a fuzzy approach[J].European Journal of Operation Research,2003,147(2):312-333.
Andreas C.Nearchou A differential evolution approach for the common due date early/tardy job scheduling problem[J].Computers & Operations Research,2008,35(4):1329-1343.
Atighehchian A.,Bijari M.,Tarkesh H.A novel hybrid algorithm for scheduling steel-making continuous casting production[J].Computers & Operations Research,2009,36(8):2450-2461.
Blum C.Beam-ACO—hybridizing ant colony optimization with beam search:an application to open shop scheduling[J].Computers & Operations Research,2005,32(6):1565-1591.
Blum C,Sampels M.An ant colony optimization algorithm for shop scheduling problems[J].Journal of Mathematical Modeling and Algorithms,2004,3(3):285-308.
Brucker P.,Gladky A.,Hoogeveen J.A.,Kovalyov M.Y.,Potts C.N.,Tautenhahn T.,Velde S.Scheduling a batching machine[J].Journal of Scheduling,1998,1(1):31-54.
Bullnheimer B.,Haiti R.R,Strauss C.A new rank based version of the ant system-a computational study[J].Central European Journal of Operational Research,1999,7(1):25-38.
Chandru V.,Lee C.Y.,Uzsoy R.Minimizing total completion time on batch processing machine with job families[J].Operations Research Letters,1993a:61-65.
Chanas S.,Kasperski.On two single machine scheduling problems with fuzzy processing times and fuzzy due dates[J].European Journal of Operational Research,2003,147(2):281-296.
Chanas S.,Kasperski A.Possible and necessary optimality of solutions in the single machine scheduling problem with fuzzy parameters[J].Fuzzy Sets and Systems,2004,142(3):359-371.
Chandru V.,Lee C.Y.,Uzsoy R.Minimizing total completion time on batch processing machine with job families[J].Operations Research Letters,1993a:61-65.
ClercM.The swarm and the queen:Towards a deterministic and adaptive particle swarm optimization[A].Proceeding of the Congress on Evolutionary Computation[C].Washington DC,1999:1951-1957.
Cynthia S.McCahon,E.Stanley Lee.Fuzzy job sequencing for a flow shop[J].European Journal of Operational Research,1992,62(3):294-301.
Damodaran P.,Chang P.Y.Heuristics to minimize makespan of parallel batch processing machines[J].International Journal of Manufacturing Technology,2008,37(10):1005-1013.
Damodaran P.,Manjeshwar P.K.,Srihari K.Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms[J].International Journal of Production Economics,2006,103(2):882-891.
Deng X.,Poon C.K.,Zhang Y.Approximation algorithms in batch processing[J].Lecture Notes in Computer Science,1999,1741:153-162.
Dorigo M.,Maniezzo V.,Colorni A.The Ant System:Optimization by a olony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41.
Dupont L.,Flipo C.D.Minimizing the makespan on a batch machine with nonidentical job sizes:an exact procedure[J].Computers & Operations Research,2002,29(7):807-819.
Fishkin A.V.,Jansen K.,Mastrolilli M.On minimizing average weighted completion time:a PTAS for the job shop problem with release dates.Lecture Notes in Computer Science 2906,2003,319-328.
Garey M.R.,Johnson D.S.Complexity results for multiprocessor scheduling under resource constraints[J].SLAM Journal on Computing,1975,4(4):397-411.
Garey M.R.,Johnson D.S.,Sethi R.The complexity of flowshop and jobshop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
Goemans M.X.,Queyranne M.,Schulz A.S.,Skutella M.,Wang Y..Single machine scheduling with release dates[J].SI AM Journal on Discrete Mathematics,2001,15(2):165-192.
Gonzalez T.,Sahni S.Open shop scheduling to minimize finish time[J].Journal of the Association for Computing Machinery,1976,23(4):665-680.
Gonzalez T.,Sahni S.Flowshop and jobshop schedules:complexity and approximation[J].Operations Research,1978,26(1):36-52.
Hall L.A..A polynomial approximation scheme for a constrained flow-shop scheduling problem[J].Mathematics of Operations Research,1994,19(1):68-85.
Hall L.A.Approximability of flow shop scheduling[J].Mathematical Programming,1998,82(1-2):175-190.
Hall L.A.,Schulz A.S.,Shmoys D.B.,and Wein J.Scheduling to minimize average completion time[J]:Off-line and On-line Approximation Algorithms.Mathematics of Operations Research,1997,22(3):513-544.
Heinonen J.,Pettersson F.Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem[J].Applied Mathematics and Computation,2007,187(2):989-998.
Hochbaum D.S.Approximation Algorithms for NP-hard Problems[M].PWS Publishing Company,1995.
Hochbaum D.S.,Landy D.Scheduling semiconductor burn-in operations to minimize total flow time[J],Operations Research,1997,45(6):874-885.
Hochbaum D.S.,Shmoys D.B.Using dual approximation algorithms for scheduling problems:Theoretical and practical results[J].Journal of the ACM,1987,34(1):144-162.
Hoogeveen J.A.,Kawaguchi T.Minimizing total completion time in a two-machine flowshop:Analysis of special cases.Mathematics of Operations Research,1999, 24(4):887-910.
Hoogeveen H.,Velde S.Scheduling by positional completion times:analysis of a two-stage flow shop problem with a batching machine[J].Mathematical Programming,1998,82(1-2):273-289.
Horn W.A.Minimizing average flow time on parallel machines.[J].Operations Research,1973,21(3):846-847.
Huang K.L.,Liao C.J.Ant colony optimization combined with taboo search for the job shop scheduling problem[J].Computers & Operations Research,2008,35(4):1030-1046.
Ikura Y.,Gimple M.Efficient scheduling algorithms for a single batch processing machine[J].Operations Research Letters,1986,5(2):61-65.
Jansen K.,Solis-Oba R.,Sviridenko M.Makespan minimization in job shops:a linear time approximation scheme[J].SLAM Journal on Discrete Mathematics,2003,16(2):288-300.
Jackson J.R.An extension of Johnson's results on job lot scheduling[J].Naval Research Logistics Quarterly,1956,3:201-203.
Javadi B.,Mehrabad M.S.,Haji A.,Mahdavi I.,Jolai R,Amiri N.M.No-wait flow shop scheduling using fuzzy multi-objective linear programming[J].Journal of the Franklin Institute,2008,345(5):452-467.
Johnson S.M.Optimal two-and three-stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1(1):61-68.
Kacem I.,Hammadi S.,Borne R Pareto-optimality approach for flexible job-shop scheduling problems:hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation,2002,60(3-5):245-376.
Kashan A.H.,Karimi B.,Jolai R Minimizing makespan on a single batch processing machine with non-identical job sizes:a hybrid genetic approach[C]Proc.Evolutionary Computation in Combinatorial Optimization—6th European Conference,2006,Lecture Notes in Computer Science 3906:135-146.
Kennedy J,Eberhart R C.Particle swarm optimization[A].Proc.IEEE International Conference on Neural Networks,IV[C].Piscataway,NJ:IEEE Service Center, 1995:1942-1948.
Kokaslan M.,Keha A.B.Using genetic algorithms for single machine bicriteria scheduling problems[J].European Journal of Operational Research,2003,145(3):543-556.
Konno T.,Ishii H.An open shop scheduling problem with fuzzy allowable time and fuzzy resource constraint[J].Fuzzy Sets and Systems,2000,109(1):141-147.
Kuo I.H.,Horng S.J.,Kao T.W.,Liu T.L.,Lee C.L.,Terano T.,Pan Y.An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model[J].Expert Systems with Applications,2009,36(3)part 2:7027-7032.
Kuroda M.,Wang Z.Fuzzy job shop scheduling[J].International Journal of Production Economics,1996,44(1-2):45-51.
Lee C.Y.,Uzsoy R.Minimizing makespan on a single batch processing machine with dynamic job arrivals[J].International Journal of Production Research,1999,37(1):219-236.
Lei D.A Pareto archive particle swarm optimization for multi-objective job shop scheduling[J].Computers & Industrial Engineering,2008,54(4):960-971,
Kuo I.H.,Horng S.J.,Kao T.W.,Liu T.L.,Lee C.L.,Terano T.,Pan Y An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model[J].Expert Systems with Applications,2009,36(3)part 2:7027-7032.
Lenstra J.K.,Kan A.R.,Brucker P.Complexity of machine scheduling problems[J].Annals of Discrete Math.1977,1:343-362.
Li T.Y,Yorke J.A.Period three implies chaos[J].Am Math Monthly,1975,82(10):982-992.
Liao G,Tsao T.Using chaos search immune genetic and fuzzy system for short-term unit commitment algorithm[J].International Journal of Electrical Power and Energy Systems,2006,28(1):1-12.
Lian Z.,Gu X.,Jiao B.A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan[J].Chaos,Solitons & Fractals,2008,35(5):851-861.
Lei D.A Pareto archive particle swarm optimization for multi-objective job shop scheduling[J].Computers & Industrial Engineering,2008,54(4):960-971,
Liu Z.,Yu W.Scheduling one batch processor subject to job release dates[J].Discrete Applied Mathematics.2000,105(1):129-136.
Marcin L.P.,Tony W.Using genetic algorithms to optimize ACS-TSP[C].Proceeding of 3rd International workshop ANTS.Brussels,2002:282-287.
Masaya O.Chaotic neural networks with reinforced self-feedbacks and its application to N-Queen problem[J].Mathematics and Computers in Simulation,2002,59(4):305-317.
Melouk S.,Damodaran P.,Chang P.Y.Minimizing makespan for single machine batch processing with nonidentical job sizes using simulated annealing[J].International Journal of Production Economics,2004,87(2):141-147.
Nezhad S.S.,Assadi R.G.Preference ratio-based maximum operator approximation and its application in fuzzy flow shop scheduling[J].Applied Soft Computing,2008,8(1):759-766.
Niu Q.,Jiao B.,Gu X.Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time[J].Applied Mathematics and Computation,2008,205(1):148-158.
Onwubolu G,Davendra D.Scheduling flow shops using differential evolution algorithm[J].European Journal of Operational Research,2006,171(2):674-692.
Ott E.,Grebogi C,Yorke J.A.Controlling Chaos[J].Physical Review Letters,1990,64(11):1196-1199.
Pan Q.K.,Tasgetiren M.R,Liang Y.C.A discrete differential evolution algorithm for the permutation flowshop scheduling problem[J].Computers & Industrial Engineering,2008,55(4):795-816.
Pan Q.K.,Wang L.,Qian B.A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J].Computers & Operations Research,2009,36(8):2498-2511.
Poon C.K.,Zhang P.Minimizing makespan in batch machine scheduling[J].Lecture Notes in Computer Science,1999,37(1):219-236..
Potts C.N.Analysis of heuristics for two-machine flow-shop sequencing subject to selease dates[J].Mathematics of Operations Research,1985,10(4):576-584.
Potts C.N.,Strusevich V.A.,Tautenhahn T.Scheduling batches with simultaneous job processing for two-machine shop problems[J].Journal of Scheduling,2001,4(1):25-51.
Ridouard R,Richard P.,Martneau P.On-line scheduling on a batch processing machine with unbounded batch size to minimize the makespan[J].European Journal of Operational Research,2008,189(3):1327-1342.
Rossi A.,Dini G.Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method[J].Robotics and Computer-Integrated Manufacturing,2007,23(5):503-516.
Ruelle D.,Takens F.On the nature of turbulence[J].Communications of Mathematical Physics,1971,20(3):167-192.
Sakawa M.,Kubota R.Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms[J].European Journal of Operational Research,2000,120(2):393-407.
Sakawa M.,Mori T.An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate[J].Computers & Industrial Engineering,36(2):325-341.
Sevastianov S.,Woeginger G.Makespan minimization in open shops:a polynomial time approximation scheme[J],Mathematical Programming,1998,82(1):191-198.
Sevaux M.,Peres S.D.Genetic algorithms to minimize the weighted number of late jobs on a single machine[J].European Journal of Operational Research,2003,151(2):296-306.
Sha D.Y.,Hsu C.Y.A hybrid particle swarm optimization for job shop scheduling problem[J].Computers & Industrial Engineering,2006,51(4):791-808.
Sha D.Y.,Hsu C.Y.A new particle swarm optimization for the open shop scheduling problem[J].Computers & Operations Research,2008,35(10):3243-3261.
Shi Yuhui,Eberhart R.A modified particle swarm optimizer[A].Proceeding IEEE International Conference on Evolutionary Computation[C].Anchorage,1998:69-73.
Shi Yuhui,Eberhart R.Empirical study of particle swarm optimization[A].Proceeding of the Congress on Evolutionary Computation[C].Washington DC,1999:1945-1950.
Shi Yuhui,Eberhart R.Parameter select ion in particle swarm optimization[A].Proceeding of the 7th Annual Conference on Evolutionary Programming[C].Washington DC,1998:591-600.
Sinha S.C,Henrichs J.T.A general approach in the design of active controllers for nonlinear systems exhibiting chaos[J].International Journal of Bifurcation and Chaos,2000,10(1):165-178.
Skutella M.Convex quadratic and semi-definite programming relaxations in scheduling[J].Journal of the ACM,2001,48(2):206-242.
Smutnicki C.Some results of the worst-case analysis for flow sShop scheduling[J].European Journal of Operational Research,1998,109(1):66-87.
Stiitzle T.,Hoos H.H.Max-min ant system[J].Future Generation Computer System,12000,16:889-914.
Suganthan P N.Particle swarm optimiser with neighborhood operator[A].Proceeding of the Congress on Evolutionary Computation[C].Washington DC,1999:1958-1962.
Sung C.S.,Choung Y.I.Minimizing makespan on a single burn-in oven in semiconductor manufacturing[J].European Journal of Operation Research,2000,120(3):559-574.
Uzsoy R.Scheduling a single batch processing machine with non-identical job sizes[J].International Journal of Production Research,1994,32(7):1615-1635.
Van den Bergh R,Engelbrecht A.P.A study of particle swarm optimization particle trajectories[J].Information Sciences,2006,176(8):937-971.
Wang C,Wang D.,Ip W H.,Yuen D.W.The single machine ready time scheduling problem with fuzzy processing times[J].Fuzzy Sets and Systems,2002,127(2):117-129.
Wang J.A fuzzy robust scheduling approach for product development projects[J].European Journal of Operation Research,2004,152(1):180-194.
Yagmahan B.,Yenisey M.M.Ant colony optimization for multi-objective flow shop scheduling problem[J].Computers & Industrial Engineering,2008,54(3):411-420.
Yao J.S.,Lin F.T.Constructing a fuzzy flow-shop sequencing model based on statistical data[J].International Journal of Approximate Reasoning,2002,29(3):215-234.
Yu W,Li R H.An effective bidirectional evolutionary algorithm[J].Mini-Micro Computer Systems,2003,24(3):527-530.
Yuan X.,Cao B.,Yang B.,Yuan Y Hydrothermal scheduling using chaotic hybrid differential evolution[J].Energy Conversion and Management,2008,49(12):3627-3633.
Zhang C,Sun J.An alternate two phases particle swarm optimization algorithm for flow shop scheduling problem[J].Expert Systems with Applications,2009,36(3),part 1:5162-5167.
Zhang Y,Cao Z.An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan.Journal of combinatorial optimization,2008 16(2):119-126