Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource

Peter Kling, Alexander Maecker, Soeren Riechers, Alexander Skopalik

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    3 Citations (Scopus)

    Abstract

    We consider a scheduling problem onm 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 pj ∈R and a resource requirement rj >0. Jobs do not benefit when receiving a share larger than rj 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).
    Original languageEnglish
    Title of host publicationSPAA '17
    Subtitle of host publicationProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
    EditorsChristian Scheideler
    Place of PublicationNew York
    PublisherACM Press
    Pages123-132
    Number of pages10
    ISBN (Print)978-1-4503-4593-4
    DOIs
    Publication statusPublished - 2017

    Keywords

    • multiprocessor scheduling
    • approximation algorithm
    • resource constraints
    • shared resources
    • bin packing with cardinality constraints and splittable items

    Cite this