PuLP 時間割作成問題

PuLP 時間割作成問題

学校や大学の時間割を作成する際には、特定の科目が特定の時間に配置されるようにする必要があります。

ここでは、時間割作成問題PuLPで解決する方法を示します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import pulp as pl

# 教師、科目、時間スロットのリスト
teachers = ['T1', 'T2']
subjects = ['Math', 'Science', 'English']
time_slots = ['Monday 9am', 'Monday 11am', 'Wednesday 9am']

# 教師が教えられる科目
teacher_subjects = {
'T1': ['Math', 'Science'],
'T2': ['Science', 'English']
}

# 問題の定義
prob = pl.LpProblem("Timetable_Problem", pl.LpMinimize)

# 変数の定義
vars = pl.LpVariable.dicts("Schedule", (teachers, subjects, time_slots), 0, 1, pl.LpBinary)

# 制約条件の定義
# 1. 各科目は1つの時間スロットに配置される
for s in subjects:
prob += pl.lpSum([vars[t][s][ts] for t in teachers for ts in time_slots]) == 1

# 2. 各教師は1つの時間スロットで1つの科目のみ教える
for t in teachers:
for ts in time_slots:
prob += pl.lpSum([vars[t][s][ts] for s in subjects]) <= 1

# 3. 教師は教えられる科目のみ教える
for t in teachers:
for s in subjects:
if s not in teacher_subjects[t]:
for ts in time_slots:
prob += vars[t][s][ts] == 0

# 問題の解決
prob.solve()

# 結果の表示
print("Status:", pl.LpStatus[prob.status])
for t in teachers:
for s in subjects:
for ts in time_slots:
if vars[t][s][ts].varValue == 1:
print(f"{t} will teach {s} at {ts}")

ソースコード解説

このソースコードは、教師、科目、時間スロットに関する時間割問題を解決するためにPuLPを使用しています。

以下に、コードの各章を詳しく説明します。

1. インポートとデータの定義

1
2
3
4
5
6
7
8
9
10
11
12
import pulp as pl

# 教師、科目、時間スロットのリスト
teachers = ['T1', 'T2']
subjects = ['Math', 'Science', 'English']
time_slots = ['Monday 9am', 'Monday 11am', 'Wednesday 9am']

# 教師が教えられる科目
teacher_subjects = {
'T1': ['Math', 'Science'],
'T2': ['Science', 'English']
}

説明:

  • pulp ライブラリを pl としてインポートします。
  • 教師、科目、時間スロットのリストを定義します。
  • teacher_subjects 辞書を用いて、各教師が教えることができる科目を定義します。

2. 問題の定義

1
2
# 問題の定義
prob = pl.LpProblem("Timetable_Problem", pl.LpMinimize)

説明:

  • LpProblem クラスを使って、新しい最適化問題を定義します。
    この問題の目的は、時間割の問題を解決することです。

目的関数LpMinimize で、最小化することを示していますが、実際の目的関数はこのコードでは特に定義されていません。

3. 変数の定義

1
2
# 変数の定義
vars = pl.LpVariable.dicts("Schedule", (teachers, subjects, time_slots), 0, 1, pl.LpBinary)

説明:

  • LpVariable.dicts を使って、3次元のバイナリ変数を定義します。

vars[t][s][ts] は、教師 t が科目 s を時間スロット ts に教えるかどうかを示すバイナリ変数です。

$0 $または$ 1 $の値を取ります。

4. 制約条件の定義

4.1 各科目は1つの時間スロットに配置される

1
2
3
# 1. 各科目は1つの時間スロットに配置される
for s in subjects:
prob += pl.lpSum([vars[t][s][ts] for t in teachers for ts in time_slots]) == 1

説明:

  • 各科目 s は、全ての教師と時間スロットに対して、ちょうど1回だけ教えられることを保証する制約です。
    lpSum 関数を使って、全ての教師と時間スロットにわたる変数の合計が$1$になるようにします。

4.2 各教師は$1$つの時間スロットで$1$つの科目のみ教える

1
2
3
4
# 2. 各教師は1つの時間スロットで1つの科目のみ教える
for t in teachers:
for ts in time_slots:
prob += pl.lpSum([vars[t][s][ts] for s in subjects]) <= 1

説明:

  • 各教師 t は、特定の時間スロット ts で、最大1つの科目 s を教えることを保証する制約です。

lpSum 関数を使って、各時間スロットにおける変数の合計が$1$以下になるようにします。

4.3 教師は教えられる科目のみ教える

1
2
3
4
5
6
# 3. 教師は教えられる科目のみ教える
for t in teachers:
for s in subjects:
if s not in teacher_subjects[t]:
for ts in time_slots:
prob += vars[t][s][ts] == 0

説明:

  • 各教師 t は、自分が教えることができない科目 s を教えないことを保証する制約です。teacher_subjects 辞書を参照し、教師が教えられない科目に対する変数を$0$に設定します。

5. 問題の解決

1
2
# 問題の解決
prob.solve()

説明:

  • 定義された問題を解決します。

PuLPsolve メソッドを使って、最適な解を見つけます。

6. 結果の表示

1
2
3
4
5
6
7
# 結果の表示
print("Status:", pl.LpStatus[prob.status])
for t in teachers:
for s in subjects:
for ts in time_slots:
if vars[t][s][ts].varValue == 1:
print(f"{t} will teach {s} at {ts}")

説明:

  • 解のステータスを表示します。pl.LpStatus[prob.status] は解の状態を示します(例えば、最適解が見つかったかどうか)。
  • 各教師、科目、時間スロットの組み合わせに対して、変数の値が$1$の場合、その教師がその時間にその科目を教えることを示すメッセージを表示します。

まとめ

このコードは、PuLP を使用して時間割作成問題を解決するための例です。

教師、科目、時間スロットの組み合わせに対してバイナリ変数を定義し、制約条件を設定して、問題を解決します。

最終的に、最適な時間割を表示します。

結果解説

[実行結果]

Status: Optimal
T1 will teach Math at Monday 11am
T2 will teach Science at Wednesday 9am
T2 will teach English at Monday 11am

この結果は、PuLPを使って時間割作成問題を解決した際の出力です。

出力の内容を以下に説明します。

結果の解釈

  • Status: Optimal

    • このステータスは、最適解が見つかったことを示しています。
      つまり、与えられた制約条件の下で最良の時間割が作成されたことを意味します。
  • T1 will teach Math at Monday 11am

    • 教師T1が、月曜日の午前11時に数学を教えることが決定されたことを示しています。
  • T2 will teach Science at Wednesday 9am

    • 教師T2が、水曜日の午前9時に科学を教えることが決定されたことを示しています。
  • T2 will teach English at Monday 11am

    • 教師T2が、月曜日の午前11時に英語を教えることが決定されたことを示しています。

解の詳細

この結果は、以下のような制約条件と目標に基づいています。

  1. 各科目は1つの時間スロットに配置される

    • どの科目も$1$つの時間スロットに割り当てられています。
  2. 各教師は1つの時間スロットで1つの科目のみ教える

    • 各教師は$1$つの時間スロットで$1$つの科目しか教えていません。
      例えば、T1は月曜日11amMathを教え、他の時間帯には何も教えていません。
  3. 教師は教えられる科目のみ教える

    • 各教師は指定された科目のみを教えています。
      T2ScienceEnglishを教えており、T1Mathを教えています。

このスケジュールは、与えられた制約をすべて満たしつつ、可能な最適な配置となるように調整されています。

PuLPがこの問題を効率的に解決し、最適な時間割を提供していることが分かります。