View PDF HTML (experimental)

Abstract: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 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.

Submission history

From: Hiroshi Fujiwara [view email]
[v1] Tue, 28 Oct 2025 05:01:25 UTC (22 KB)
[v2] Fri, 5 Dec 2025 14:25:13 UTC (22 KB)
[v3] Thu, 15 Jan 2026 01:49:31 UTC (22 KB)
[v4] Sun, 1 Mar 2026 23:34:00 UTC (22 KB)
[v5] Mon, 6 Jul 2026 11:37:17 UTC (169 KB)