数理最適化による時間割作成

0,初めに

時間割の最適化について、今では様々なソフトがあり、ある程度簡単にできるだろう時間割作成だが自治体や学校、はたまた教務主任のこだわりなど多様なニーズがある。
将来的な目標として多様なニーズに対応できる、LLMを用いたプロンプトによる最適化を目指すため、今回は基本的な制約条件を実装していく。

1,定数と集合の定義

必要な情報を整理し、定式化していくために定数と集合を定義する。

定数名	説明
d	曜日
p	時限
g	学年
c	クラス
s	授業名
t	教員名

集合名	説明
D	曜日dの集合
P	時限pの集合
G	学年gの集合
C	クラスcの集合
S	授業名sの集合
T	教員名tの集合
$S_m$	移動教室の集合

2,変数の定義

１の定数を使って変数を定義する。

\begin{aligned}
x_{d,p,g,c,s} &= 
\begin{cases}
1 & \text{曜日$d$の時限$p$に学年$g$のクラス$c$で授業$s$を実施する}\\
0 & \text{実施しない}
\end{cases}\\
y_{d,p,n} &= 
\begin{cases}
1 & \text{曜日$d$の時限$p$に教員$t$が授業を実施する}\\
0 & \text{実施しない}
\end{cases}\\
\end{aligned}

以上の変数を使って最適化を行っていく。

3,制約条件の定式化

今回は以下の7つの制約条件を用いる。

3.1クラスごとの制約

(1) 1 つの時限では必ず 1 つ授業を行う

$$ \sum_{s\in{S}}x_{d,p,g,c,s} = 1 　d\in{D},p\in{P},g\in{G},c\in{C} $$

3.2教科ごとの制約

(2) 各教科sは1週間の必要授業数 f(s) だけ行う

$$ \sum_{d\in{D},p\in{P}}x_{d,p,g,c,s} = f_{(s)} 　g\in{G},c\in{C},s\in{S} $$

(3) 各教科は 1 日の授業数の上下限を守る

$$ \sum_{p\in{P}}x_{d,p,g,c,s} \leq 1 　d\in{D},g\in{G},c\in{C},s\in{S} $$

(4) 体育など移動教室は連続しない

$$ \sum_{s\in{S_m}}x_{d,p,g,c,s}+x_{d,p+1,g,c,s} \leq 1 　d\in{D},p\in{P-\{6\}},g\in{G},c\in{C} $$

(5)総合と道徳の制約

➀総合と道徳は6限に行う

$$ \sum_{s\in{\{総合,道徳\}}}x_{d,p,g,c,s} = 0 　d\in{D},p\in{P-\{6\}},g\in{G},c\in{C} $$

➁総合と道徳は学年で曜日を統一して行う

$$ x_{d,p,g_i,c,s} = x_{d,p,g_j,c,s} 　d\in{D},p\in{P-\{6\}},g_i,g_j\in{G},c\in{C},{s\in{\{総合,道徳\}}} $$

➂総合と道徳は異なる学年で同じ時間には行わない

$$ \sum_{g\in{G}}x_{d,p,g,c,s} \leq 0 　d\in{D},p\in{P},c\in{C},{s\in{\{総合,道徳\}}} $$

3.3教員の制約

(6) 1教員が1日に行う授業数の上下限を守る

$$ 4 \leq \sum_{p\in{P}}y_{d,p,t} \leq 5 　d\in{D},t\in{T} $$
(修正時追記)

(7) 1教員が同日同時限に行える授業は一つ

$$ y_{d,p,t}=1 　d\in{D},p\in{P},t\in{T} $$

4,目的変数の設定

最適化問題では目的変数を設定して、それが最大もしくは最小になるように計算をするが、以上の条件を満たす時間割であればいいので設定しなくても解くことは可能である。
今回は職員室に残る教員のバランスを考慮して、所属学年ごとの空きコマである教員の人数の偏りを最小化する。
定式化のため、新しく変数を定義する。
$$ z_{d,p,g}:曜日dの時限pが空きコマである学年gの教員の人数 $$
これを用いて目的変数を定義すると、
$$ Minimize:\sum_{d\in{D},p\in{P}}max_{g\in{G}}(z_{d,p,g}) - min_{g\in{G}}(z_{d,p,g}) $$

5,Pythonによる実装

今回はPuLPを使って実装する。
なお環境としてJupyter Notebookを想定している。
まず必要なライブラリとデータを準備する。

#ライブラリのインポート
import pandas as pd
import numpy as np
import pulp

#基本情報のデータ
teacher_list = [f'教員{i}' for i in range(22)]
subject_list = ["英語","数学","国語","理科","社会","美術","音楽","体育","技術","家庭科","総合","道徳"]
grade_list = [1,2,3]
class_dict = {3:[1,2,3,4,5],2:[1,2,3,4],1:[1,2,3,4]}
teacher_dict = {t:g for t,g in zip(teacher_list,[3,3,3,2,1,1,3,2,1,3,2,1,2,1,1,3,2,1,3,2,3,2])} #教員の所属学年
period = [1,2,3,4,5,6]
week = ["月","火","水","木","金"]
Classroom_mobility = ["美術","音楽","体育","技術","家庭科"] #移動教室授業
six_period = ["総合","道徳"] #6限のみの授業
subject_dict = {s:n for s,n in zip(subject_list,[4,4,4,4,4,2,2,2,1,1,1,1])} #必要授業数

上記はPythonでは作成したがExcelなど表計算ソフトでまとめておくとフレキシブルに対応できる。
またPythonで作成するには手順が冗長になってしまったDataframeも作成したのでそれは下記で一部例のみ示す。(最後にテスト用のデータフレームを作成するコードを載せます。※1)

gr	cl	英語	数学	…
3	1	教員6	教員9	…
3	2	教員6	教員9	…

今回は上のようにカラムに学年,クラス,教科、要素として授業担当教員の構成を当てはめたcsvを実務的にはExcelなどで作成し読み込んだとする。

lesson_df = pd.read_csv("https://raw.githubusercontent.com/ryosuke0010/opt_test/master/composition.csv")

これで準備はできたので、変数を定義していく。

model = pulp.LpProblem("model",pulp.LpMinimize)
x = {}
y = {}
z = {}
#x_曜日_時限_学年_クラス_授業
for d in week:
    for p in period:
        for g in grade_list:
            for c in class_dict[g]:
                for s in subject_list:
                    x[d,p,g,c,s] = pulp.LpVariable(cat="Binary",name=f"x_{d}_{p}_{g}_{c}_{s}")

#y_曜日_時限_教員
for d in week:
    for p in period:
        for t in teacher_list:
            y[d,p,t] = pulp.LpVariable(cat="Binary",name=f"y_{d}_{p}_{t}")

#z_曜日_時限_学年
for d in week:
    for p in period:
        for g in grade_list:
            z[d,p,g] = pulp.LpVariable(cat="Integer",name=f"z_{d}_{p}_{g}")

#(1)1 つの時限では必ず 1 つ授業を行う
for d in week:
    for p in period:
        for g in grade_list:
            for c in class_dict[g]:
                model += pulp.lpSum([x[d,p,g,c,s] for s in subject_list]) == 1

#(2)各教科sは1週間の必要授業数だけ行う
for g in grade_list:
    for c in class_dict[g]:
        for s in subject_list:
            model += pulp.lpSum([x[d,p,g,c,s] for d in week for p in period]) == subject_dict[s]

#(3)教科は 1 日の授業数の上下限を守る
for d in week:
    for g in grade_list:
        for c in class_dict[g]:
            for s in subject_list:
                model += pulp.lpSum([x[d,p,g,c,s] for p in period]) <= 1

#(4)体育など移動教室は連続しない
for d in week:
    for p in period[:5]:
        for g in grade_list:
            for c in class_dict[g]:
                model += pulp.lpSum([x[d,p,g,c,s] + x[d,p+1,g,c,s] for s in Classroom_mobility]) <= 1

#(5)総合と道徳の制約
#➀総合と道徳は6限
for d in week:
    for p in period[:5]:
        for g in grade_list:
            for c in class_dict[g]:
                model += pulp.lpSum([x[d,p,g,c,s] for s in six_period]) == 0

#➁総合と道徳は学年で曜日を統一して行う
for d in week:
    for g in grade_list:
        for c in class_dict[g][:-1]:
            for s in six_period:
                model += x[d,6,g,c,s] == x[d,6,g,c+1,s]
 
#➂総合と道徳は異なる学年で同じ時間には行わない
for d in week:
    for s in six_period:
        model += pulp.lpSum(x[d,6,g,1,s] for g in grade_list) <= 1

#yをxの関数として定義 y=f(x)
for d in week:
    for p in period:
        for g in grade_list:
            for c in class_dict[g]:
                for s in subject_list:
                    df = lesson_df[lesson_df["gr"] == g]
                    t = df[df["cl"] == c][s].values[0]
                    y[d,p,t] += x[d,p,g,c,s]

#(6)1教員が1日に行う授業数の上下限を守る
for d in week:
    for t in teacher_list:
        model += pulp.lpSum([y[d,p,t] for p in period]) <= 6
        model += pulp.lpSum([y[d,p,t] for p in period]) >= 4

#(7)1教員が同日同時限に行える授業は一つ
for d in week:
    for p in period:
        for t in teacher_list:
            model += y[d,p,t] == 1

for d in week:
    for p in period:
        for g in grade_list:
            z[d,p,g] = list(teacher_dict.values()).count(g) - pulp.lpSum([y[d,p,t] for t in [a for a in teacher_list if teacher_dict[a] == g]])

model += pulp.lpSum([np.max([z[d,p,g] for g in grade_list]) - np.min([z[d,p,g] for g in grade_list]) for d in week for p in period])

model.solve()

以上で(解が存在すれば)最適化が完了したので、以下ではPythonで出力していく。

def export_table(g,c):
    timetable_df = pd.DataFrame(index=period,columns=week)
    
    for d in week:
        for p in period:
            for s in subject_list:
                if x[d,p,g,c,s].value() == 1.0:
                    timetable_df[d][p] = s

    print(timetable_df)

export_table(3,1)

これで３年１組の時間割が以下のように表示される。

	月	火	水	木	金
1	美術	技術	理科	英語	音楽
2	数学	英語	社会	社会	社会
3	理科	家庭科	美術	理科	体育
4	国語	数学	国語	国語	英語
5	英語	音楽	数学	数学	国語
6	社会	理科	体育	総合	道徳

実際に運営するうえでは他クラスとの整合性も確認するところではあるが、一クラス分では間違いが見当たらない出来となった。
ただ同じ授業が違う曜日の同じ時限にあったりと、（経験がないので分からないが）おそらく文句が出そうなポイントがあるので、そういったこだわりポイントをどのように制約として条件付けするかが課題である。

6,まとめ

今回は組み合わせ最適化による時間割を作成を行った。

このような最適化モデルをつくるには多少の勉強時間が必要なため、実際の教育現場で使用していくことは難しい部分が多いだろうと思う。今後はLLMを用いて数理最適化の知識がなくても、制約条件や目的変数の設定などができるモデルの作成をしていく。