改进遗传算法在作业车间优化调度中的应用研究
|
摘要
作业车间调度问题作为著名的机器调度问题之一,也是最困难的组合优化问题,在生产系统和工程应用中有着非常重要的意义,开发精确而有效的调度算法是近年来研究的热点。
本文首先对确定性的作业车间调度问题进行了详细的描述,并在当前研究的基础上,结合生产实际情况,对生产中因各种随机因素的影响而产生的不确定性调度问题进行了研究。把不确定的加工时间和交货期分别用三角模糊数和梯形模糊数表示,同时考虑模糊加工时间和模糊交货期,以最大化平均满意度作为优化目标,建立了模糊作业车间调度模型。
近年来,邻域搜索算法在作业车间调度问题中得到了广泛的应用,本文重点对其中的遗传算法进行了深入的研究。针对传统遗传算法在求解时存在早熟收敛和局部搜索能力差的缺点,本文采用两种改进方法来改善遗传算法的局部搜索能力,提高优化质量和搜索效率。
算法一首先采用双种群相互指导进化的思想,既增加了种群的多样性又提高了算法的抗早熟能力,同时采用一种优差染色体相互的交叉方式来避免局部最优,并且对基于工序的编码方式设计了一种新的交叉算子,避免因交叉操作产生不可行解。将改进的遗传算法应用于确定性的作业车间调度问题中,通过对经典算例的仿真,验证了该算法的可行性和有效性。
算法二采用遗传算法和模拟退火算法相结合的方法,利用模拟退火算法能概率性的跳出局部最优解的特性,让其承担遗传算法选择的压力,同时发挥遗传算法良好的全局最优特性,设计了一种性能优良的全局最优的混合优化算法。通过对模糊作业车间调度问题仿真,验证了该混合算法的有效性和实用性。
Job-shop scheduling problem is one of the well-known machine scheduling, and also the most difficult combinatorial optimization problems. It plays a significant role in production systems and engineering applications. The development of accurate and effective scheduling algorithm has come into the focus of research in recent years.
This dissertation firstly presents a detailed description of deterministic job-shop scheduling problem and then studies some uncertain scheduling problems arising in production due to a variety of random factors, with consideration of actual production processes. In this study, uncertain processing time and due date are denoted by a triangular fuzzy number and a trapezoid fuzzy number respectively, and at the same time factors like fuzzy processing time and fuzzy due date are considered. As a result, the model of the fuzzy job-shop scheduling problem is proposed, and the maximum average satisfaction is taken as the optimization objective.
In recent years, local search method has been widely applied to job-shop scheduling problem. This dissertation is intended to make deep investigation into genetic algorithm. It employs two kinds of methods to promote the local search function of traditional genetic algorithm, to tackle such problems as premature convergence and poor local search function and in turn to better optimization quality and search efficiency.
The first algorithm proposed, based upon the principle of mutually-guided evolution of two populations, not only increases the diversity of the population, but also improves the ability of resisting pre-maturity; at the same time, it uses the best and worst chromosome to crossover each other to avoid local optimum. And then for the operation-based representation, a new crossover operator is designed for avoiding unfeasible solution resulting from cross-operation. Application of the improved genetic algorithm in deterministic job-shop scheduling problems, and the simulation results of the classic example have proved the feasibility and effectiveness of the algorithm.
The second algorithm proposed combines genetic algorithm with simulated annealing algorithm. Simulated annealing algorithm can probably circumvent the local optimal solution. The algorithm uses simulated annealing to bear the selection pressure of genetic algorithm, and uses the good global optimum characteristics of the genetic algorithm. The paper proposes a global optimal of the hybrid optimization algorithm. The simulations of fuzzy job-shop scheduling show the effectiveness and practicality of the hybrid algorithm.
本文首先对确定性的作业车间调度问题进行了详细的描述,并在当前研究的基础上,结合生产实际情况,对生产中因各种随机因素的影响而产生的不确定性调度问题进行了研究。把不确定的加工时间和交货期分别用三角模糊数和梯形模糊数表示,同时考虑模糊加工时间和模糊交货期,以最大化平均满意度作为优化目标,建立了模糊作业车间调度模型。
近年来,邻域搜索算法在作业车间调度问题中得到了广泛的应用,本文重点对其中的遗传算法进行了深入的研究。针对传统遗传算法在求解时存在早熟收敛和局部搜索能力差的缺点,本文采用两种改进方法来改善遗传算法的局部搜索能力,提高优化质量和搜索效率。
算法一首先采用双种群相互指导进化的思想,既增加了种群的多样性又提高了算法的抗早熟能力,同时采用一种优差染色体相互的交叉方式来避免局部最优,并且对基于工序的编码方式设计了一种新的交叉算子,避免因交叉操作产生不可行解。将改进的遗传算法应用于确定性的作业车间调度问题中,通过对经典算例的仿真,验证了该算法的可行性和有效性。
算法二采用遗传算法和模拟退火算法相结合的方法,利用模拟退火算法能概率性的跳出局部最优解的特性,让其承担遗传算法选择的压力,同时发挥遗传算法良好的全局最优特性,设计了一种性能优良的全局最优的混合优化算法。通过对模糊作业车间调度问题仿真,验证了该混合算法的有效性和实用性。
Job-shop scheduling problem is one of the well-known machine scheduling, and also the most difficult combinatorial optimization problems. It plays a significant role in production systems and engineering applications. The development of accurate and effective scheduling algorithm has come into the focus of research in recent years.
This dissertation firstly presents a detailed description of deterministic job-shop scheduling problem and then studies some uncertain scheduling problems arising in production due to a variety of random factors, with consideration of actual production processes. In this study, uncertain processing time and due date are denoted by a triangular fuzzy number and a trapezoid fuzzy number respectively, and at the same time factors like fuzzy processing time and fuzzy due date are considered. As a result, the model of the fuzzy job-shop scheduling problem is proposed, and the maximum average satisfaction is taken as the optimization objective.
In recent years, local search method has been widely applied to job-shop scheduling problem. This dissertation is intended to make deep investigation into genetic algorithm. It employs two kinds of methods to promote the local search function of traditional genetic algorithm, to tackle such problems as premature convergence and poor local search function and in turn to better optimization quality and search efficiency.
The first algorithm proposed, based upon the principle of mutually-guided evolution of two populations, not only increases the diversity of the population, but also improves the ability of resisting pre-maturity; at the same time, it uses the best and worst chromosome to crossover each other to avoid local optimum. And then for the operation-based representation, a new crossover operator is designed for avoiding unfeasible solution resulting from cross-operation. Application of the improved genetic algorithm in deterministic job-shop scheduling problems, and the simulation results of the classic example have proved the feasibility and effectiveness of the algorithm.
The second algorithm proposed combines genetic algorithm with simulated annealing algorithm. Simulated annealing algorithm can probably circumvent the local optimal solution. The algorithm uses simulated annealing to bear the selection pressure of genetic algorithm, and uses the good global optimum characteristics of the genetic algorithm. The paper proposes a global optimal of the hybrid optimization algorithm. The simulations of fuzzy job-shop scheduling show the effectiveness and practicality of the hybrid algorithm.
引文
[1]王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003
[2]J.F.Muth,G.L.Thompson(eds.),Industrial Scheduling[M].Prentice Hall,Englewood Cliffs,New Jersey,1963
[3]于竟.基于遗传算法的Job-shop车间调度问题研究[D].南京理工大学硕士学位论文,2008
[4]Jain A.S,Meeran S,Deterministic Job-Shop Scheduling:Past,Present and Futuer[J].European Journal of Operational Researeh,1999,vol.113,issue2,390
[5]Lundgren M G;Lundgren J T,Persson J A.An optimization model for refinery production scheduling[J].International Journal of Production Economics,2002,78(3):255-270
[6]Harjunkoski I,Grossmann I E.A decomposition approach for the scheduling of a steel plant production[J].Computer and Chemical Engineering,2001,25(11):1647-1660
[7]Chen Haoxun,Chu ChengBin,Porth J M.A More Efficient Lagrangian Relaxation Approach to Job shop Scheduling Problems[C].Proeeedings.Proceeding of IEEE Int Confon Robotics and Automation,JaPan,1995:496-501
[8]王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007
[9]Vicente Vails,M.Angeles Perez,M.Sacramento Quintanilla,A Tabu Search to Machine Schedulnig[J].European Journal of Operational Researeh.1998,106,277-300
[10]Jackson J R.Scheduling a Production Line to Minimize Maximum Tardiness,Research Report 43,Management Science Research Projects,1955,University of California,Los Angeles,USA
[11]Smith W E.Various Optimizers for Single Stage Production[J].Naval Research Logistics Quarterly,1956,3:59-66
[12]Panwalkar S,Iskander W.A Survey of Scheduling Rules[J].Operations Research,1977,25(1):45-61
[13]Park Y,Balckboad T.Scheduling control knowledge for diagnostic problem solving [J].Artificial Intelligence.1995,(9):289-299
[14]Wu D,Ierapetritou M G.Decomposition approaches for the efficient solution of shortterm scheduling problems[J].Computer and Chemical Engineering,1994,18(9):859-875
[15]Adams J,Balas E,Zawack D.The Shifting Bottleneck Procedure for Job-Shop Scheduling [J].Management Science34,1988:391-401
[16]Holland J.H.Adaptation in Natural and Artificial Systems.The University of Michigan Press,Ann Arbor,91,1975
[17]Kirkpatrick S.Jr.,Gelatt C.D.and Vecchi M.P.,Optimization by Simulated Annealing [J].Science,1983,220:671-680
[18]Moon S,Hrymak A N.Scheduling of the batch annealing process deterministic case[J].Computers and Chemical Engineering,1999,23(9):1193-1208
[19]Glover F.Tabu Search-Part Ⅰ[J].ORSA Journal on Computing,1989,1(3):190-206
[20]蒋丽雯,基于遗传算法的车间作业调度问题研究[D].上海交通大学硕士学位论文,2007
[21]Fox M S,Smith S F.ISIS:A knowledge-based system for factory scheduling[J].Expert System,1984,1(1):25-49
[22]Dorigo M,Bonabeau E,Theraulaz.G Ant algorithm and stigmergy[J].Futer Generation Computer Systems,2000,16:851-871
[23]Colonri A,Dorigo M,etal.Ant system for job shop scheduling[J].Belgian Journal of Operations Research Statistics and Computer Seience,1994,34:39-53
[24]路飞,田国会,姜健,李晓磊.用基于模拟退火机制的多种群并行遗传算法解Job-shop调度问题[J].山东工业大学学报,2001,31(4):361-364
[25]杨晓梅,曾建潮.采用多个体交叉的遗传算法求解作业车间问题[J].计算机集成制造系统.2004,10(9):1114-1119
[26]张超勇,饶运清,刘向军.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程,2004,12(23):2149-2153
[27]Masato W,Kenichi I,Mitsuo G.A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem[J].Computer & Industrial Engineering,2005,4(48):743-752
[28]Dagli C,Sittisathanchai S.Genetic neuro-scheduler for job shop scheduling[J].Computers and Industrial Engineering,1993,25(1-4):267-270
[29]杨红红,吴智铭.混合遗传算法在柔性系统动态调度中的应用研[J].信息与控制,2001,30(5):392-397
[30]丁书斌,李启堂,徐继涛等.混合遗传算法求解经典作业车间调度问题[J].煤矿机械,2007,28(1):22-24
[31]Balas E.Machine sequencing via disjunctive graphs:an implicit enumeration algo- rithm[J].Operations Research,1969,17:941-957
[32]Pinedo,M.Scheduling:Theroy,Algoyithms,andSystems[M].北京:清华大学出版社,2005
[33]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002
[34]陈伟.基于遗传算法的绿色制造车间调度方法研究[D].武汉科技大学硕士学位论文,2005
[35]梁霞,黄明,梁旭.改进的自适应遗传算法及其在作业车间调度中的应用[J].大连铁道学院学报,2005,4(26):33-35
[36]张华,陶泽.基于混合遗传算法的车间调度问题的研究[J].机械设计及制造,2005(3):129-131
[37]耿兆强,邹益仁.基于遗传算法的作业车间模糊调度问题的研究[J].计算机集成制造系统,2002,8(8):616-620
[38]李富明,朱云龙,尹朝万,宋晓宇.基于模糊遗传算法的模糊调度研究[J].信息与控制,2004,33(6):703-708
[39]陈水利,李敬功,王向公.模糊集理论及其应用[M].北京:科学出版社,2005
[40]郭永丽.具有模糊参量的单机调度问题[D].北京师范大学硕士学位论文,2007
[41]Slowinski R,Hapke M.Scheduling under fuaainess[M].New York:Physica Verlag,2000
[42]黄洪钟.模糊设计[M].北京:机械工业出版社,1999
[43]Masatoshi Sakawa,Roubens Kubota.Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms[J].European Journal of Operation Research,2000(120):393-407
[44]SAKAWA M,KUBOTA R.Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms[J].European Journal of Operational Research,2000,(120):393-407
[45]汪定伟,王俊伟,王洪峰,张瑞友,郭哲.智能优化算法[M].北京:高等教育出版社,2006
[46]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001
[47]吴怡,刘民,吴澄.JSSP基本约束特点分析及调度算法[J].清华大学学报(自然科学版),2004,44(10):1380-1383
[48]雷英杰,张善文,李续武,周创明.MATLAB遗传算法工具箱及其应用[M].西安:西安电子科技大学出版社,2005
[49]王凌,刘波.微粒群优化与调度算法[M].北京:清华大学出版社,2008
[2]J.F.Muth,G.L.Thompson(eds.),Industrial Scheduling[M].Prentice Hall,Englewood Cliffs,New Jersey,1963
[3]于竟.基于遗传算法的Job-shop车间调度问题研究[D].南京理工大学硕士学位论文,2008
[4]Jain A.S,Meeran S,Deterministic Job-Shop Scheduling:Past,Present and Futuer[J].European Journal of Operational Researeh,1999,vol.113,issue2,390
[5]Lundgren M G;Lundgren J T,Persson J A.An optimization model for refinery production scheduling[J].International Journal of Production Economics,2002,78(3):255-270
[6]Harjunkoski I,Grossmann I E.A decomposition approach for the scheduling of a steel plant production[J].Computer and Chemical Engineering,2001,25(11):1647-1660
[7]Chen Haoxun,Chu ChengBin,Porth J M.A More Efficient Lagrangian Relaxation Approach to Job shop Scheduling Problems[C].Proeeedings.Proceeding of IEEE Int Confon Robotics and Automation,JaPan,1995:496-501
[8]王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007
[9]Vicente Vails,M.Angeles Perez,M.Sacramento Quintanilla,A Tabu Search to Machine Schedulnig[J].European Journal of Operational Researeh.1998,106,277-300
[10]Jackson J R.Scheduling a Production Line to Minimize Maximum Tardiness,Research Report 43,Management Science Research Projects,1955,University of California,Los Angeles,USA
[11]Smith W E.Various Optimizers for Single Stage Production[J].Naval Research Logistics Quarterly,1956,3:59-66
[12]Panwalkar S,Iskander W.A Survey of Scheduling Rules[J].Operations Research,1977,25(1):45-61
[13]Park Y,Balckboad T.Scheduling control knowledge for diagnostic problem solving [J].Artificial Intelligence.1995,(9):289-299
[14]Wu D,Ierapetritou M G.Decomposition approaches for the efficient solution of shortterm scheduling problems[J].Computer and Chemical Engineering,1994,18(9):859-875
[15]Adams J,Balas E,Zawack D.The Shifting Bottleneck Procedure for Job-Shop Scheduling [J].Management Science34,1988:391-401
[16]Holland J.H.Adaptation in Natural and Artificial Systems.The University of Michigan Press,Ann Arbor,91,1975
[17]Kirkpatrick S.Jr.,Gelatt C.D.and Vecchi M.P.,Optimization by Simulated Annealing [J].Science,1983,220:671-680
[18]Moon S,Hrymak A N.Scheduling of the batch annealing process deterministic case[J].Computers and Chemical Engineering,1999,23(9):1193-1208
[19]Glover F.Tabu Search-Part Ⅰ[J].ORSA Journal on Computing,1989,1(3):190-206
[20]蒋丽雯,基于遗传算法的车间作业调度问题研究[D].上海交通大学硕士学位论文,2007
[21]Fox M S,Smith S F.ISIS:A knowledge-based system for factory scheduling[J].Expert System,1984,1(1):25-49
[22]Dorigo M,Bonabeau E,Theraulaz.G Ant algorithm and stigmergy[J].Futer Generation Computer Systems,2000,16:851-871
[23]Colonri A,Dorigo M,etal.Ant system for job shop scheduling[J].Belgian Journal of Operations Research Statistics and Computer Seience,1994,34:39-53
[24]路飞,田国会,姜健,李晓磊.用基于模拟退火机制的多种群并行遗传算法解Job-shop调度问题[J].山东工业大学学报,2001,31(4):361-364
[25]杨晓梅,曾建潮.采用多个体交叉的遗传算法求解作业车间问题[J].计算机集成制造系统.2004,10(9):1114-1119
[26]张超勇,饶运清,刘向军.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程,2004,12(23):2149-2153
[27]Masato W,Kenichi I,Mitsuo G.A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem[J].Computer & Industrial Engineering,2005,4(48):743-752
[28]Dagli C,Sittisathanchai S.Genetic neuro-scheduler for job shop scheduling[J].Computers and Industrial Engineering,1993,25(1-4):267-270
[29]杨红红,吴智铭.混合遗传算法在柔性系统动态调度中的应用研[J].信息与控制,2001,30(5):392-397
[30]丁书斌,李启堂,徐继涛等.混合遗传算法求解经典作业车间调度问题[J].煤矿机械,2007,28(1):22-24
[31]Balas E.Machine sequencing via disjunctive graphs:an implicit enumeration algo- rithm[J].Operations Research,1969,17:941-957
[32]Pinedo,M.Scheduling:Theroy,Algoyithms,andSystems[M].北京:清华大学出版社,2005
[33]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002
[34]陈伟.基于遗传算法的绿色制造车间调度方法研究[D].武汉科技大学硕士学位论文,2005
[35]梁霞,黄明,梁旭.改进的自适应遗传算法及其在作业车间调度中的应用[J].大连铁道学院学报,2005,4(26):33-35
[36]张华,陶泽.基于混合遗传算法的车间调度问题的研究[J].机械设计及制造,2005(3):129-131
[37]耿兆强,邹益仁.基于遗传算法的作业车间模糊调度问题的研究[J].计算机集成制造系统,2002,8(8):616-620
[38]李富明,朱云龙,尹朝万,宋晓宇.基于模糊遗传算法的模糊调度研究[J].信息与控制,2004,33(6):703-708
[39]陈水利,李敬功,王向公.模糊集理论及其应用[M].北京:科学出版社,2005
[40]郭永丽.具有模糊参量的单机调度问题[D].北京师范大学硕士学位论文,2007
[41]Slowinski R,Hapke M.Scheduling under fuaainess[M].New York:Physica Verlag,2000
[42]黄洪钟.模糊设计[M].北京:机械工业出版社,1999
[43]Masatoshi Sakawa,Roubens Kubota.Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms[J].European Journal of Operation Research,2000(120):393-407
[44]SAKAWA M,KUBOTA R.Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms[J].European Journal of Operational Research,2000,(120):393-407
[45]汪定伟,王俊伟,王洪峰,张瑞友,郭哲.智能优化算法[M].北京:高等教育出版社,2006
[46]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001
[47]吴怡,刘民,吴澄.JSSP基本约束特点分析及调度算法[J].清华大学学报(自然科学版),2004,44(10):1380-1383
[48]雷英杰,张善文,李续武,周创明.MATLAB遗传算法工具箱及其应用[M].西安:西安电子科技大学出版社,2005
[49]王凌,刘波.微粒群优化与调度算法[M].北京:清华大学出版社,2008