# Adaptive search heuristics for the generalized assignment problem.

Helena Ramalhinho Lourenço; Daniel Serra

Mathware and Soft Computing (2002)

- Volume: 9, Issue: 2-3, page 209-234
- ISSN: 1134-5632

## Access Full Article

top## Abstract

top## How to cite

topRamalhinho Lourenço, Helena, and Serra, Daniel. "Adaptive search heuristics for the generalized assignment problem.." Mathware and Soft Computing 9.2-3 (2002): 209-234. <http://eudml.org/doc/39244>.

@article{RamalhinhoLourenço2002,

abstract = {The Generalized Assignment Problem consists of assigning a set of tasks to a set of agents at minimum cost. Each agent has a limited amount of a single resource and each task must be assigned to one and only one agent, requiring a certain amount of the agent's resource. We present the application of a MAX-MIN Ant System (MMAS) and a greedy randomized adaptive search procedure (GRASP) to the generalized assignment problem based on hybrid approaches. The MMAS heuristic can be seen as an adaptive sampling algorithm that takes into consideration the experience gathered in earlier iterations of the algorithm. Moreover, the latter heuristic is combined with local search and tabu search heuristics to improve the search. Several neighborhoods are studied, including one based on ejection chains that produces good moves without increasing the computational effort. We present computational results of a comparative analysis of the two adaptive heuristics, followed by concluding remarks and ideas on future research in generalized assignment related problems.},

author = {Ramalhinho Lourenço, Helena, Serra, Daniel},

journal = {Mathware and Soft Computing},

keywords = {Optimización global; Algoritmo de búsqueda; Problemas combinatorios; Asignación; Heurística; generalized assignment problem},

language = {eng},

number = {2-3},

pages = {209-234},

title = {Adaptive search heuristics for the generalized assignment problem.},

url = {http://eudml.org/doc/39244},

volume = {9},

year = {2002},

}

TY - JOUR

AU - Ramalhinho Lourenço, Helena

AU - Serra, Daniel

TI - Adaptive search heuristics for the generalized assignment problem.

JO - Mathware and Soft Computing

PY - 2002

VL - 9

IS - 2-3

SP - 209

EP - 234

AB - The Generalized Assignment Problem consists of assigning a set of tasks to a set of agents at minimum cost. Each agent has a limited amount of a single resource and each task must be assigned to one and only one agent, requiring a certain amount of the agent's resource. We present the application of a MAX-MIN Ant System (MMAS) and a greedy randomized adaptive search procedure (GRASP) to the generalized assignment problem based on hybrid approaches. The MMAS heuristic can be seen as an adaptive sampling algorithm that takes into consideration the experience gathered in earlier iterations of the algorithm. Moreover, the latter heuristic is combined with local search and tabu search heuristics to improve the search. Several neighborhoods are studied, including one based on ejection chains that produces good moves without increasing the computational effort. We present computational results of a comparative analysis of the two adaptive heuristics, followed by concluding remarks and ideas on future research in generalized assignment related problems.

LA - eng

KW - Optimización global; Algoritmo de búsqueda; Problemas combinatorios; Asignación; Heurística; generalized assignment problem

UR - http://eudml.org/doc/39244

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.