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.
AT&T Labs Research Technical Report, April 7, 2003.