In mathematics and computer science, the pinwheel scheduling problem is a problem in real-time scheduling with repeating tasks of unit length and hard constraints on the time between repetitions. When a pinwheel scheduling problem has a solution, it has one in which the schedule repeats periodically. This repeating pattern resembles the repeating pattern of set and unset pins on the gears of a pinwheel cipher machine, justifying the name. If the fraction of time that is required by each task totals less than 5/6 of the total time, a solution always exists, but some pinwheel scheduling problems whose tasks use a total of slightly more than 5/6 of the total time do not have solutions. Certain formulations of the pinwheel scheduling problem are

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

Definition

The input to pinwheel scheduling consists of a list of tasks, each of which is assumed to take unit time per instantiation. Each task has an associated positive integer value, its maximum repeat time (the maximum time from the start of one instantiation of the task to the next). Only one task can be performed at any given time. The desired output is an infinite sequence specifying which task to perform in each unit of time. Each input task should appear infinitely often in the sequence, with the largest gap between two consecutive instantiations of a task at most equal to the repeat time of the task. For example, the infinitely repeating sequence ... would be a valid pinwheel schedule for three tasks A, B, and C with repeat times that are at least 2, 4, and 4 respectively.

Density

If the task to be scheduled are numbered from

1

n

, let

t_i

denote the repeat time for task

i

. In any valid schedule, task

i

must use a

1/t_i

fraction of the total time, the amount that would be used in a schedule that repeats that task at exactly its specified repeat time. The ''density'' of a pinwheel scheduling problem is defined as the sum of these fractions,

\textstyle\sum 1/t_i

. For a solution to exist, the times devoted to each task cannot sum to more than the total available time, so it is necessary for the density to be at This condition on density is also sufficient for a schedule to exist in the special case that all repeat times are multiples of each other. For instance, this would be true when all repeat times are

powers of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^n(1). In the Hardy hi ...

. In this case one can solve the problem using a disjoint

covering system In mathematics, a covering system (also called a complete residue system) is a collection :\ of finitely many residue classes : a_i\pmod = \, whose union contains every integer. Examples and definitions The notion of covering system was i ...

. Having density at most

1

is also sufficient when there are exactly two distinct repeat times. However, having density at most 1 is not sufficient in some other cases. In particular, there is no schedule for three items with repeat times

t_1=2

t_2=3

, and

t_3

, no matter how large

t_3

may be, even though the density of this system is only

5/6 + 1/t_3

. In 1993, it was conjectured that, when the density of a pinwheel scheduling is at most

5/6

, a solution exists. This was proven in 2024.

Periodicity and complexity

When a solution exists, it can be assumed to be periodic, with a period at most equal to the product of the repeat times. However, it is not always possible to find a repeating schedule of sub-exponential length. With a compact input representation that specifies, for each distinct repeat time, the number of objects that have that repeat time, pinwheel scheduling is

Algorithms

Despite the NP-hardness of the pinwheel scheduling problem for general inputs, some types of inputs can be scheduled efficiently. An example of this occurs for inputs where (when listed in sorted order) each repeat time evenly divides the next one, and the density is at most one. In this case, the problem can be solved by a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

that schedules the tasks in sorted order, scheduling each task to repeat at exactly its repeat time. At each step in this algorithm, the time slots that have already been assigned form a repeating sequence, with period equal to the repeat time of the most recently-scheduled task. This pattern allows each successive task to be scheduled greedily, maintaining the same invariant. The same idea can be used for arbitrary instances with density at most 1/2, by rounding down each repeat time to a

power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number 2, two as the Base (exponentiation), base and integer as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^ ...

that is less than or equal to it. This rounding process at most doubles the density, keeping it at most one. After rounding, all densities are multiples of each other, allowing the greedy algorithm to work. The resulting schedule repeats each task at its rounded repeat time; because these rounded times do not exceed the input times, the schedule is valid. Instead of rounding to powers of two, a greater density threshold can be achieved by rounding to other sequences of multiples, such as the numbers of the form

x\cdot 2^i

for a careful choice of the coefficient

x

, or by rounding to two different

geometric series In mathematics, a geometric series is a series (mathematics), series summing the terms of an infinite geometric sequence, in which the ratio of consecutive terms is constant. For example, 1/2 + 1/4 + 1/8 + 1/16 + ⋯, the series \tfrac12 + \tfrac1 ...

and generalizing the idea that tasks with two distinct repeat times can be scheduled up to density one.

Applications

The original work on pinwheel scheduling proposed it for an application in which a single base station must communicate with multiple

satellite A satellite or an artificial satellite is an object, typically a spacecraft, placed into orbit around a celestial body. They have a variety of uses, including communication relay, weather forecasting, navigation ( GPS), broadcasting, scient ...

s or

remote sensor Remote sensing is the acquisition of information about an object or phenomenon without making physical contact with the object, in contrast to in situ or on-site observation. The term is applied especially to acquiring information about Earth ...

s, one at a time, with distinct communications requirements. In this application, each satellite becomes a task in a pinwheel scheduling problem, with a repeat time chosen to give it adequate bandwidth. The resulting schedule is used to assign time slots for each satellite to communicate with the base station. Other applications of pinwheel scheduling include scheduling maintenance sessions for a collection of objects (such as oil changes for automobiles), the arrangement of repeated symbols on the print chains of

line printer A line printer Printer (computing), prints one entire line of text before advancing to another line. Most early line printers were printer (computing)#Impact printers, impact printers. Line printers are mostly associated with unit record eq ...

s, computer processing of multimedia data, and contention resolution in real-time wireless computer networks.

References

{{reflist, refs= {{citation , last1 = Chan , first1 = M. Y. , last2 = Chin , first2 = Francis , author2-link = Francis Y. L. Chin , doi = 10.1007/BF01187034 , issue = 5 , journal = Algorithmica , mr = 1212158 , pages = 425–462 , title = Schedulers for larger classes of pinwheel instances , volume = 9 , year = 1993, s2cid = 6069661 {{citation , last1 = Chan , first1 = M. Y. , last2 = Chin , first2 = Francis , author2-link = Francis Y. L. Chin , date = June 1992 , doi = 10.1109/12.144627 , issue = 6 , journal = IEEE Transactions on Computers , pages = 755–768 , title = General schedulers for the pinwheel problem based on double-integer reduction , volume = 41 {{citation , last1 = Holte , first1 = Robert , last2 = Mok , first2 = Al , last3 = Rosier , first3 = Louis , last4 = Tulchinsky , first4 = Igor , last5 = Varvel , first5 = Donald , contribution = The pinwheel: a real-time scheduling problem , doi = 10.1109/hicss.1989.48075 , pages = 693–702 , publisher = IEEE Computer Society Press , title = Proceedings of the Twenty-Second Annual Hawaii International Conference on System Sciences, Volume II: Software Track , year = 1989, s2cid = 62617897 {{citation , last1 = Holte , first1 = Robert , last2 = Rosier , first2 = Louis , last3 = Tulchinsky , first3 = Igor , last4 = Varvel , first4 = Donald , doi = 10.1016/0304-3975(92)90365-M , issue = 1 , journal = Theoretical Computer Science , mr = 1171436 , pages = 105–135 , title = Pinwheel scheduling with two distinct numbers , volume = 100 , year = 1992, doi-access = . Previously announced at MFCS 1989. {{citation , last = Kawamura , first = Akitoshi , editor1-last = Mohar , editor1-first = Bojan , editor2-last = Shinkar , editor2-first = Igor , editor3-last = O'Donnell , editor3-first = Ryan , contribution = Proof of the density threshold conjecture for pinwheel scheduling , doi = 10.1145/3618260.3649757 , pages = 1816–1819 , title = Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24–28, 2024 , contribution-url = https://www.kurims.kyoto-u.ac.jp/~kawamura/pinwheel/paper_e.pdf , year = 2024 {{citation , last1 = Lin , first1 = Shun-Shii , last2 = Lin , first2 = Kwei-Jay , doi = 10.1007/PL00009181 , issue = 4 , journal = Algorithmica , mr = 1470043 , pages = 411–426 , title = A pinwheel scheduler for three distinct numbers with a tight schedulability bound , volume = 19 , year = 1997, s2cid = 22001959 {{citation , last1 = Wu , first1 = Jean-Lien C. , last2 = Shin , first2 = Haw-Yun , last3 = Wu , first3 = Yi-Hsien , date = June 2005 , doi = 10.1080/02533839.2005.9671037 , issue = 4 , journal = Journal of the Chinese Institute of Engineers , pages = 701–711 , title = A pinwheel packet scheduling scheme for broadband wireless networks , volume = 28, s2cid = 62761108

External links

Pinwheel scheduling (1989)
Douglas B. West, University of Illinois Processor scheduling algorithms