Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Pinwheel scheduling
open-in-new
<p>In mathematics and computer science, the pinwheel scheduling problem is a problem in <a href="/facts/Scheduling_analysis_real-time_systems/CV37fJS7">real-time scheduling</a> with repeating tasks of unit length and hard constraints on the time between repetitions. </p><p>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 <a href="/facts/Pinwheel_(cryptography)/dNdwY1w4">pinwheel cipher machine</a>, 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. </p><p>Certain formulations of the pinwheel scheduling problem are <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>. </p>