Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource
Kling, Peter
Mäcker, Alexander
Riechers, Sören
Skopalik, Alexander
ddc:040
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).
2017
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/59
Kling P, Mäcker A, Riechers S, Skopalik A. Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource. In: <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. ; 2017:123--132. doi:<a href="https://doi.org/10.1145/3087556.3087578">10.1145/3087556.3087578</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1145/3087556.3087578
info:eu-repo/semantics/closedAccess