Optimization Online


Parallel Strategies for GRASP with path-relinking

Renata M. Aiex (rmaiex***at***yahoo.com)
Mauricio G. C. Resende (mgcr***at***research.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society