Osman, Ibrahim H.
(1995)
*
Heuristics for the Generalized Assignment Problem - Simulated Annealing and Tabu Search Approaches.
*
Or Spektrum,
17
(4).
pp. 211-225.
ISSN 0171-6468.
(The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided)
(KAR id:19427)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided. |

## Abstract

The generalised assignment problem (GAP) is the problem of finding a minimum cost assignment of a set of jobs to a set of agents. Each job is assigned to exactly one agent. The total demands of all jobs assigned to any agent can not exceed the total resources available to that agent. A review of exact and heuristic methods is presented. A lambda-generation mechanism is introduced. Different search strategies and parameter settings are investigated for the lambda-generation descent, hybrid simulated annealing/tabu search and tabu search heuristic methods. The developed methods incorporate a number of features that have proven useful for obtaining optimal and near optimal solutions. The effectiveness of our approaches is established by comparing their performance in terms of solution quality and computional requirement to other specialized branch-and-bound tree search, simulated annealing and set partitioning heuristics on a set of standard problems from the literature.

Item Type: | Article |
---|---|

Uncontrolled keywords: | generalized assignment problem; local search; simulated annealing; tabu search; heuristics; set partitioning; branch and bound |

Subjects: | Q Science > Operations Research - Theory |

Divisions: | Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Mathematics, Statistics and Actuarial Science |

Depositing User: | O.O. Odanye |

Date Deposited: | 01 Jun 2009 20:25 UTC |

Last Modified: | 16 Nov 2021 09:57 UTC |

Resource URI: | https://kar.kent.ac.uk/id/eprint/19427 (The current URI for this page, for reference purposes) |

- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV

- Depositors only (login required):