タイムテーブリング問題

【 たいむてーぶりんぐもんだい(time tabling problem) 】

タイムテーブリング問題は，スケジューリング問題の１変種である． 具体的には，学生と教師の組合せに対し，授業の時間割を， 授業を行う部屋等も考慮に入れて構築する問題を指すことが多い． 非常に簡単な場合は，２部グラフの枝彩色問題となることが知られている． 他の変種として， スポーツの試合日程を定める問題などが知られている． 稀に，列車の時刻表を構築する問題を指すこともあるが， これは上記の問題とは性質がかなり異なる．