TY - JOUR

T1 - The Price of Bounded Preemption

AU - Alon, Noga

AU - Azar, Yossi

AU - Berlin, Mark

N1 - Funding Information:
A shortened version of this article appeared at the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’18). Research of the first author is supported in part by the NSF under grant № DMS-1855464, the Israel Science Foundation (ISF) under grant № 281/17, and the U.S.-Israel Binational Science Foundation (BSF) under grant № 2018267. Research of the second author is supported in part by the ISF under grants № 2304/20 and №1506/16. Authors’ addresses: N. Alon, Department of Mathematics, Princeton University, Princeton, NJ; Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel; email: nalon@math.princeton.edu, nogaa@post.tau.ac.il; Y. Azar, Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel; email: azar@tau.ac.il; M. Berlin, Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel; email: markberlin193@gmail.com. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM. 2329-4949/2021/03-ART3 $15.00 https://doi.org/10.1145/3434377
Publisher Copyright:
© 2021 ACM.

PY - 2021/4

Y1 - 2021/4

N2 - In this article 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+1P}) 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.

AB - In this article 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+1P}) 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.

KW - Scheduling jobs

KW - bounded preemptions

KW - bounded-degree sub-forest

KW - multiple machines

UR - http://www.scopus.com/inward/record.url?scp=85104822644&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85104822644&partnerID=8YFLogxK

U2 - 10.1145/3434377

DO - 10.1145/3434377

M3 - Article

AN - SCOPUS:85104822644

VL - 8

JO - ACM Transactions on Parallel Computing

JF - ACM Transactions on Parallel Computing

SN - 2329-4949

IS - 1

M1 - 3434377

ER -