パンクしない予定の組み方の限界は処理能力の“6分の5”──30年来の数学未解決問題「輪番割当」京大証明【研究紹介】 - レバテックLAB

山下（Seamless） 2014年から幅広い分野の研究論文をピックアップして解説しているメディア「Seamless」を個人運営。 X（@shiropen2）でも更新情報を発信中。 @shiropen2 Seamless（シームレス） 著者記事一覧 京都大学数理解析研究所の河村彰星准教授がPNASで発表した論文「Proof of the Density Threshold Conjecture for Pinwheel Scheduling」は、複数のタスクを期限通りにこなすための基礎となる「輪番割当」に関する30年来の数学の難問を証明した研究報告だ。 さらに関連する成果として、同研究所の小林佑輔准教授との共著論文が、2026年8月31日から9月4日(現地時間)にイタリアで開かれる欧州算法シンポジウム（ESA 2026）で発表される。 どんな仕事の組み合わせでもスケジュールが成立する「6分

[lenore]

“今回の証明により、全体の仕事量が約83.3%以下ならシステムはパンクしないという数学的なお墨付きが得られたことになる” 1週間の営業日を4日と思って組めばいいな

[kurage_lizard]

なるほど。私は7割くらいでけっこう十分な感じあるので、そのくらいでお願いできませんかねぇ

[Expway]

普段3割頑張って5割くらいじゃないと続かない気がする。

[yorkfield]

6分の5自体は予想されていて証明に成功したのか。どこかに間違いなく境界条件はあるんだろうけど、それが6分の5になるのは不思議な感じがするな。よく考えれば直感的に出てくる数字なんだろうか。

[zyzy]

これはあくまで疲れたりとかしないロボットとかが例外割り込み作業が発生しない場合での話であって、生物はまた別だろうよ。

[quwachy]

AIが得意そうだけど久々に人間の成果だ

[yamamoto-h]

「よって理論上睡眠は4時間あれば十分」

[Kuromaku]

輪番割当問題

[punkgame]

理論上の数値で予定組むとかアホか。普通9掛とか8掛とかにするやろ。

[heyacho]

そんなカツカツ嫌でござる

[gcyn]

へー、そういうもんなのか…。

[semimaru]

2/3のチカラでやってる。

[nguyen-oi]

83.3％以下なら絶対破綻しないという数学的保証はスケジューリング設計で胸熱だな

[Seamless]

輪番割当「仕事Aは3日に1回,Bは5日に1回」…複数仕事をどれか毎日1つ実行し期限遅れなく永遠回せるか問題→全仕事量が処理能力の83.3%以下ならスケジュールが回ると証明