Fixed-Parameter Tractability of Pinwheel Scheduling

Benjamin Smith

The pinwheel scheduling problem asks if it is possible to construct a perpetual schedule for a set of $k$ tasks of unit length where the maximum gap between repetitions of the same task is limited by an ordered multiset $A  = a_1 \leq a_2 \leq \cdots \leq a_n$ of constraints, one per task. We demonstrate that pinwheel scheduling is fixed-parameter tractable with respect to the parameter $k$. We also show that, for any given value of $n$, a finite set of schedules can solve \emph{all solvable} pinwheel scheduling instances. We then introduce exhaustive-search algorithms for both pinwheel scheduling instances and partial pinwheel scheduling instances (where only a prefix of $A$ is known and gaps have to be left in the schedule), and use that to construct the Pareto surfaces over all possible schedules for $k$ tasks, for $k \leq 5$. These results have implications for the bamboo garden trimming problem (Gąsieniec et al. SOFSEM 2017).

 Overview  Program