This page provides the supporting data for Lemma 5 of my paper “Proof of the Density Threshold Conjecture for Pinwheel Scheduling”, which proves the “5/6 conjecture” for pinwheel scheduling.
The lemma states that all pinwheel instances consisting of integers up to 21 and satisfying a certain modified density bound are schedulable. Let 𝓑 be the (finite) set of such instances. Rather than listing schedules for all 25592971 instances in 𝓑, we give schedules for a set 𝓒 of 5852 instances such that for each 𝐵 in 𝓑, there is 𝐶𝐵 in 𝓒 such that 𝐵 can be obtained from 𝐶𝐵 using the two operations in Lemma 3: first splitting some tasks (part (2) of the lemma) several times, and then increasing the periods of some tasks (part (1)).
(4 5 5 7 7): (5 4 5 7 5 4 7)
” says that the pinwheel instance (4, 5, 5, 7, 7), which means we have five jobs A, B, C, D, E with periods 4, 5, 5, 7, 7, respectively, has a valid schedule where we indefinitely repeat the 14-day sequence in which we perform tasks B, A, C, D, B, A, E, C, A, B, D, C, A, E in this order. Note that 𝓒 contains instances that do not belong to 𝓑; those that do are marked with an asterisk.(3 4 8 13 20 20) <- (3 4 8 10 20 20) <- (3 4 5 8)
” means that because the instance (3, 4, 5, 8) is in 𝓒 and thus is schedulable, the instance (3, 4, 8, 10, 20, 20), which is obtained by splitting the period-5 task into two period-10 tasks and then splitting one of them again into two period-20 tasks, is also schedulable, and so is the instance (3, 4, 8, 13, 20, 20) which is obtained by increasing 10 to 13.