2003 · 218 citations · 11 references
ManagementComputer EngineeringSystems EngineeringDistributed SystemsOptimizationSchedulingDiscrete OptimizationInteger ProgrammingResource AllocationResource OptimizationResource ProvisioningResource SchedulingLocal SearchLocal Search OptimizationMixed-integer OptimizationMixed-integer ProgrammingMulti-resource SchedulingNp-hardnessScheduling ProblemsSystem Utility Evaluation
The problem of maximizing system utility by allocating a single finite resource to satisfy discrete Quality of Service (QoS) requirements of multiple applications along multiple QoS dimensions was studied previously. In this paper we consider the more complex problem of apportioning multiple finite resources to satisfy the QoS needs of multiple applications along multiple QoS dimensions. In other words, each application, such as video-conferencing, needs multiple resources to satisfy its QoS requirements. We evaluate and compare three strategies to solve this provably NP-hard problem. We show that dynamic programming and mixed integer programming compute optimal solutions to this problem but exhibit very long running times. We then adapt the mixed integer programming problem to yield near-optimal results with smaller running times. Finally, we present an approximation algorithm based on a local search technique that is less than 5% away from the optimal solution but which is more than two orders of magnitude faster. Perhaps more significantly, the local search technique turns out to be very scalable and robust as the number of resources required by each application increases.
11
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Didier Le Gall · Communications of the ACM · 1991 · 2K citations · Full text