A Survey of the Generalized Assignment Problem and Its Applications
作者： Temel Öncan
关键词: Facility location problem 、 Variable neighborhood search 、 Knapsack problem 、 Continuous knapsack problem 、 Metaheuristic 、 Mathematical optimization 、 Linear bottleneck assignment problem 、 Weapon target assignment problem 、 Mathematics 、 Generalized assignment problem
摘要: Abstract Given n items and m knapsacks, the Generalized Assignment Problem (GAP) is to find optimum assignment of each item exactly one knapsack, without exceeding capacity any knapsack. This problem can also be described as optimal jobs mcapacitated agents. During last three decades, many papers have been published on GAP. In this survey we mainly concentrate its real‐life applications in scheduling, timetabling, telecommunication, facility location, transportation, production planning, etc. We mention some most recent solution approaches: from state‐of‐the‐art metaheuristics variable neighborhood search algorithms exact procedures simple heuristic algorithms.
gsu.edu.tr
sci-hub.se 参考文章(151)
Konstantin Kogan, Avraham Shtub, Vadim E. Levit, DGAP - The Dynamic Generalized Assignment Problem Annals of Operations Research. ,vol. 69, pp. 227- 239 ,(1997) , 10.1023/A:1018933012422
L.R. Foulds, J.M. Wilson, A variation of the generalized assignment problem arising in the New Zealand dairy industry Annals of Operations Research. ,vol. 69, pp. 105- 114 ,(1997) , 10.1023/A:1018968625626
Jacques A. Ferland, Generalized Assignment-Type Problems: A Powerful Modeling Scheme PATAT '97 Selected papers from the Second International Conference on Practice and Theory of Automated Timetabling II. pp. 53- 77 ,(1997) , 10.1007/BFB0055881
Alan P. French, John M. Wilson, Heuristic Solution Methods for the Multilevel Generalized Assignment Problem Journal of Heuristics. ,vol. 8, pp. 143- 153 ,(2002) , 10.1023/A:1017900606269
Jayant R. Kalagnanam, Andrew J. Davenport, Ho S. Lee, Computational Aspects of Clearing Continuous Call Double Auctions with Assignment Constraints and Indivisible Demand Electronic Commerce Research. ,vol. 1, pp. 221- 238 ,(2001) , 10.1023/A:1011589804040
H. Edwin Romeijn, Nanda Piersma, A Probabilistic Feasibility and Value Analysis of the Generalized Assignment Problem Journal of Combinatorial Optimization. ,vol. 4, pp. 325- 355 ,(2000) , 10.1023/A:1009874227903
Mutsunori Yagiura, Takashi Yamaguchi, Toshihide Ibaraki, A Variable Depth Search Algorithm for the Generalized Assignment Problem Meta-Heuristics : Advances and Trends in Local Search Paradigms for Optimization. pp. 459- 471 ,(1999) , 10.1007/978-1-4615-5775-3_31
J.M. Belenguer, E. Benavent, The Capacitated Arc Routing Problem: Valid Inequalities and Facets Computational Optimization and Applications. ,vol. 10, pp. 165- 187 ,(1998) , 10.1023/A:1018316919294
Daniel Serra, Helena Ramalhinho Lourenço, Adaptive search heuristics for the generalized assignment problem soft computing. ,vol. 9, pp. 209- 234 ,(2002)
Alberto Ceselli, Giovanni Righini, A branch-and-price algorithm for the capacitated p-median problem Networks. ,vol. 45, pp. 125- 142 ,(2005) , 10.1002/NET.V45:3