Non-clairvoyant precedence constrained scheduling

Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the online problem of scheduling jobs on identical machines, where jobs have precedence constraints. We are interested in the demanding setting where the jobs sizes are not known up-front, but are revealed only upon completion (the non-clairvoyant setting). Such precedence-constrained scheduling problems routinely arise in map-reduce and large-scale optimization. For minimizing the total weighted completion time, we give a constant-competitive algorithm. And for total weighted flow-time, we give an O(1/ε2)-competitive algorithm under (1+ε)-speed augmentation and a natural “no-surprises” assumption on release dates of jobs (which we show is necessary in this context). Our algorithm proceeds by assigning virtual rates to all waiting jobs, including the ones which are dependent on other uncompleted jobs. We then use these virtual rates to decide on the actual rates of minimal jobs (i.e., jobs which do not have dependencies and hence are eligible to run). Interestingly, the virtual rates are obtained by allocating time in a fair manner, using a Eisenberg-Gale-type convex program (which we can solve optimally using a primal-dual scheme). The optimality condition of this convex program allows us to show dual-fitting proofs more easily, without having to guess and hand-craft the duals. This idea of using fair virtual rates may have broader applicability in scheduling problems.

Original languageEnglish (US)
Title of host publication46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771092
DOIs
StatePublished - Jul 1 2019
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: Jul 9 2019Jul 12 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume132
ISSN (Print)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period7/9/197/12/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Nash welfare
  • Online algorithms
  • Primal-Dual analysis
  • Scheduling

Fingerprint Dive into the research topics of 'Non-clairvoyant precedence constrained scheduling'. Together they form a unique fingerprint.

  • Cite this

    Garg, N., Gupta, A., Kumar, A., & Singla, S. (2019). Non-clairvoyant precedence constrained scheduling. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 [63] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 132). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2019.63