A survey of the generalized assignment problem and its applications


Oncan T.

INFOR, cilt.45, sa.3, ss.123-141, 2007 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Derleme
  • Cilt numarası: 45 Sayı: 3
  • Basım Tarihi: 2007
  • Doi Numarası: 10.3138/infor.45.3.123
  • Dergi Adı: INFOR
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.123-141
  • Galatasaray Üniversitesi Adresli: Evet

Ö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.