Parallel strategies for GRASP with path-relinking

R.M. Aiex and M.G.C. Resende

To appear in "Metaheuristics: Progress as Real Problem Solvers,"  T. Ibaraki, K. Nonobe and M. Yagiura, (Eds.), Kluwer Academic Publishers,  2005.

ABSTRACT

A Greedy Randomized Adaptive Search Procedure (GRASP) is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on  a greedy randomized algorithm and local search. Path-relinking is an intensification strategy that explores trajectories that connect high quality solutions. We analyze two parallel strategies for GRASP  with path-relinking and propose a criterion to predict parallel efficiency based on experiments  with a  sequential implementation of the algorithm.  Independent and cooperative parallel strategies are described and implemented for the 3-index assignment problem and the job-shop scheduling problem. The computational results for independent parallel strategies are shown to qualitatively behave as predicted by the criterion.


PDF file of full paper

DjVu file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 12 October 2004

Copyright Notice