新型蛙跳算法求解总能耗约束FJSP
|
摘要
针对具有总能耗约束且以总延迟时间为目标的柔性作业车间调度问题(job shop scheduling problem,FJSP),首先将该问题转化为具有总能耗和总延迟时间的两目标问题,从而有效地处理能耗约束,然后提出了一种新型蛙跳算法直接优化转化后的两目标FJSP,该算法利用模因组构建和模因组搜索的新策略以及模因组内最好解的强化搜索以提高求解质量。计算实验和分析结果表明,新型蛙跳算法对所研究的FJSP具有较强的搜索能力和优势。
To solve the flexible job shop scheduling problem(FJSP)with total energy consumption constraints and the objective of total tardiness,the problem was transformed into the bi-objective FJSP with objectives of total energy consumption and total tardiness to effectively deal with energy consumption constraints,and then a novel shuffled frog leaping algorithm was proposed to directly optimize the transformed FJSP.Some new methods were used to improve the solution qualities,which were the new strategies of memeplex construction and memeplex search,and the reinforced search of the best solution in memeplex.The computational experiments and the result analyses show that the novel algorithm has a strong search ability to solve the considered problems.
To solve the flexible job shop scheduling problem(FJSP)with total energy consumption constraints and the objective of total tardiness,the problem was transformed into the bi-objective FJSP with objectives of total energy consumption and total tardiness to effectively deal with energy consumption constraints,and then a novel shuffled frog leaping algorithm was proposed to directly optimize the transformed FJSP.Some new methods were used to improve the solution qualities,which were the new strategies of memeplex construction and memeplex search,and the reinforced search of the best solution in memeplex.The computational experiments and the result analyses show that the novel algorithm has a strong search ability to solve the considered problems.
引文
[1] XIE N M,CHEN N L.Flexible Job Shop Scheduling Problem with Interval Grey Processing Time[J].Applied Soft Computing,2018,70:513-524.
[2] BRUKER P,SCHLIE R.Job-shop Scheduling with Multi-purpose Machines[J].Computing,1990,45(4):369-375.
[3] KACEM I,HAMMADI S,BORNE P.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-276.
[4] NING T,JIN H,SONG X D,et al.An Improved Quantum Genetic Algorithm Based on MAGTD for Dynamic FJSP[J].Journal of Ambient Intelligence&Humanized Computing,2018,9(4):931-940.
[5] AHMADI E,ZANDIEH M,FARROKH M,et al.A Multi-objective Optimization Approach for Flexible Job Shop Scheduling Problem under Random Machine Breakdown by Evolutionary Algorithm[J].Computers and Operations Research,2016,73(1):56-66.
[6] SHEN X N,HAN Y,FU J Z.Robustness Measures and Robust Scheduling for Multi-objective Stochastic Flexible Job Shop Scheduling Problems[J].Soft Computing,2017,21(21):1-24.
[7] LIU Y,TIWARI A.An Investigation into Minimizing Total Energy Consumption and Total Completion Time in a Flexible Job Shop for Recycling Carbon Fiber Reinforced Polymer[C]//The 22nd CIRP Conference on Life Cycle Engineering.Sydney,2015:722-727.
[8] KATO E R R,ARANHA G D A,TSUNAKI R H.A New Approach to Solve the Flexible Job Shop Problem Based on an Hybrid Particle Swarm Optimization and Random-restart Hill Climbing[J].Computers&Industrial Engineering,2018,125:178-189.
[9] SINGH M R,SINGH M,MAHAPATRA S S,et al.Particle Swarm Optimization Algorithm Embedded with Maximum Deviation Theory for Solving Multiobjective Flexible Job Shop Scheduling Problem[J].International Journal of Advanced Manufacturing Technology,2016,85(9):2353-2366.
[10] LI J Q,PAN Q K,TASGETIREN M F.A Discrete Artificial Bee Colony Algorithm for the Multi-objective Flexible Job-shop Scheduling Problem with Maintenance[J].Applied Mathematical Modeling,2014,38(3):1111-1132.
[11] LI J Q,PAN Q K,SUGANTHAN P N,et al.A Hybrid Tabu Search Algorithm with an Efficient Neighborhood Structure for the Flexible Job Shop Scheduling[J].International Journal of Advanced Manufacturing Technology,2011,52(5):683-697.
[12] JIA S,HU Z H.Path-relinking Tabu Search for the Multiobjective Flexible Job Shop Scheduling Problem[J].Computers and Operations Research,2014,47(1):11-26.
[13] BAGHERI A,ZANDIEH M.Bi-criteria Flexible Job-shop Scheduling with Sequence Dependent Setup Times Variable Neighborhood Search Approach[J].Journal of Manufacturing Systems,2011,30(1):8-15.
[14]雷德明,杨冬婧.具有总能耗约束的柔性作业车间调度问题研究[J].自动化学报,2018,44:1-9.LEI Deming,YANG Dongjing.Research on Flexible Job Shop Scheduling Problem with Total Energy Consumption Constraint[J].Acta Automatica Sinica,2018,44:1-9.
[15] WANG L,WANG S Y,LIU M.A Pareto-based Estimation of Distribution Algorithm for the Multi-objective Flexible Job Shop Scheduling Problem[J].International Journal of Production Research,2013,51(12):3574-3592.
[16] TANG D B,DAI M.Energy-efficient Approach to Minimizing the Energy Consumption in an Extended Job-shop Scheduling Problem[J].Chinese Journal of Mechanical Engineering,2015,28(5):1-8.
[17] HE Y,LI Y F,WU T,et al.An Energy-responsive Optimization Method for Machine Tool Selection and Operation Sequence in Flexible Machining Job Shops[J].Journal of Cleaner Production,2015,87(1):245-254.
[18] PIROOZFARD H,WONG K Y,WONG W P.Minimizing Total Carbon Footprint and Total Late Work Criterion in Flexible Job Shop Scheduling by Using an Improved Multi-objective Genetic Algorithm[J].Resources Conservation and Recycling,2018,128:267-283.
[19]蒋增强,左乐.低碳策略下的多目标柔性作业车间调度[J].计算机集成制造系统,2015,21(4):1023-1031.JIANG Zengqiang,ZUO Le.Multi-objective Flexible Job-shop Scheduling Based on Low-carbon Strategy[J].Computer Intergrated Manufacturing Systems,2015,21(4):1023-1031.
[20] DEB K,PRATAP A,AGARWAL S,et al.A Fast and Elitist Multi-objective Genetic Algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[21]唐立力.求解低碳调度问题的改进型候鸟优化算法[J].计算机工程与应用,2016,52(17):166-171.TANG Lili.Improved Migrating Birds Optimization Algorithm to Solve Low-carbon Scheduling Problem[J].Computer Engineering and Applications,2016,52(17):166-171.
[22] YIN L J,LI X Y,GAO L,et al.A Novel Mathematical Model and Multi-objective Method for the Low-carbon Flexible Job Shop Scheduling Problem[J].Sustainable Computing:Informatics and Systems,2017,13:15-30.
[23] LEI D M,ZHENG Y L,GUO X P.A Shuffled Frog Leaping Algorithm for Flexible Job Shop Scheduling with the Consideration of Energy Consumption[J].International Journal of Production Research,2017,55(11):3126-3140.
[24]雷德明.基于新型教学优化算法的低碳柔性作业车间调度[J].控制与决策,2017,32(9):1621-1627.LEI Deming.Novel Teaching-learning-based Optimization Algorithm for Low Carbon Scheduling of Flexible Job Shop[J].Control and Decision,2017,32(9):1621-1627.
[25]刘琼,许金辉,张超勇.基于改进蛙跳算法的鲁棒性车间布局[J].计算机集成制造系统,2014,20(8):1879-1886.LIU Qiong,XU Jinhui,ZHANG Chaoyong.Robust Layout of Floor Shop Based on Improved Shuffled Frog Leaping Algorithm[J].Computer Integrated Manufacturing Systems,2014,20(8):1879-1886.
[26]王松,孙振忠,郭建文,等.基于混合蛙跳算法的复杂产品装配序列规划[J].计算机集成制造系统,2014,20(12):2991-2999.WANG Song,SUN Zhenzhong,GUO Jianwen,et al.Research on Assembly Sequence Planning Based on Shuffled Frog Leaping Algorithm[J].Computer Integrated Manufacturing Systems,2014,20(12):2991-2999.
[27]王茜,张粒子,舒隽,等.基于阈值选择策略的改进混合蛙跳算法在电网规划中的应用[J].电力系统保护与控制,2011,39(3):34-39.WANG Xi,ZHANG Lizi,SHU Jun,et al.Application of Improved Shuffled Frog Leaping Algorithm Based on Threshold Selection Strategy in Transmission Network Planning[J].Power System Protection and Control,2011,39(3):34-39.
[28]罗雪晖,杨烨,李霞.改进混合蛙跳算法求解旅行商问题[J].通信学报,2009,30(7):130-135.LUO Xuehui,YANG Ye,LI Xia.Modified Shuffled Frog-leaping Algorithm to Solve Traveling Salesman Problem[J].Journal on Communications,2009,30(7):130-135.
[29]艾子义,雷德明.基于新型蛙跳算法的低碳柔性作业车间调度[J].控制理论与应用,2017,34(10):1361-1368.AI Ziyi,LEI Deming.A Novel Shuffled Frog Leaping Algorithm for Low Carbon Flexible Job Shop Scheduling[J].Control Theory&Applications,2017,34(10):1361-1368.
[30]崔文华,刘晓冰,王伟,等.混合蛙跳算法研究综述[J].控制与决策,2012,27(4):481-486.CUI Wenhua,LIU Xiaobing,WANG Wei,et al.Survey on Shuffled Frog Leaping Algorithm[J].Control and Decision,2012,27(4):481-486.
[31] DING J Y,SONG S J,WU C.Carbon-efficient Scheduling of Flow Shops by Multi-objective Optimization[J].European Journal of Operational Research,2016,248(3):758-771.
[32]王勇,蔡自兴,周育人,等.约束优化进化算法[J].软件学报,2009,20(1):11-29.WANG Yong,CAI Zixing,ZHOU Yuren,et al.Constrained Optimization Evolutionary Algorithms[J].Journal of Software,2009,20(1):11-29.
[33] PENG S Y.Hybrid Immune Clonal Particle Swarm Optimization Multi-objective Algorithm for Constrained Optimization Problems[J].International Journal of Patter Recognition and Artificial Intelligence,2017,31(1):2495-2508.
[34] EUSUFF M M,LANSEY K E.Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J].Journal of Water Resources Planning and Management,2003,129(3):210-225.
[35] LEI D M,GUO X P.A Shuffled Frog-leaping Algorithm for Hybrid Flow Shop Scheduling with Two Agents[J].Expert Systems with Applications,2015,42(23):9333-9339.
[36] BARNES J W,CHAMBERS J B.Flexible Job Shop Scheduling by Tabu Search[R].Austin:The University of Texas at Austin,1998.
[2] BRUKER P,SCHLIE R.Job-shop Scheduling with Multi-purpose Machines[J].Computing,1990,45(4):369-375.
[3] KACEM I,HAMMADI S,BORNE P.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-276.
[4] NING T,JIN H,SONG X D,et al.An Improved Quantum Genetic Algorithm Based on MAGTD for Dynamic FJSP[J].Journal of Ambient Intelligence&Humanized Computing,2018,9(4):931-940.
[5] AHMADI E,ZANDIEH M,FARROKH M,et al.A Multi-objective Optimization Approach for Flexible Job Shop Scheduling Problem under Random Machine Breakdown by Evolutionary Algorithm[J].Computers and Operations Research,2016,73(1):56-66.
[6] SHEN X N,HAN Y,FU J Z.Robustness Measures and Robust Scheduling for Multi-objective Stochastic Flexible Job Shop Scheduling Problems[J].Soft Computing,2017,21(21):1-24.
[7] LIU Y,TIWARI A.An Investigation into Minimizing Total Energy Consumption and Total Completion Time in a Flexible Job Shop for Recycling Carbon Fiber Reinforced Polymer[C]//The 22nd CIRP Conference on Life Cycle Engineering.Sydney,2015:722-727.
[8] KATO E R R,ARANHA G D A,TSUNAKI R H.A New Approach to Solve the Flexible Job Shop Problem Based on an Hybrid Particle Swarm Optimization and Random-restart Hill Climbing[J].Computers&Industrial Engineering,2018,125:178-189.
[9] SINGH M R,SINGH M,MAHAPATRA S S,et al.Particle Swarm Optimization Algorithm Embedded with Maximum Deviation Theory for Solving Multiobjective Flexible Job Shop Scheduling Problem[J].International Journal of Advanced Manufacturing Technology,2016,85(9):2353-2366.
[10] LI J Q,PAN Q K,TASGETIREN M F.A Discrete Artificial Bee Colony Algorithm for the Multi-objective Flexible Job-shop Scheduling Problem with Maintenance[J].Applied Mathematical Modeling,2014,38(3):1111-1132.
[11] LI J Q,PAN Q K,SUGANTHAN P N,et al.A Hybrid Tabu Search Algorithm with an Efficient Neighborhood Structure for the Flexible Job Shop Scheduling[J].International Journal of Advanced Manufacturing Technology,2011,52(5):683-697.
[12] JIA S,HU Z H.Path-relinking Tabu Search for the Multiobjective Flexible Job Shop Scheduling Problem[J].Computers and Operations Research,2014,47(1):11-26.
[13] BAGHERI A,ZANDIEH M.Bi-criteria Flexible Job-shop Scheduling with Sequence Dependent Setup Times Variable Neighborhood Search Approach[J].Journal of Manufacturing Systems,2011,30(1):8-15.
[14]雷德明,杨冬婧.具有总能耗约束的柔性作业车间调度问题研究[J].自动化学报,2018,44:1-9.LEI Deming,YANG Dongjing.Research on Flexible Job Shop Scheduling Problem with Total Energy Consumption Constraint[J].Acta Automatica Sinica,2018,44:1-9.
[15] WANG L,WANG S Y,LIU M.A Pareto-based Estimation of Distribution Algorithm for the Multi-objective Flexible Job Shop Scheduling Problem[J].International Journal of Production Research,2013,51(12):3574-3592.
[16] TANG D B,DAI M.Energy-efficient Approach to Minimizing the Energy Consumption in an Extended Job-shop Scheduling Problem[J].Chinese Journal of Mechanical Engineering,2015,28(5):1-8.
[17] HE Y,LI Y F,WU T,et al.An Energy-responsive Optimization Method for Machine Tool Selection and Operation Sequence in Flexible Machining Job Shops[J].Journal of Cleaner Production,2015,87(1):245-254.
[18] PIROOZFARD H,WONG K Y,WONG W P.Minimizing Total Carbon Footprint and Total Late Work Criterion in Flexible Job Shop Scheduling by Using an Improved Multi-objective Genetic Algorithm[J].Resources Conservation and Recycling,2018,128:267-283.
[19]蒋增强,左乐.低碳策略下的多目标柔性作业车间调度[J].计算机集成制造系统,2015,21(4):1023-1031.JIANG Zengqiang,ZUO Le.Multi-objective Flexible Job-shop Scheduling Based on Low-carbon Strategy[J].Computer Intergrated Manufacturing Systems,2015,21(4):1023-1031.
[20] DEB K,PRATAP A,AGARWAL S,et al.A Fast and Elitist Multi-objective Genetic Algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[21]唐立力.求解低碳调度问题的改进型候鸟优化算法[J].计算机工程与应用,2016,52(17):166-171.TANG Lili.Improved Migrating Birds Optimization Algorithm to Solve Low-carbon Scheduling Problem[J].Computer Engineering and Applications,2016,52(17):166-171.
[22] YIN L J,LI X Y,GAO L,et al.A Novel Mathematical Model and Multi-objective Method for the Low-carbon Flexible Job Shop Scheduling Problem[J].Sustainable Computing:Informatics and Systems,2017,13:15-30.
[23] LEI D M,ZHENG Y L,GUO X P.A Shuffled Frog Leaping Algorithm for Flexible Job Shop Scheduling with the Consideration of Energy Consumption[J].International Journal of Production Research,2017,55(11):3126-3140.
[24]雷德明.基于新型教学优化算法的低碳柔性作业车间调度[J].控制与决策,2017,32(9):1621-1627.LEI Deming.Novel Teaching-learning-based Optimization Algorithm for Low Carbon Scheduling of Flexible Job Shop[J].Control and Decision,2017,32(9):1621-1627.
[25]刘琼,许金辉,张超勇.基于改进蛙跳算法的鲁棒性车间布局[J].计算机集成制造系统,2014,20(8):1879-1886.LIU Qiong,XU Jinhui,ZHANG Chaoyong.Robust Layout of Floor Shop Based on Improved Shuffled Frog Leaping Algorithm[J].Computer Integrated Manufacturing Systems,2014,20(8):1879-1886.
[26]王松,孙振忠,郭建文,等.基于混合蛙跳算法的复杂产品装配序列规划[J].计算机集成制造系统,2014,20(12):2991-2999.WANG Song,SUN Zhenzhong,GUO Jianwen,et al.Research on Assembly Sequence Planning Based on Shuffled Frog Leaping Algorithm[J].Computer Integrated Manufacturing Systems,2014,20(12):2991-2999.
[27]王茜,张粒子,舒隽,等.基于阈值选择策略的改进混合蛙跳算法在电网规划中的应用[J].电力系统保护与控制,2011,39(3):34-39.WANG Xi,ZHANG Lizi,SHU Jun,et al.Application of Improved Shuffled Frog Leaping Algorithm Based on Threshold Selection Strategy in Transmission Network Planning[J].Power System Protection and Control,2011,39(3):34-39.
[28]罗雪晖,杨烨,李霞.改进混合蛙跳算法求解旅行商问题[J].通信学报,2009,30(7):130-135.LUO Xuehui,YANG Ye,LI Xia.Modified Shuffled Frog-leaping Algorithm to Solve Traveling Salesman Problem[J].Journal on Communications,2009,30(7):130-135.
[29]艾子义,雷德明.基于新型蛙跳算法的低碳柔性作业车间调度[J].控制理论与应用,2017,34(10):1361-1368.AI Ziyi,LEI Deming.A Novel Shuffled Frog Leaping Algorithm for Low Carbon Flexible Job Shop Scheduling[J].Control Theory&Applications,2017,34(10):1361-1368.
[30]崔文华,刘晓冰,王伟,等.混合蛙跳算法研究综述[J].控制与决策,2012,27(4):481-486.CUI Wenhua,LIU Xiaobing,WANG Wei,et al.Survey on Shuffled Frog Leaping Algorithm[J].Control and Decision,2012,27(4):481-486.
[31] DING J Y,SONG S J,WU C.Carbon-efficient Scheduling of Flow Shops by Multi-objective Optimization[J].European Journal of Operational Research,2016,248(3):758-771.
[32]王勇,蔡自兴,周育人,等.约束优化进化算法[J].软件学报,2009,20(1):11-29.WANG Yong,CAI Zixing,ZHOU Yuren,et al.Constrained Optimization Evolutionary Algorithms[J].Journal of Software,2009,20(1):11-29.
[33] PENG S Y.Hybrid Immune Clonal Particle Swarm Optimization Multi-objective Algorithm for Constrained Optimization Problems[J].International Journal of Patter Recognition and Artificial Intelligence,2017,31(1):2495-2508.
[34] EUSUFF M M,LANSEY K E.Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J].Journal of Water Resources Planning and Management,2003,129(3):210-225.
[35] LEI D M,GUO X P.A Shuffled Frog-leaping Algorithm for Hybrid Flow Shop Scheduling with Two Agents[J].Expert Systems with Applications,2015,42(23):9333-9339.
[36] BARNES J W,CHAMBERS J B.Flexible Job Shop Scheduling by Tabu Search[R].Austin:The University of Texas at Austin,1998.