×

A genetic algorithm for the generalised assignment problem. (English) Zbl 0881.90070

Summary: We present a genetic algorithm (GA)-based heuristic for solving the generalised assignment problem. The generalized 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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cattrysse, D.; Van Wassenhove, L. N., A survey of algorithms for the generalized assignment problem, Eur. J. Oper. Res., 60, 260-272 (1992) · Zbl 0760.90071
[2] Osman, I. H., Heuristics for the generalised assignment problem: simulated annealing and tabu search approaches, OR Spektrum, 17, 211-225 (1995) · Zbl 0841.90098
[3] Beasley, J. E. and Chu, P. C., A Genetic Algorithm for the Set Covering Problem. Eur. J. Oper. Res.; Beasley, J. E. and Chu, P. C., A Genetic Algorithm for the Set Covering Problem. Eur. J. Oper. Res. · Zbl 0953.90565
[4] Chu, P. C.; Beasley, J. E., A genetic algorithm for the set partitioning problem, (Working paper (1995), The Management School, Imperial College: The Management School, Imperial College London SW7 2AZ, England) · Zbl 0953.90565
[5] Cattrysse, D., Set partitioning approaches to combinatorial optimization problems, (Ph.D. thesis (1990), Katholieke Universiteit Leuven, Centrum Industrieel Beleid: Katholieke Universiteit Leuven, Centrum Industrieel Beleid Belgium)
[6] Cattrysse, D.; Salomon, M.; Van Wassenhove, L. N., A set partitioning heuristic for the generalized assignment problem, Eur. J. Oper. Res., 72, 167-174 (1994) · Zbl 0798.90107
[7] Amini, M. M.; Racer, M., A rigorous computational comparison of alternative solution methods for the generalized assignment problem, Mgmt Sci., 40, 868-890 (1994) · Zbl 0816.90096
[8] Klastorin, T. D., An effective subgradient algorithm for the generalized assignment problem, Comp. Oper. Res., 6, 155-164 (1979) · Zbl 0446.90026
[9] Trick, M., A linear relaxation heuristic for the generalised assignment problem, Naval Res. Logist., 39, 137-151 (1992) · Zbl 0758.90047
[10] Fisher, M. L.; Jaikumar, R.; Van Wassenhove, L. N., A multiplier adjustment method for the generalized assignment problem, Mgmt Sci., 32, 1095-1103 (1986) · Zbl 0626.90036
[11] Martello, S.; Toth, P., Linear assignment problems, Annals of Discrete Mathematics, 31, 259-282 (1987)
[12] Ross, G. T.; Soland, R. M., A branch and bound algorithm for the generalized assignment problem, math. Prog., 8, 91-103 (1975) · Zbl 0308.90028
[13] Martello, S.; Toth, P., An algorithm for the generalized assignment problem, (Brans, J. P., Operational Research ’81 (1981), North-Holland), 589-603
[14] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), Wiley: Wiley New York · Zbl 0708.68002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.