In the pinwheel scheduling problem, each task $i$ is associated with a positive integer $a_i$, called its period. Our goal is to schedule one task per day so that each task $i$ is performed at least once every $a_i$ days. An obvious necessary condition for schedulability is the density, defined as the sum of execution rates $\sum \frac{1}{a_i}$, which must not exceed $1$. We prove that all instances with density not exceeding $\frac{5}{6}$ are schedulable, as conjectured by Chan and Chin in 1993.
Similar to known partial progress towards the conjecture, our proof involves computer search for a large but finite set of instances. A key idea in our reduction to these finite cases is to generalize the problem to fractional (non-integer) periods appropriately.
As byproducts of our ideas, we obtain a simple proof that every instance with two distinct periods and density at most $1$ is schedulable, as well as a fast algorithm for the bamboo garden trimming problem with an approximation ratio of $\frac{4}{3}$.
Blogger's Review: This paper not only proves the density threshold conjecture but also demonstrates the complexity of scheduling problems through computer search methods. The idea of generalizing to fractional periods is particularly clever and offers new perspectives for further research, especially in the potential applications of algorithm design.