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

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

Abstract

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

CLC Number:

TP301.6

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.

0
/ / Recommend

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jsjkx.com/EN/10.11896／j.issn.1002-137X.2018.10.044

https://www.jsjkx.com/EN/Y2018/V45/I10/240

References

[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.

Related Articles 15

[1]	LI Dan-dan, WU Yu-xiang, ZHU Cong-cong, LI Zhong-kang. Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies [J]. Computer Science, 2022, 49(6A): 217-222.
[2]	LIU Bao-bao, YANG Jing-jing, TAO Lu, WANG He-ying. Study on Prediction of Educational Statistical Data Based on DE-LSTM Model [J]. Computer Science, 2022, 49(6A): 261-266.
[3]	YU Jia-shan, WU Lei. Two Types of Leaders Salp Swarm Algorithm [J]. Computer Science, 2021, 48(4): 254-260.
[4]	ZHANG Zhi-qiang, LU Xiao-feng, SUI Lian-sheng, LI Jun-huai. Salp Swarm Algorithm with Random Inertia Weight and Differential Mutation Operator [J]. Computer Science, 2020, 47(8): 297-301.
[5]	HOU Gai, HE Lang, HUANG Zhang-can, WANG Zhan-zhan, TAN Qing. Pyramid Evolution Strategy Based on Differential Evolution for Solving One-dimensional Cutting Stock Problem [J]. Computer Science, 2020, 47(7): 166-170.
[6]	LI Zhang-wei,WANG Liu-jing. Population Distribution-based Self-adaptive Differential Evolution Algorithm [J]. Computer Science, 2020, 47(2): 180-185.
[7]	WANG Xuan, MAO Ying-chi, XIE Zai-peng, HUANG Qian. Inference Task Offloading Strategy Based on Differential Evolution [J]. Computer Science, 2020, 47(10): 256-262.
[8]	LIU Xiao-zhen,LIU Jing-sen. Distribution Routing Problem Based on Cuckoo Search Algorithm with Directional Mutation [J]. Computer Science, 2019, 46(7): 165-171.
[9]	DONG Ming-gang,LIU Bao,JING Chao. Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation [J]. Computer Science, 2019, 46(7): 224-232.
[10]	NI Hong-jie, PENG Chun-xiang, ZHOU Xiao-gen, YU Li. Differential Evolution Algorithm with Stage-based Strategy Adaption [J]. Computer Science, 2019, 46(6A): 106-110.
[11]	XIAO Peng, ZOU De-xuan, ZHANG Qiang. Efficient Dynamic Self-adaptive Differential Evolution Algorithm [J]. Computer Science, 2019, 46(6A): 124-132.
[12]	ZHANG Yu-pei, ZHAO Zhi-jin, ZHENG Shi-lian. Cognitive Decision Engine of Hybrid Learning Differential Evolution and Particle Swarm Optimization [J]. Computer Science, 2019, 46(6): 95-101.
[13]	ZHAO Yun-tao, CHEN Jing-cheng, LI Wei-gang. Multi-objective Grey Wolf Optimization Hybrid Adaptive Differential Evolution Mechanism [J]. Computer Science, 2019, 46(11A): 83-88.
[14]	YANG Xiao-hua, GAO Hai-yun. Improved Bayesian Algorithm Based Automatic Classification Method for Bibliography [J]. Computer Science, 2018, 45(8): 203-207.
[15]	YU Wei-wei,XIE Cheng-wang. Hybrid Particle Swarm Optimization with Multiply Strategies [J]. Computer Science, 2018, 45(6A): 120-123.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Dynamic Strategy-based Differential Evolution for Flexible Job Shop Scheduling Optimization

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0