A genetic algorithm for scheduling open shops with sequence-dependent setup times

Abstract

In the open shop scheduling problem with sequence-dependent setup times, there is no established order for the processing of the jobs, which leads to a large number of possible solutions for the scheduling problem. Furthermore, there is a setup time between two consecutive operations, which depends on the job previously processed. In this work we propose a hybrid genetic algorithm for the OSSP with sequence-dependent setup times and total completion time minimization as objective function. Our proposal uses two novel constructive heuristics which are combined for the generation of the initial population. We carry out an extensive computational experience using problem instances taken from the related literature to evaluate the performance of the proposed algorithms as compared to existing heuristics for the problem. The quality of the solutions and the CPU time required are used as performance criteria. Among them, the genetic algorithm with direct decoding presents a smaller value for the average relative percentage deviation in comparison with the electromagnetic algorithm proposed by Naderi et al. (2011). The computational results prove the excellent performance of the proposed metaheuristic for the tested instances, resulting in the most efficient algorithm so-far for the problem under consideration.