您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（工学版）》

山东大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (5): 21-28.doi: 10.6040/j.issn.1672-3961.1.2016.215

• • 上一篇    下一篇

零等待flow shop多目标调度的混合差分进化算法

邓冠龙1,杨洪勇1,张淑宁1,顾幸生2   

  1. 1.鲁东大学信息与电气工程学院, 山东 烟台 264025;2.华东理工大学化工过程先进控制和优化技术教育部重点实验室, 上海 200237
  • 收稿日期:2016-03-01 出版日期:2016-10-20 发布日期:2016-03-01
  • 作者简介:邓冠龙(1985— ),男,湖南郴州人,讲师,博士,主要研究方向为生产计划与调度,智能优化方法. E-mail:dglag@163.com
  • 基金资助:
    国家自然科学基金资助项目(61403180,61573144);山东省优秀中青年科学家科研奖励基金资助项目(BS2015DX018);鲁东大学引进人才资助项目(LY2013005)

Multi-objective scheduling in no-wait flow shop using a hybridized differential evolution algorithm

DENG Guanlong1, YANG Hongyong1, ZHANG Shuning1, GU Xingsheng2   

  1. 1. School of Information and Electrical Engineering, Ludong University, Yantai 264025, Shandong, China;
    2. Key Laboratory of Advanced Control and Optimization for Chemical Processes of Ministry of Education, East China University of Science and Technology, Shanghai 200237, China
  • Received:2016-03-01 Online:2016-10-20 Published:2016-03-01

PDF (PC)

1197

摘要： 针对具有零等待约束的flow shop问题,以总流程时间和最大完工时间为多目标,提出一种结合多目标变邻域搜索的混合差分进化算法(multi-objective differential evolution hybridized with variable neighborhood search,MDEVNS)进行求解。 提出一种基于改进Nawaz-Enscore-Ham(NEH)规则的多样化种群初始化方法;设计了差分进化的变异、试验、目标个体更新操作; 为提高多目标搜索能力,在算法的进化中混合了一种多目标变邻域搜索方法。通过Taillard标准测试算例的计算试验,证明了MDEVNS算法获得的Pareto前沿解在多样性和性能方面要优于多目标模拟退火算法和非支配排序遗传算法,验证了MDEVNS算法求解多目标零等待流水车间调度问题的有效性。

关键词: 智能算法, 流水车间, 生产调度, 差分进化, 多目标优化

Abstract: To sovle the no-wait flow shop scheduling with the makespan and total flow time criteria, a multi-objective differential evolution algorithm hybridized with variable neighborhood search(MDEVNS)was proposed. A diversified population initialization method was proposed by using the improved Nawaz-Enscore-Ham(NEH)heuristics. The updating operations of mutant, trial and target individuals were developed in differential evolution. To improve the multi-objective searching ability, a multi-objective variable neighborhood search was embedded in the algorithm. The computational experiments based on Taillard benchmark set revealed that the MDEVNS yielded Pareto front solutions with better diversity and performance than the multi-objective simulated annealing algorithm and the non-dominated sorting genetic algorithm, and the effectiveness of the MDEVNS for multi-objective scheduling in no-wait flow shop was proved.

Key words: differential evolution, flow shop, intelligent algorithm, multi-objective optimization, production scheduling

中图分类号: 

  • TP273
[1] BONNEY M C, GUNDRY S W. Solutions to the constrained flowshop sequencing problem[J]. Operational Research Quarterly, 1976, 27(4):869-883.
[2] 张飞, 耿红琴. 基于混沌粒子群算法的车间作业调度优化[J]. 山东大学学报(工学版), 2013, 43(3):19-37. ZHANG Fei, GENG Hongqin. Optimization of job-shop scheduling problem based on chaos particle swarm optimization algorithm[J]. Journal of Shandong Universtiy(Engineering Science), 2013, 43(3):19-37.
[3] RAJENDRAN C. A no-wait flowshop scheduling heuristic to minimize makespan[J]. Journal of the Operational Research Society, 1994, 45(4):472-478.
[4] GANGADHARAN R, RAJENDRAN C. Heuristic algorithms for scheduling in the no-wait flowshop[J]. International Journal of Production Economics, 1993, 32(3):285-290.
[5] SCHUSTER C J, FRAMINAN J M. Approximate procedure for no-wait job shop scheduling[J]. Operations Research Letters, 2003, 31(4):308-318.
[6] GRABOWSKI J, PEMPERA J. Some local search algorithms for no-wait flow-shop problem with makespan criterion[J]. Computers and Operations Research, 2005, 32(8):2197-2212.
[7] 潘全科, 王文宏, 朱剑英. 解决无等待流水车间调度问题的离散粒子群优化算法[J]. 计算机集成制造系统, 2007, 13(6):1127-1136. PAN Quanke, WANG Wenhong, ZHU Jianying. Modified discrete particle swarm optimization algorithm for no-wait flow shop problem[J]. Computer Integrated Manufacturing Systems, 2007, 13(6):1127-1136.
[8] PAN Q K, TASGETIREN M F, LIANG Y C. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem[J]. Computers and Operations Research, 2008, 35(9):2807-2839.
[9] 张其亮, 陈永生. 基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J]. 系统工程理论与实践, 2014, 34(3):802-809. ZHANG Qiliang, CHEN Yongsheng. Hybrid PSO-NEH algorithm for solving no-wait flexible flow shop scheduling problem[J]. Systems Engineering Theory and Practice, 2014, 34(3):802-809.
[10] QIAN B, WANG L, HU Rong, et al. A DE-based approach to no-wait flow-shop scheduling[J]. Computers and Industrial Engineering, 2009, 57(3):787-805.
[11] DAVENDRA D, ZELINKA I, BIALIC-DAVENDRA M, et al. Discrete self-organising migrating algorithm for flow-shop scheduling with no-wait makespan[J]. Mathematical and Computer Modelling, 2013, 57(1):100-110.
[12] DING J Y, SONG S J, GUPTA J N D, et al. An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem[J]. Applied Soft Computing, 2015, 30:604-613.
[13] 潘全科, 赵保华, 屈玉贵, 等. 一类解决无等待流水车间调度问题的蚁群算法[J]. 计算机集成制造系统, 2007, 13(9):1801-1815. PAN Quanke, ZHAO Baohua, QU Yugui, et al. Ant-colony heuristic algorithm for no-wait flow shop problem with makespan criterion[J]. Computer Integrated Manufacturing Systems, 2007, 13(9):1801-1815.
[14] GAO K Z, PAN Q K, LI J Q. Discrete harmony search algorithm for the no-wait flow shop scheduling problem with total flow time criterion[J]. The International Journal of Advanced Manufacturing Technology, 2011, 56(5):683-692.
[15] GAO K Z, PAN Q K, LI J Q, et al. A hybrid harmony search algorithm for the no-wait flow-shop scheduling problems[J]. Asia-Pacific Journal of Operational Reaearch, 2012, 29(2):1250012.1-1250012.23.
[16] AKHSHABI M, TAVAKKOLI-MOGHADDAM R, RAHNAMAY-ROODPOSHTI F. A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time[J]. International Journal of Advanced Manufacturing Technology, 2014, 70(5):1181-1188.
[17] GAO K, PAN Q K, SUGANTHAN P N, et al. Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization[J]. International Journal of Advanced Manufacturing Technology, 2013, 66(9):1563-1572.
[18] SAPKAL S U, LAHA D. A heuristic for no-wait flow shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2013, 68(5):1327-1338.
[19] LAHA D, SAPKAL S U. An improved heuristic to minimize total flow time for scheduling in the m-machine no-wait flow shop[J]. Computers and Industrial Engineering, 2014, 67(1):36-43.
[20] ALLAHVERDI A, ALDOWAISAN T. No-wait flowshops with bicriteria of makespan and maximum lateness[J]. European Journal of Operational Research, 2004, 152(1):132-147.
[21] TAVAKKOLI-MOGHADDAM R, RAHIMI-VAHED A, MIRZAEI A H. A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness[J]. Information Sciences, 2007, 177(22):5072-5090.
[22] QIAN B, WANG L, HUANG D X, et al. Multi-objective no-wait flowshop scheduling with a memetic algorithm based on differential evolution[J]. Soft Computing, 2009, 13(8):847-869.
[23] PAN Q K, WANG L, QIAN B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J]. Computers and Operations Research, 2009, 36(8):2498-2511.
[24] 杨隆浩, 傅仰耿, 巩晓婷. 置信规则库参数学习的并行差分进化算法[J]. 山东大学学报(工学版), 2015, 45(1):30-36. YANG Longhao, FU Yanggeng, GONG Xiaoting. Parallel differential evolution algorithm for parameter learning of belief rule base[J]. Journal of Shandong Universtiy(Engineering Science), 2015, 45(1):30-36.
[25] 邱晓红, 胡玉婷, 李渤. 求解多处理器任务调度问题的改进差分进化算法[J]. 控制与决策, 2016, 31(2):217-224. QIU Xiaohong, HU Yuting, LI Bo. Multiprocessor task scheduling based on improved differential evolution algorithm[J]. Control and Decision, 2016, 31(2):217-224.
[26] WANG L, PAN Q K, TASGETIREN M F. Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms[J]. Expert Systems with Applications, 2010, 37(12):7929-7936.
[27] DENG G L, XU Z H, GU X S. A discrete artificial bee colony algorithm for minimizing the total flow time in the blocking flow shop scheduling[J]. Chinese Journal of Chemical Engineering, 2012, 20(6):1067-1073.
[28] LIN S W, YING K C. Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm[J]. Computers and Operations Research, 2013, 40(6):1625-1647.
[29] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[1] 邵孟伟,袁世飞,周宏志,王乃华. 基于BP神经网络和遗传算法的翅片管结构优化[J]. 山东大学学报 (工学版), 2025, 55(6): 76-82.
[2] 赵天怀,王目树,潘为刚,康超,秦石铭,徐飞. 挖掘机智能辅助施工系统设计[J]. 山东大学学报 (工学版), 2023, 53(4): 163-172.
[3] 李浩源,于景明,张桂林,张斌. 基于智能算法的光纤预制棒芯层制备工艺参数优化[J]. 山东大学学报 (工学版), 2023, 53(4): 149-156.
[4] 赵康,田浩,马欢,杨冬. 基于复杂网络理论的多直流馈入受端电网优化分区方法[J]. 山东大学学报 (工学版), 2022, 52(1): 128-134.
[5] 赵云龙, 车仁飞, 陈家辉. 基于差分进化算法的配电网智能换相策略[J]. 山东大学学报 (工学版), 2021, 51(5): 107-113.
[6] 武慧虹,钱淑渠,刘衍民,徐国峰,郭本华. 精英克隆局部搜索的多目标动态环境经济调度差分进化算法[J]. 山东大学学报 (工学版), 2021, 51(1): 11-23.
[7] 杨冬,王世文,王勇,陈博,郑天茹,周宁,肖天,赵雅文. 并网型风电场扩展光伏互补发电容量优化配置[J]. 山东大学学报 (工学版), 2019, 49(5): 44-51.
[8] 孙润稼,朱海南,刘玉田. 基于偏好多目标优化和遗传算法的输电网架重构[J]. 山东大学学报 (工学版), 2019, 49(5): 17-23.
[9] 钱淑渠,武慧虹,徐国峰,金晶亮. 计及排放的动态经济调度免疫克隆演化算法[J]. 山东大学学报(工学版), 2018, 48(4): 1-9.
[10] 王飞,徐健,李伟,汪新浩,施啸寒. 基于分布式储能系统的风储滚动优化调度方法[J]. 山东大学学报(工学版), 2017, 47(6): 89-94.
[11] 裴小兵,陈慧芬,张百栈,陈孟辉. 改善式BVEDA求解多目标调度问题[J]. 山东大学学报(工学版), 2017, 47(4): 25-30.
[12] 杨隆浩, 傅仰耿, 巩晓婷. 置信规则库参数学习的并行差分进化算法[J]. 山东大学学报(工学版), 2015, 45(1): 30-36.
[13] 刘淳安. 基于核分布估计的动态多目标优化进化算法[J]. 山东大学学报(工学版), 2011, 41(1): 167-172.
[14] 李明,李歧强,郭庆强,丁然. 基于炼油过程生产特性的优化调度模型[J]. 山东大学学报(工学版), 2010, 40(3): 51-56.
[15] 夏茂森 郭庆强 张斌. 生产调度广义析取规划模型求解算法[J]. 山东大学学报(工学版), 2009, 39(6): 53-57.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 李 侃 . 嵌入式相贯线焊接控制系统开发与实现[J]. 山东大学学报(工学版), 2008, 38(4): 37 -41 .
[2] 来翔 . 用胞映射方法讨论一类MKdV方程[J]. 山东大学学报(工学版), 2006, 36(1): 87 -92 .
[3] 余嘉元1 , 田金亭1 , 朱强忠2 . 计算智能在心理学中的应用[J]. 山东大学学报(工学版), 2009, 39(1): 1 -5 .
[4] 陈瑞,李红伟,田靖. 磁极数对径向磁轴承承载力的影响[J]. 山东大学学报(工学版), 2018, 48(2): 81 -85 .
[5] 王波,王宁生 . 机电装配体拆卸序列的自动生成及组合优化[J]. 山东大学学报(工学版), 2006, 36(2): 52 -57 .
[6] 张英,郎咏梅,赵玉晓,张鉴达,乔鹏,李善评 . 由EGSB厌氧颗粒污泥培养好氧颗粒污泥的工艺探讨[J]. 山东大学学报(工学版), 2006, 36(4): 56 -59 .
[7] Yue Khing Toh1 ， XIAO Wendong2 ， XIE Lihua1 . 基于无线传感器网络的分散目标跟踪：实际测试平台的开发应用（英文）[J]. 山东大学学报(工学版), 2009, 39(1): 50 -56 .
[8] 孙炜伟,王玉振. 考虑饱和的发电机单机无穷大系统有限增益镇定[J]. 山东大学学报(工学版), 2009, 39(1): 69 -76 .
[9] 孙玉利,李法德,左敦稳,戚美 . 直立分室式流体连续通电加热系统的升温特性[J]. 山东大学学报(工学版), 2006, 36(6): 19 -23 .
[10] 王勇, 谢玉东.

大流量管道煤气的控制技术研究

[J]. 山东大学学报(工学版), 2009, 39(2): 70 -74 .
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发