A genetic algorithm for the generalised assignment problem

A genetic algorithm for the generalised assignment problem

0.00 Avg rating0 Votes
Article ID: iaor19972517
Country: United Kingdom
Volume: 24
Issue: 1
Start Page Number: 17
End Page Number: 23
Publication Date: Jan 1997
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

In this paper the authors present a genetic algorithm (GA)-based heuristic for solving the generalised assignment problem. The generalised assignment problem is the problem of finding the minimum cost assignment of n jobs to m agents such that each job is assigned to exactly one agent, subject to an agent’s capacity. In addition to the standard GA procedures, the present GA heuristic incorporates a problem-specific coding of a solution structure, a fitness-unfitness pair evaluation function and a local improvement procedure. The performance of the algorithm is evaluated on 84 standard test problems of various sizes ranging from 75 to 4000 decision variables. Computational results show that the genetic algorithm heuristic is able to find optimal and near optimal solutions that are on average less than 0.01% from optimality. The performance of the present heuristic also compares favourably to all other existing heuristic algorithms in terms of solution quality.

Reviews

Required fields are marked *. Your email address will not be published.