学校の時間割を整数計画法を使って自動作成した話

こんにちは、@daifukusanです。専門学校でIT系の教員をしています。

この記事を書いているのが3月なのですが、この時期は卒業式、入学式、次年度の準備と何かと忙しい時期となっています。 (学生からは「先生たちって春休みは授業なくて暇でいいっすねｗ」とか言われたりしますが。。。）

次年度の準備の中でも特に面倒な作業の一つが「時間割の作成」だったりします。
時間割の作成というのは、簡単にいえば以下の表を作成する作業です。

※担当者の名前は実在の人物とは関係ありません。

この時間割ですが、作成してみると意外と様々な条件を考慮しないといけないことが分かります。
一例をあげると、次のようなものです。

1. 同じ時間に同じクラスの授業が重ならないようにすること
2. 同じ時間に同じ教員が複数の授業を行わないようにすること
3. 各クラスがカリキュラムで指定された授業を指定された回数実施すること

上の表を見ると、火曜日の2限に鈴木先生が2つの授業を持っており、2番目の条件を満たしていません。この程度の表であればすぐに気付けますが、クラス数が増えると見落としやすくなります。

このような衝突が発生すると、衝突したコマを別の時間帯に移動する必要があります。しかし、この作業は非常に難解なパズルを解かなければならず、手間がかかります。
例えば、D教室の火曜日の1、2限を入れ替えると、火曜日の2限に斉藤先生のコマが衝突します。同様に、E教室の火曜日の1、2限を入れ替えても、同じ問題が起こります。

時間割作成は、非常に厄介な作業であり、多くの学校では学期ごとに教員が悪戦苦闘しながら手作業で作成しています。

そこで、整数計画法を用いた時間割自動作成ツールを作成しました。このツールは2年前に作成し、私の所属する学科の時間割作成にも使用されています。

今回は、このツールのロジックについて紹介します。

※整数計画法を使った定式化方法の解説が中心です。整数計画法自体の解説は省略してますので、予めご了承ください。

1. 事前に設定する情報

はじめに、整数計画法に与える入力値を定義します。

1.1. 基本的な集合

今回の定式化では、「どのクラスの、どの科目を、どの教員が、どの時限に、どの教室で実施するか」を決めていきます。そのため、まずは授業、教員、時限、教室の集合を定義します。

\begin{eqnarray}
&\mathbf{Classes} &=& \{1A, 1B, \cdots , 1E \} \\
&\mathbf{Subjects} &=& \{科目A\_1A, 科目A\_1B, \cdots , 科目G\_1E \} \\
&\mathbf{Teachers} &=& \{鈴木, 佐藤, \cdots , 斉藤 \} \\
&\mathbf{Periods} &=& \{月1, 月2, \cdots , 金3 \} \\
&\mathbf{Rooms} &=& \{A教室, B教室, \cdots , F教室 \} \\
\end{eqnarray}

ここで$\mathbf{Subjects}$の要素を授業とよび、[科目名]_[クラス名]で決まるものとします。つまり、同名の科目でも別クラスで行われる場合は"別の授業"として扱います。

1.2. 授業とクラス、授業と科目担当の紐づけ

今回の設定では、授業を担当する教員は、予め決められている前提とします。また、前述した通り授業が決まれば、実施する科目名、クラス名は一意に決まります。

これらの紐づけを管理するために、新たに3つの集合を定義します。

\begin{eqnarray}
&\mathbf{TeacherCourses}_t &=& \{ s \in \mathbf{Subjects} \mid P(s,t) : 教員tが授業sの担当である \} \quad\text{for all  $t \in \mathbf{Teachers}$} \\
&\mathbf{ClassCourses}_c &=& \{ s \in \mathbf{Subjects} \mid Q(s,c) : クラスcが授業sの実施クラスである \} \quad\text{for all  $c \in \mathbf{Classes}$} \\
&\mathbf{SubjectProperties} &=& \{ sp_{s,p} \mid s \in \mathbf{Subjects}, p \in \{実施クラス,コマ数,担当教員,科目名\} \}
\end{eqnarray}

$\mathbf{TeacherCourses}$は教員$t$の担当授業のリストです。教員をキーに、授業の一覧を取得できます。逆に授業をキーに教員を取得する場合は、$\mathbf{SubjectProperties}$を使います。$\mathbf{SubjectProperties}$の要素$sp_{s,p}$は、授業$s$のプロパティ$p$を取得するために使用します。例えば、授業$s1$の担当教員を取得する場合は$sp_{s1,担当教員}\hspace{1em}$と書きます。

$\mathbf{ClassCourses}$はクラス$c$の実施授業のリストです。

1.3. 制約条件に必要な情報

整数計画法の制約条件を設定するにあたり、追加で必要な情報群です。
1.1-1.2については、定式化前に一度設定してしまえば、その後変更されることはほぼないですが、こちらの項目については、様々な理由(会議の都合である時間帯は授業が出来ない、別の学科の授業で教室が利用不可など)により、後から調整する必要が多い項目です。

\begin{eqnarray}
d_{s,r} &=& 
\begin{cases}
1 & \text{授業$s$を教室$r$で実施可能}\\
0 & \text{otherwise}
\end{cases}\\

e_{r,p} &=& 
\begin{cases}
1 & \text{教室$r$を時限$p$で使用可能}\\
0 & \text{otherwise}
\end{cases}\\

f_{t,p} &=& 
\begin{cases}
1 & \text{教員$t$が時限$p$に授業可能}\\
0 & \text{otherwise}
\end{cases}\\

g_{s,p} &=& 
\begin{cases}
1 & \text{授業$s$が時限$p$に実施可能}\\
0 & \text{otherwise}
\end{cases}\\

h_{c,p} &=& 
\begin{cases}
1 & \text{時限$p$にクラス$c$の授業がある}\\
0 & \text{otherwise}
\end{cases}\\

\end{eqnarray}

$h_{c,p}$について補足しますと、私のいる専門学校では一部のクラスにおいて授業が午前中で終わる日などがあります。クラスごとにどの時限に授業があるのかを個別に設定する必要があるため、このような情報を設定できるようにしています。

2. 整数計画法の定式化

1で定義した情報を使って、整数計画法を定義していきます。

2.1. 変数の定義

まずは、最適化で使用する変数を定義します。

時間割は、「どのクラスの、どの科目を、どの教員が、どの時限に、どの教室で実施するか」で決まると説明しました。このうち、科目、教員、クラスについては授業が決まれば自然と決まりますので、変数は以下のものを用意します。

\begin{eqnarray}
x_{s,p,r} &=& 
\begin{cases}
1 & \text{授業$s$を時限$p$に教室$r$で実施する}\\
0 & \text{otherwise}
\end{cases}\\
\end{eqnarray}

2.2. 制約条件の定義

続いて、この定式化の肝である制約条件について説明します。

整数計画法で定式化する場合、人間にとっては当たり前だと思うような条件もすべて条件式として盛り込む必要があります。以下の時間割表に振った番号の順番に説明していきます。

① 同じ時間の同じ教室に複数の授業を割り当てない

当然のことですが、ある教室を同時に使用できるのは1授業までです。この条件は、以下の式で定義されます。

\begin{eqnarray}
\sum_{s\in \mathbf{Subjects}} x_{s,p,r} \leq 1 \quad \text{for $p \in \mathbf{Periods}$, $ r \in \mathbf{Rooms}$}
\end{eqnarray}

② 教員は同じ時間に複数コマの授業を行えない

教員が担当できるのは、同じ時間帯に1コマまでです。上の表の②では鈴木先生がその条件に違反します。このような違反を起こさないために、この条件も追加していきます。

\begin{eqnarray}
\sum_{\substack{s \in \mathbf{TeacherCourses}_t,\\ r \in \mathbf{Rooms}}} x_{s,p,r} \leq 1 \quad \text{for $t \in \mathbf{Teachers}$, $ p \in \mathbf{Periods}$}
\end{eqnarray}

③ クラスは同じ時間に複数コマの授業を行えない

①の条件は教室についてでしたが、同じ条件をクラスについても考慮しなければいけません。これは移動教室などを想定して設定しています。

\begin{eqnarray}
\sum_{\substack{s \in \mathbf{ClassCourses}_c,\\ r \in \mathbf{Rooms}}} x_{s,p,r} \leq 1 \quad \text{for $c \in \mathbf{Classes}$, $ p \in \mathbf{Periods}$}
\end{eqnarray}

④ クラスは授業を実施しなければいけない時限が決まっている

1.3の$h_{c,p}$の補足で説明した通り、授業の実施タイミングが各クラスごとに設定されています。この条件は、指定された時間に必ず授業を実施するようにするための制約条件です。

\begin{eqnarray}
\sum_{\substack{s \in \mathbf{ClassCourses}_c,\\ r \in \mathbf{Rooms}}} x_{s,p,r} \geq h_{c,p} \quad \text{for $c \in \mathbf{Classes}$, $ p \in \mathbf{Periods}$}
\end{eqnarray}

⑤ 授業は指定されたコマ数回実施する

表の⑤から分かる通り、授業によっては同じクラスで週に複数回実施するものもあります。この制約条件は、指定回数だけ授業を実施するための条件です。
※$sp_{s,コマ数}\hspace{1em}$については、1.2で説明しています。

\begin{eqnarray}
\sum_{\substack{p \in \mathbf{Periods},\\ r \in \mathbf{Rooms}}} x_{s,p,r} = sp_{s,コマ数} \quad \text{for $s \in \mathbf{Subjects}$}
\end{eqnarray}

⑥ 各授業は使用できる教室が決まっている

設備の関係で、授業によっては実施可能な教室が決まっている場合があります。また、高校などの授業では一部の授業以外は基本的にクラスごとに授業を行う自教室が決まっていることが多いと思います。

この制約は、そのような状況を想定して設定するものになります。

\begin{eqnarray}
x_{s,p,r} \leq d_{s,r}
\quad \text{for $s \in \mathbf{Subjects}$, $p \in \mathbf{Periods}$, $r \in \mathbf{Rooms}$}
\end{eqnarray}

⑦ 各授業は実施できる時限が決まっている

あまり多くはありませんが、例えば特定の授業を必ず1限にしたいなどの場合にこの条件を指定します。

\begin{eqnarray}
x_{s,p,r} \leq g_{s,p}
\quad \text{for $s \in \mathbf{Subjects}$, $p \in \mathbf{Periods}$, $r \in \mathbf{Rooms}$}
\end{eqnarray}

⑧ 教員は講義できる時間が決まっている

非常勤講師が受け持つ授業については、授業を受け持つ曜日が決まっていることが多いです。また、私の所属する専門学校の場合は、他学科と掛け持ちで授業を持っている教員も一部います。

そのような教員については、授業の実施できる時限を細かく指定する必要があります。

\begin{eqnarray}
\sum_{\substack{s \in \mathbf{TeacherCourses}_t,\\ r \in \mathbf{Rooms}}} x_{s,p,r} \leq f_{t,p} \quad \text{for $t \in \mathbf{Teachers}$, $ p \in \mathbf{Periods}$}
\end{eqnarray}

⑨ 時間ごとに使用できる教室が決まっている

私のいる学校では、全学科で使用可能な大教室があります。その教室については、他の学科が使わない時間の中からしか授業を割り当てることが出来ません。

\begin{eqnarray}
\sum_{s \in \mathbf{Subjects}} x_{s,p,r} = e_{r,p} \quad \text{for $r \in \mathbf{Rooms}$, $p \in \mathbf{Periods}$}
\end{eqnarray}

2.3. 目的関数の定義

上記を満足する時間割であれば、どんなものでも時間割として成立するため、目的関数は例えば定数などでもモデルとしては成立します。ただし、目的関数を何らかの指標で設定したほうが、結果的には求解速度が速くなると聞いたことがあります。

私の定式化では適当な変数を追加して、目的関数に組み込んでいますが、目的に合わせて設定すると良いと思います。

2.4. その他

上記の定式化で最低限の条件はすべて盛り込んだつもりですが、学校ごとに個別の制約条件が必要な場合が多いと思います。

例えば、私のいる専門学校で追加で考慮すべき条件は以下の2つです。

• 選択授業を実施する場合、同じクラスが2つの教室に分かれて授業を実施する
• 合同授業の場合、複数のクラスが同時に同じ教室で授業を実施する

こういった個別の事情に対応する場合は、2.2の制約式を新しく追加する必要がありますが、数理最適化をある程度かじった人でないと難しいかもしれません。。。

3. Pythonによる実装

上記のモデルをPythonで実装しました。最も簡単に用意できたのがpulpだったため、今回はpulpを使って定式化しています。

# 線形/整数線形最適化問題を解くためにPuLPをインポート
import pulp
# 計算時間を計るのにtimeをインポート
import time
import pandas as pd

#####使用する集合・辞書の定義#####
'''
Subjects                # 授業のリスト
Periods                 # 時限の集合
Rooms                   # 教室の集合
Classes                 # クラスの集合
Teachers                # 教員の集合
SubjectProperties        # 授業の辞書 (変数名： [クラス, コマ数, 科目担当,授業名])
TeacherCourses          # 科目担当の辞書 (教員名: 授業のリスト)
ClassCourses            # クラス授業の辞書 (クラス名: 授業のリスト)
D                       # 授業sが教室rで実施可能かどうかの0-1
E                       # 時限rに教室pが利用可能かどうかの0-1
F                       # 教員tが時限pに授業可能かどうかの0-1
G                       # 授業sが時限pに授業可能かどうかの0-1
H                       # クラスが時限pに授業可能かどうかの0-1
'''

### 集合・辞書の読み込み #########
#
# 省略(csvなどのデータを読み込み)
#
################################

# 数理最適化問題（最小化）を宣言
problem = pulp.LpProblem("Problem-2", pulp.LpMaximize)
# pulp.LpMinimize : 最小化 
# pulp.LpMaximize : 最大化

# 変数集合を表す辞書
x = {} # 空の辞書

# 0-1変数を宣言
for s in Subjects:
    for p in Periods:
        for r in Rooms:
            x[s,p,r] = pulp.LpVariable(f"x({s},{p},{r})", 0, 1, pulp.LpInteger)

##### 制約条件を宣言 #####
#基本制約 : 同じ時間の同じ教室に複数の授業を割り当てない
for p in Periods:
    for r in Rooms:
        problem += pulp.lpSum(x[s,p,r] for s in Subjects) <= 1, f"基本制約_{p}_{r}"

# 教員基本制約 : 教員は同じ時間に複数コマの授業を行えない
for t in Teachers:
    for p in Periods:
        problem += pulp.lpSum(x[s,p,r] for s in TeacherCourses[t] for r in Rooms) <= 1, f"教員基本制約_{t}_{p}"

# クラス基本制約 : クラスは同じ時間に複数コマの授業を行えない
for c in Classes:
    for p in Periods:
        problem += pulp.lpSum(x[s,p,r] for s in ClassCourses[c] for r in Rooms ) <= 1, f"クラス基本制約_{c}_{p}"

# クラス時限制約 : クラスは授業を実施しなければいけない時限が決まっている
for c in Classes:
    for p in Periods:
        problem += pulp.lpSum(x[s,p,r] for s in ClassCourses[c] for r in Rooms) >= H.loc[c,p],  f"クラス時限制約_{c}_{p}"
    
# 授業コマ数制約 : 授業は指定されたコマ数回実施する
for s in Subjects:
    problem += pulp.lpSum(x[s,p,r] for p in Periods for r in Rooms) == SubjectProperties[s][1], f"授業コマ数制約_{s}"

# 授業教室制約 : 各授業は使用できる教室が決まっている
for s in Subjects:
    for p in Periods:
        for r in Rooms:
            problem +=  x[s,p,r] <= D.loc[s,str(r)], f"授業教室制約_{s}_{p}_{r}"

# 授業時限制約 : 各授業は実施できる時限が決まっている
for s in Subjects:
    for p in Periods:
        for r in Rooms:
            problem += x[s,p,r] <= G.loc[s,p], f"授業時限制約_{s}_{p}_{r}"

# # 教員時限制約 : 教員は講義できる時間が決まっている
for t in Teachers:
    for p in Periods:
        problem += pulp.lpSum(x[s,p,r] for s in TeacherCourses[t] for r in Rooms) <= F.loc[t,p], f"教員時限制約_{t}_{p}"
    
# # 授業教室制約 : 時間ごとに使用できる教室が決まっている
for p in Periods:
    for r in Rooms:
        problem += pulp.lpSum(x[s,p,r] for s in Subjects) <= E.loc[r,p], f"教員時限制約_{p}_{r}"

# 目的関数を宣言
# その日の最後のコマが担任だった場合加点
problem += pulp.lpSum(x[s,p,r]
                      for s in Subjects
                      for p in Periods
                      for r in Rooms
), "目的関数は本来不要だが適当に設定"

# 問題の式全部を表示
print("問題のサイズ")
print(f"-" * 8)
va = problem.variables()
co = problem.constraints
print(f"変数:{len(va)}, 制約:{len(co)}")
print(f"-" * 8)
print("")

# 計算
solver = pulp.COIN_CMD(path=r'lib\Cbc\bin\cbc.exe', threads=8, timeLimit=120.5)

# 時間計測開始
time_start = time.perf_counter()
result_status = problem.solve(solver)
# 時間計測終了
time_stop = time.perf_counter()

# （解が得られていれば）目的関数値や解を表示
print("解 x[i,j]: ")
with open('result.txt', 'w') as f:
    for r in Rooms:
        for p in Periods:
            for s in Subjects:
                if x[s,p,r].value() > 0.9:
                    sp = SubjectProperties[s]
                    print(f"{r}\t{p}\t{sp[0]}\t{sp[2]}\t{sp[3]}")
                    print(f"{r}\t{p}\t{sp[0]}\t{sp[2]}\t{sp[3]}", file=f)

print(f"*" * 8)
print("計算結果")
print(f"*" * 8)
print(f"最適性 = {pulp.LpStatus[result_status]}, ", end="")
print(f"目的関数値 = {pulp.value(problem.objective)}, ", end="")
print(f"計算時間 = {time_stop - time_start:.3f} (秒)")

途中の省略している部分では、実際はExcelで入力した授業や教員などの情報をもとに、1.で紹介した集合群を用意しています。こちらのサンプルをお見せできればよかったのですが、学校の授業に関わるデータとなるためお見せできません。

4. 実際に実行したときの情報

2023年度の時間割を作成するのにかかった時間などを紹介します。

まずは、基本的な集合のサイズです。

• クラス数 : 10
• 教室数 : 11
• 時限数 : 14
• 教員数 : 18
• 授業数 : 101

これらを使ってモデルを作成した際のモデルの規模と結果を得るまでにかかった時間は以下の通りです。

• 変数の数 : 約16,000
• 制約の数 : 約33,000
• 処理時間 : 13.5秒

計算に使用したのは、一般的なノートPC(Core i5, メモリ8GB)を使用しています。現在のところ、10クラス規模(2学年5クラスや3学年3クラス)であれば、十分に家庭用PCで解ける範囲だと思います。

計算時間以上にデータの入力が最も時間がかかる作業ですが、一度設定してしまえば、条件が変更になったとしても修正してすぐに新たな答えを出力できるのが大きいです。実際、毎年時間割を作成していますが、初回で時間割が決まることはほぼなく、数回～十数回の修正が必要になっています。

5. 最後に

今回は整数計画法を使って、時間割を作成する方法について紹介しました。

整数計画法を含む数理最適化を使いこなすには、数理モデルの定式化を理解する必要があり、簡単に誰でも使えるようなものではありません。ですが、使いこなすと、人の頭では複雑すぎて答えが求まらないようなものも、一瞬で解くことが可能になる技術です。

近年は、機械学習にばかり注目が集まりますが、この記事をきっかけにして興味を持つ方が一人でも増えてくれたら嬉しいです。