A survey of the generalized assignment problem and its applications

Oncan T.

INFOR, vol.45, no.3, pp.123-141, 2007 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Review
  • Volume: 45 Issue: 3
  • Publication Date: 2007
  • Doi Number: 10.3138/infor.45.3.123
  • Journal Name: INFOR
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.123-141
  • Galatasaray University Affiliated: Yes


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.