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 combinato rial optimization problems. More recently, genetic algorithms have als o been applied. However, there are few studies which compare the relat ive performance of these different methods on the same problem. In thi s paper, these techniques are applied to the problem of scheduling job s on unrelated parallel machines to minimize the maximum completion ti me. Results of extensive computational tests indicate that the quality of solutions generated by a genetic algorithm is poor. However, a hyb rid method in which descent is incorporated into the genetic algorithm is comparable in performance with simulated annealing and taboo searc h.