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

山东大学学报(工学版) ›› 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)

941

摘要： 针对具有零等待约束的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] 钱淑渠,武慧虹,徐国峰,金晶亮. 计及排放的动态经济调度免疫克隆演化算法[J]. 山东大学学报(工学版), 2018, 48(4): 1-9.
[2] 王飞,徐健,李伟,汪新浩,施啸寒. 基于分布式储能系统的风储滚动优化调度方法[J]. 山东大学学报(工学版), 2017, 47(6): 89-94.
[3] 裴小兵,陈慧芬,张百栈,陈孟辉. 改善式BVEDA求解多目标调度问题[J]. 山东大学学报(工学版), 2017, 47(4): 25-30.
[4] 杨隆浩, 傅仰耿, 巩晓婷. 置信规则库参数学习的并行差分进化算法[J]. 山东大学学报(工学版), 2015, 45(1): 30-36.
[5] 刘淳安. 基于核分布估计的动态多目标优化进化算法[J]. 山东大学学报(工学版), 2011, 41(1): 167-172.
[6] 李明,李歧强,郭庆强,丁然. 基于炼油过程生产特性的优化调度模型[J]. 山东大学学报(工学版), 2010, 40(3): 51-56.
[7] 夏茂森 郭庆强 张斌. 生产调度广义析取规划模型求解算法[J]. 山东大学学报(工学版), 2009, 39(6): 53-57.
[8] 曲延鹏 陈颂英 杨新振 解富超 李文峰 宋秀琴. 低比转速离心泵叶轮几何参数多目标优化[J]. 山东大学学报(工学版), 2009, 39(3): 103-105.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 陈瑞,李红伟,田靖. 磁极数对径向磁轴承承载力的影响[J]. 山东大学学报(工学版), 2018, 48(2): 81 -85 .
[2] 陈华鑫, 陈拴发, 王秉纲. 基质沥青老化行为与老化机理[J]. 山东大学学报(工学版), 2009, 39(2): 125 -130 .
[3] 卜德云 张道强. 自适应谱聚类算法研究[J]. 山东大学学报(工学版), 2009, 39(5): 22 -26 .
[4] 任敬喜,耿金花,高齐圣 . 多因素多指标产品的质量优化[J]. 山东大学学报(工学版), 2007, 37(3): 114 -117 .
[5] 孟健, 李贻斌, 李彬. 四足机器人跳跃步态控制方法[J]. 山东大学学报(工学版), 2015, 45(3): 28 -34 .
[6] 穴洪涛,田国会,李晓磊,路飞 . QR Code在多种类物体识别与操作中的应用[J]. 山东大学学报(工学版), 2007, 37(6): 25 -30 .
[7] 马其华 王宜泰. 高密度电阻率法在煤矿界外巨空水探测上的应用[J]. 山东大学学报(工学版), 2009, 39(4): 107 -111 .
[8] 张明亮 李凡长. 一种新的博弈树搜索方法[J]. 山东大学学报(工学版), 2009, 39(6): 1 -7 .
[9] 周绍伟. 随机Markov跳跃系统有限时间稳定性[J]. 山东大学学报(工学版), 2016, 46(2): 78 -84 .
[10] 胥晓东 刘燕 王威强 陈同蕾 刘琦. 压力容器的无量纲设计法及其应用(Ⅱ)[J]. 山东大学学报(工学版), 2009, 39(6): 101 -104 .
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发