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

作者：Deng, Guanlong; Gu, Xingsheng^*

来源：Computers & Operations Research, 2012, 39(9): 2152-2160.

DOI：10.1016/j.cor.2011.10.024

• No-idle flow shop
• Scheduling
• Differential evolution
• Speed-up
• Insert neighborhood
• Local search

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.

• 出版日期2012-9
• 单位华东理工大学