情報処理学会第85回全国大会 会期:2023年3月2日~4日 会場:電気通信大学

7S-07
公平なインターバルスケジューリング問題に関する研究
○酒井洸星,岩崎 敦(電通大)
本研究では、公平なインターバルスケジューリング問題を解くアルゴリズムを扱う。インターバルスケジューリング問題とは、それぞれのジョブがリリース時間と〆切時間を、各ジョブに対して機械(もしくは労働者)が処理可能時間をもつとき、どのようにジョブを機械に割り当てるかを決定する問題である。スケジューリング問題における公平性には様々な概念があるが、本研究では機械全員の効用の積であるナッシュ積を最大化することを目的としたインターバルスケジューリング問題を構築し、その解を求めるアルゴリズムを考察する。