Adaptive search heuristics for the generalized assignment problem.

Título inglés	Adaptive search heuristics for the generalized assignment problem.
Título español	Heurística de búsqueda adaptativa para el problema de asignación generalizada.
Autor/es	Ramalhinho Lourenço, Helena ; Serra, Daniel
Organización	DEE Univ. Pompeu Fabra, Barcelona, España
Revista	1134-5632
Publicación	2002, 9 (2-3): 209-234, 42 Ref.
Tipo de documento	articulo
Idioma	Inglés
Resumen inglés	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.
Clasificación UNESCO	120304 ; 120700
Palabras clave español	Optimización global ; Algoritmo de búsqueda ; Problemas combinatorios ; Asignación ; Heurística
Código MathReviews	MR1983793
Código Z-Math	Zbl 1031.68056
Acceso al artículo completo