Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times

This paper deals with an unrelated parallel machine scheduling problem with the objective of minimizing the makespan. There are machine-dependent and job sequence-dependent setup times and all jobs are available at time zero. This is a NP-hard problem and a set of dominance properties are developed including inter-machine (i.e., adjacent and non-adjacent interchange) and intra-machine switching properties as necessary conditions of job sequencing orders in an optimal schedule. As a result, by applying these dominance properties for a given sequence, a near-optimal solution can be derived. In addition, a new meta-heuristic is introduced by integrating the dominance properties with genetic algorithm to further improve the solution quality for larger problems. The performance of this meta-heuristic is evaluated by using benchmark problems from the literature. The intensive experimental results show that GADP can find all optimal solutions for the small problems and outperformed the solutions obtained by the existing heuristics for larger problems. (C) 2010 Elsevier B.V. All rights reserved.