時間割最適化
藤井綾香

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

はじめに

4

大学の時間割は、必修科目、教職科目、語学など、同じ時間帯に重なってほしくない科目が複数あり、時間割を考えるのは難しい。そこで本研究は、重なってほしくない科目が重ならないような時間割を簡単に作成するための方法を考案することを目的とする。

2モデル

時間割ネットワーク上の反強磁性的ポッツ模型のエネルギーを次のように定義する。

E=∑

Jij δqi ,qj +(i,j)

時間割ネットワーク

slot n ∑noden∑
k=1

wik δqi ,ki=1

第１項は辺で結ばれた頂点 (i, j) の間に生じるエネルギーである。

まず、複雑な時間割をグラフで表す。科目を頂点とし、同じ時間帯に重なってはいけない科目を辺で結んでできるネットワークを、時間割ネットワークと呼ぶことにする。2013 年度の情報科学科前期の時間割ネッ
トワークは図 1 のようになる。

• i,j: 頂点 (科目)• qi ,qj : それぞれの頂点の色 (それぞれの科目のコマ)• Jij : 枝の重み、今は Jij = 1 とする
qi = qj ならば、δqi ,qj = 1、qi 6= qj ならば、δqi ,qj = 0である。つまり、結ばれた頂点同士の色が同じ色ならば、１であり、違う色ならば０である。したがって、エネルギーの合計が０になれば、重なってはいけない科目が重ならずに時間割が組める。
第２項は各コマの色に関する制約を表している。

• i: 頂点 (科目)
図 1: 情報科学科前期の時間割ネットワーク。頂点が• k: 色 (コマ)講義、重なってほしくない授業を辺で結んだ。この場• qi : 頂点 i の色 (科目が入れられているコマ)合、対象学年が同じ科目同士、同じ先生の科目同士、• n slot: 色の数、n node: 頂点数

計算機室を使う授業同士を結んだ。

3

頂点 (科目)i が避けたい色 (コマ)k に対して、正の重み (wik > 0) を、塗りたい色 (コマ)k に対して、負の重み (wik < 0) をあたえる。よって、頂点の重みが最小になるように色を塗っていけば、制約を満たせる。
このエネルギー E が最小のとき、時間割は最適な状態である。E が最小である状態を探すには、どうすればよいか。考えられるすべての色配置について、それぞれ E を計算し、その中から最小のものを選んでくるというやり方では、とても時間がかかってしまう。そこで、本研究ではシミュレーテッド・アニーリング法を用いる。シミュレーテッド・アニーリング法は、モンテカルロ法の一種であるメトロポリス法を発展させた方法であり、近似解を求める一般的な方法である。

時間割を組む方法

時間割ネットワークを無向グラフとし、頂点彩色をする。まず、コマ (時間帯) それぞれに色を振り分ける。
例えば、赤は月曜日１限、緑は火曜日２限などといったようにする。その後頂点彩色をすると、つながれた頂点同士は違う色で塗り分けられるので、重なってはいけない科目が重ならずに時間割が組める (図 2)。しかし、頂点彩色での時間割作成には問題点がある。まず、頂点彩色問題は NP 完全問題である。つまり任意のネットワークに対して多項式時間でこの問題を解けるアルゴリズムは存在しない。また、時間割には頂点彩色では解けない制約がある。例えば、実習科目は午後がいい、などである。特に後者の問題点を解決するために、時間割ネットワークに関してエネルギーを定義し、最適化問題を解く方法を採用する。

5アルゴリズム

シミュレーテッド・アニーリング法を使った時間割最適化アルゴリズムは、以下の通りである [1]。
ステップ０ 初期値設定
すべての頂点にランダムに色を塗る。
ステップ１ 次の色配置を設定する
ランダムに頂点を一つ選び、ランダムに色を塗り替える。塗り替える前の状態を X (t) 、後の状態をX 0 とする。

図 2: 頂点彩色後の例

63

ステップ２ エネルギー変化率の計算
0エネルギー変化率 : ∆ = exp( E−ET )E: 状態 X (t) のときのエネルギー
E 0 : 状態 X 0 のときのエネルギーT : パラメーター (温度に対応、シミュレーテッドアニーリング法の特徴)ままに対応できるのだろうか。制約をつけるための重みが wik 6= 0 となる i と k の組み合わせの制約の数と、時間割最適化の成功率の統計をとった結果が図 4 である。T の初期値は、Tmax = 103 、最小値は Tmin = 10−2に設定する。温度変化率が 0.1 の場合、E が順調に下がっていけば、アルゴリズムの繰り返し回数は５回である。制約の数が 10 から 300 までは、平均繰り返し回数が５程度なので E が順調に下がり、最小値を見つけることができている。制約の数が 400 以上になると、成功率が１未満になった。そこで、温度変化率 dT を大きくし、ゆっくり温度を下げるようにした。制約の数が 600 になると、成功率は大きく下がる。以上をまとめると、制約の数が 10 から 300 程度であれば、時間割が組みやすく、400 以上になると時間割が組みにくくなることがわかった。

ステップ３ 変化率 ∆ と乱数との比較
一様乱数 r ∈ [0, 1] を生成し、以下のように次の状態 X (t+1) を決める。

{X(t+1)=X0X (t)r≤∆(状態更新)

otherwise (状態更新なし)

ステップ１〜３を何回か繰り返す。
ステップ４ パラメーター T の更新
状態が更新されたら T を下げる: T = T · dT
状態が更新されなければいったん T を上げる: T =T /dT(dT は温度変化率、0 ≤ dT < 1 )ステップ５ 繰り返し
ステップ１に戻って、同じ操作を繰り返す。

6

実行

図 4: 10000 回の実行に関する統計。時間割最適化の上記のアルゴリズムを使用して、情報科学科前期の授業で実行した。重なってはいけない講義を、「対象学年が同じ学年」、「同じ先生の授業」、「計算機室を使う授業」とする。制約条件としては、「コア科目・語学・教職科目の開講時間を避ける（対象学年が同じのもの）」、「計算室を使う授業は午後」、「専門科目は水曜日を避ける」とする。
実行結果は図 3 のようになった。重なってはいけない科目が重ならずに組めている。また、制約もすべて満たせている。

成功率 (E = 0 で実行終了したら成功)、１回の実行でアルゴリズム（ステップ１〜５）を何回繰り返したかの平均を計算したもの。ただし、1000 回を超えると E 6= 0 でも、ループをぬける。(wik ＝ {0, 1} とし、wik = 1 となる i, k はランダムに選ぶ。制約の数は最大で 672 個である。)

8

まとめ

時間割ネットワークの頂点彩色問題を解くことで時間割を組むことを土台とし、時間割ネットワーク上のポッツ模型を導入した。シミュレーテッドアニーリン
グ法を用いたアルゴリズムを使い、ポッツ模型のエネルギーを最小化することで、時間割を組む方法を提案した。この時間割最適化アルゴリズムを、実データで実行した結果、重なってはいけない科目同士が重ならないという条件と、制約を満たすことができた。実験的に制約の数を増やすと、ある値以上で成功率が下がり、計算時間が増えるという結果になった。
今後は、より複雑なネットワークでこのアルゴリズムを使い、研究を発展させたい。

参考文献[1] 福島孝治, 「モンテカルロ法の前線」, 若手研究者・学生向けに最新技術をわかりやすく紹介する
講演会「確率的アルゴリズムによる情報処理」講義ノート, (2003)

図 3: 実行結果。オレンジ：１年生、青：２年生、赤：3〜４年生対象のもの。

7

制約の数と時間割の組みにくさの関係[2] R.J. ウィルソン (原著), 西関 隆夫 (翻訳)・西関裕子 (翻訳), 「グラフ理論入門」, 近代科学社,(2001)

時間割アルゴリズムの大きな特徴は、制約をつけられることである。月曜日はいやだ、午後がいいなどのわがままに対応できる。では、どのくらい多くのわが64