• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

Online Non-preemptive Scheduling on Unrelated Machines with Rejections

Lucarelli, Giorgio; Moseley, Benjamin; Thang, Nguyen Kim; Srivastav, Abhinav; Trystram, Denis (2018), Online Non-preemptive Scheduling on Unrelated Machines with Rejections, SPAA '18: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures, ACM - Association for Computing Machinery : New York, NY, p. 291-300. 10.1145/3210377.3210402

Type
Communication / Conférence
External document link
https://arxiv.org/abs/1802.10309v1
Date
2018
Conference title
SPAA 2018 - 30th ACM Symposium on Parallelism in Algorithms and Architectures
Conference date
2018-07
Conference city
Vienna
Conference country
Austria
Book title
SPAA '18: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures
Publisher
ACM - Association for Computing Machinery
Published in
New York, NY
ISBN
978-1-4503-5799-9
Pages
291-300
Publication identifier
10.1145/3210377.3210402
Metadata
Show full item record
Author(s)
Lucarelli, Giorgio cc

Moseley, Benjamin

Thang, Nguyen Kim

Srivastav, Abhinav
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Trystram, Denis
Abstract (EN)
When a computer system schedules jobs there is typically a significant cost associated with preempting a job during execution. This cost can be from the expensive task of saving the memory's state and loading data into and out of memory. There is a need for non-preemptive system schedulers to avoid the costs of preemption on desktops, servers and data centers. Despite this need, there is a gap between theory and practice. Indeed, few non-preemptive online schedulers are known to have strong foundational guarantees. This gap is likely due to strong lower bounds on any online algorithm for popular objectives. Indeed, typical worst case analysis approaches, and even resource augmented approaches such as speed augmentation, result in all algorithms having poor performance guarantees. This paper considers online non-preemptive scheduling problems in the worst-case model where the algorithm is allowed to reject a small fraction of jobs. By rejecting only few jobs, this paper shows that the strong lower bounds can be circumvented. This model can be used to discover scheduling policies with desirable worst-case guarantees. Specifically, the paper presents algorithms for minimizing the total flow-time and minimizing the total weighted flow-time plus energy under the speed-scaling mechanism. The algorithms have a small constant competitive ratio while rejecting only a constant fraction of jobs. Beyond specific results, the paper asserts that alternative models beyond speed augmentation should be explored to aid in the discovery of good schedulers in the face of the requirement of being online and non-preemptive.
Subjects / Keywords
Theory of computation; Design and analysis of algorithms; Approximation algorithms analysis; Scheduling algorithms; Online algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    Online scheduling of bounded length jobs to maximize throughput 
    Nguyen Kim, Thang; Lukasz, Jez; Dürr, Christoph (2012) Article accepté pour publication ou publié
  • Thumbnail
    Improved Online Scheduling in Maximizing Throughput of Equal Length Jobs 
    Nguyen Kim, Thang (2011) Communication / Conférence
  • Thumbnail
    Non-clairvoyant Scheduling Games 
    Nguyen Kim, Thang; Dürr, Christoph; Cohen, Johanne (2011) Article accepté pour publication ou publié
  • Thumbnail
    Congestion Games with Capacitated Resources 
    Gourvès, Laurent; Monnot, Jérôme; Moretti, Stefano; Kim Thang, Nguyen (2012) Communication / Conférence
  • Thumbnail
    Congestion Games with Capacitated Resources 
    Gourvès, Laurent; Monnot, Jérôme; Moretti, Stefano; Kim Thang, Nguyen (2015) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo