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的猜想对于实数周期同样成立。

0
下载
关闭预览

相关内容

【ICML2025】生成模型中潜空间的Hessian几何结构
专知会员服务
17+阅读 · 6月15日
非Transformer不可?最新《状态空间模型(SSM)》综述
专知会员服务
75+阅读 · 2024年4月16日
专知会员服务
25+阅读 · 2021年7月31日
专知会员服务
50+阅读 · 2021年6月2日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Arxiv
0+阅读 · 12月2日
VIP会员
相关VIP内容
【ICML2025】生成模型中潜空间的Hessian几何结构
专知会员服务
17+阅读 · 6月15日
非Transformer不可?最新《状态空间模型(SSM)》综述
专知会员服务
75+阅读 · 2024年4月16日
专知会员服务
25+阅读 · 2021年7月31日
专知会员服务
50+阅读 · 2021年6月2日
相关资讯
相关基金
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员