Towards the 5/6-Density Conjecture of Pinwheel Scheduling

Pinwheel Scheduling aims to find a perpetual schedule for unit-length tasks $i=1,\ldots,k$ on a single machine subject to given maximal time spans (frequencies $a_i$) between any two consecutive executions of the same task. The density of a Pinwheel Scheduling instance is $d=\sum_{i=1}^k \frac1{a_i}$.

The $\frac56$-Conjecture of Chan and Chin (1993) states that any Pinwheel Scheduling instance with density at most $\frac56$ is schedulable. We verify this conjecture for all instances with at most $k=12$ tasks through a combination structural insights and algorithm engineering.

Update 2023

Akitoshi Kawamura found an elegant general proof of the $\frac56$-Conjecture!