The price of bounded preemption

Noga Alon, Yossi Azar, Mark Berlin

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

Abstract

In this paper we provide a tight bound for the price of preemption for scheduling jobs on a single machine (or multiple machines). The input consists of a set of jobs to be scheduled and of an integer parameter k ≥ 1. Each job has a release time, deadline, length (also called processing time) and value associated with it. The goal is to feasibly schedule a subset of the jobs so that their total value is maximal; while preemption of a job is permitted, a job may be preempted no more than k times. The price of preemption is the worst possible (i.e., largest) ratio of the optimal non-bounded-preemptive scheduling to the optimal k-bounded-preemptive scheduling. Our results show that allowing at most k preemptions suffices to guarantee a Θ(min{logk+1 n, logk+1 P}) fraction of the total value achieved when the number of preemptions is unrestricted (where n is the number of the jobs and P the ratio of the maximal length to the minimal length), giving us an upper bound for the price; a specific scenario serves to prove the tightness of this bound. We further show that when no preemptions are permitted at all (i.e., k = 0), the price is Θ(min{n, log P}). As part of the proof, we introduce the notion of the Bounded-Degree Ancestor-Free Sub-Forest (BAS). We investigate the problem of computing the maximal-value BAS of a given forest and give a tight bound for the loss factor, which is Θ(logk+1 n) as well, where n is the size of the original forest and k is the bound on the degree of the sub-forest.

Original languageEnglish (US)
Title of host publicationSPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages301-310
Number of pages10
ISBN (Electronic)9781450357999
DOIs
StatePublished - Jul 11 2018
Event30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 - Vienna, Austria
Duration: Jul 16 2018Jul 18 2018

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Other

Other30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018
CountryAustria
CityVienna
Period7/16/187/18/18

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • Bounded preemptions
  • Bounded-degree sub-forest
  • Multiple machines
  • Scheduling jobs

Fingerprint Dive into the research topics of 'The price of bounded preemption'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Azar, Y., & Berlin, M. (2018). The price of bounded preemption. In SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 301-310). (Annual ACM Symposium on Parallelism in Algorithms and Architectures). Association for Computing Machinery. https://doi.org/10.1145/3210377.3210407