Ecole d'ingénieur et centre de recherche en Sciences du numérique

Algorithms for scheduling deadline-sensitive malleable tasks

Wu, Xiaohu; Loiseau, Patrick

ALLERTON 2015, 53rd Annual Allerton Conference on Communication, Control, and Computing, September 30th-October 2nd, 2015, Urbana-Champaign, IL, USA

Due to the ubiquity of batch data processing in cloud computing, the fundamental problem of scheduling malleable batch tasks and its extensions have received significant attention recently. In this paper, we consider an important model in which a set of n tasks is to be scheduled on C identical machines and each task is specified by a value, a workload, a deadline and a parallelism bound. Within the parallelism bound, the number of machines allocated to a task can vary over time without affecting its workload. For this model, we obtain two core results: a quantitative characterization of a sufficient and necessary condition such that a set of malleable batch tasks with deadlines can be scheduled on C machines, and a polynomial-time algorithm to produce such a feasible schedule. These core results provide a conceptual tool and an optimal scheduling algorithm that enable proposing new analyses and designs of algorithms and improving existing algorithms for extensive scheduling objectives.

Document Doi Arxiv Bibtex

Titre:Algorithms for scheduling deadline-sensitive malleable tasks
Département:Data Science
Eurecom ref:4746
Copyright: © 2015 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+4746, doi = {}, year = {2015}, title = {{A}lgorithms for scheduling deadline-sensitive malleable tasks}, author = {{W}u, {X}iaohu and {L}oiseau, {P}atrick}, booktitle = {{ALLERTON} 2015, 53rd {A}nnual {A}llerton {C}onference on {C}ommunication, {C}ontrol, and {C}omputing, {S}eptember 30th-{O}ctober 2nd, 2015, {U}rbana-{C}hampaign, {IL}, {USA}}, address = {{U}rbana-{C}hampaign, {\'{E}}{TATS}-{UNIS}}, month = {09}, url = {} }
Voir aussi: