Density threshold in pinwheel scheduling

10^th August 2023, 13:00 Ashton 2.08
Akitoshi Kawamura
Kyoto University

Abstract

In Pinwheel Scheduling Problem, we are given a set of jobs i, each of
which must be done with period a_i, i.e., done at least once during any
consecutive a_i days. We ask whether we can achieve this (perpetually)
by doing one job every day. An obvious necessary condition is that the
sum of the reciprocals 1/a_i not exceed 1. It is also not hard to see
that the jobs can be scheduled if this sum is 1/2 or smaller. We show
that this bound can be increased to 5/6 (which is the best possible), as
conjectured by Chan and Chin.