Parallel Strategies for GRASP with path-relinking
Renata M. Aiex (rmaiexyahoo.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.
Entry Submitted: 10/27/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|