×

Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches. (English) Zbl 0841.90098

Summary: The generalized assignment problem (GAP) is the problem of finding a minimum cost assignment of a set of jobs to a set of agents. Each job is assigned to exactly one agent. The total demands of all jobs assigned to any agent can not exceed the total resources available to that agent. A review of exact and heuristic methods is presented. A \(\lambda\)-generation mechanism is introduced. Different search strategies and parameter settings are investigated for the \(\lambda\)-generation descent, hybrid simulated annealing/tabu search and tabu search heuristic methods. The developed methods incorporate a number of features that have proven useful for obtaining optimal and near optimal solutions. The effectiveness of our approaches is established by comparing their performance in terms of solution quality and computational requirements to other specialized branch-and-bound tree search, simulated annealing and set partitioning heuristics on a set of standard problems from the literature.

MSC:

90C10 Integer programming
90B80 Discrete location and assignment
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts EHL, Korst J (1988) Simulated annealing and boltzmann machines. Wiley and Sons, Chichester
[2] Amini MM, Racer M (1994) A rigourous computational comparison of alternative solution methods for the generalized assignment problem. Manag Sci 40:868–890 · Zbl 0816.90096 · doi:10.1287/mnsc.40.7.868
[3] Balas E, Martin CH (1980) Pivot and complement – a heuristic for 0/1 programming. Manag Sci 26:86–96 · Zbl 0442.90060 · doi:10.1287/mnsc.26.1.86
[4] Barcia P, Holm S (1988) A revised bound improvement sequence algorithm. Eur J Oper Res 36:202–206 · Zbl 0643.90062 · doi:10.1016/0377-2217(88)90426-2
[5] Barcia P, Jörnsten K (1990) Improved Lagrangean decomposition: An application to the generalised assignment problem. Eur J Oper Res 46:84–92 · Zbl 0711.90055 · doi:10.1016/0377-2217(90)90300-Z
[6] Beasley JE (1990) OR-library: distribution test problems by electronic mail. Library email address using anonymous ftp:mscmga.ms.ic.ac.uk. J Oper Res Soc 41:1069–1072
[7] Benders JF, Van Nunen JA (1983) A property of assignment type mixed linear programming problems. Oper Res Lett 2:47–52 · Zbl 0506.90060 · doi:10.1016/0167-6377(83)90035-4
[8] Cattrysse DG (1990) Set partitioning approaches to combinatorial optimization problems. Ph. D. Thesis, Katholieke Universiteit Leuven, Departement Wertuigkunde, Centrum Industrieel Beleid, Belgium
[9] Cattrysse DG, Van Wassenhove LN (1992) A survey of algorithms for the generalized assignment problem. Eur J Oper Res 60:260–272 · Zbl 0760.90071 · doi:10.1016/0377-2217(92)90077-M
[10] Cattrysse DG, Salomon M, Van Wassenhove LN (1994) A set partitioning heuristic for the generalized assignment problem. Eur J Oper Res 72:167–174 · Zbl 0798.90107 · doi:10.1016/0377-2217(94)90338-7
[11] Collins NE, Eglese RW, Golden BL (1988) Simulated annealing: An annotated bibliography. Am J Math Manag Sci 8:209–307 · Zbl 0669.65047
[12] Dammeyer D, Voß S (1993) Dynamic tabu list management using the reverse elimination method. Ann Oper Res 41:31–46 · Zbl 0775.90290 · doi:10.1007/BF02022561
[13] De Werra D, Hertz A (1989) Tabu search techniques: A tutorial and an application to neural networks. OR Spektrum 11:131–141 · Zbl 0672.90089 · doi:10.1007/BF01720782
[14] Dyer M, Frieze A (1990) Probabilistic analysis of the generalized assignment problem. Math Program 55:169–181 · Zbl 0767.90052 · doi:10.1007/BF01581197
[15] Fang L, Li T (1990) Design of competition based neural networks for combinatorial optimization. Int J Neural System 3:221–235 · doi:10.1142/S0129065790000126
[16] Fisher M, Jaikumar R, Van Wassenhove L (1986) A multiplier adjustment method for the generalised assignment problem. Manag Sci 32:1095–1103 · Zbl 0626.90036 · doi:10.1287/mnsc.32.9.1095
[17] Fisher M, Jaikumar R (1981) A generalised assignment heuristic for the large scale vehicle routing. Networks 11:109–124 · doi:10.1002/net.3230110205
[18] Gavish B, Pirkul H (1991) Algorithms for the multi-resource generalized assignment problem. Manag Sci 37:695–713 · Zbl 0753.90053 · doi:10.1287/mnsc.37.6.695
[19] Gheysens F, Golden BL, Assad A (1984) A comparison of techniques for solving the fleet size and mix vehicle routing problem. OR Spektrum 6:207–216 · Zbl 0549.90068 · doi:10.1007/BF01720070
[20] Glover F (1986) Future path for integer programming and links to artificial intelligence. Comput Oper Res 13:533–549 · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[21] Glover F (1989) Tabu search part I. ORSA J Comput 1:190–206 · Zbl 0753.90054
[22] Glover F (1990) Tabu search part II. ORSA J Comput 2:4–32 · Zbl 0771.90084
[23] Glover F, Laguna M (1993) Tabu search. In: Modern heuristic techniques for combinatorial problems Reeves CR (ed). Blackwell, Oxford, U.K., pp 70–150
[24] Glover F, Laguna M, Taillard E, de Werra D (1993) Tabu search. Annals of Operations Research 41:Baltzer AG, Switzerland · Zbl 0772.90063
[25] Glover F, Taillard E, de Werra D (1993) A user’s guide to tabu search. Ann Oper Res 41:3–28 · Zbl 0772.90063 · doi:10.1007/BF02078647
[26] Gottlieb ES, Rao MR (1990) (1,K)-Configuration facets for the generalized assignment problem. Math Program 46:53–60 · Zbl 0701.90065 · doi:10.1007/BF01585726
[27] Gottlieb ES, Rao MR (1990) The generalized assignment problem – valid inequalities and facets. Math Program 46:31–52 · Zbl 0694.90071 · doi:10.1007/BF01585725
[28] Guinard M, Rosenwein MB (1989) An improved dual based algorithm for the generalised assigment problem. Oper Res 17:658–663 · Zbl 0674.90068 · doi:10.1287/opre.37.4.658
[29] Hallefjord A, Jörnsten KO, Värbrand P (1993) Solving large scale generalised assignment problem. Oper Res 64:103–104 · Zbl 0776.90057 · doi:10.1016/0377-2217(93)90011-B
[30] Hasan M, Osman IH (1995) Local search strategies for the maximal planar graph. Int Transact Oper Res 2:(1) forthcoming
[31] Jänicke W (1989) Optimal assignment of orders to parallel working subplants without splitting. Computer-Integrated Manufacturing Syst 2:186–187 · doi:10.1016/0951-5240(89)90009-8
[32] Jörnsten KO, Näsberg M (1986) A new lagrangean relaxation approach to the generalised assignment problem. Eur J Oper Res 27:313–323 · Zbl 0617.90068 · doi:10.1016/0377-2217(86)90328-0
[33] Jörnsten KO, Värbrand P (1990) Relaxation techniques and valid inequalities applied to the generalized assignment problem. Asia-Pacific Oper Res 7:172–189 · Zbl 0726.90063
[34] Jörnsten KO, Värbrand P (1991) A hybrid algorithm for the genralized assignment problem. Optimization 2:273–282 · Zbl 0726.90065 · doi:10.1080/02331939108843666
[35] Kirkpatrick S, Gelatt JR. CD, Vecchi PM (1983) Optimization by simulated annealing. Science 220:671–680 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[36] Klastorin TD (1979) An effective sub-gradient algorithm for the generalised assignment problem. Cumput Oper Res 6:155–164 · doi:10.1016/0305-0548(79)90028-5
[37] Klastorin TD (1979) On the maximal covering location problem and the generalized assignment problem. Manag Sci 25:107–112 · Zbl 0446.90026 · doi:10.1287/mnsc.25.1.107
[38] Laguna M, Kelly JP, Gonzalez-Velarde JL, Glover F (1995) Tabu search for the multilevel assignment problem. Eur J Oper Res 95:(82)170 · Zbl 0905.90122
[39] Laporte G, Osman IH (1995) Metaheuristics in combinatorial optimization. Annals of Operations Research, Baltzer AG, Switzerland. (forthcoming)
[40] Lee MK (1992) A storage assignment policy in a man-on-board automated storage/retrieval system. Int J Prod Res 30:2281–2292 · doi:10.1080/00207549208948155
[41] Martello S, Toth P (1981) An algorithm for the generalised assignment problem. In proceedings of the 9th IFORS conference, Hamburg, Germany · Zbl 0473.90047
[42] Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley and Sons, Chichester · Zbl 0708.68002
[43] Martello S, Toth P (1992) Generalized assignment problems. Lecture Notes, In Computer Science 660:351–369
[44] Mazzola JB (1989) Generalized assignment with nonlinear capacity interaction. Manag Sci 35:923–941 · Zbl 0675.90057 · doi:10.1287/mnsc.35.8.923
[45] Mazzola JB, Neebe AW (1993) An algorithm for the bottleneck generalized assignment problem. Comput Oper Res 20:355–362 · Zbl 0772.90064 · doi:10.1016/0305-0548(93)90079-X
[46] Osman IH (1990) A comparison of heuristics for the generalised assignment problem. Research Report, University of Kent, Canterbury. Presented at IFORS 90, Athens
[47] Osman IH (1991) Metastrategy simulated annealing and tabu search for combinatorial optimization problems. Ph. D. Thesis, The Management School, Imperial College, University of London
[48] Osman IH (1993) Metastrategy simulated annealing and tabu search algorithm for the vehicle routing problem. Ann Oper Res 41:421–451 · Zbl 0775.90153 · doi:10.1007/BF02023004
[49] Osman IH, Christofides N (1994) Capacitated clustering problems by hybrid simulated annealing and tabu search. Int Transact Oper Res 1:317–336 · Zbl 0857.90107 · doi:10.1016/0969-6016(94)90032-9
[50] Osman IH, Laporte G (1995) Modern Heuristics for combinatorial optimization problems. An annotated bibliography. Ann Oper Res (forthcoming)
[51] Osman IH, Pott CN (1989) Simulated annealing for permutation flow-shop scheduling. Omega 17:551–557 · doi:10.1016/0305-0483(89)90059-5
[52] Osman IH, Salhi S (1994) Heuristics for the vehicle fleet mix problem. Proceedings of TRISTAN II, Capri, Italy. Bianco L, (editor) I.A.S.I.-C.N.R. Viale Manzoni 30, 00185 Rome, Italy. Part I:67–72
[53] Pesch E, Voß S (1995) Applied local search. OR Spektrum 17:55–65 · Zbl 0842.90098 · doi:10.1007/BF01719248
[54] Racer M, Amini M (1994) A robust heuristic for the generalized assignment problem. Ann Oper Res 50:487–503 · Zbl 0812.90097 · doi:10.1007/BF02085655
[55] Reeves CR (1993) Modern heuristic techniques for combinatorial problems. Blackwell, Oxford · Zbl 0942.90500
[56] Ross GT, Soland RM (1975) A branch and bound algorithm for the generalised assignment problem. Math Program 8:91–103 · Zbl 0308.90028 · doi:10.1007/BF01580430
[57] Ross GT, Soland RM (1977) Modelling facility location problems as generalised assignment problems. Manag Sci 24:345–357 · Zbl 0378.90066 · doi:10.1287/mnsc.24.3.345
[58] Savelsbergh MWP (1993) A branch-and-price algorithm for the generalized assignment problem, Report COC-93-02, Computational Optimization Centre, Georgia Institute of Technology, Atlanta, Georgia, USA
[59] Shtub A (198) Modelling group technology cell formation as a generalized assignment problem. Int J Prod Res 27:775–782
[60] Skorin-Kapov J (1990) Tabu search applied to the quadratic assignment problem. ORSA J Comput 2:33–45 · Zbl 0752.90054
[61] Thangiah SR, Osman IH, Vinayagamoorthy R, Sun T (1993) Algorithms for Vehicle Routing Problems With Time Deadlines. Am J Math Manag Sci 13:323–357 · Zbl 0808.90064
[62] Thangiah SR, Osman IH, Sun T (1994) Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems With Time Windows. Working Paper UKC/IMS/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury, UK
[63] Trick MA (1992) A linear relaxation heuristic for the generalized assignment problem. Naval Res Logist 39:137–151 · Zbl 0758.90047 · doi:10.1002/1520-6750(199203)39:2<137::AID-NAV3220390202>3.0.CO;2-D
[64] Van Laarhoven PJM, Aarts EHL (1987) Simulated annealing theory and applications. Reidel, Dordrecht · Zbl 0643.65028
[65] Zimokha VA, Rubinshtein MI (1988) R & D planning and the generalised assignment problem. Automation and Remote Control 49:484–492 · Zbl 0659.90058
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.