Article ID: | iaor20121275 |
Volume: | 39 |
Issue: | 9 |
Start Page Number: | 2152 |
End Page Number: | 2160 |
Publication Date: | Sep 2012 |
Journal: | Computers and Operations Research |
Authors: | Gu Xingsheng, Deng Guanlong |
Keywords: | networks, heuristics: 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.