A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion

被引:76
作者
Deng, Guanlong [1 ]
Gu, Xingsheng [1 ]
机构
[1] E China Univ Sci & Technol, Minist Educ, Key Lab Adv Control & Optimizat Chem Proc, Shanghai 200237, Peoples R China
基金
国家高技术研究发展计划(863计划); 中国国家自然科学基金;
关键词
No-idle flow shop; Scheduling; Differential evolution; Speed-up; Insert neighborhood; Local search; MACHINE; WAIT; OPTIMIZATION; MINIMIZE;
D O I
10.1016/j.cor.2011.10.024
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This paper presents a hybrid discrete differential evolution (HDDE) algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion, which is not so well studied. The no-idle condition requires that each machine must process jobs without any interruption from the start of processing the first job to the completion of processing the last job. A novel speed-up method based on network representation is proposed to evaluate the whole insert neighborhood of a job permutation and employed in HDDE, and moreover, an insert neighborhood local search is modified effectively in HDDE to balance global exploration and local exploitation. Experimental results and a thorough statistical analysis show that HDDE is superior to the existing state-of-the-art algorithms by a significant margin. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码:2152 / 2160
页数:9
相关论文
共 50 条
[41]   An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling [J].
Laha, Dipak ;
Chakraborty, Uday Kumar .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2009, 44 (5-6) :559-569
[42]   A hybrid differential evolution algorithm with estimation of distribution algorithm for reentrant hybrid flow shop scheduling problem [J].
Zhou, Bing-hai ;
Hu, Li-man ;
Zhong, Zhen-yi .
NEURAL COMPUTING & APPLICATIONS, 2018, 30 (01) :193-209
[43]   A Hybrid Backtracking Search Algorithm for Permutation Flow-Shop Scheduling Problem Minimizing Makespan and Energy Consumption [J].
Chen, Peng ;
Wen, Long ;
Li, Ran ;
Li, Xinyu .
2017 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM), 2017, :1611-1615
[44]   A differential evolution algorithm for the permutation flowshop scheduling problem with total flow time criterion [J].
Santucci, Valentino ;
Baioletti, Marco ;
Milani, Alfredo .
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8672 :161-170
[45]   An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion [J].
Pan, Quan-Ke ;
Wang, Ling ;
Zhao, Bao-Hua .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2008, 38 (7-8) :778-786
[46]   An ensemble discrete water wave optimization algorithm for the blocking flow-shop scheduling problem with makespan criterion [J].
Zhao, Fuqing ;
Shao, Dongqu ;
Xu, Tianpeng ;
Zhu, Ningning ;
Jonrinaldi .
APPLIED INTELLIGENCE, 2022, 52 (14) :15824-15843
[47]   An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion [J].
Quan-Ke Pan ;
Ling Wang ;
Bao-Hua Zhao .
The International Journal of Advanced Manufacturing Technology, 2008, 38 :778-786
[48]   The flow shop problem with no-idle constraints: A review and approximation [J].
Goncharov, Yaroslav ;
Sevastyanov, Sergey .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 196 (02) :450-456
[49]   A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem [J].
Wang, Ling ;
Pan, Quan-Ke ;
Tasgetiren, M. Fatih .
COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 61 (01) :76-83
[50]   A New Hybrid Genetic Algorithm to Deal with the Flow Shop Scheduling Problem for Makespan Minimization [J].
Boumediene, Fatima Zohra ;
Houbad, Yamina ;
Hassam, Ahmed ;
Ghomri, Latefa .
COMPUTATIONAL INTELLIGENCE AND ITS APPLICATIONS, 2018, 522 :399-410