Pereamon Copyright © 1996 Elsevier Science Ltd 6 PII: S0305-0548(%)00032-9 Printed in Great Britain. All rights reserved Computers Ops Res. Vol. 24, No. I, pp. 17-23, 1997 9 1996 Elsevier Science Ltd t Britain. All rights reserved 0305-0548/96 $17.00+0.00 A GENETIC ALGORITHM FOR THE GENERALISED ASSIGNMENT PROBLEM P. C. Chutt and J. E. Beasley§ The Management School, Imperial College, London SW7 2AZ, England (Received January 1996; in revised form April 1996) Scope and Purpose—The generalised assignment problem is an important problem, that, judging by the number of articles concerned with it, has attracted a fair amount of interest from Operations Research workers. Both exact (optimal) and heuristic approaches have been presented in the literature. This article shows that genetic algorithms, an approach that arose with computer science, can be applied successfully to a problem that has traditionally been associated with Operations Research. The article demonstrates clearly that genetic algorithms are capable of producing better quality results for the generalised assignment problem than traditional Operations Research heuristic approaches (albeit at greater computational cost). This result should be of interest, not only to those interested in the generalised assignment problem, but also to others involved in developing heuristics for integer programming problems. In particular, this article illustrates that, applied correctly, genetic algorithms can provide the best possible heuristic solution approach for such problems. In order to advance the state of the art in algorithms for the generalised assignment problem a benchmark set of relatively large test problems is solved and made publically available to others. Abstract—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 OA 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. Copyright © 1996 Elsevier Science Ltd 1. INTRODUCTION The generalised assignment problem (GAP) is a well-known, NP-complete combinatorial optimisation problem which involves 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 available capacity. Recent extensive reviews of applications of the GAP and the existing exact and heuristic algorithms can be found in Cattrysse and Van Wassenhove [1] and Osman [2] and will not be repeated here. The existing exact algorithms are only effective in certain GAP instances where the constraints are loose. For the more difficult highly-capacitated problems, exact algorithms can only solve problems involving up to a few hundred decision variables before the search trees grow prohibitively large. Thus larger-sized problems are often tackled by applying heuristics to obtain approximate solutions. This article proposes a heuristic method based on genetic algorithms. A genetic algorithm (GA) is an 'intelligent' probabilistic search algorithm which simulates the process of evolution by taking a population of solutions and applying genetic operators in each reproduction. Each solution in the population is evaluated according to some fitness measure. Highly fit solutions in the population are given opportunities to reproduce. New 'offspring' solutions are generated and unfit solutions in the population are replaced. This evaluation-selection-reproduction cycle is repeated until a satisfactory solution is found. Examples for which GAs have been applied successfully to combinatorial optimisation problems are the set covering problem [3] and the set partitioning problem [4]. In addition to the standard GA procedures, our GA heuristic also incorporates a problem-specific t To whom all correspondence should be addressed (email: p.chu@ic.ac.uk) t Paul. C. Chu received a Bachelor's degree in Electrical Engineering from Cornell University in 1992 and a Master's degree in Operations Research and Industrial Engineering also from Cornell University in 1993. He is currently doing a PhD in the Management School (Operational Research Group) at Imperial College. § J. E. Beasley has a BA in Mathematics from Cambridge University and an MSc and PhD in Management Science from Imperial College, London. He is a member of the academic staff at Imperial College, London. His research interests are in linear optimisation (principally integer programming/combinatorial optimisation) and he is the author of some fifty papers. 17 18 P. C. Chu and J. E. Beasley representation scheme, separated fitness and unfitness evaluation functions and a local improvement procedure. Our empirical testing shows that the quality of the solutions generated by the GA heuristic is superior to all existing heuristic methods, albeit at greater computational expense compared with some heuristics. Larger-sized problems up to 20 agents and 200 jobs with different levels of difficulty are also generated and benchmark results for these are given using our GA heuristic. 2. THE GENERALISED ASSIGNMENT PROBLEM (GAP) Let / = {1,2,. ..,m] be a set of agents, and let J = {1,2,...,«} be a set of jobs. For i e I, j e J, define cu as the cost of assigning job y' to agent / (or assigning agent i to job y), rv as the resource required by agent / to perform job;, and b-, as the resource availability (capacity) of agent i. Also, x0 is a 0-1 variable that is 1 if agent í performs job y and 0 otherwise. The mathematical formulation of the GAP is: Minimise X X c fa (1) lei jsJ Subject to Xxu=\,VjeJ (2) X r faciei (3) ^e{0,l},VJ6/,Vyey (4) (2) ensures that each job is assigned to exactly one agent and (3) ensures that the total resource requirement of the jobs assigned to an agent does not exceed the capacity of the agent. 3. THE GA HEURISTIC Genetic algorithms deal with a population of solutions and tend to manipulate each solution in a simple way. In a GA a potential solution to a problem is represented as a set of parameters known as a gene. These parameters are joined together to form a string of values known as a chromosome. A good representation scheme is important in a GA and it should clearly define meaningful crossover, mutation and other problem-specific operators such that minimal computational effort is involved in these procedures. To meet this requirement, we use an efficient representation in which the solution structure is an ordered structure («-dimensional vector) of integer numbers. These integer numbers identify the agents, as assigned to vector elements denoted by the jobs (see Fig. 1). This representation ensures that all the equality constraints in (2) are automatically satisfied since exactly one agent is assigned to each job. However this representation does not guarantee mat the capacity constraints in (3) will be satisfied. The steps involved in our GA heuristic for the GAP are as follows: 1. Generate an initial population of N randomly constructed solutions. Each of the initial solutions is generated by randomly assigning an agent to each job. Note that since the initial solutions may violate the capacity constraints in (3), initial solutions may be infeasible. Let skj represent the agent assigned to job y (j=l.....n) in solution k (k=l.....A0- 2. Decode the solution structure to obtain the fitness value. The fitness of a solution is calculated according to a given fitness function. Conventionally it must take into account not just the cost of a solution, but also the degree of infeasibility of a solution. Rather than penalise the fitness (or the objective function) when a solution is infeasible, which is a common approach in GAs, we adopt the approach used in [4] and associate two values with each solution. One of these values is called fitness and the other is called unfitness. The fitness/* of solution k is equal to its objective function value as calculated by A-.S/v (5) J€J job 1 2 3 4 5 •••«-! n 2 1 3 m 3 ... 1 2 Fig. 1. Representation of an individual's chromosome. A genetic algorithm for the generalised assignment problem 19 The unfitness uk of solution k is a measure of infeasibility (in relative terms) as calculated by uk= S max IE/ K-i/'H (6) and note here that uk =0 if and only if solution k is feasible. 3. Select two parent solutions for reproduction. We use the binary tournament selection method. In a binary tournament selection, two individuals are chosen randomly from the population. The more fit (smaller fitness value) individual is then allocated a reproductive trial. In order to produce a child, two binary tournaments are held, each of which produces one parent. Note that the selection criteria does not involve the unfitness value of an individual. 4. Generate a child solution by first applying a crossover operator to the selected parents. We use the simple one-point crossover operator, in which a crossover point pel is selected randomly and the child solution will consist of the first p genes taken from the first parent and the remaining (n-p) genes taken from the second parent, or vice versa with equal probabilities. The crossover procedure is followed by a mutation procedure. This mutation procedure involves exchanging elements in two randomly selected genes (i.e. exchanging assigned agents between two randomly selected jobs). Computational experience (see Section 4) showed that the GA involving only the crossover and mutation operators is effective in producing good-quality solutions. But the algorithm can be further improved by using a problem-specific heuristic operator which involves two local improvement steps as described below. (a) Let Tj represent the agent assigned to job j in the child solution. For each agent i e /, if the resource capacity of agent / is exceeded I S r^bj J, then a single randomly selected job q with \jeJ.T,=i J Tq = i is reassigned from agent i to the next agent (in the order of i+l,...,m, 1,...,/— 1) that has adequate remaining capacity (if one can be found). (b) For each joby e7, search for min,J6^,y that satisfies both cj/ B — u a-s c "Š e ^ s " e* .22 ľ8 s1! t) .-3 11 t« "o S — ** XI ^ S 00 Cu s ä ° S S ě o «u i? * ř £ CO 'S « O CA »U "3 'S 11 S I g, s 5Í T» CB «ž n i* Jf •o M B " C3 u b a> 2 -c r-, - 6 H (D 3 S g CA '« g U •32 'S t"5 0-T3 1 ä) "O 1 S g 3 3 S g 2 00 ^ " .2 o| 8 <2 >» Í2 « •a E ä'5 .a -a ® S *I £ 6 1° 'S .2 y -?s ts 3 •n u § -c H S *> •g c« O 3 :t O- B .. *-* lä CA u a a i e C * « 2 «lüg 8 3-S e»-i S3 Ö »J .g S3 T» Ü u -e © «•"■ •£. 'S 3 T3 > tí a * XI « XI III TtO-tSWNOON^MOinOCl-h^ c5-dd6d-rtNOirtd"d^ — oso — (Ncnoo^n,.,^ — c*-, M •"~d"sOf^^-r-m t»- — « ^ —< M f*^ ■* M M CÍ d (*) Cí Třsooosooo-ímo^so^mr-^rooo^cípo — OsoofMr-MOsoo^ — RS^^MSEl^^^aS^^SIi^mřaíř^i^v^SS&S ^^^^^«^^^«^««««««'nintfii^r^r^^^cnCnoiCno'^.,^, — _.r-*r*-t*-i^-ŕ*-asosososos„-_--__~^.3—1 — 2 iiiiliiiiiiíliiiiiiiiii A genetic algorithm for the generalised assignment problem 21 Table 2. Computational results for 'large-sized' problems Size Best Avg. Avg. Prob Overall Best Soľ n Exec. type m n Best so ľ n in each of the 10 trials soľ n time time A 5 100 o o 0 0 o 0 0 0 0 0 1698 0.5 435.0 200 o 0 0 0 o o 0 0 0 0 3235 0.3 898.4 10 100 o o o 0 o o 0 0 0 o 1360 0.3 409.4 200 0 0 0 0 o 0 0 0 0 0 2623 17.0 1213.0 20 100 0 o 0 0 o 0 0 0 0 0 1158 0.4 737.0 200 o o o 0 0 o 0 0 o 0 2339 43.4 1687.8 B 5 100 1847 b 1847 1849 1846 1848 1852 1859 i860 b 1843 126.9 288.2 200 3563 3570 3563 3559 3566 3555 3567 b 3565 3566 3553 439.5 790.0 10 100 b b b 1409 b b 1409 1409 1409 1409 1407 30.1 276.0 200 2842 2838 2833 2836 2835 2836 2844 2835 b 2837 2831 608.4 1027.4 20 100 1168 1167 1168 b 1167 1167 b b 1167 b 1166 191.5 617.3 200 2341 2341 2344 2341 2341 2341 2343 2341 2341 b 2340 518.5 1323.5 C 5 100 b 1938 1940 1939 1940 1943 1942 b 1942 1937 1931 139.1 302.4 200 b 3461 3463 3461 3465 3460 3466 3468 3467 3470 3458 531.2 810.1 10 100 1409 b b b 1405 b 1412 1407 1412 b 1403 170.6 394.2 200 2822 2821 2820 2818 2821 2826 2822 2816 b 2815 2814 628.6 1046.0 20 100 1247 1254 1255 1249 1247 1247 1251 1249 1251 b 1244 279.9 669.3 200 2401 b 2406 2410 2402 2409 2404 2412 2409 2408 2397 1095.9 1792.3 D 5 100 6379 6406 6409 6397 6415 b 6388 6391 6406 6384 6373 369.9 530.3 200 12869 12825 b 12801 12826 12816 12827 12835 12843 12823 127% 1665.9 1942.8 10 100 6438 6431 6436 6431 6476 6417 6443 6418 b 6407 6379 870.2 1094.7 200 12603 12641 12638 12654 12605 12633 b 12632 12615 12648 12601 2768.7 3189.6 20 100 6327 6293 b 6332 6308 6314 6273 6324 6308 6337 6269 1746.1 2126.1 200 12532 12483 12535 b 12552 12567 12516 12567 12510 12567 12452 4878.4 5565.1 o = optima] solution value. b = best overall solution value. • The number of agents m is set to 5, 8 and 10 and the ratio p of die number of jobs to the number of agents I p= — J is set to 3, 4, 5 and 6 to determine the number of jobs. Five problems are V m) generated for each agent/job combination, giving a total of 60 problems. We have indexed each agent/job combination as follows: Name gapl gap2 gap3 gap4 gap5 gap6 gap7 gap8 gap9 gap 10 gapll gap 12 m,n 5,15 5,20 5,25 5,30 8,24 8,32 8,40 8,48 10,30 10,40 10,50 10,60 • The resource requirement rVj are integers from the uniform distribution ř/(5, 25), the cost Table 3. Average percentage deviation (