In this article, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) to generate a good approximation of the efficient or Pareto optimal set of a multi-objective combinatorial optimization problem. The algorithm is applied for the 0/1 knapsack problem with r objective functions. This problem is formulated as r classic 0/1 knapsack problems. n items, … Read more
The multiprocessor scheduling problem consists in scheduling a set of tasks with known processing times into a set of identical processors so as to minimize their makespan, i.e., the maximum processing time over all processors. We propose a new heuristic for solving the multiprocessor scheduling problem, based on a hybrid heuristic to the bin packing … Read more
We propose a new strategy for solving the non-bijective graph matching problem in model-based pattern recognition. The search for the best correspondence between a model and an over-segmented image is formulated as a combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together … Read more
Professional sports leagues are a major economic activity around the world. Teams and leagues do not want to waste their investments in players and structure in consequence of poor schedules of games.Game scheduling is a difficult task, involving several decision makers, different types of constraints, and multiple objectives to optimize. The Traveling Tournament Problem abstracts … Read more
We show in this work how the problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition coloring problem in a conflict graph. A new tabu search heuristic is also proposed for the … Read more
This paper presents an annotated bibliography of greedy randomized adaptive search procedures (GRASP). The bibliography is current up to early 2004. The bibliography contains: background material; tutorials and surveys; enhancements to the basic method; hybrid methods; software; parallel GRASP; graph theory; quadratic and other assignment problems; location, layout, and cutting; covering, clustering, packing, and partitioning; … Read more
This paper deals with a capacitated hub location problem arising in the design of telecommunications networks. The problem is different from the classical hub location problem in two ways: the cost of using an edge is not linear but stepwise and the capacity of an hub restricts the amount of traffic transiting through the hub … Read more
A Greedy Randomized Adaptive Search Procedure (GRASP) is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and local search. Path-relinking is an intensification strategy that explores trajectories that connect high quality solutions. We analyze two parallel strategies for GRASP with path-relinking and propose a criterion … Read more
This document contains references related to GRASP (greedy randomized adaptive search procedure) that have either appeared in the literature or as technical reports. If you are aware of any uncited reference, incorrectly cited reference, or update to a cited reference, please contact Mauricio G. C. Resende at the address given at the end of this … Read more
A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. We propose a new neighborhood structure for the phylogeny problem. A GRASP heuristic based on this neighborhood structure and using VND for … Read more