基于多样性增强的自适应遗传算法的开放式车间调度优化

doi:10.13196/j.cims201410016

计算机集成制造系统 ›› 2014, Vol. 20 ›› Issue (10): 2479-2493.DOI: 10.13196/j.cims201410016

基于多样性增强的自适应遗传算法的开放式车间调度优化

王军强^1,2,郭银洲^1,2,崔福东^1,2,张承武^1,2,孙树栋^1,2

1.西北工业大学生产与运作系统性能分析中心
2.西北工业大学现代设计与集成制造技术教育部重点实验室

出版日期:2014-10-31 发布日期:2014-10-31
基金资助:
国家自然科学基金资助项目(51275421);西北工业大学基础研究基金资助项目(JC20120227);高等学校“111”引智计划资助项目(B13044);西北工业大学研究生创业种子基金资助项目。

Diversity enhancement-based adaptive genetic algorithm for open-shop scheduling problem

Online:2014-10-31 Published:2014-10-31
Supported by:
Project supported by the National Natural Science Foundation,China(No.51275421),the Basic Research Foundation of Northwestern Polytechnical University,China(No.JC20120227),the 111 Project of NPU,China(No.B13044),and the Graduate Starting Seed Fund of North Western Polytechnical University,China.

摘要/Abstract

摘要： 针对开放式车间调度问题,提出了基于多样性增强的自适应遗传算法进行优化求解。设计了多样性判定增强算子、自适应交叉变异算子、多元竞争选择算子等五个算子,以提高遗传算法的进化效率和进化质量;通过分析算法各算子的时间复杂度,发现所提算子并未增加算法复杂度;采用正交试验确定了各算子的最优参数;设计了三组实验,分析了所提算子对算法的影响,结果表明多样性增强算子提高了求解质量,自适应交叉变异算子加快了收敛速度;基于60个标准算例,通过与已有5种算法比较,验证了所提算法的有效性和稳定性。采用100个算例,分析了算例规模对调度性能的影响规律。

关键词: 开放式车间调度, 遗传算法, 多样性增强, 自适应遗传算子, 复杂度分析, 正交试验

Abstract: Aiming at the Open-shop Scheduling Problem (OSP),an improved Genetic Algorithm (GA) named Diversity Enhancement-based Adaptive Genetic Algorithm (DEAGA) was proposed.Five operators such as diversity enhancement operator,adaptive crossover operator,adaptive mutation operator and multiple tournament selections operator were designed to improve convergence efficiency and evolution quality of GA.The time complexity of each operator in DEAGA was analyzed,and the results proved that the complexity was not increased by comparing with the simple genetic algorithm.An orthogonal design method was used to determine the optimal parameters of the operators.Three experiments were designed to analyze the role of the propose operators,and the result showed that the diversity enhanced operator could improve the solution quality,and the adaptive operator could promote the convergence rate.Based on 60 benchmarks of OSP,the effectiveness and stability of the proposed algorithm were verified by comparing with the existing 5 algorithms.The effect of problem scale on the scheduling performance was analyzed by using 100 cases.

Key words: open shop scheduling, genetic algorithms, diversity enhancement, adaptive genetic operator, complexity analysis, orthogonal design

中图分类号:

TH166
TH186

王军强,郭银洲,崔福东,张承武,孙树栋. 基于多样性增强的自适应遗传算法的开放式车间调度优化[J]. 计算机集成制造系统, 2014, 20(10): 2479-2493.

[1]	陈年,金涛,王建民. 基于变异反馈的临床路径优化[J]. 计算机集成制造系统, 2021, 27(9): 2556-2564.
[2]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[3]	王文中,张树生,余隋怀,陈登凯. 基于解构·重构思维的潜水器舱室布局优化[J]. 计算机集成制造系统, 2021, 27(7): 2045-2052.
[4]	王勇,周雪,刘永,许茂增. 基于车辆共享的多中心共同配送联盟优化[J]. 计算机集成制造系统, 2021, 27(6): 1820-1832.
[5]	张昊鹏,郭宇,汤鹏洲,黄少华,刘道元,李晗. 基于图像匹配的增强现实装配系统跟踪注册方法[J]. 计算机集成制造系统, 2021, 27(5): 1281-1291.
[6]	胡金昌,刘紫薇,马文凯,吴耀华. 考虑学习效应的单人作业车间多目标调度算法[J]. 计算机集成制造系统, 2021, 27(5): 1361-1370.
[7]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[8]	裴小兵,李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.
[9]	李从东,章志伟,曹策俊,张帆顺. 复杂产品设计变更传播路径的多目标优选[J]. 计算机集成制造系统, 2021, 27(3): 842-856.
[10]	杨小明,徐子奇,金雯,舒帆. 复合拣选策略下堆垛机作业序列优化问题[J]. 计算机集成制造系统, 2021, 27(3): 933-942.
[11]	李丽丽,陈琨,高建民,李辉,冯增行,张建. 采用优化概率神经网络的质量异常识别方法[J]. 计算机集成制造系统, 2021, 27(10): 2813-2821.
[12]	薛玲玲. 作业车间调度的块结构邻域搜索遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2848-2857.
[13]	罗焕,陈浩杰,宋小欣,张剑. 带有缓存约束的作业车间调度求解方法[J]. 计算机集成制造系统, 2021, 27(10): 2880-2888.
[14]	张韵,钟慧超,张春江,李新宇,丛建臣. 基于机器学习的多策略并行遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2921-2928.
[15]	狄卫民,王然. 考虑多级设施中断的供应链选址—库存决策模型及优化算法[J]. 计算机集成制造系统, 2021, 27(1): 270-283.

基于多样性增强的自适应遗传算法的开放式车间调度优化

Diversity enhancement-based adaptive genetic algorithm for open-shop scheduling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics