Finite Pinwheel Scheduling: the \(\text{k}\)-Visits Problem
Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou, Ευριπίδης Μάρκου, Aris Pagourtzis · Society for Industrial and Applied Mathematics eBooks · 2026
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 perpetually appears at least once in every \(d_i\) time slots. Although conjectured to be PSPACE-complete, it remains open whether Pinwheel Scheduling is NP-hard (unless a compact input encoding is used) or even contained in NP.