A Hybrid Genetic Algorithm for Solving the Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times

The parallel machine scheduling problem is a well known combinatorial optimization problem with several applications in computer science, telecommunications and operations management. Several studies have shown that exact approaches for this problem are not useful in practical situations due to the high computational costs involved. This paper describes a hybrid genetic algorithm for solving the unrelated parallel machine scheduling problem with sequence dependent setup times. Computational results with simulated data are presented and discussed. A case study on the granite industry is presented.The proposed approach outperformed three traditional dispatch rules presented in the current literature.