Scheduling shared continuous resources on many-cores

Ernst Althaus (), André Brinkmann (), Peter Kling (), Friedhelm Meyer Heide (), Lars Nagel (), Sören Riechers (), Jiří Sgall () and Tim Süß ()
Additional contact information
Ernst Althaus: Johannes Gutenberg-Universität Mainz
André Brinkmann: Johannes Gutenberg-Universität Mainz
Peter Kling: Simon Fraser University
Friedhelm Meyer Heide: Paderborn University
Lars Nagel: Johannes Gutenberg-Universität Mainz
Sören Riechers: Paderborn University
Jiří Sgall: Charles University
Tim Süß: Johannes Gutenberg-Universität Mainz

Journal of Scheduling, 2018, vol. 21, issue 1, No 6, 77-92

Abstract: Abstract We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement . The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of $$r_j$$ r j , it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete–continuous scheduling. Known results are either very pessimistic or heuristic in nature. In this article, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include a polynomial-time algorithm for any constant number of processors. Since the running time is infeasible for practical purposes, we also provide more efficient algorithm variants: an optimal algorithm for two processors and a -approximation algorithm for m processors.

Keywords: Scheduling; Approximation algorithms; Resources (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-017-0518-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:21:y:2018:i:1:d:10.1007_s10951-017-0518-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-017-0518-0

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().