计算机科学 ›› 2018, Vol. 45 ›› Issue (10): 240-245.doi: 10.11896/j.issn.1002-137X.2018.10.044
张贵军, 王文, 周晓根, 王柳静
ZHANG Gui-jun, WANG Wen, ZHOU Xiao-gen, WANG Liu-jing
摘要: 针对柔性作业车间调度问题,提出基于动态策略的差分进化优化方法。首先,基于差分进化算法框架,考虑个体之间的距离,设计种群拥挤度指标来衡量当前种群的分布情况,进而自适应判断算法所处阶段;然后,针对不同阶段的特点设计相应的变异策略池,实现变异策略的动态阶段选择,达到提高算法搜索效率的目的;最后,10个标准测试函数的计算结果表明了所提方法的有效性,进一步,采用工序和机器双层编码的方式,以最大完工时间为目标,求解得到作业车间调度测试问题的最佳调度方案。
中图分类号:
[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. |
[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. |
|