增强分布估计算法求解低碳分布式流水线调度
|
摘要
针对低碳分布式流水线调度问题(DFSP–LC),提出了一种基于序关系的增强分布估计算法(OEEDA),用于最小化最大完成时间和总碳排放量.在OEEDA的第1阶段,利用基于贝叶斯统计推断的分布估计算法(BEDA)在问题解空间进行一定时间的搜索,用于发现优质解并将其保存于非劣解集中.在OEEDA的第2阶段,提出了基于序关系的四维矩阵(OFDM)对优质解的序关系(即工件块结构及其位置信息)进行有效学习和积累,进而设计了在解中固定部分块结构的采样机制,可更加明确地指导算法的全局搜索方向.同时,引入基于解、工厂间、工厂内的3种不同Insert融合的搜索方式,对2个阶段全局搜索得到的优质解区域进行较为细致的局部搜索.最后,通过仿真实验和算法对比验证了OEEDA的有效性.
An enhanced estimation of distribution algorithm based on ordered relationship(OEEDA) is presented to minimize the makespan and total carbon emission for a low carbon scheduling of distributed flow shop problem(DFSP–LC). In the first stage of OEEDA, an estimation of distribution algorithm based on Bayesian statistical inference(BEDA) is utilized to perform the global search in the problem's solution space for a certain period of time, with the purpose of finding good solutions and storing them in the non-dominated set. In the second stage of OEEDA, a four-dimensional matrix based on ordered relationship(OFDM) is proposed to effectively learn and accumulate the excellent solutions' information of ordered relationship, i.e., the information of job blocks and their corresponding positions. Then, a sampling scheme that fixes some blocks in the solution is designed to guide the global search direction more clearly. Moreover, a search method based on three kinds of Insert operator, i.e., solution-based Insert, inter-factory Insert, and intra-factory Insert, is introduced to execute a more thorough local search from the promising regions obtained by the above two stages' global search. Finally, simulations and comparisons show the efficiency of the proposed OEEDA.
An enhanced estimation of distribution algorithm based on ordered relationship(OEEDA) is presented to minimize the makespan and total carbon emission for a low carbon scheduling of distributed flow shop problem(DFSP–LC). In the first stage of OEEDA, an estimation of distribution algorithm based on Bayesian statistical inference(BEDA) is utilized to perform the global search in the problem's solution space for a certain period of time, with the purpose of finding good solutions and storing them in the non-dominated set. In the second stage of OEEDA, a four-dimensional matrix based on ordered relationship(OFDM) is proposed to effectively learn and accumulate the excellent solutions' information of ordered relationship, i.e., the information of job blocks and their corresponding positions. Then, a sampling scheme that fixes some blocks in the solution is designed to guide the global search direction more clearly. Moreover, a search method based on three kinds of Insert operator, i.e., solution-based Insert, inter-factory Insert, and intra-factory Insert, is introduced to execute a more thorough local search from the promising regions obtained by the above two stages' global search. Finally, simulations and comparisons show the efficiency of the proposed OEEDA.
引文
[1]WANG L,SHEN W.Process Planning and Scheduling for Distributed Manufacturing.London:Springer,2007.
[2] FANG K, UHAN N, ZHAO F, et al. A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. Journal of Manufacturing Systems, 2011, 30(4):234–240.
[3] GILLES M, MEHMET B, JANET T. Operational methods for minimization of energy consumption of manufacturing equipment. International Journal of Production Research, 2007, 45(18/19):4247–4271.
[4] YAN J, LI L, ZHAO F, et al. A multi–level optimization approach for energy-efficient flexible flow shop scheduling. Journal of Cleaner Production, 2016, 137:1543–1552.
[5] TANG D, DAI M, SALIDO M A, et al. Energy–efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization. Computers in Industry, 2016, 81(C):82–95.
[6] ZHANG R, CHIONG R. Solving the energy-efficient job shop scheduling problem:a multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption. Journal of Cleaner Production, 2015, 112:3361–3375.
[7] DING J Y, SONG S, WU C. Carbon-efficient scheduling of flow shops by multi–objective optimization. European Journal of Operational Research, 2015, 248(3):758–771.
[8] AI Ziyi, LEI Deming. A novel shuffled frog leaping algorithm for low carbon flexible job shop scheduling. Control Theory&Applications,2017, 34(10):1361–1368.(艾子义,雷德明.基于新型蛙跳算法的低碳柔性作业车间调度.控制理论与应用, 2017, 34(10):1361–1368.)
[9] LU C, GAO L, LI X, et al. Energy–efficient permutation flow shop scheduling problem using a hybrid multi–objective backtracking search algorithm. Journal of Cleaner Production, 2017, 144:228–238.
[10] ZHENG H Y, WANG L. Reduction of carbon emissions and project makespan by a Pareto–based estimation of distribution algorithm. International Journal of Production Economics, 2015, 164:421–432.
[11] DAI M, TANG D, GIRET A, et al. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, 2013,29(5):418–429.
[12] NADERI B, RUIZ R. A scatter search algorithm for the distributed permutation flowshop scheduling problem. European Journal of Operational Research, 2014, 239(2):323–334.
[13] GAO J, CHEN R. An NEH-based heuristic algorithm for distributed permutation flowshop scheduling problems. Scientific Research and Essays, 2011, 6(14):3094–3100.
[14] NADERI B, RUIZ R. The distributed permutation flowshop scheduling problem. Computers&Operations Research, 2010, 37(4):754–768.
[15] XU Y, WANG L, WANG S, et al. An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem. Engineering Optimization, 2014, 46(9):1269–1283.
[16] RIFAI A P, NGUYEN H T, DAWAL S Z M. Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling. Applied Soft Computing, 2016, 40(C):42–57.
[17] DENG J, WANG L, WU C, et al. A competitive memetic algorithm for carbon–efficient scheduling of distributed flow–shop. International Conference on Intelligent Computing. Lanzhou:ICIC, 2016, 9771:476–488.
[18] BALUJA S. Population-based incremental learning:A method for integrating genetic search based function optimization and competitive learning. Pittsburgh:Carnegie Mellon University, 1994.
[19] MUHLENBEIN H, PAASS G. From recombination of genes to the estimation of distributions I:Binary parameters. Lecture Notes in Computer Science, 1996, 1141(1):178–187.
[20] LARRAANAGA P, LOZANO J A. Estimation of distribution algorithms:a new tool for evolutionary computation. Kluwer Academic Publishers, 2001, 64(5):454–468.
[21] JARBOUI B, EDDALY M, SIARRY P. An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems. Computers&Operations Research, 2009,36(9):2638–2646.
[22] SALHI A, ZHANG Q. An estimation of distribution algorithm with guided mutation for a complex flow shop scheduling problem. Genetic&Evolutionary Computation Conference, 2007, 14(14):570–576.
[23] WANG F, TANG Q H, RAO Y Q, et al. Efficient estimation of distribution for flexible hybrid flow shop scheduling. Zidonghua Xuebao/Acta Automatica Sinica, 2017, 43(2):280–293.
[24] WANG S Y, WANG L, LIU M, et al. Estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machine. International Journal of Advanced Manufacturing Technology, 2013, 68(9/12):2043–2056.
[25] QIAN B, LI Z C, HU R. A copula-based hybrid estimation of distribution algorithm for M-machine reentrant permutation flow-shop scheduling problem. Applied Soft Computing, 2017, 46(1):139–149.
[26] RAWAT V P S, CUSAN M, DESHPANDE A, et al. Two new robust genetic algorithms for the flowshop scheduling problem. Omega,2006, 34(5):461–476.
[27] CHEN S F, QIAN B, LIU B, et al. Bayesian statistical inferencebased estimation of distribution algorithm for the re-entrant job-shop scheduling problem with sequence-dependent setup times. International Conference on Intelligent Computing. Taiyuan:ICIC, 2014,8589:686–696.
[28] ISHIBUCHI H, YOSHIDA T, MURATA T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation, 2003, 7(2):204–223.
[29] MONTGOMERY D C. Design and Analysis of Experiments. Hoboken:John Wiley and Sons, 2005.
[30] MAY G, STAHL B, TAISCH M, et al. Multi-objective genetic algorithm for energy-efficient job shop scheduling. International Journal of Production Research, 2015, 53(23):7071–7089.
[31] WANG S Y, WANG L, LIU M, et al. An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem. International Journal of Production Economics,2013, 145(1):387–396.
测试问题及测试实例可在https://pan.baidu.com/s/1qkgsMUcmeNlPxelHW8wCCw下载, 若链接失效请联系通讯作者.
[2] FANG K, UHAN N, ZHAO F, et al. A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. Journal of Manufacturing Systems, 2011, 30(4):234–240.
[3] GILLES M, MEHMET B, JANET T. Operational methods for minimization of energy consumption of manufacturing equipment. International Journal of Production Research, 2007, 45(18/19):4247–4271.
[4] YAN J, LI L, ZHAO F, et al. A multi–level optimization approach for energy-efficient flexible flow shop scheduling. Journal of Cleaner Production, 2016, 137:1543–1552.
[5] TANG D, DAI M, SALIDO M A, et al. Energy–efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization. Computers in Industry, 2016, 81(C):82–95.
[6] ZHANG R, CHIONG R. Solving the energy-efficient job shop scheduling problem:a multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption. Journal of Cleaner Production, 2015, 112:3361–3375.
[7] DING J Y, SONG S, WU C. Carbon-efficient scheduling of flow shops by multi–objective optimization. European Journal of Operational Research, 2015, 248(3):758–771.
[8] AI Ziyi, LEI Deming. A novel shuffled frog leaping algorithm for low carbon flexible job shop scheduling. Control Theory&Applications,2017, 34(10):1361–1368.(艾子义,雷德明.基于新型蛙跳算法的低碳柔性作业车间调度.控制理论与应用, 2017, 34(10):1361–1368.)
[9] LU C, GAO L, LI X, et al. Energy–efficient permutation flow shop scheduling problem using a hybrid multi–objective backtracking search algorithm. Journal of Cleaner Production, 2017, 144:228–238.
[10] ZHENG H Y, WANG L. Reduction of carbon emissions and project makespan by a Pareto–based estimation of distribution algorithm. International Journal of Production Economics, 2015, 164:421–432.
[11] DAI M, TANG D, GIRET A, et al. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, 2013,29(5):418–429.
[12] NADERI B, RUIZ R. A scatter search algorithm for the distributed permutation flowshop scheduling problem. European Journal of Operational Research, 2014, 239(2):323–334.
[13] GAO J, CHEN R. An NEH-based heuristic algorithm for distributed permutation flowshop scheduling problems. Scientific Research and Essays, 2011, 6(14):3094–3100.
[14] NADERI B, RUIZ R. The distributed permutation flowshop scheduling problem. Computers&Operations Research, 2010, 37(4):754–768.
[15] XU Y, WANG L, WANG S, et al. An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem. Engineering Optimization, 2014, 46(9):1269–1283.
[16] RIFAI A P, NGUYEN H T, DAWAL S Z M. Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling. Applied Soft Computing, 2016, 40(C):42–57.
[17] DENG J, WANG L, WU C, et al. A competitive memetic algorithm for carbon–efficient scheduling of distributed flow–shop. International Conference on Intelligent Computing. Lanzhou:ICIC, 2016, 9771:476–488.
[18] BALUJA S. Population-based incremental learning:A method for integrating genetic search based function optimization and competitive learning. Pittsburgh:Carnegie Mellon University, 1994.
[19] MUHLENBEIN H, PAASS G. From recombination of genes to the estimation of distributions I:Binary parameters. Lecture Notes in Computer Science, 1996, 1141(1):178–187.
[20] LARRAANAGA P, LOZANO J A. Estimation of distribution algorithms:a new tool for evolutionary computation. Kluwer Academic Publishers, 2001, 64(5):454–468.
[21] JARBOUI B, EDDALY M, SIARRY P. An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems. Computers&Operations Research, 2009,36(9):2638–2646.
[22] SALHI A, ZHANG Q. An estimation of distribution algorithm with guided mutation for a complex flow shop scheduling problem. Genetic&Evolutionary Computation Conference, 2007, 14(14):570–576.
[23] WANG F, TANG Q H, RAO Y Q, et al. Efficient estimation of distribution for flexible hybrid flow shop scheduling. Zidonghua Xuebao/Acta Automatica Sinica, 2017, 43(2):280–293.
[24] WANG S Y, WANG L, LIU M, et al. Estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machine. International Journal of Advanced Manufacturing Technology, 2013, 68(9/12):2043–2056.
[25] QIAN B, LI Z C, HU R. A copula-based hybrid estimation of distribution algorithm for M-machine reentrant permutation flow-shop scheduling problem. Applied Soft Computing, 2017, 46(1):139–149.
[26] RAWAT V P S, CUSAN M, DESHPANDE A, et al. Two new robust genetic algorithms for the flowshop scheduling problem. Omega,2006, 34(5):461–476.
[27] CHEN S F, QIAN B, LIU B, et al. Bayesian statistical inferencebased estimation of distribution algorithm for the re-entrant job-shop scheduling problem with sequence-dependent setup times. International Conference on Intelligent Computing. Taiyuan:ICIC, 2014,8589:686–696.
[28] ISHIBUCHI H, YOSHIDA T, MURATA T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation, 2003, 7(2):204–223.
[29] MONTGOMERY D C. Design and Analysis of Experiments. Hoboken:John Wiley and Sons, 2005.
[30] MAY G, STAHL B, TAISCH M, et al. Multi-objective genetic algorithm for energy-efficient job shop scheduling. International Journal of Production Research, 2015, 53(23):7071–7089.
[31] WANG S Y, WANG L, LIU M, et al. An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem. International Journal of Production Economics,2013, 145(1):387–396.
测试问题及测试实例可在https://pan.baidu.com/s/1qkgsMUcmeNlPxelHW8wCCw下载, 若链接失效请联系通讯作者.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |