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

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.