Skip to main content

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

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)

University of Kent Author Information

Osman, Ibrahim H..

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.