情報理工学特別講義「計算理論特論 輪番割当問題」

令和6年度 九州大学システム情報科学府

講義資料

幾つかある仕事のそれぞれについて、連続する○○日には必ず一度以上やるべしという日数が指定されています。これを満し続けながら毎日いずれか一つだけ仕事をできるでしょうか。勿論これが可能であるには指定された日数の逆数の和が1以下である必要がありますが、逆にこの逆数和が或る程度小さければ十分であることも判っています。輪番割当(pinwheel scheduling)とよばれるこの問題について、必要条件や十分条件、判定法やその効率、「一度以上」を「一度以下」や「ちょうど一度」にした変種など、研究動向を紹介します。

11月15日

過去の分