Heuristics for the Generalized Assignment Problem - Simulated Annealing and Tabu Search Approaches

Osman, I.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 available from this repository)

The full text of this publication is not available from this repository. (Contact us about this Publication)

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: Faculties > Science Technology and Medical Studies > School of Mathematics Statistics and Actuarial Science
Depositing User: O.O. Odanye
Date Deposited: 01 Jun 2009 20:25
Last Modified: 01 Jun 2009 20:25
Resource URI: http://kar.kent.ac.uk/id/eprint/19427 (The current URI for this page, for reference purposes)
  • Depositors only (login required):