UNRELATED PARALLEL MACHINE SCHEDULING USING LOCAL SEARCH

Simulated annealing and taboo search are well-established local search methods for obtaining approximate solutions to a variety of combinatorial optimization problems. More recently, genetic algorithms have also been applied. However, there are few studies which compare the relative performance of these different methods on the same problem. In this paper, these techniques are applied to the problem of scheduling jobs on unrelated parallel machines to minimize the maximum completion time. Results of extensive computational tests indicate that the quality of solutions generated by a genetic algorithm is poor. However, a hybrid method in which descent is incorporated into the genetic algorithm is comparable in performance with simulated annealing and taboo search.