JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2016, Vol. 46 ›› Issue (5): 21-28.doi: 10.6040/j.issn.1672-3961.1.2016.215

Previous Articles     Next Articles

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)

1198

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

CLC Number: 

  • 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] SHAO Mengwei, YUAN Shifei, ZHOU Hongzhi, WANG Naihua. Optimisation of finned tube structure based on BP neural network and genetic algorithm [J]. Journal of Shandong University(Engineering Science), 2025, 55(6): 76-82.
[2] Haoyuan LI,Jingming YU,Guilin ZHANG,Bin ZHANG. Optimization of manufacturing parameters for optical fiber preform core based on intelligent algorithm [J]. Journal of Shandong University(Engineering Science), 2023, 53(4): 149-156.
[3] Yunlong ZHAO, Renfei CHE, Jiahui CHEN. Intelligent commutation system of distribution network based on differential evolution algorithm [J]. Journal of Shandong University(Engineering Science), 2021, 51(5): 107-113.
[4] WU Huihong, QIAN Shuqu, LIU Yanmin, XU Guofeng, GUO Benhua. Multiobjective dynamic economic emission dispatch differential evolution algorithm based on elites cloning local search [J]. Journal of Shandong University(Engineering Science), 2021, 51(1): 11-23.
[5] Dong YANG,Shiwen WANG,Yong WANG,Bo CHEN,Tianru ZHENG,Ning ZHOU,Tian XIAO,Yawen ZHAO. Optimal complementary photovoltaic capacity configuration for grid-connected wind farms expansion [J]. Journal of Shandong University(Engineering Science), 2019, 49(5): 44-51.
[6] ZHANG Shuangsheng, QIANG Jing, LIU Xikun, LIU Hanhu, ZHU Xueqiang. Inverse problems of pollution source identification based on Bayesian-DE [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(1): 131-136.
[7] PEI Xiaobing, CHEN Huifen, ZHANG Baizhan, CHEN Menghui. Improved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 25-30.
[8] YANG Longhao, FU Yanggeng, GONG Xiaoting. Parallel differential evolution algorithm for parameter learning of belief rule base [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(1): 30-36.
[9] LIANG Xingjian, ZHAN Zhihui. Improved genetic algorithm based on the dual-mode mutation strategy [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 1-7.
[10] LIU Chun-an. A dynamic multi-objective optimization evolutionary algorithm based on estimation of core distribution [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(1): 167-172.
[11] LI Ming, LI Qi-qiang, GUO Qing-qiang, DING Ran. Scheduling optimization model of refinery processes based on production characteristics [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 51-56.
[12] JIA Mao-Sen, GUO Qiang-Jiang, ZHANG Bin. Algorithm for generalized disjunctive programming model of production scheduling [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(6): 53-57.
[13] QU Yan-peng, CHEN Song-ying, YANG Xin-zhen, XIE Fu-chao, LI Wen-feng, SONG Xiu-qin. Multi-objective optimization for the geometrical parameters of the low-specific-speed centrifugal impeller [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(3): 103-105.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[2] LAI Xiang . The global domain of attraction for a kind of MKdV equations[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 87 -92 .
[3] YU Jia yuan1, TIAN Jin ting1, ZHU Qiang zhong2. Computational intelligence and its application in psychology[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 1 -5 .
[4] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[5] WANG Bo,WANG Ning-sheng . Automatic generation and combinatory optimization of disassembly sequence for mechanical-electric assembly[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 52 -57 .
[6] ZHANG Ying,LANG Yongmei,ZHAO Yuxiao,ZHANG Jianda,QIAO Peng,LI Shanping . Research on technique of aerobic granular sludge cultivationby seeding EGSB anaerobic granular sludge[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(4): 56 -59 .
[7] Yue Khing Toh1， XIAO Wendong2， XIE Lihua1. Wireless sensor network for distributed target tracking: practices via real test bed development[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 50 -56 .
[8] SUN Weiwei， WANG Yuzhen. Finite gain stabilization of singlemachine infinite bus system subject to saturation[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 69 -76 .
[9] SUN Yu-li,LI De-fa,ZUO Dun-wen,QI mei . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(6): 19 -23 .
[10] WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd