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 jo
bs to m agents such that each job is assigned to exactly one agent, su
bject to an agent's capacity. In addition to the standard GA procedure
s, our GA heuristic incorporates a problem-specific coding of a soluti
on 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 algori
thm 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 al
gorithms in terms of solution quality. Copyright (C) 1996 Elsevier Sci
ence Ltd