@phdthesis{Aie02a,
        author = "R.M. Aiex",
        title = "Uma investiga\c{c}\~ao experimental da distribui\c{c}\~ao
		 de probabilidade de tempo de solu\c{c}\~ao em heur\'{\i}sticas
		 {GRASP} e sua aplica\c{c}\~ao na an\'alise de
		 implementa\c{c}\~oes paralelas",
	school = "Department of Computer Science, Catholic University of
		  Rio de Janeiro",
        address = "Rio de Janeiro, Brazil",
        year = "2002",
	annote	= "This thesis describes a new methodology
		   for the analysis of {GRASP}.  Hybrid strategies
		   with path-relinking are also proposed.  These
		   are studied on the 3-index assignment problem
		   as well as the job shop scheduling problem and
		   analyzed with the proposed methodology to predict
		   qualitatively how the quality of the solution
		   varies in a parallel independent {GRASP}.",
}

@Article{AieBinRes03a,
        author = "R.M. Aiex and S. Binato and M.G.C. Resende",
        title = "Parallel {GRASP} with path-relinking for job  
                 shop scheduling",
        journal = "Parallel Computing",
	volume  = {29},
	pages = {393--430},
        year = "2003",
        annote   =     "In this paper, a parallel {GRASP} with path-relinking 
			as intensification strategy for the job shop 
			problem is described using some ideas proposed 
			in the {GRASP} of Binato et al. (2002). 
			During the construction phase, the restricted 
			candidate list is made up of elements 
			that among those that can be added to the current 
			partial solution without causing any infeasibility 
			have greedy function value above a specified 
			threshold. 
			While in Binato et al. (2002) the greedy function 
			value of an operation $k$ is the makespan resulting 
			from the inclusion of $k$ to the already scheduled 
			operations, in this paper the authors propose 
			the so called {\em time-remaining} function. 
			It is a new greedy function to be used in conjunction 
			with the makespan and that favors operations from 
			jobs having long remaining processing times. 
			The authors employ the two exchange local searches 
			used in Binato et al. (2002). 
			Two parallelization strategies are proposed: an 
			independent and a cooperative strategy. 
			The independent strategy shows a sub-linear 
			speedup, while the cooperative one shows an 
			approximate linear speedup, thus confirming that 
			the extra time spent for processes communication 
			is compensated by an increase in solution quality.",
}

@Article{AieResRib02a,
	 author = "R.M. Aiex and M.G.C. Resende and C.C. Ribeiro",
	 title  = "Probability distribution of solution time in
		  {GRASP}: {A}n experimental investigation",
        journal = "Journal of Heuristics",
        volume = "8",
	pages = "343--373",
	year = "2002",
        annote   =     "The authors study the probability distributions of 
			solution time to a sub-optimal target value in five 
			{GRASPs} that have appeared
                	in the literature and for which source code is available.
                	The distributions are estimated by running 12,000
                	independent runs of the heuristic.
                	Standard methodology for graphical analysis is used to compare
                	the empirical and theoretical distributions and estimate the
                	parameters of the distributions.
                	They conclude that the solution time
                	to a sub-optimal target value fits a two-parameter exponential
                	distribution.
                	Hence, it is possible to approximately achieve linear speed-up
                	by implementing {GRASP} in parallel.",
}

@mastersthesis{Alv98a,
	author = "A.C.F. Alvim",
	title = "Parallelization strategies for the metaheuristic {GRASP}",
        school = "Department of Computer Science,
		Catholic University of Rio de Janeiro",
	address = "Rio de Janeiro, RJ 22453-900 Brazil",
        month = "April",
	year = "1998",
	annote = 	"Two parallelization strategies for
                	{GRASP} are discussed and compared:
                	parallelization by distributing {GRASP} iterations and
                	parallelization by varying the {GRASP} random parameter
                	$\alpha$. Both strategies are adapted to several
                	parallel computation models, such as MPI 
			(Message Passing Interface) and PVM (Parallel Virtual 
			Machine). In Portuguese."
}

@techreport{AlvRib98a,
	author = "A.C.F. Alvim and C.C. Ribeiro",
	title = "Load balancing in the parallelization of the metaheuristic
		  {GRASP}",
	institution = "Department of Computer Science,
			Catholic University of Rio de Janeiro",
	address = "Rio de Janeiro, RJ 22453-900 Brazil",
	year = "1998",
        annote = 	"Two parallelization strategies for {GRASP} are 
			compared.
                	The difference between the two strategies concerns 
			the way in which data is partitioned:
                	pre-scheduled (static load balancing) or self-scheduled
                	(dynamic load balancing). 
			The strategies have been tested considering an 
			application to optimal traffic assignment
                	in TDMA satellite system. 
			Best results have been obtained
                	by using the self-scheduling strategy. In Portuguese."
}

@techreport{DiaVelSol99a,
        author = {J.C.Z. Diaz and J.S. Vel\'azquez and J.F. Solis},
	title = {{Un modelo tipo {GRASP} para la paralelizaci\'on de algoritmos
	         en computadoras {MIMD}: Aplicaci\'on al algoritmo de
		 Jarmenson}}, 
        institution = {Universidad Aut\'onoma del Estado de Morelos,
	               Facultad de Ciencias},
	address = {Cuernavaca, Morelos, Mexico},
	annote = {In this paper, the authors use a {GRASP} to 
		optimize operations needed to parallelize algorithms 
		on a MIMD. 
		The greedy criterion is to minimize the cost associated 
		with comunication among processors, while local search 
		uses an exchange neighborhood structure. 
		In Spanish.},
	year = {1999}
}

@Article{FeoResSmi94a,
	author = "T.A. Feo and M.G.C. Resende and S.H. Smith",
	title = "A greedy randomized adaptive search procedure for
                 maximum independent set",
	journal = "Operations Research",
	volume = "42",
	pages = "860--878",
	year = "1994",
        annote   =     "A {GRASP} for approximately solving the
                	maximum independent set problem is described.
                	The greedy function chosen orders admissible vertices
                	with respect to the minimum admissible vertex degree.
                	The adjective admissible is referred to a vertex that
                	is not adjacent to any vertex in the current independent
                	set. 
			The neighborhood definition used in the local search
                	is $(2,1)$-exchange, where two nonadjacent vertices
                	can be added to the current solution if a single vertex
                	from the solution is removed.
                	The proposed heuristic can be easily implemented in
                	parallel by decomposing the problem into smaller
                	subproblems, each defined by conditioning on vertices
                	being in the solution.
                	An implementation of this algorithm was tested
                	on a MIMD computer with up to eight processors.
                	Average linear speedup is observed.",
}

@phdthesis{Mar99a,
        author = "S.L. Martins",
        title = "Estrat\'egias de Paraleliza\c{c}\~ao de Metaheur\'{\i}sticas 
	         em Ambientes de Mem\'oria Distribu\'{\i}da",
	school = "Department of Computer Science, Catholic University of
                  Rio de Janeiro",
        address = "Rio de Janeiro, Brazil",
        year = "1999",
	annote =	"This thesis considers parallelization strategies for
                	metaheuristics in distributed memory environments.
                	{GRASPs} for the Steiner tree problem in graphs are
                	described and implemented in parallel. In Portuguese."
}

@Article{MarResRibPar00b,
	author = "S.L. Martins and M.G.C. Resende and C.C. Ribeiro and
			  P.M. Pardalos",
        title = "A parallel {GRASP} for the {Steiner} tree problem in graphs
                  using a hybrid local search strategy",
        journal = "Journal of Global Optimization",
        volume = "17",
        year = "2000",
        pages = "267--283",
        annote   =     "This paper presents a {GRASP} for the Steiner
                	problem in graphs.  The construction phase is
                	based on the Mehlhorn distance network heuristic, which
                	consists of computing the modified distance network graph
                	and using Kruskal's algorithm to solve the minimum spanning
                	tree problem for the resulting graph. The local search is
                	done by using a combination of key-path based local search
                	and node based local search.",
}

@incollection{MurParPit98b,
	author = "R.A. Murphey and P.M. Pardalos and L.S. Pitsoulis",
	title = "A parallel {GRASP} for the data association multidimensional 
		assignment problem",
	booktitle = "Parallel Processing of Discrete Problems",
	editor = "P.M.  Pardalos",
	series = "The {IMA} Volumes in Mathematics and its Applications",
	publisher = "Springer-Verlag",
	volume = "106", 
	pages = "159--180", 
	year = "1998",
        annote =     	"A {GRASP} for finding good solutions for
                	the data association multidimensional assignment problem
                	is described.
                	At each discrete time interval, the data set is 
			formulated as a multidimensional assignment problem 
			(MAP) with a maximum likelihood cost function. 
			A near-optimal solution to each MAP is obtained with 
			a {GRASP}.
                	The proposed method can be easily parallelized to 
			substantially decrease the running time."
}

@incollection{ParPitMavRes95a,
	author = "P.M. Pardalos and L. Pitsoulis and
		  T. Mavridou and M.G.C. Resende",
	title = "Parallel search for combinatorial optimization: {G}enetic
		 algorithms, simulated annealing and {GRASP}",
	booktitle = "Parallel Algorithms for Irregularly
	             Structured Problems, Proceedings of
		     the Second International Workshop --Irregular'95",
        editor = "A. Ferreira and J. Rolim",
	series = "Lecture Notes in Computer Science",
	publisher = "Springer-Verlag",
	volume = "980",
	year   = "1995",
	pages  = "317--331",
        annote   =     "This paper summarizes some parallel search techniques
                	for approximating the global optimal solution of 
			combinatorial optimization problems. 
			For large-scale problems, one of the main limitations 
			of heuristic search is its computational complexity. 
			Therefore, efficient parallel implementation of search 
			algorithms can significantly increase the size of the 
			problems that can be solved.",
}

@incollection{ParPitRes95a,
	author = "P.M. Pardalos and L.S. Pitsoulis and M.G.C. Resende",
	title = "A parallel {GRASP} implementation for the quadratic
                 assignment problem",
	booktitle = "Parallel Algorithms for Irregularly
	             Structured Problems~-- Irregular'94",
        editor = "A. Ferreira and J. Rolim",
	publisher = "Kluwer Academic Publishers",
	year = "1995",
	pages = "115--130",
        annote =	"Efficient parallel techniques for large-scale sparse 
			quadratic assignment problems are discussed.  
			The paper provides a detailed description of a
                	parallel implementation on an MIMD computer of the 
			sequential {GRASP} proposed by Li, Pardalos, and 
			Resende (1994) for solving the QAP.
                	The {GRASP} iterations are distributed among the 
			processors.
                	Each processor is given its own input data and random 
			number sequence and are run independently.
                	A shared global variable stores the
                	value of the incumbent solution."
}

@Article{ParPitRes96a,
	author = "P.M. Pardalos and L.S. Pitsoulis and M.G.C. Resende",
	title = "A parallel {GRASP} for {MAX-SAT} problems",
	journal = "Lecture Notes in Computer Science",
	volume = "1184",
        pages = "575--585",
	year = "1996",
        annote   =     "A parallel {GRASP} for weighted maximum
                	satisfiability (MAX-SAT) problem is proposed.
                	The {GRASP} is based on the
                	serial {GRASP} presented by Resende, Pitsoulis, and
                	Pardalos (1997).
                	The parallel implementation distributes the {GRASP} 
			iterations among several processors operating in 
			parallel, avoiding that two processors have as input
                	the same random number generator seed. 
			The best solution found among all processors is 
			identified and used as solution of the problem.",
}

@Article{RibRos02a,
        author = "C.C. Ribeiro and I. Rosseti",
        title = "A parallel {GRASP} for the 2-path network design problem",
        journal = "Lecture Notes in Computer Science",
        volume = "2004",
        pages = "922--926",
        year = "2002",
        annote   =     "Given a connected undirected graph $G(V,E)$, a 
			nonnegative edge weight function 
			$w:\ E\rightarrow {\mathbb R}^+$, 
			and a set $D$ of pairs of origin-destination nodes, the 
			$2$-path network design problem consists in finding a 
			minimum weighted subset of edges $E'\subseteq E$ 
			containing a $2$-path between the extremities of every 
			origin-destination pair in $D$. 
			In this paper, a parallel {GRASP} with path-relinking 
			is proposed for solving this problem.",
}

@mastersthesis{Riv98a,
        author = "L.I.D. Rivera",
        title = "Evaluation of parallel implementations of heuristics
		  for the course scheduling problem",
	school = "Instituto Tecnologico y de Estudios Superiores de
		  Monterrey",
        address = "Monterrey, Mexico",
        year = "1998",
	annote   =	"This thesis presents several parallel
                 	implementations of heuristics for the
                 	course scheduling problem.
                 	One of the heuristics is a {GRASP}.
                 	In Spanish."
}

@techreport{AieRes03a,
	author = {R.M. Aiex and M.G.C. Resende},
	title = {Parallel strategies for {GRASP} with path-relinking},
	institution = {Internet and Network Systems Research Center, 
		       AT\&T Labs Research},
        address = {Florham Park, NJ},
   	year = {2003},
	annote = {
		This paper analyzes two parallel
		strategies for GRASP  with path-relinking and proposes a
		criterion to predict parallel efficiency based on experiments
		with a  sequential implementation of the algorithm.
		Independent and cooperative parallel strategies are described
		and implemented for the 3-index assignment problem and the
		job-shop scheduling problem. The computational results for
		independent parallel strategies are shown to qualitatively
		behave as predicted by the criterion.
		},
}