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