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.
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 ABACABACABAC... 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 {\displaystyle 1} to n {\displaystyle n} , let t i {\displaystyle t_{i}} denote the repeat time for task i {\displaystyle i} . In any valid schedule, task i {\displaystyle i} must use a 1 / t i {\displaystyle 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, ∑ 1 / t i {\displaystyle \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 most 1 {\displaystyle 1} . 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. In this case one can solve the problem using a disjoint covering system. Having density at most 1 {\displaystyle 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 {\displaystyle t_{1}=2} , t 2 = 3 {\displaystyle t_{2}=3} , and t 3 {\displaystyle t_{3}} , no matter how large t 3 {\displaystyle t_{3}} may be, even though the density of this system is only 5 / 6 + 1 / t 3 {\displaystyle 5/6+1/t_{3}} . In 1993, it was conjectured that, when the density of a pinwheel scheduling is at most 5 / 6 {\displaystyle 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 NP-hard.
… excerpt ends here. Continue reading the full article.
