A branch and bound algorithm for the generalized assignment problem |
| |
Authors: | G. Terry Ross Richard M. Soland |
| |
Affiliation: | (1) University of Massachusetts, Amherst, Mass., USA;(2) University of Texas, Austin, Tex., USA |
| |
Abstract: | This paper describes what is termed the generalized assignment problem. It is a generalization of the ordinary assignment problem of linear programming in which multiple assignments of tasks to agents are limited by some resource available to the agents. A branch and bound algorithm is developed that solves the generalized assignment problem by solving a series of binary knapsack problems to determine the bounds. Computational results are cited for problems with up to 4 000 0–1 variables, and comparisons are made with other algorithms.This research was partly supported by ONR Contracts N00014-67-A-0126-0008 and N00014-67-A-0126-0009 with the Center for Cybernetic Studies, The University of Texas. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|