Finite Pinwheel Scheduling: the k-Visits Problem

Pinwheel Scheduling is a fundamental scheduling problem, in which each task i is associated with a positive integer deadline d i , and the objective is to schedule one task per time slot, ensuring each task i perpetually appears at least once in every d i time slots. Although conjectured to be PSPACE-complete, the complexity of Pinwheel Scheduling remains open.

We introduce k-Visits, a finite version of Pinwheel Scheduling, where given the deadlines of n tasks, the goal is to schedule each task exactly k times. While we observe that the 1-Visit problem is trivial, we prove that 2-Visits is strongly NP-complete through a reduction from Numerical 3-Dimensional Matching. We further extend our strong NP-hardness result to a generalization of k-Visits (k ≥ 2) in which the deadline of each task may vary throughout the schedule, as well as to a similar generalization of Pinwheel Scheduling, thus making progress towards settling the complexity of the latter.

Additionally, we prove that 2-Visits can be solved in linear time if all deadlines are distinct, rendering it one of the rare natural problems which exhibit the interesting dichotomy of being in P if their input is a set and NP-complete if the input is a multiset. We also present an FPT algorithm for 2-Visits parameterized by a value related to how close the input deadlines are to each other, as well as a linear-time algorithm for instances with up to two distinct values of deadlines close to each other.