A methodology for the analysis of parallel GRASP strategies

Renata M. Aiex (rmainf.puc-rio.br)
Mauricio G. C. Resende (mgcrresearch.att.com)

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.

Download: [PDF]

Entry Submitted: 04/07/2003
Entry Accepted: 04/07/2003
Entry Last Modified: 04/07/2003

Modify/Update this entry