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)

790

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] 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.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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] 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 .
[2] CHEN Huaxin, CHEN Shuanfa, WANG Binggang. The aging behavior and mechanism of base asphalts[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 125 -130 .
[3] BO De-Yun, ZHANG Dao-Jiang. Adaptive spectral clustering algorithm[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 22 -26 .
[4] REN Jing-xi,GENG Jin-hua,GAO Qi-sheng . Quality optimization of the multifactor and multi-index product[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 114 -117 .
[5] MENG Jian, LI Yibin, LI Bin. Bound gait controlling method of quadruped robot[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(3): 28 -34 .
[6] XUE Hongtao,TIAN Guohui,LI Xiaolei,LU Fei . Application of the QR Code for various object identificationand manipulation[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(6): 25 -30 .
[7] MA Qi-Hua, WANG Yi-Tai. Application of the high density resistivity method to surrvey huge empty water  outside of a coal mine[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(4): 107 -111 .
[8] ZHANG Ming-Liang, LI Fan-Chang. A new search method for a game tree[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(6): 1 -7 .
[9] ZHOU Shaowei. The finite-time stability of stochastic Markov jumping systems[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(2): 78 -84 .
[10] XU Xiao-Dong, LIU Yan, WANG Wei-Jiang, CHEN Tong-Lei, LIU Qi. Non-dimensional design method of pressure vessels  and its application(Ⅱ)[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(6): 101 -104 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd