Originators: Robert Holte and Louis Rosier (presented by Hemanshu Kaul - REGS 2008)
Definitions: Let v be a list of n positive integers. A pinwheel schedule for v is a doubly infinite sequence drawn from the labels {1,...,n} such that each label i occurs at least once in each window of vi consecutive positions. If such a schedule exists for v, then v is schedulable. Without loss of generality, we may assume that the list v is nondecreasing. The value ∑(1/vi) is the density of v, written d(v).
Background: An obvious necessary condition for schedulability is having density at most 1. This is not sufficient, as (2,3,v3) is never schedulable. If each vi is a power of 2, then density at most 1 is sufficient.
Question 1: Which lists with density 1 are schedulable?
Conjecture 2 (Chan-Chin [CC1]) If d(v)≤5/6, then v is schedulable.
Comments: The earliest posing of the problem may be in [HMRTV], which showed that d(v)≤1/2 is sufficient to make v schedulable. If v is schedulable, then there is a periodic pinwheel schedule for v with period at most ∏vi [HRTV]. The desired condition d(v)≤5/6 has been proved sufficient when n=3 [LL] and when v1=2 [FL].
For the general problem, Chan and Chin [CC1] gave various algorithms that proved the sufficiency of d(v)≤2/3 and d(v)≤.65. This was improved to 0.7 in Chan and Chin [CC2]. Fishburn and Lagarias [FL] further improved it to 0.75.
The decision problem of schedulability is in PSPACE [HMRTV]. For density 1, the problem is in NP but may not be NP-hard. Fast algorithms for generating schedules have also been studied.
References:
[CC1] Chan, M. Y.; Chin, Francis; Schedulers for larger classes of pinwheel
instances. Algorithmica 9 (1993), no. 5, 425--462.
[CC2] Mee Yee Chan, Francis Y. L. Chin; General schedulers for the pinwheel
problem based on double-integer reduction, IEEE Transactions on Computers,
41 (1992), 755--768.
[FL] Fishburn, P. C.; Lagarias, J. C.; Pinwheel scheduling: achievable
densities. Algorithmica 34 (2002), 14--38.
[HMRTV] Holte, Robert; Mok, A; Rosier, Louis; Tulchinsky, Igor; Varvel, Donald;
The pinwheel: A scheduling problem, Proc. 22nd Hawaii Intl. Conf. Systems Sci.,
(1989), 693-702.
[HRTV] Holte, Robert; Rosier, Louis; Tulchinsky, Igor; Varvel, Donald;
Pinwheel scheduling with two distinct numbers. Mathematical foundations of
computer science 1989 (Por\polhk abka-Kozubnik, 1989), 281--290,
Lecture Notes in Comput. Sci., 379, Springer, Berlin, 1989, and
Theoret. Comput. Sci. 100 (1992), no. 1, 105--135.
[LL] Lin, Shun-Shii; Lin, Kwei-Jay; A pinwheel scheduler for three distinct
numbers with a tight schedulability bound. Algorithmica 19 (1997), no. 4,
411--426.