Varying bandwidth resource allocation problem with bag constraints

摘要

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(Bmax/Bmin))-approximation algorithm, where Bmax and Bmin 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.