Towards the 5/6-Density Conjecture of Pinwheel Scheduling

Gąsieniec, Leszek ORCID: 0000-0003-1809-9814, Smith, Benjamin and Wild, Sebastian ORCID: 0000-0002-6061-9177
(2021) Towards the 5/6-Density Conjecture of Pinwheel Scheduling. In: ALENEX 2022, 2022-1-9 - 2022-1-10, Alexandria, VG, USA.

[thumbnail of main.pdf] Text
main.pdf - Author Accepted Manuscript

Download (1MB) | Preview


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: Conference or Workshop Item (Unspecified)
Additional Information: Accepted at ALENEX 2022
Uncontrolled Keywords: cs.DS, cs.DS
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 04 Nov 2021 08:02
Last Modified: 07 Jun 2024 08:57
Related URLs: