The generalized assignment problem with flexible jobs Academic Article uri icon


  • The Generalized Assignment Problem (GAP) seeks an allocation of jobs to capacitated resources at minimum total assignment cost, assuming a job cannot be split among multiple resources. We consider a generalization of this broadly applicable problem in which each job must not only be assigned to a resource, but its resource consumption must also be determined within job-specific limits. In this profit-maximizing version of the GAP, a higher degree of resource consumption increases the revenue associated with a job. Our model permits a job's revenue per unit resource consumption to decrease as a function of total resource consumption, which allows modeling quantity discounts. The objective is then to determine job assignments and resource consumption levels that maximize total profit. We develop a class of heuristic solution methods, and demonstrate the asymptotic optimality of this class of heuristics in a probabilistic sense. 2008 Elsevier B.V. All rights reserved.

published proceedings


author list (cited authors)

  • Rainwater, C., Geunes, J., & Romeijn, H. E.

citation count

  • 8

complete list of authors

  • Rainwater, Chase||Geunes, Joseph||Romeijn, H Edwin

publication date

  • January 2009