周期的な仕事の割当について (Scheduling recurring tasks)

開催日時
2024/04/24 水 16:45 - 17:45
場所
RIMS110号室
講演者
河村 彰星
講演者所属
京都大学
概要

いくつかある仕事のそれぞれについて、どの連続する○○日にも一度以上
やるべしという日数が指定されている。これを満しながら毎日ひとつづつ
仕事をし続けることができるだろうか。できるためには明らかに、指定
された日数の逆数の和が1以下である必要があるが、逆にこの逆数和が
或る程度小さければ十分であることも判っている。本講演ではこの問題に
ついて、必要条件や十分条件、判定する方法(アルゴリズム)やその効率、
「一度以上」を「一度以下」や「ちょうど一度」にした変種や、これらに
関する最近の研究動向などを解説する。