Back to Search Start Over

Varying bandwidth resource allocation problem with bag constraints

Authors :
Venkatesan T. Chakaravarthy
Deva P. Seetharam
Yogish Sabharwal
Vinayaka Pandit
Source :
IPDPS
Publication Year :
2010
Publisher :
IEEE, 2010.

Abstract

We consider the problem of scheduling jobs on a pool of machines. Each job requires multiple machines on which it executes in parallel. For each job, the input specifies release time, deadline, processing time, profit and the number of machines required. The total number of machines may be different at different points of time. A feasible solution is a subset of jobs and a schedule for them such that at any timeslot, the total number of machines required by the jobs active at the timeslot does not exceed the number of machines available at that timeslot. We present an O(log(B max /B min ))-approximation algorithm, where B max and B min are the maximum and minimum available bandwidth (maximum and minimum number of machines available over all the timeslots). Our algorithm and the approximation ratio are applicable for more a general problem that we call the Varying bandwidth resource allocation problem with bag constraints (BagVBRap). The BagVBRap problem is a generalization of some previously studied scheduling and resource allocation problems.

Details

Database :
OpenAIRE
Journal :
2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS)
Accession number :
edsair.doi...........9e8d66c653572854d9b7153bbeaed80b
Full Text :
https://doi.org/10.1109/ipdps.2010.5470347