To access the full text documents, please follow this link: http://hdl.handle.net/10230/292

Adaptive approach heuristics for the generalized assignment problem;
Meta-heuristics for the Generalized Assignment Problem
Ramalhinho-Lourenço, Helena; Serra, Daniel
Universitat Pompeu Fabra. Departament d'Economia i Empresa
The Generalized Assignment Problem consists in assigning a setof tasks to a set of agents with minimum cost. Each agent hasa limited amount of a single resource and each task must beassigned to one and only one agent, requiring a certain amountof the resource of the agent. We present new metaheuristics forthe generalized assignment problem based on hybrid approaches.One metaheuristic is a MAX-MIN Ant System (MMAS), an improvedversion of the Ant System, which was recently proposed byStutzle and Hoos to combinatorial optimization problems, and itcan be seen has an adaptive sampling algorithm that takes inconsideration the experience gathered in earlier iterations ofthe algorithm. Moreover, the latter heuristic is combined withlocal search and tabu search heuristics to improve the search.A greedy randomized adaptive search heuristic (GRASP) is alsoproposed. Several neighborhoods are studied, including one basedon ejection chains that produces good moves withoutincreasing the computational effort. We present computationalresults of the comparative performance, followed by concludingremarks and ideas on future research in generalized assignmentrelated problems.
2005-09-15
Statistics, Econometrics and Quantitative Methods
metaheuristics
generalized assignment
local search
grasp
tabu search
ant systems
L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Working Paper
         

Show full item record

 

Coordination

 

Supporters