Pinwheel scheduling
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.
This repeating pattern resembles the repeating pattern of set and unset pins on the gears of a pinwheel cipher machine, justifying the name.
Certain formulations of the pinwheel scheduling problem are NP-hard.
The input to pinwheel scheduling consists of a list of tasks, each of which is assumed to take unit time per instantiation.
[1] The desired output is an infinite sequence specifying which task to perform in each unit of time.
The density of a pinwheel scheduling problem is defined as the sum of these fractions,
[2] 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.
However, it is not always possible to find a repeating schedule of sub-exponential length.
[2] 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.
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 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.
[1] 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 that is less than or equal to it.
After rounding, all densities are multiples of each other, allowing the greedy algorithm to work.
,[3] or by rounding to two different geometric series and generalizing the idea that tasks with two distinct repeat times can be scheduled up to density one.
[3][5] The original work on pinwheel scheduling proposed it for an application in which a single base station must communicate with multiple satellites or remote sensors, 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.
[1] 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 printers,[3] computer processing of multimedia data,[6] and contention resolution in real-time wireless computer networks.
