Pinwheel Scheduling with Real Periods

Read full text
Authors: Hiroshi Fujiwara, Kota Miyagi, Katsuhisa Ouchi
Cited by: 0

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 (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.

Fields of Study & Subjects

Optimization and Search Problems Scheduling and Optimization Algorithms Resource-Constrained Project Scheduling

Publication details

Journal / source
Discrete Mathematics & Theoretical Computer Science
Volume
vol. 28:4, SOFSEM 2026
Issue
Special issues
Publication date
17 August 2026
Language
EN