---
res:
bibo_abstract:
- 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).@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Peter
foaf_name: Kling, Peter
foaf_surname: Kling
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Mäcker, Alexander
foaf_surname: Mäcker
foaf_workInfoHomepage: http://www.librecat.org/personId=13536
- foaf_Person:
foaf_givenName: Sören
foaf_name: Riechers, Sören
foaf_surname: Riechers
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Skopalik, Alexander
foaf_surname: Skopalik
foaf_workInfoHomepage: http://www.librecat.org/personId=40384
bibo_doi: 10.1145/3087556.3087578
dct_date: 2017^xs_gYear
dct_language: eng
dct_title: 'Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource@'
...