Towards the 5/6-Density Conjecture of Pinwheel Scheduling.

Gasieniec, Leszek, Smith, Benjamin and Wild, Sebastian ORCID: 0000-0002-6061-9177 (2021) Towards the 5/6-Density Conjecture of Pinwheel Scheduling. [Preprint]

Access the full-text of this item by clicking on the Open Access link.

Abstract

Pinwheel Scheduling aims to find a perpetual schedule for unit-length tasks on a single machine subject to given maximal time spans (a.k.a. frequencies) between any two consecutive executions of the same task. The density of a Pinwheel Scheduling instance is the sum of the inverses of these task frequencies; the 5/6-Conjecture (Chan and Chin, 1993) states that any Pinwheel Scheduling instance with density at most 5/6 is schedulable. We formalize the notion of Pareto surfaces for Pinwheel Scheduling and exploit novel structural insights to engineer an efficient algorithm for computing them. This allows us to (1) confirm the 5/6-Conjecture for all Pinwheel Scheduling instances with at most 12 tasks and (2) to prove that a given list of only 23 schedules solves all schedulable Pinwheel Scheduling instances with at most 5 tasks.

Item Type:	Preprint
Uncontrolled Keywords:	49 Mathematical Sciences, 4904 Pure Mathematics, 33 Built Environment and Design
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	27 Nov 2023 08:53
Last Modified:	23 May 2025 00:46
DOI:	10.48550/arxiv.2111.01784
Open Access URL:	https://arxiv.org/abs/2111.01784
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3177012