### 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{log_{k}+_{1} n, log_{k}+_{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 Θ(log_{k}+_{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 language | English (US) |
---|---|

Title of host publication | SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures |

Publisher | Association for Computing Machinery |

Pages | 301-310 |

Number of pages | 10 |

ISBN (Electronic) | 9781450357999 |

DOIs | |

State | Published - Jul 11 2018 |

Event | 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 - Vienna, Austria Duration: Jul 16 2018 → Jul 18 2018 |

### Publication series

Name | Annual ACM Symposium on Parallelism in Algorithms and Architectures |
---|

### Other

Other | 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 |
---|---|

Country | Austria |

City | Vienna |

Period | 7/16/18 → 7/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

*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