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