Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
For theoretical computer scientists studying scheduling complexity, this paper resolves key open questions about the hardness and tractability of finite Pinwheel Scheduling variants.
The paper proves that 2-Visits (a finite Pinwheel Scheduling variant) is strongly NP-complete even when maximum multiplicity is 2, settling an open question. It also shows 2-Visits is in RP when the number of distinct deadlines is constant, and establishes density thresholds: a lower bound of ~0.9142 for 2-Visits and a limit of 5/6 for k-Visits as k→∞.
The k-Visits problem is a recently introduced finite version of Pinwheel Scheduling [Kanellopoulos et al., SODA 2026]. Given the deadlines of n tasks, the problem asks whether there exists a schedule of length kn executing each task exactly k times, with no deadline expiring between consecutive visits (executions) of each task. In this work we prove that 2-Visits is strongly NP-complete even when the maximum multiplicity of the input is equal to 2, settling an open question from [Kanellopoulos et al., SODA 2026] and contrasting the tractability of 2-Visits for simple sets. On the other hand, we prove that 2-Visits is in RP when the number of distinct deadlines is constant, thus making progress on another open question regarding the parameterization of 2-Visits by the number of numbers. We then generalize all existing positive results for 2-Visits to a version of the problem where some tasks must be visited once and some other tasks twice, while providing evidence that some of these results are unlikely to transfer to 3-Visits. Lastly, we establish bounds for the density thresholds of k-Visits, analogous to the $(5/6)$-threshold of Pinwheel Scheduling [Kawamura, STOC 2024]; in particular, we show a $\sqrt{2}-1/2\approx 0.9142$ lower bound for the density threshold of 2-Visits and prove that the density threshold of k-Visits approaches $5/6\approx 0.8333$ for $k \to \infty$.