A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times

• DOI: 10.1016/j.ejor.2011.01.011
• Publication Date: 2011-01-10T09:05:26Z
• Authors: Eva Vallada; Rubén Ruiz
• Keywords: Setup times; Makespan; Parallel machine; Scheduling; ESTADISTICA E INVESTIGACION OPERATIVA; 0211 other engineering and technologies; 02 engineering and technology

The authors are indebted to the referees and editor for the many constructive comments that have significantly improved the paper. This work is partially funded by the Spanish Ministry of Science and Innovation, under the project "SMPA - Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances" with reference DPI2008-03511/DPI. The authors should also thank the IMPIVA - Institute for the Small and Medium Valencian Enterprise, for the project OSC with references IMIDIC/2008/137, IMIDIC/2009/198 and IMIDIC/2010/175 and the Polytechnic University of Valencia, for the project PPAR with reference 3147. Eva Vallada is also partly funded by the Government of Comunitat Valenciana under a grant (BEST 2009). The authors are also indebted with Dario Diotallevi for his help in coding some of the re-implemented methods from the literature used in the tests.<br/>In this work a genetic algorithm is presented for the unrelated parallel machine scheduling problem in which machine and job sequence dependent setup times are considered. The proposed genetic algorithm includes a fast local search and a local search enhanced crossover operator. Two versions of the algorithm are obtained after extensive calibrations using the Design of Experiments (DOE) approach. We review, evaluate and compare the proposed algorithm against the best methods known from the literature. We also develop a benchmark of small and large instances to carry out the computational experiments. After an exhaustive computational and statistical analysis we can conclude that the proposed method shows an excellent performance overcoming the rest of the evaluated methods in a comprehensive benchmark set of instances.<br/>