Discrete differential evolution metaheuristics for permutation flow shop scheduling problems

Abstract

Scheduling problems (SP) in the permutation flow shop (PFS) environment are present in many intermittent production industries, consisting of to determinate the processing order of n jobs in m sequential machines, with the purpose to optimize some performance criterion. In this paper, three optimization algorithms based on discrete differential evolution (DE) metaheuristics are applied to PFS scheduling problems, to minimize the makespan, are proposed, that are Discrete Differential Evolution, and Discrete Self-Adaptive Differential Evolution for SP in PFS named DDE-PFS, DSADE-PFS1 and DSADE-PFS2, respectively. The Carlier (CB), Heller (HB), Reeves (RB), and Taillard (TB) numerical benchmarks were adopted to test the proposed optimization algorithms. The performance of the optimization algorithms was evaluated regarding relative percentage error (RPE) criterion, convergence, standard deviation (Std), statistical tests of Friedman and post-hoc Nemenyi. For TB, the DSADE-PFS1 algorithm presented a better performance in terms of RPE and Std measures. For CB and HB, the DSADE-PFS1 and DSADE-PFS2 algorithms presented a better performance in RPE, and the DSADE-PFS2 algorithm in terms of Std. For RB, the DSADE-PFS2 algorithm presented a better performance in RPE, while the DSADE-PFS1 algorithm was achieved in Std. Considering the processing time for each algorithm the DSADE-PFS2 approach achieved better results than CB, HB, and RB. Overall the results have shown that the optimization approaches proposed in this paper are promising for the SP in PFS, with highly competitive results in terms of average performance values.