A methodology for the analysis of parallel GRASP strategies
Renata M. Aiex (rmainf.puc-rio.br)
Abstract: In this paper, we describe a methodology for the analysis of greedy randomized adaptive search procedures (GRASP). GRASP is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and a local search. Hybrid approaches of GRASP with path-relinking developed for the 3-index assignment problem (AP3) and for the job-shop scheduling problem (JSP) are analyzed with the methodology proposed. Independent and cooperative parallelization strategies are described and implemented for the AP3 and for the JSP. The computational results for independent parallel strategies are compared to the results obtained using the methodology. The experiments confirm the fact that the methodology proposed is a useful tool to predict qualitatively the behavior of GRASP when implemented using multiple independent processes.
Keywords: GRASP, parallel computing, path-relinking
Category 1: Optimization Software and Modeling Systems (Parallel Algorithms )
Category 2: Combinatorial Optimization (Meta Heuristics )
Citation: AT&T Labs Research Technical Report, April 7, 2003.
Entry Submitted: 04/07/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|