The pinwheel scheduling problem takes as input a collection of tasks, each taking unit time but needing to be repeated with some given maximum repeat time. The goal is to find a schedule: an infinite sequence of tasks to perform so that the gaps between each repetition of each task are no bigger than allowed. I drew the following illustration for Wikipedia, with the help of Adobe Illustrator’s new AI-based vector drawing features; it shows tasks A, B, and C with repeat times 2, 4, and 5, respectively, scheduled with the infinite repeating sequence ABACABAC… One real-world situation that this might model is scheduling equipment maintenance sessions, where certain kinds of equipment have different demands on how frequently they are maintained.

A pinwheel scheduling instance

But the name of the problem and the illustration are a little misleading. Periodic schedules, cycling through the same fixed subsequence of tasks, are allowed and always possible (when a schedule exists at all). But periodicity is not required. I want to describe a situation where aperiodicity can be helpful: it leads to a quick proof that certain kinds of inputs can always be scheduled.

The inputs in question are those with only two distinct repeat times, as studied by Holte et al. [“Pinwheel scheduling with two distinct numbers”, Theor. Comput. Sci. 1992]. You can describe these inputs by four numbers \(n_1\), \(n_2\), \(r_1\), and \(r_2\), where there are \(n_i\) tasks with repeat time \(r_i\). An obvious necessary condition for a schedule to exist is that the “density” \(n_1/r_1+n_2/r_2\) must be at most one, and the main result of Holte et al. is that this density condition is also sufficient.

The easy case is when the density is exactly one. As an example, let \(n_1=4\), \(r_1=6\), \(n_2=5\), and \(r_2=15\). In order for the density to be one, the total density of the tasks of any type must be an integer multiple of \(1/g\), where \(g=\gcd(r_1,r_2)\). That forces each \(n_i\) to be an integer multiple of \(r_i/g\). You can group the tasks of type \(i\) into subsets of \(r_i/g\) tasks, and schedule each subset as if it were a single task of repeat time \(g\), reducing the problem to a trivial one in which all tasks have the same repeat time. In this case, aperiodicity is impossible.

This leaves the case when the density is less than one. Because of this density gap, it is possible to find an irrational number \(x_1\) between \(r_1/n_1\) and \(1-r_2/n_2\). Then, symmetrically, \(x_2=1-x_1\) will lie between \(r_2/n_2\) and \(1-r_1/n_1\). For any two irrational numbers summing to one, like \(x_1\) and \(x_2\), Rayleigh’s theorem states that the two Beatty sequences

\[\left\lfloor\frac{j}{x_i}\right\rfloor,\quad j = 1, 2, 3, \dots\]

are complementary: each positive integer belongs to exactly one of these two sequences. For example, with \(n_1=3\), \(r_1=5\), \(n_2=3\), and \(r_2=8\), we may choose \(x_1=(\sqrt5-1)/2\approx 0.618\), giving the two complementary Beatty sequences

\[1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, \dots\]

(the integer multiples of the golden ratio, rounded down) and

\[2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, \dots\]

Now simply schedule all of the tasks with repeat time \(r_1\) in time slots belonging to the first of these complementary Beatty sequences (choosing among these tasks in a periodic sequence), and schedule all of the tasks with repeat time \(r_2\) in time slots belonging to the second sequence. For a task with repeat time \(r_i\), this schedule will place the task in time slots whose spacing is sometimes \(\lfloor n_i/x_i\rfloor\) and sometimes \(\lceil n_i/x_i\rceil\). Because of the way we chose \(x_i\), both of these are at most \(r_i\), as required.

For the example with \(n_1=3\), \(r_1=10\), \(n_2=2\), \(r_2=3\), and \(x_1=(\sqrt5-1)/2\), and with tasks labeled as \(5a, 5b, 5c, 8a, 8b, 8c\), the schedule of tasks is

\[5a, 8a, 5b, 5c, 8b, 5a, 8c, 5b, 5c, 8a, 5a, 5b, 8b, 5c, 8c, 5a, 5b, \dots\]

So this method gives an aperiodic schedule, for any instance of pinwheel scheduling with two distinct repeat times and with density less than one, and an easy proof that having density at most one suffices for a schedule to exist when there are two repeat times.

(Discuss on Mastodon)