A methodology for the analysis of parallel GRASP strategies

  • Renata M. Aiex
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Parallel Algorithms Tags , , Short URL: https://optimization-online.org/?p=9350

    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.

    Citation

    AT&T Labs Research Technical Report, April 7, 2003.

    Article

    Download

    View A methodology for the analysis of parallel GRASP strategies