Adaptive approach heuristics for the generalized assignment problem

Helena Ramalhinho-Lourenço () and Daniel Serra ()
Additional contact information
Helena Ramalhinho-Lourenço: https://www.upf.edu/web/econ/faculty/-/asset_publisher/6aWmmXf28uXT/persona/id/3418484

Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra

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.

Keywords: Metaheuristics; generalized assignment; local search; GRASP; tabu search; ant systems (search for similar items in EconPapers)
JEL-codes: C61 C63 L80 (search for similar items in EconPapers)
Date: 1998-05
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://econ-papers.upf.edu/papers/288.pdf Whole Paper (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:upf:upfgen:288

Access Statistics for this paper

More papers in Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra
Bibliographic data for series maintained by ( this e-mail address is bad, please contact ).