Adaptive approach heuristics for the generalized assignment problem
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Ramalhinho-Lourenço, Helena
- dc.contributor.author Serra, Daniel
- dc.contributor.other Universitat Pompeu Fabra. Departament d'Economia i Empresa
- dc.date.accessioned 2020-05-25T09:27:01Z
- dc.date.available 2020-05-25T09:27:01Z
- dc.date.issued 1998-05-01
- dc.date.modified 2020-05-25T09:17:31Z
- dc.description.abstract The Generalized Assignment Problem consists in assigning a set of tasks to a set of agents with 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 resource of the agent. We present new metaheuristics for the generalized assignment problem based on hybrid approaches. One metaheuristic is a MAX-MIN Ant System (MMAS), an improved version of the Ant System, which was recently proposed by Stutzle and Hoos to combinatorial optimization problems, and it can be seen has an adaptive sampling algorithm that takes in 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. A greedy randomized adaptive search heuristic (GRASP) is also proposed. Several neighborhoods are studied, including one based on ejection chains that produces good moves without increasing the computational effort. We present computational results of the comparative performance, followed by concluding remarks and ideas on future research in generalized assignment related problems.
- dc.format.mimetype application/pdf*
- dc.identifier https://econ-papers.upf.edu/ca/paper.php?id=288
- dc.identifier.citation Mathware & Soft Computing, Special Issue on Ant Colony Pptimization: Models and Applications, 2, 9, (2002), pp. 209-234
- dc.identifier.uri http://hdl.handle.net/10230/292
- dc.language.iso eng
- dc.relation.ispartofseries Economics and Business Working Papers Series; 288
- dc.rights 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
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/es/
- dc.subject.keyword metaheuristics
- dc.subject.keyword generalized assignment
- dc.subject.keyword local search
- dc.subject.keyword grasp
- dc.subject.keyword tabu search
- dc.subject.keyword ant systems
- dc.subject.keyword Statistics, Econometrics and Quantitative Methods
- dc.title Adaptive approach heuristics for the generalized assignment problem
- dc.title.alternative Meta-heuristics for the Generalized Assignment Problem
- dc.type info:eu-repo/semantics/workingPaper