10.1145/3087556.3087578
Kling, Peter
Peter
Kling
Mäcker, Alexander
Alexander
Mäcker
Riechers, Sören
Sören
Riechers
Skopalik, Alexander
Alexander
Skopalik
Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource
2017
2017-10-17T12:41:02Z
2019-04-11T13:48:16Z
conference
https://ris.uni-paderborn.de/record/59
https://ris.uni-paderborn.de/record/59.json
784867 bytes
application/pdf
We consider a scheduling problem on $m$ identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each job $j$ comes with a size $p_j \in \mathbb{R}$ and a resource requirement $r_j > 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan.Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed).