ABSTRACT
The generalized assignment problem (GAP) is one of the representative combinatorial optimization problems known to be NP-hard. Given n https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_17832.tif"/> jobs and m https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_17833.tif"/> 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 and/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]; a scalable parallel genetic algorithm by Liu and Wang [8]; variable depth search algorithms by Racer and Amini [9, 10]; a tabu search based on ejection chain approach by Laguna et al. [11] (which is proposed for a generalization of GAP); another tabu search by Díaz and Fernández [12]; a hybrid approach of tabu search and branch-and-bound by Woodcock and Wilson [13]; a Lagrangian heuristic algorithm by Haddadi and Ouzia [14]; Lagrangian relaxation guided problem space search heuristics by Jeet and Kutanoglu [15]; a MAX-MIN ant system combined with local search and tabu search by Lourenço and Serra [16]; a path-relinking algorithm by Alfandari et al. [17]; ejection chain approaches by Yagiura et al. [18, 19]; a very large-scale variable neighborhood search heuristic by Mitrovi ć https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_17834.tif"/> -Mini ć https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_17835.tif"/> and Punnena [20]; a bees algorithm by Özbakir et al. [21], 714and so on. Research for exact algorithms also has long history since early papers by Ross and Soland [22], Martello and Toth [4], and Fisher et al. [23]. Among more recent exact algorithms successful for GAP are the branch-and-bound methods by Savelsbergh [24], Nauss [25], Haddadi and Ouzia [26], Avella et al. [27], Munapo et al. [28] and Posta et al. [29], and an ascending hyper-plane approach through network flows by Munapo et al. [30].
