Parallel Strategies for GRASP with path-relinking

Renata M. Aiex (rmaiexyahoo.com)
Mauricio G. C. Resende (mgcrresearch.att.com)

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.

Keywords: Combinatorial optimization, job shop scheduling, 3-index assignment, local search, GRASP, path-relinking, parallel computing

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Combinatorial Optimization

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: AT&T Labs Research Technical Report TD-5SQKM9. October 27, 2003.

Download: [PDF]

Entry Submitted: 10/27/2003
Entry Accepted: 10/31/2003
Entry Last Modified: 10/27/2003

Modify/Update this entry