アニーリングマシンによる時間割最適化
折田祐希美

1(指導教員：工藤和恵)

はじめにてはいけない頂点同士を結ぶ。
一方ソフトな制約は H3 , H4 , H5 , H6 , H7 の 5 つの制約項で構成する。それぞれの項を以下で説明する。
H3 は科目 i を割り当てたくないコマ c を指定するという制約を課すために次式で与える。
∑H3 = w3xi,c(2)

近年、中学や高校の教員の長時間労働が問題となっている。中学校では一日あたりの学内勤務時間が平均で 11 時間 32 分、さらに有給休暇も 8.8 日/年と過酷な環境にある [1]。
そこで本研究では教員の業務量を軽減させるために、従来教員が手動で行なっていた時間割作成を自動で行うことができるのでないかと考えた。従来型コンピュータよりも組み合わせ最適化問題の計算を高速に処理できる量子アニーリングマシンを用いれば、複雑な条件を満たす時間割を複数提案することができる。

2(i,c)∈P

P は、科目 i をコマ c に割り当てたくない組み合わせの集合である。例えば、教員が短時間勤務で 1 限に出られない時や非常勤講師の曜日指定などに使用する。
また、この制約はソフトな制約の中でも特に満たすべき制約のため、重み w3 は他の制約よりも大きくする。
H4 は科目 i, j を二時間連続にするという制約を課すために次式で与える。
∑∑
xi,c1 xj,c2
H4 = −w4(3)

方法と問題設定

本研究では、制約を破る数が最小となる時間割をシ
ミュレーテッドアニーリングと量子アニーリングマシ
ン D-Wave 2000Q を用いて求める。制約はハードな制
約とソフトな制約の二種類に分けられる。ハードな制約は時間割を生成する際に必ず満たすべき最低限の制約で、ソフトな制約は教員の希望など必ずしも満たさなくて構わない制約である。それぞれの制約にかける重みを調整し、ハードな制約は必ず満たすようにする。

3(i,j)∈E (c1 ,c2 )∈K

E は連続にしたい科目のペアの集合で、例えば長い時間の確保が必要な家庭科の科目のペアでなどが含まれる。K は連続コマのペアの集合で、[(月曜 1 限, 月曜 2限),(月曜 2 限, 月曜 3 限),...] と表される。また、この制約もソフトな制約の中でも特に満たすべき制約のため、重み w4 は他の制約よりも大きくする。
H5 は同じ教科の科目の割り当てを 1 日に 1 コマまでにするという制約を課すために次式で与える。
()()
∑∑ ∑∑
∑∑
H5 = w 5xi,cxi,c − 1

アルゴリズムと定式化

アニーリングマシンを利用して解くためには、イジングモデルや QUBO 形式での定式化が必要となる [2]。
定式化された目的関数を最小にする変数の組み合わせを求めると最適な時間割が得られる。ハードな制約は二つの制約項で構成され、目的関数は次式で表される。

H = w1n∑ ∑(i,j)∈E c=1xi,c xj,c + w2( nm∑∑i=1)2xi,c − 1s∈S t∈Ti∈s c∈ti∈s c∈t(4)
S は 1 日に多くて 1 コマのみ割り当てたい科目の集合
で、[(国語 1, 国語 2,...),(数学 1, 数学 2,...),...] と表される。T は 1 日に行うコマの集合で [(月曜 1 限, 月曜 2限,...),(火曜 1 限, 火曜 2 限,...),...] と表される。この制約は、同じ教科の科目が 1 日に 2 コマ以上割り当てられていると生徒への負担が大きいために課せられる。
H6 は同じ教科の科目の割り当てを同じ時間帯に 1 コマまでにするという制約を課すために次式で与える。
()()∑∑ ∑∑∑∑
H6 = w 6xi,cxi,c − 1c=1(1)(i,j) は科目のペア、E はクラス・教員・場所が同じ科目のペアの集合を示す。n はコマの総数、m は科目の総数である。xi,c は科目 i がコマ c に割り当てられているかどうかを示し、割り当てられている場合は 1、いない場合は 0 となる。また、w1 , w2 はそれぞれの制約項の重みである。
第一項は、クラス・教員・場所が同じである科目が同じコマに割り当てられることを避ける制約項である。
科目 i,j が同じコマを選択している場合は xi,c xj,c = 1となり、選択していない場合は xi,c xj,c = 0 となる。つまり、クラス・教員・場所が同じ全ての科目が同じコマではない時にこの制約項は 0 になる。
第二項は一つの科目に一つのコマのみを割り当てる制約項である。科目 i がただ一つのみのコマに割り当∑nてられている時に c=1 xi,c = 1 となり、この時にこの制約項は０になる。
なお、ハードな制約はグラフの彩色問題と類似した問題である [3]。グラフの彩色問題とは隣りあう頂点が同じ色にならないようにしながら塗り分けるという問題である。一方、ハードな制約は辺で結ばれた科目に違うコマを割り当てる問題である。また、辺は重なっs∈S t∈Ti∈s c∈ti∈s c∈t(5)S は同じ時間に 1 コマのみ割り当てたい科目の集合で、[(国語 1, 国語 2,...),(数学 1, 数学 2,...),...] と表される。
T は同じ時間帯のコマの集合で、[(月曜 1 限, 火曜 1限,...),(月曜 4 限, 火曜 4 限,...),...] と表される。この制約は、同じ教科の科目が 1 限のコマに複数割り当てられると遅刻する生徒が単位を落としてしまうため、また、同じ教科の科目が昼休み後の 4 限のコマに複数割り当てられると居眠りする生徒が多く成績が下がってしまうために課せられる。
H7 は教員が３連続授業を行うことを避けるという

1

制約を課すために次式で与える。
∑∑
H7 = w7xi,c1 xj,c2

表 1: 制約の充足レベル。制約を満たす場合は○、満たさない場合は×とする。

(6)(i,j)∈E (c1 ,c2 )∈K

レベル

E は同じ教員が担当する科目のペアの集合である。Kは連続するコマのペアの集合で、[(月曜 1 限, 月曜 2限),(月曜 2 限, 月曜 3 限),...] と表される。式としては2 連続になった場合に重みが追加されるが、他の制約よりも重み w7 を小さくし、実質的に 3 連続になるのを防ぐ。

4結果

本研究では川越女子高校へのヒアリング調査のもと、9 クラス/1 学年で 3 学年の 27 クラス、5 限/1 日 (木曜 5 限を除く) で月曜から金曜の週 5 日の 24 コマのデータを使用する。科目には事前にクラス・教員・場所の情報を付与する。H3 は教員 1 名が 1 限に出勤しないように、また、2 名が曜日固定になるように設定する。H4 は 4 ペアの科目が連続するように設定する。
H5 , H6 は全ての同じ教科の科目に適用する。H7 は全ての教員に適用する。そして木曜 5 限は全学年合同授業なので固定する。
シミュレーテッドアニーリング (SA) と量子アニー
リングマシン D-Wave 2000Q (DW) を用いて上記のデータを使用し、時間割最適化を実行した。本研究では実際の運用を考慮し、エクセルファイルに最適化された時間割が出力されるよう実装した。実行結果の一部は図 1 のようになった。また、この時間割のグラフの一部 (3 クラス分) は図 2 のようになっている。それぞれの頂点は科目、色はコマを表している。重なってはいけない科目の頂点同士を辺で結んでいる。同じクラスの科目の頂点がクラスタになっており、中央の科目の頂点は複数クラス合同の科目の頂点である。辺で結ばれた科目の頂点は全て違うコマの色で塗り分けられていることが分かる。

制約の種類

12345

ハードな制約 (1 年生)

×○○○○

ハードな制約 (2 年生)

××○

○

○

ハードな制約 (3 年生)

×××

○

○

ソフトな制約 (H3 , H4 )

××××

○

ソフトな制約 (H5 , H6 , H7 )×××××

表 2: 各方法による結果の制約充足レベルの w2 依存性

w2SADW

3.0

レベル 1

レベル 1

4.0

レベル 3

レベル 1

5.0

レベル 3

レベル 5 (91%充足)

6.0

レベル 5 (88%充足)

レベル 5 (88%充足)

7.0

レベル 5 (87%充足)

レベル 3

時間割は 1 学年ごとに最適化する。その時間割のコマデータを取り出し、次の学年の時間割を最適化する
際にクラス・教員・場所が重ならないように制約項を追加する。表 1 で制約の充足レベルを定義する。表 2 はw2 を調整した時の、各方法による結果の制約充足レベルを示す。その他の制約の重みは w1 = w3 = w4 =3.0, w5 = w6 = 0.3, w7 = 0.1 で固定した。なお、ハードな制約が満たされていない場合はソフトな制約は考えないものとする。SA では w2 = 6.0 の時、DW ではw2 = 5.0 の時に最も多くの制約を満たす時間割が得ることができた。

5

まとめ

本研究では中学高校の時間割を対象とした最適化をアニーリングマシンを用いて行った。時間割には必ず満たすべきハードな制約と必ずしも満たさなくて構わないソフトな制約がある。ハードな制約を満たしつつソフトな制約を最も多く満たす重みの比を見つけることが出来た。

参考文献

図 1: 時間割の出力結果[1]

文 部 科 学 省 ホ ー ム ペ ー ジ,
「教員勤務 実 態 調 査 (平 成 28 年 度)」,https://www.mext.go.jp/component/a_menu/
education/detail/__icsFiles/afieldfile/2018/09/27/1409224_001_4.pdf, (2021 年 1 月17 日アクセス)[2]

D-Wave, 「量子コンピューティング」, https://www.dwavejapan.com/system/, (2021 年 1 月20 日アクセス)[3] Fixstars, 「 グ ラ フ の 彩 色 問 題 」, https://quantum.fixstars.com/techresouces/application/graph-coloring/, (2021 年 1 月
20 日アクセス)

図 2: 1-1 組、1-2 組、1-3 組の時間割のグラフ2