A variable iterated greedy algorithm with differential evolution for solving no-idle flowshops

Abstract

In this paper we present a variable iterated greedy algorithm where its parameters (basically destruction size and probability of whether or not to apply the iterated greedy algorithm to an individual) are optimized by the differential evolution algorithm. A unique multi-chromosome solution representation is presented in such a way that the first chromosome represents the destruction size and the probability whereas the second chromosome is simply a job permutation assigned to each individual in the population randomly. The proposed algorithm is applied to the no-idle permutation flowshop scheduling problem with the makespan criterion. The performance of the proposed algorithm is tested on the Ruben Ruiz's benchmark suite and compared to their best known solutions available in http://soa.iti.es/rruiz as well as to a very recent discrete differential evolution algorithm from the literature. The computational results show its highly competitive performance and ultimately 183 out of 250 instances are further improved. In comparison to the very recent hybrid discrete differential evolution algorithm 114 out of 150 new best known solutions they provided are also further improved. © 2012 Springer-Verlag. © 2012 Elsevier B.V. All rights reserved.