Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm

This paper proposes a hybrid metaheuristic for the minimization of makespan in scheduling problems with parallel machines and sequence-dependent setup times. The solution approach is robust, fast, and simply structured, and comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) for Solution evolution, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. The hybridization of an ACO. SA with VNS, combining the advantages of these three individual components. is the key innovative aspect of the approach. Two algorithms of a hybrid VNS-based algorithm, SA/VNS and ACO/VNS, and the VNS algorithm presented previously are used to compare with the proposed hybrid algorithm to highlight its advantages in terms of generality and quality for large instances. (C) 2008 Published by Elsevier Ltd.