A differential evolution algorithm for the no-idle flowshop scheduling problem with total tardiness criterion

Abstract

In this paper we investigate the use of a continuous algorithm for the no-idle permutation flowshop scheduling (NIPFS) problem with tardiness criterion. For this purpose a differential evolution algorithm with variable parameter search (vpsDE) is developed to be compared to a well-known random key genetic algorithm (RKGA) from the literature. The motivation is due to the fact that a continuous DE can be very competitive for the problems where RKGAs are well suited. As an application area we choose the NIPFS problem with the total tardiness criterion in which there is no literature on it to the best of our knowledge. The NIPFS problem is a variant of the well-known permutation flowshop (PFSP) scheduling problem where idle time is not allowed on machines. In other words the start time of processing the first job on a given machine must be delayed in order to satisfy the no-idle constraint. The paper presents the following contributions. First of all a continuous optimisation algorithm is used to solve a combinatorial optimisation problem where some efficient methods of converting a continuous vector to a discrete job permutation and vice versa are presented. These methods are not problem specific and can be employed in any continuous algorithm to tackle the permutation type of optimisation problems. Secondly a variable parameter search is introduced for the differential evolution algorithm which significantly accelerates the search process for global optimisation and enhances the solution quality. Thirdly some novel ways of calculating the total tardiness from makespan are introduced for the NIPFS problem. The performance of vpsDE is evaluated against a well-known RKGA from the literature. The computational results show its highly competitive performance when compared to RKGA. It is shown in this paper that the vpsDE performs better than the RKGA thus providing an alternative solution approach to the literature that the RKGA can be well suited. © 2011 Taylor & Francis. © 2011 Elsevier B.V. All rights reserved.