Solving the generalized assignment problem: An optimizing and heuristic approach

The classical generalized assignment problem (GAP) may be stated as finding a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent's resource capacity is honored. This NP-hard problem has applications that include job scheduling, routing, loading for flexible manufacturing systems, and facility location. Due to the difficulty in solving ‘hard’ GAPs to optimality, most recent papers either describe heuristic methods for generating ‘good’ solutions or, in the case of optimizing methods, computational results are limited to 500 to 1,000 binary variables. In this paper we describe a special purpose branch-and-bound algorithm that utilizes linear programming cuts, feasible-solution generators, Lagrangean relaxation, and subgradient optimization. We present computational results for solving ‘hard’ problems with up to 3,000 binary variables. An unanticipated benefit of the algorithm is its ability to generate good feasible solutions early in the process whose solution quality generally dominates the solutions generated by two recently published heuristics. Furthermore, the computation time required is often less than the time taken by the heuristics. Thus, we have an optimizing algorithm that can be used quite effectively as a heuristic when proof of optimality is not an absolute requirement.