ABSTRACT
The generalized assignment problem (GAP) is one of the representative combinatorial optimization problems known to be NP-hard. Given n jobs and m agents, we undertake to determine a minimum-cost assignment such that every job is assigned to exactly one agent and the resource constraint for each agent is satisfied. This problem is a natural generalization of such representative combinatorial optimization problems as bipartite matching, knapsack, and bin packing problems, and has many important applications, including flexible manufacturing systems [1], facility location [2], and vehicle routing problems [3]. Consequently, designing good, exact, or heuristic algorithms for GAP has significant practical as well as theoretical value. Among various heuristic algorithms developed for GAP are a combination of the greedy method and the local search by Martello and Toth [4,5]; a tabu search and simulated annealing by Osman [6]; a genetic algorithm by Chu and Beasley [7]; variable depth search algorithms by Racer and Amini [8,9]; a tabu search based on ejection chain approach by Laguna et al. [10] (which is proposed for a generalization of GAP); another tabu search by Dı´az and Ferna´ndez [11]; a Lagrangian heuristic algorithm by Haddadi and Ouzia [12]; a MAX-MIN ant system combined with local search and tabu search by Lourenc¸o and Serra [13]; a path-relinking algorithm by Alfandari et al. [14]; ejection chain approaches by Yagiura et al. [15,16], and so on. Research for exact algorithms also has long history since early papers by Ross and Soland [17], Martello and Toth [4], and Fisher et al. [18]. Among recent exact algorithms successful for GAP are the branch-and-bound methods by Savelsbergh [19], Nauss [20], and Haddadi and Ouzia [21].
