面向柔性工艺的作业车间调度问题混合遗传算法
|
摘要
针对离散制造业的许多产品采用柔性工艺设计增加作业计划调度的复杂性这一问题,对传统的FJSP进行了工序顺序柔性的扩展,将问题抽象为柔性工艺的作业车间调度问题(flexible process Job-Shop scheduling problem,FPJSP)。以缩短生产周期为目标,建立了该问题的整数规划模型,并设计了混合遗传算法。该算法针对FPJSP的特点设计了改进的遗传算法染色体编码方式和遗传算子,并结合变邻域搜索算法,设计了适合求解该问题的四种不同的邻域结构进行动态邻域搜索,以提高遗传算法的邻域搜索性能。通过应用实例验证了所提出的混合遗传算法在求解FPJSP的求解效率和优化性能方面的有效性。
To deal with the problem that many products in discrete manufacturing factories had flexible process design which had increased the complexity of scheduling,this paper proposed the FPJSP as an extension of JSP,and built the mathematical model for the new scheduling problem to shorten the production cycle.It proposed the hybrid genetic algorithm(HGA) to solve the model.According to the characteristics of FPJSP,it designed the genetic algorithm(GA) with improved chromosome encoding schema and genetic operators.In combination with the variable neighborhood search algorithm(VNS),it designed four neighborhood structures to enable dynamic neighborhood search and improve the neighborhood search performance of GA.The experiment shows the effectiveness and optimize performance of the proposed HGA for solving FPJSP.
To deal with the problem that many products in discrete manufacturing factories had flexible process design which had increased the complexity of scheduling,this paper proposed the FPJSP as an extension of JSP,and built the mathematical model for the new scheduling problem to shorten the production cycle.It proposed the hybrid genetic algorithm(HGA) to solve the model.According to the characteristics of FPJSP,it designed the genetic algorithm(GA) with improved chromosome encoding schema and genetic operators.In combination with the variable neighborhood search algorithm(VNS),it designed four neighborhood structures to enable dynamic neighborhood search and improve the neighborhood search performance of GA.The experiment shows the effectiveness and optimize performance of the proposed HGA for solving FPJSP.
引文
[1]SAYGIN C,KILIC S E.Integrating flexible process plans with scheduling in flexible manufacturing systems[J].International Journal of Advanced Manufacturing Techonology,1999,15(4):268-280.
[2]BECK J C,FOX M S.Constraint-directed techniques for scheduling alternative activities[J].Artificial Intelligence,2000,121(1):211-250.
[3]BRUCKER P,SCHILIE R.Job-shop scheduling with multi-purpose machines[J].Computing,1990,45(4):369-375.
[4]GAO L,PENG C Y,ZHOU C,et al.Solving flexible job-shop scheduling problem using general particle swarm optimization[C]//Proc of the 36th International Conference on Computers&Industrial Engineering.2006:3018-3027.
[5]SAIDI-MEHRABAD M,FATTAHI P.Flexible job shop scheduling with tabu search algorithm[J].International Journal of Advanced Manufacturing Technology,2007,32(5-6):563-570.
[6]LOUKIL T,TEGHEM J,FORTEMPS P.A multi-objective production scheduling case study solved by simulated annealing[J].European Journal of Operational Research,2007,179(3):709-722.
[7]GIOVANNI D L,PEZZELLA F.An improved genetic algorithm for the distributed and flexible job-shop scheduling problem[J].European Journal of Operational Research,2010,200(2):395-408.
[8]AMIRI M,ZANDIEH M,YAZDANI M,et al.A variable neighbourhood search algorithm for the flexible job-shop scheduling problem[J].International Journal of Production Research,2010,48(19):5671-5689.
[9]GAO Jie,SUN Lin-yan,GEN M.A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems[J].Computers&Operations Research,2008,35(9):2892-2907.
[10]宋莉波,徐学军,孙延明,等.一种求解柔性工作车间调度问题的混合遗传算法[J].管理科学学报,2010,13(11):49-54.
[11]ZHANG Y F,SARAVANAN A N,FUH J Y H.Integration of process planning and scheduling by exploring the flexibility of process planning[J].International Journal of Production Research,2003,41(3):611-628.
[12]JAIN A,JAIN P K,SINGH I P.An integrated scheme for process planning and scheduling in FMS[J].International Journal of Advanced Manufacturing Technology,2006,30(11-12):1111-1118.
[13]OGUVEN C,OZBAKIR L,YAVUZ Y.Mathematical models for jobshop scheduling problems with routing and process plan flexibility[J].Applied Mathematical Modelling,2010,34(6):1539-1548.
[14]LI Xin-yu,SHAO Xin-yu,GAO Ling.Optimization of flexible process planning by genetic programming[J].International Journal of Advanced Manufacturing Technology,2008,38(1-2):143-153.
[15]SHAO Xin-yu,LI Xin-yu,GAO L,et al.Integration of process planning and scheduling:a modified genetic algorithm-based approach[J].Computer&Operations Research,2009,36(6):2082-2096.
[16]LI Xin-yu,SHAO Xin-yu,GAO Ling,et al.An effective hybrid algorithm for integrated process planning and scheduling[J].International Journal of Production Economics,2010,126(2):289-298.
[17]LI Xin-yu,GAO Ling,SHAO Xin-yu.An active learning genetic algorithm for integrated process planning and scheduling[J].Expert Systems with Applications,2012,39(8):6683-6691.
[18]张国辉,高亮,李培根,等.改进遗传算法求解柔性作业车间调度问题[J].机械工程学报,2009,45(7):145-151.
[19]潘全科,王文宏,朱剑英,等.基于粒子群优化和变邻域搜索的混合调度算法[J].计算机集成制造系统,2007,13(2):323-328.
[20]黄学文,马雪丽,曹德弼.工序顺序柔性的作业车间调度问题的改进遗传算法求解[J].运筹与管理,2013,22(1):65-70.
[21]QIAO Li-hong,LV Sheng-ping.An improved genetic algorithm for integrated process planning and scheduling[J].International Journal of Advanced Manufacturing Technology,2012,58(5-8):727-740.
[2]BECK J C,FOX M S.Constraint-directed techniques for scheduling alternative activities[J].Artificial Intelligence,2000,121(1):211-250.
[3]BRUCKER P,SCHILIE R.Job-shop scheduling with multi-purpose machines[J].Computing,1990,45(4):369-375.
[4]GAO L,PENG C Y,ZHOU C,et al.Solving flexible job-shop scheduling problem using general particle swarm optimization[C]//Proc of the 36th International Conference on Computers&Industrial Engineering.2006:3018-3027.
[5]SAIDI-MEHRABAD M,FATTAHI P.Flexible job shop scheduling with tabu search algorithm[J].International Journal of Advanced Manufacturing Technology,2007,32(5-6):563-570.
[6]LOUKIL T,TEGHEM J,FORTEMPS P.A multi-objective production scheduling case study solved by simulated annealing[J].European Journal of Operational Research,2007,179(3):709-722.
[7]GIOVANNI D L,PEZZELLA F.An improved genetic algorithm for the distributed and flexible job-shop scheduling problem[J].European Journal of Operational Research,2010,200(2):395-408.
[8]AMIRI M,ZANDIEH M,YAZDANI M,et al.A variable neighbourhood search algorithm for the flexible job-shop scheduling problem[J].International Journal of Production Research,2010,48(19):5671-5689.
[9]GAO Jie,SUN Lin-yan,GEN M.A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems[J].Computers&Operations Research,2008,35(9):2892-2907.
[10]宋莉波,徐学军,孙延明,等.一种求解柔性工作车间调度问题的混合遗传算法[J].管理科学学报,2010,13(11):49-54.
[11]ZHANG Y F,SARAVANAN A N,FUH J Y H.Integration of process planning and scheduling by exploring the flexibility of process planning[J].International Journal of Production Research,2003,41(3):611-628.
[12]JAIN A,JAIN P K,SINGH I P.An integrated scheme for process planning and scheduling in FMS[J].International Journal of Advanced Manufacturing Technology,2006,30(11-12):1111-1118.
[13]OGUVEN C,OZBAKIR L,YAVUZ Y.Mathematical models for jobshop scheduling problems with routing and process plan flexibility[J].Applied Mathematical Modelling,2010,34(6):1539-1548.
[14]LI Xin-yu,SHAO Xin-yu,GAO Ling.Optimization of flexible process planning by genetic programming[J].International Journal of Advanced Manufacturing Technology,2008,38(1-2):143-153.
[15]SHAO Xin-yu,LI Xin-yu,GAO L,et al.Integration of process planning and scheduling:a modified genetic algorithm-based approach[J].Computer&Operations Research,2009,36(6):2082-2096.
[16]LI Xin-yu,SHAO Xin-yu,GAO Ling,et al.An effective hybrid algorithm for integrated process planning and scheduling[J].International Journal of Production Economics,2010,126(2):289-298.
[17]LI Xin-yu,GAO Ling,SHAO Xin-yu.An active learning genetic algorithm for integrated process planning and scheduling[J].Expert Systems with Applications,2012,39(8):6683-6691.
[18]张国辉,高亮,李培根,等.改进遗传算法求解柔性作业车间调度问题[J].机械工程学报,2009,45(7):145-151.
[19]潘全科,王文宏,朱剑英,等.基于粒子群优化和变邻域搜索的混合调度算法[J].计算机集成制造系统,2007,13(2):323-328.
[20]黄学文,马雪丽,曹德弼.工序顺序柔性的作业车间调度问题的改进遗传算法求解[J].运筹与管理,2013,22(1):65-70.
[21]QIAO Li-hong,LV Sheng-ping.An improved genetic algorithm for integrated process planning and scheduling[J].International Journal of Advanced Manufacturing Technology,2012,58(5-8):727-740.