A genetic algorithm for the generalised assignment problem

In this paper we 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�...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 1997, Vol.24 (1), p.17-23
Main Authors: Chu, P.C., Beasley, J.E.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Assignment problem
Exact sciences and technology
Flows in networks. Combinatorial problems
Genetic algorithms
Heuristic
Operational research and scientific management
Operational research. Management science
Operations research
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we 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, our 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 our 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 our heuristic also compares favourably to all other existing heuristic algorithms in terms of solution quality.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/S0305-0548(96)00032-9