Towards grid implementations of metaheuristics for hard combinatorial optimization problems

Metaheuristics are approximate algorithms that are able to find very good solutions to hard combinatorial optimization problems. They do, however, offer a wide range of possibilities for implementations of effective robust parallel algorithms which run in much smaller computation times than their sequential counterparts. We present four slightly differing strategies for the parallelization of an extended GRASP with ILS heuristic for the mirrored traveling tournament problem. Computational results on widely used benchmark instances, using a varying number of processors, illustrate the effectiveness and the scalability of the different strategies. These low communication cost parallel heuristics not only find solutions faster, but also produce better quality solutions than the best known sequential algorithm.