Greedy randomized adaptive search procedure

The greedy randomized adaptive search procedure (also known as GRASP) is a metaheuristic algorithm commonly applied to combinatorial optimization problems. GRASP typically consists of iterations made up from successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a local search. The greedy randomized solutions are generated by adding elements to the problem's solution set from a list of elements ranked by a greedy function according to the quality of the solution they will achieve. To obtain variability in the candidate set of greedy solutions, well-ranked candidate elements are often placed in a restricted candidate list (also known as RCL), and chosen at random when building up the solution. This kind of greedy randomized construction method is also known as a semi-greedy heuristic, first described in Hart and Shogan (1987).

GRASP was first introduced in Feo and Resende (1989). Survey papers on GRASP include Feo and Resende (1995), Pitsoulis and Resende (2002), and Resende and Ribeiro (2003). An annotated bibliography of GRASP can be found in Festa , G. C Resende (2002).

References

• J.P. Hart and A.W. Shogan (1987) Semi-greedy heuristics: An empirical study. Operations Research Letters, 6:107–114, 1987.
• T.A. Feo and M.G.C. Resende (1989) A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8:67–71, 1989.
• T.A. Feo and M.G.C. Resende (1995) Greedy randomized adaptive search procedures. J. of Global Optimization, 6:109–133, 1995.
• L. Pitsoulis and M. G. C. Resende (2002) Greedy randomized adaptive search procedures. In P. M. Pardalos and M. G. C. Resende, editors, Handbook of Applied Optimization, pp. 168–181, Oxford University Press.
• M. G. C. Resende and C. C. Ribeiro (2003) Greedy randomized adaptive search procedures. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pp. 219–249, Kluwer Academic Publishers, 2003.
• P. Festa and M. G. C. Resende (2002) GRASP: An annotated bibliography. In C. C. Ribeiro and P. Hansen, editors, Essays and Surveys on Metaheuristics, pp. 325–367, Kluwer Academic Publishers, 2002.
• Prabhaharan G , Shahul Hamid Khan B and Rakesh L (2006). An implementation of GRASP in flow shop scheduling, International Journal of advanced manufacturing Technology, Vol. 30, No. 11- 12, 1126 – 1131. GRASP
• Shahul Hamid Khan B, Prabhaharan G and Asokan P (2007). A GRASP algorithm for m - machine flow shop scheduling problem with bicriteria of makespan and maximum tardiness, International Journal of Computer Mathematics, Vol. 84, Issue 12, 1731 – 1741.
• Shahul Hamid Khan B, Prabhaharan G (2009). A GRASP Algorithm with Path Relinking for Permutation Flow Shop Scheduling Problem International Journal of Artificial Intelligence and Computational Research (IJAICR), Vol 1 (1) 13-18.