Hiroshi Fujiwara ; Kota Miyagi ; Katsuhisa Ouchi - Pinwheel Scheduling with Real Periods

dmtcs:17657 - Discrete Mathematics & Theoretical Computer Science, August 17, 2026, vol. 28:4, SOFSEM 2026 - https://doi.org/10.46298/dmtcs.17657
Pinwheel Scheduling with Real PeriodsArticle

Authors: Hiroshi Fujiwara 1; Kota Miyagi 2; Katsuhisa Ouchi 1

For a sequence of tasks, each with a positive integer period, the pinwheel scheduling problem involves finding a valid schedule in the sense that the schedule performs one task per day and each task is performed at least once every consecutive days of its period. It had been conjectured by Chan and Chin (1993) that there exists a valid schedule for any sequence of tasks with density, the sum of the reciprocals of each period, at most $\frac{5}{6}$. Recently, Kawamura (2024, in press) settled this conjecture affirmatively. In this paper we consider an extended version with real periods proposed by Kawamura, in which a valid schedule must perform each task $i$ having a real period~$a_{i}$ at least $l$ times in any $\lceil l a_{i} \rceil$ consecutive days for all positive integer $l$. We show that any sequence of tasks such that the periods take three distinct real values and the density is at most $\frac{5}{6}$ admits a valid schedule. We hereby conjecture that the conjecture of Chan and Chin is true also for real periods.


Volume: vol. 28:4, SOFSEM 2026
Section: Special issues
Published on: August 17, 2026
Accepted on: July 7, 2026
Submitted on: March 6, 2026
Keywords: Discrete Mathematics, Data Structures and Algorithms

Consultation statistics

This page has been seen 96 times.
This article's PDF has been downloaded 56 times.