2024/06/10 by Akitoshi Kawamura · 1 voice
Computer Science · Mathematics · #Combinatorics #Computer science #Conjecture #Discrete mathematics #Integer (computer science) #Interconnection Networks and Systems #Mathematical optimization #Mathematics #Parallel Computing and Optimization Techniques #Real-Time Systems Scheduling #Scheduling (production processes) #Theoretical computer science #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.1145/3618260.3649757
openalex publication_date 2024/06/10 · openalex created_date 2025/10/10 · arxiv published 2026/06/25 · arxiv updated 2026/06/25 · openalex updated_date 2026/08/06
In the pinwheel scheduling problem, each task i is associated with a positive integer ai called its period, and we want to (perpetually) schedule one task per day so that each task i is performed at least once every ai days. An obvious necessary condition for schedulability is that the density, i.e., the sum of the reciprocals 1/ai, not exceed 1. We prove that all instances with density not exceeding 5/6 are schedulable, as was conjectured by Chan and Chin in 1993. Like some of the known partial progress towards the conjecture, our proof involves computer search for schedules for a large but finite set of instances. A key idea in our reduction to these finite cases is to generalize the problem to fractional (non-integer) periods in an appropriate way. As byproducts of our ideas, we obtain a simple proof that every instance with two distinct periods and density at most 1 is schedulable, as well as a fast algorithm for the bamboo garden trimming problem with approximation ratio 4/3.