A survey of the generalized assignment problem and its applications


Oncan T.

INFOR, cilt.45, ss.123-141, 2007 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 45 Konu: 3
  • Basım Tarihi: 2007
  • Doi Numarası: 10.3138/infor.45.3.123
  • Dergi Adı: INFOR
  • Sayfa Sayıları: ss.123-141

Özet

Given n items and m knapsacks, the Generalized Assignment Problem (GAP) is to find the optimum assignment of each item to exactly one knapsack, without exceeding the capacity of any knapsack. This problem can also be described as the optimal assignment of n jobs to m capacitated agents. During the last three decades, many papers have been published on the GAP. In this survey we mainly concentrate on its real-life applications in scheduling, timetabling, telecommunication, facility location, transportation, production planning, etc. We also mention some of the most recent solution approaches: from state-of-the-art metaheuristics to variable neighborhood search algorithms and from exact solution procedures to simple heuristic algorithms.