時間割作成ツール

学校関連のスケジューリング問題は多岐にわたります。
その中でも特に時間割の作成は、担当クラスや教員、授業を実施する教室などの要因を考慮する必要があるため、週単位での時間がかかると言われています。

時間割作成では、授業を頂点とし、同じコマに割り当ててはいけない（同じ先生、同じ時間など）授業同士を辺でつないだグラフを定義し、グラフにおいて隣接する頂点が違う色になるように塗り分ける、グラフ頂点彩色問題に置き換えて考えることができます。

ここでは以下のような単純なユースケースを想定してシミュレーションしてみます。

上記のように教科ごとの教員と週必要コマ数が決まっている前提で、以下の条件を満たしつつ割り当てなければなりません。

・各クラスで全教科の週必要コマ数を割り当てなければならない。
・教員が複数クラスの同じコマに割り当てられてはいけない。

現実的には、以下のようなさらに複雑な条件を考慮する必要があります。

・同じコマで授業を実施する教室が重複してはならない。
・特定の教科の割り当てを1日にnコマまでにする。
・同じ教科の割り当てを同じ時間帯にnコマまでにする。
・特定の教科は2コマ連続にする。
・教員が3コマ連続で授業を行うことを避ける。

2020年度未踏ターゲット事業折田PJでは、これらの制約条件についても取り組まれています。