The generalized assignment problem with flexible jobs |
| |
Authors: | Chase Rainwater Joseph Geunes |
| |
Institution: | Department of Industrial and Systems Engineering, University of Florida, P.O. Box 116595, Gainesville, FL 32611-6595, United States |
| |
Abstract: | 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. |
| |
Keywords: | Generalized assignment problem Heuristics Asymptotic feasibility Asymptotic optimality |
本文献已被 ScienceDirect 等数据库收录! |
|