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 in 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 consecutive $\lceil l a_{i} \rceil$ 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.
翻译:对于一组具有正整周期的任务序列,风车调度问题旨在寻找一种有效调度方案,使得每天执行一个任务,且每个任务在其周期内的任意连续天数中至少被执行一次。Chan和Chin于1993年提出猜想:对于任意任务序列,若其密度(即各周期倒数的和)不超过$\\frac{5}{6}$,则存在有效调度方案。近期,Kawamura肯定性地证明了该猜想。本文研究了Kawamura提出的具有实数周期的扩展版本,其中对于具有实数周期~$a_{i}$的每个任务$i$,有效调度方案需满足:对于任意正整数$l$,在任意连续$\\lceil l a_{i} \\rceil$天内至少执行该任务$l$次。我们证明:对于周期取三个不同实数值且密度不超过$\\frac{5}{6}$的任意任务序列,均存在有效调度方案。基于此,我们进一步猜想Chan和Chin的猜想对于实数周期同样成立。