ABSTRACT
The generalized assignment problem (GAP) has been investigated in numerous research papers over the past 30 years. The problem 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 not violated. Applications of the GAP range from jobs assigned to computers in computer networks (Balachandran [1]) to loading for flexible manufacturing systems (Mazolla et al. [17]) to facility location (Ross and Soland [24]). A review of applications and algorithms (both exact and heuristic) appears in Cattrysse and Van Wassenhove [5]. Osman [20] describes various heuristic approaches to the GAP.
