A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem

Abstract

This paper presents a variable iterated greedy algorithm (IG) with differential evolution (vIG_DE) designed to solve the no-idle permutation flowshop scheduling problem. In an IG algorithm size d of jobs are removed from a sequence and re-inserted into all possible positions of the remaining sequences of jobs which affects the performance of the algorithm. The basic concept behind the proposed vIG_DE algorithm is to employ differential evolution (DE) to determine two important parameters for the IG algorithm which are the destruction size and the probability of applying the IG algorithm to an individual. While DE optimizes the destruction size and the probability on a continuous domain by using DE mutation and crossover operators these two parameters are used to generate a trial individual by directly applying the IG algorithm to each target individual depending on the probability. Next the trial individual is replaced with the corresponding target individual if it is better in terms of fitness. A unique multi-vector chromosome representation is presented in such a way that the first vector represents the destruction size and the probability which is a DE vector whereas the second vector simply consists of a job permutation assigned to each individual in the target population. Furthermore the traditional IG and a variable IG from the literature are re-implemented as well. The proposed algorithms are applied to the no-idle permutation flowshop scheduling (NIPFS) problem with the makespan and total flowtime criteria. The performances of the proposed algorithms are tested on the Ruben Ruiz benchmark suite and compared to the best-known solutions available at http://soa.iti.es/rruiz as well as to those from a recent discrete differential evolution algorithm (HDDE) from the literature. The computational results show that all three IG variants represent state-of-art methods for the NIPFS problem. (C) 2013 Elsevier Ltd. All rights reserved.