Optimization Online


A methodology for the analysis of parallel GRASP strategies

Renata M. Aiex (rma***at***inf.puc-rio.br)
Mauricio G. C. Resende (mgcr***at***research.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

  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