An Efficient Memetic Algorithm for the Flexible Job Shop with Setup Times

This paper addresses the flexible job shop scheduling problem with sequence-dependent setup times (SDST-FJSP). This is an extension of the classical job shop scheduling problem with many applications in real pro-duction environments. We propose an effective neigh-borhood structure for the problem, including feasibil-ity and non improving conditions, as well as procedures for fast neighbor estimation. This neighborhood is em-bedded into a genetic algorithm hybridized with tabu search. We conducted an experimental study to com-pare the proposed algorithm with the state-of-the-art in the SDST-FJSP and also in the standard FJSP. In this study, our algorithm has obtained better results than those from other methods. Moreover, it has established new upper bounds for a number of instances.