基于动态策略的差分进化柔性车间优化调度

doi:10.11896／j.issn.1002-137X.2018.10.044

摘要/Abstract

摘要： 针对柔性作业车间调度问题,提出基于动态策略的差分进化优化方法。首先,基于差分进化算法框架,考虑个体之间的距离,设计种群拥挤度指标来衡量当前种群的分布情况,进而自适应判断算法所处阶段;然后,针对不同阶段的特点设计相应的变异策略池,实现变异策略的动态阶段选择,达到提高算法搜索效率的目的;最后,10个标准测试函数的计算结果表明了所提方法的有效性,进一步,采用工序和机器双层编码的方式,以最大完工时间为目标,求解得到作业车间调度测试问题的最佳调度方案。

关键词: 变异策略, 差分进化, 动态策略, 柔性作业车间调度, 双层编码

Abstract: To solve the flexible job shop scheduling problem,a differential evolution optimization method based on dynamic strategy was proposed in this paper.Firstly,based on the framework of differential evolution algorithm,taking the distance between individuals into consideration,the indicator of population crowding degree was designed,which for measuring the distribution of the current population,and the stage of the algorithm can be further determined adaptively.Then,in view of characteristics of different stages,the corresponding mutation strategy pool was designed to realize the dynamic stage selection of mutation strategy,so as to improve the search efficiency of the algorithm.Finally,the test results on 10 benchmark functions show that the proposed algorithm is feasible and efficient.Based on the double layer coding method of working procedure and machine,the best scheduling scheme was obtained by minimizing the maximum completion time.

Key words: Differential evolution, Double layer coding, Dynamic strategy, Flexible job shop scheduling, Mutation strategy

中图分类号:

TP301.6

张贵军, 王文, 周晓根, 王柳静. 基于动态策略的差分进化柔性车间优化调度[J]. 计算机科学, 2018, 45(10): 240-245. https://doi.org/10.11896／j.issn.1002-137X.2018.10.044

ZHANG Gui-jun, WANG Wen, ZHOU Xiao-gen, WANG Liu-jing. Dynamic Strategy-based Differential Evolution for Flexible Job Shop Scheduling Optimization[J]. Computer Science, 2018, 45(10): 240-245. https://doi.org/10.11896／j.issn.1002-137X.2018.10.044

参考文献

[1]WANG L,DENG J,WANG S Y.Survey on optimization algorithms for distributed shop scheduling[J].Control and Decision,2016,31(1):1-11.(in Chinese)
王凌,邓瑾,王圣尧.分布式车间调度优化算法研究综述[J].控制与决策,2016,31(1):1-11.
[2]LI C B,SHEN H,LI L L,et al.A Batch Splitting Flexible Job Shop Scheduling Model for Energy Saving under Alternative Process Plans[J].Journal of Mechanical Engineering,2017,53(5):12-23.(in Chinese)
李聪波,沈欢,李玲玲,等.面向能耗的多工艺路线柔性作业车间分批优化调度模型[J].机械工程学报,2017,53(5):12-23.
[3]STORN R,PRICE K.Differential evolution:a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.
[4]LI J Q,PAN Q K,LIANG Y C.An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems[J].Computers & Industrial Engineering,2010,59(4):647-662.
[5]ZHANG J,WANG W L,XU X L,et al.Improved particle swarm algorithm for batch splitting flexible job shop scheduling[J].Control and Decision,2012,27(4):513-518.(in Chinese)
张静,王万良,徐新黎,等.基于改进粒子群算法求解柔性作业车间批量调度问题[J].控制与决策,2012,27(4):513-518.
[6]T’KINDT V,MONMARCH N,TERCINET F,et al.An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem[J].European Journal of Operational Research,2002,142(2):250-257.
[7]AN Y W,YAN H S.Solution Strategy of Integrated Optimization of Production Planning and Scheduling in a Flexible Job-shop[J].Acta Automatica Sinic,2013,39(9):1476-1491.(in Chinese)
安玉伟,严洪森.柔性作业车间生产计划与调度集成优化求解策略[J].自动化学报,2013,39(9):1476-1491.
[8]GU J W,GU M Z,CAO C W,et al.A novel competitive co-evolutionary quantum genetic algorithm for stochastic Job Shop scheduling problem [J].Computers and Operations Research,2010,37(5):927-937.
[9]CAI L W,ZHANG J H,LI X.A Multi-Population Genetic Algorithm for Job Shop Scheduling Problem[J].Acta Electronica Sinica,2005,33(6):991-994.(in Chinese)
蔡良伟,张基宏,李霞.作业车间调度问题的多种群遗传算法[J].电子学报,2005,33(6):991-994.
[10]WANG L,ZHOU G,XU Y,et al.An effective artificial bee co- lony algorithm for the flexible job-shop scheduling problem[J].International Journal of Advanced Manufacturing Technology,2012,60(1-4):303-315.
[11]WANG L,WANG S,XU Y,et al.A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem[J].Computers & Industrial Engineering,2012,62(4):917-926.
[12]YAZDANI M,AMIRI M,ZANDIEH M.Flexible job-shop scheduling with parallel variable neighborhood search algorithm[J].Expert Systems with Applications,2010,37(1):678-687.
[13]CHEN H,IHLOW J,LEHMANN C.A genetic algorithm for flexible job-shop scheduling[C]∥1999 IEEE International Conference on Robotics and Automation.IEEE,1999:1120-1125.
[14]YANG X M,ZENG J C.Solving flexible job shop scheduling problem using genetic algorithm[J].Control and Decision,2004,19(10):1197-1200.(in Chinese)
杨晓梅,曾建潮.遗传算法求解柔性 job shop 调度问题[J].控制与决策,2004,19(10):1197-1200.
[15]LI Z W,ZHOU X G,ZHANG G J.Dynamic Adaptive Differential Evolution Algorithm[J].Computer Science,2015,42(S1):52-56,74.(in Chinese)
李章维,周晓根,张贵军.一种动态自适应差分进化算法[J].计算机科学,2015,42(S1):52-56,74.
[16]ZHOU X G,ZHANG G J,HAO X H,et al.Differentail Evolution Algorithm Based on Local Lipschitz Underestimate Supporting Hyperplanes[J].Acta Automatic Sinica,2015,41(7):1315-1327.(in Chinese)
周晓根,张贵军,郝小虎,等.局部抽象凸区域剖分差分进化算法[J].自动化学报,2015,41(7):1315-1327.
[17]ZHOU X G,ZHANG G J,HAO X H,et al.Enhanced differen- tial evolution using local Lipschitz underestimate strategy for computationally expensive optimization problems[J].Applied Soft Computing,2016,48 (11):169-181.
[18]WANG F,TANG Q H,RAO Y Q,et al.Effcient Estimation of Distribution for Flexible Hybrid Flow Shop Scheduling[J].Acta Automatica Sinica,2017,43(2):280-293.(in Chinese)
王芳,唐秋华,饶运清,等.求解柔性流水车间调度问题的高效分布估算算法[J].自动化学报,2017,43(2):280-293.
[19]ZHOU X G,ZHANG G J.Abstract convex underestimation assisted multistage differential devolution[J].IEEE Transactions on Cybernetics,2017,47(9):2730-2741.
[20]ZHOU X G,ZHANG G J,HAO X H,et al.A novel differential evolution algorithm using local abstract convex underestimate strategy for global optimization[J].Computers & Operation Research,2016,75(11):132-149.
[21]QIN A K,HUANG V L,SUGANTHAN P N.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation,2009,13(2):398-417.
[22]ZHANG J,SANDERSON A C.JADE:adaptive differential evolution with optional external archive[J].IEEE Transactions on Evolutionary Computation,2009,13(5):945-957.
[23]WANG Y,CAI Z,ZHANG Q.Differential evolution with composite trial vector generation strategies and control parameters[J].IEEE Transactions on Evolutionary Computation,2011,15(1):55-66.
[24]ZHOU X G,ZHANG G J,HAO X H,et al.Differentail Evolution Algorithm Based on Local Lipschitz Underestimate Supporting Hyperplanes[J].Chinese Journal of Computers,2016,39(12):2631-2651.(in Chinese)
周晓根,张贵军,郝小虎,等.一种基于局部Lipschitz下界估计支撑面的差分进化算法[J].计算机学报,2016,39(12):2631-2651.
[25]WANG W L,ZHAO C,XIONG J,et al.Method to Resolve Flexible Job-shop Scheduling Problem Based on Improved Ant Colony Algorithm[J].Journal of System Simulation,2008,20(16):4326-4329.(in Chinese)
王万良,赵澄,熊婧,等.基于改进蚁群算法的柔性作业车间调度问题的求解方法[J].系统仿真学报,2008,20(16):4326-4329.
[26]KACEM I,HAMMADI S,BORNE P.Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J].IEEE Transactions on Systems Man and Cybernetics Part C－Applications and Reviews,2002,32(1):1-13.

相关文章 15

[1]	刘宝宝, 杨菁菁, 陶露, 王贺应. 基于DE-LSTM模型的教育统计数据预测研究 Study on Prediction of Educational Statistical Data Based on DE-LSTM Model 计算机科学, 2022, 49(6A): 261-266. https://doi.org/10.11896/jsjkx.220300120
[2]	俞家珊, 吴雷. 双领导者樽海鞘群算法 Two Types of Leaders Salp Swarm Algorithm 计算机科学, 2021, 48(4): 254-260. https://doi.org/10.11896/jsjkx.200600181
[3]	张志强, 鲁晓锋, 隋连升, 李军怀. 集成随机惯性权重和差分变异操作的樽海鞘群算法 Salp Swarm Algorithm with Random Inertia Weight and Differential Mutation Operator 计算机科学, 2020, 47(8): 297-301. https://doi.org/10.11896/jsjkx.190700063
[4]	侯改, 何朗, 黄樟灿, 王占占, 谈庆. 基于差分进化的金字塔演化策略求解一维下料问题 Pyramid Evolution Strategy Based on Differential Evolution for Solving One-dimensional Cutting Stock Problem 计算机科学, 2020, 47(7): 166-170. https://doi.org/10.11896/jsjkx.190500014
[5]	李章维,王柳静. 基于群体分布的自适应差分进化算法 Population Distribution-based Self-adaptive Differential Evolution Algorithm 计算机科学, 2020, 47(2): 180-185. https://doi.org/10.11896/jsjkx.181202356
[6]	王瑄, 毛莺池, 谢在鹏, 黄倩. 基于差分进化的推断任务卸载策略 Inference Task Offloading Strategy Based on Differential Evolution 计算机科学, 2020, 47(10): 256-262. https://doi.org/10.11896/jsjkx.190800159
[7]	刘晓珍,刘景森. 基于定向变异布谷鸟算法的配送路径问题 Distribution Routing Problem Based on Cuckoo Search Algorithm with Directional Mutation 计算机科学, 2019, 46(7): 165-171. https://doi.org/10.11896/j.issn.1002-137X.2019.07.026
[8]	董明刚,刘宝,敬超. 模糊自适应排序变异多目标差分进化算法 Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation 计算机科学, 2019, 46(7): 224-232. https://doi.org/10.11896/j.issn.1002-137X.2019.07.034
[9]	肖鹏, 邹德旋, 张强. 一种高效动态自适应差分进化算法 Efficient Dynamic Self-adaptive Differential Evolution Algorithm 计算机科学, 2019, 46(6A): 124-132.
[10]	倪洪杰, 彭春祥, 周晓根, 俞立. 一种阶段性策略自适应差分进化算法 Differential Evolution Algorithm with Stage-based Strategy Adaption 计算机科学, 2019, 46(6A): 106-110.
[11]	张煜培, 赵知劲, 郑仕链. 融合学习差分进化和粒子群优化算法的认知决策引擎 Cognitive Decision Engine of Hybrid Learning Differential Evolution and Particle Swarm Optimization 计算机科学, 2019, 46(6): 95-101. https://doi.org/10.11896/j.issn.1002-137X.2019.06.013
[12]	赵云涛, 谌竟成, 李维刚. 融合自适应差分进化机制的多目标灰狼优化算法 Multi-objective Grey Wolf Optimization Hybrid Adaptive Differential Evolution Mechanism 计算机科学, 2019, 46(11A): 83-88.
[13]	杨晓花, 高海云. 基于改进贝叶斯的书目自动分类算法 Improved Bayesian Algorithm Based Automatic Classification Method for Bibliography 计算机科学, 2018, 45(8): 203-207. https://doi.org/10.11896/j.issn.1002-137X.2018.08.036
[14]	余伟伟,谢承旺. 一种多策略混合的粒子群优化算法 Hybrid Particle Swarm Optimization with Multiply Strategies 计算机科学, 2018, 45(6A): 120-123.
[15]	邹华福,谢承旺,周杨萍,王立平. 应用反向学习和差分进化的群搜索优化算法 Group Search Optimization with Opposition-based Learning and Differential Evolution 计算机科学, 2018, 45(6A): 124-129.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed