時間割最適化
藪内

1

友紀

(指導教員：工藤和恵)

はじめに科目が重ならずに時間割が組める。

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

2

第２項は各コマに関する制約の項である。

• i: 頂点 (科目)、k: 色 (コマ)• qi : 頂点 i の色 (科目が入れられているコマ)• n slot: 色の数、n node: 頂点数

時間割を組む方法

頂点 (科目)i が避けたい色 (コマ)k に対しては正の重み (wik > 0) を、塗りたい色 (コマ)k に対しては負の重み (wik < 0) をあたえる。つまり、頂点の重みが最小になるように色を塗り分けることで、制約を満たせる。
このエネルギー E が最小のとき、時間割は最適な状態である。E が最小である状態を探すために、本研究ではシミュレーテッド・アニーリング法を用いる。

時間割をグラフで表す。科目を頂点とし、同じ時間帯に重なってほしくない科目を辺で結んでできるネットワークを、時間割グラフと呼ぶことにする (図 1)。

4アルゴリズム

シミュレーテッド・アニーリング法を使った時間割最適化アルゴリズムは、以下の通りである [1]。
ステップ０ 初期値設定
すべての頂点にランダムに色を塗る。

図 1: 情報科学科前期の時間割グラフ。頂点が科目に対応する。重なってほしくない科目、すなわち、対象

ステップ１ 次の色配置設定
ランダムに選んだ１つの頂点の色を塗り替える。
塗り替える前の状態を X (t) 、後の状態を X ′ とする。

学年または教員が同じ、計算機室を使う授業同士を結んだ。
時間割グラフを頂点彩色する。色ごとにコマ (時間帯) を割り当てた後、頂点彩色をおこなうと、つながった頂点同士は違う色で塗り分けられるので、重なってはいけない科目が重ならずに時間割が組める。しかし、頂点彩色のみでの時間割作成には、頂点彩色では解けない制約がある。例えば、月曜日の１限は避けるなど、個別のコマに対する制約を課す場合である。この問題点を解決するために、時間割グラフに関してエネルギーを定義し、最適化問題を解く方法を採用する。

3

ステップ２ エネルギー変化率の計算′
エネルギー変化率 : ∆ = exp( E−ET )E: 状態 X (t) のときのエネルギーE ′ : 状態 X ′ のときのエネルギー
T : 温度のパラメータ
ステップ３ 状態更新
一様乱数 r ∈ [0, 1] を生成し、以下のように次の状態 X (t+1) を決める。

モデル{

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

E=∑

Jij δqi ,qj +(i,j)

n∑slot n ∑node
k=1

wik δqi ,kX (t+1) =X′X (t)r≤∆otherwise(状態更新)(状態更新なし)

ステップ 1〜3 を何回か繰り返す。

(1)i=1ステップ４ パラメーター T の更新
状態更新 → T を下げる: T = T · dT
T
状態更新なし → T を上げる: T = dT
(dT は温度変化率、0 < dT < 1 )第１項は重なってはいけない科目に関する項である。

• i,j: 頂点 (科目)• qi ,qj :それぞれの頂点の色 (それぞれの科目のコマ)

ステップ５ 繰り返し
ステップ１に戻って、同じ操作を繰り返す。

• Jij : 枝の重み (ここでは Jij = 1 とする)
qi = qj ならば、δqi ,qj = 1、qi ̸= qj ならば、δqi ,qj = 0である。つまり、結ばれた頂点同士の色が同じ色ならば、１であり、違う色ならば０である。したがって、エネルギーの合計が０になれば、重なってはいけない

5制約条件

本研究では、式 (1) 第１項の制約条件に関して「対象学年が同じ」、「同じ教員」、「計算機室を使用」という条件に加え、講義教室の選択ができるように制約55

条件を追加した。式 (1) の第１項を、式 (2) のように「学年・教員の項」、「教室第１希望の項」、「教室第２希望の項」の３つの項に分割しエネルギーを考えることで、制約を満たすことができるようにした。
∑∑∑∑
Jij δqi ,qj =J0 δqi ,qj +J1 δqi ,qj +J2 δqi ,qj
(i,j)

(i,j)

(i,j)

(i,j)

(2)
まず、登録科目の講義教室の第１希望を比較する。第
１希望が違うならば、J0 = 1, J1 = J2 = 0。第１希望が同じならば第２希望を比較し、第２希望が違うならば、J0 = J1 = 1 , J2 = 0。第２希望も同じならば、
J0 = J1 = J2 = 1 とする。式 (1) 第２項の制約条件に関しては、「コア科目・教職科目・語学の開講時間を避ける」、「計算機室を使う授業は午後」、「専門科目は水曜日を避ける」を制約条件とする。

6

図 3: 制約の割合を 10%、30%、50%、70%、90%とし、1 年生 (緑)・2 年生 (青)・3,4 年生 (赤) について全ての通りで 10000 回実行した統計データ。横軸は制約の割合の最大値、縦軸は成功率である。

PHP への実装と実行らかが最大値をとるとき 0.85 程度の成功率を得る。そして、2 年生と 3,4 年生が共に最大値をとるとき、または全学年が共に最大値をとるとき成功率は 0.7 程度である。最大値 90%では、大幅に成功率が下がる。1 年生のみが最大値をとるとき 0.3 から 0.6 の成功率を得るが、2 年生または 3,4 年生のどちらか一方でも最大値をとる組み合わせのとき、成功率は 0.1 に満たない。
これより、成功率には 2 年生と 3,4 年生の制約の割合が大きく関係していると考えられる。実際に、図 1についてネットワークの次数の合計は、3,4 年生科目が 118 と最も多く、次に多いのは 2 年生科目の 97 であった。1 年生科目の次数の合計は 49 で、2 年生と 3,4年生の次数の合計のおよそ半分であった。ネットワー
クの次数の多さと、制約の割合が成功率に及ぼす影響は相関関係があると推測できる。

本研究では、実際の運用を考え、Web を通して時間割作成ができるよう PHP に載せて実装した。上記のアルゴリズムを使用し、情報科学科前期の授業についてPHP 上で実行した。制約条件は前述のとおりである。
実行結果は図 2 のようになった。学年、教員、教室が重ならずに組めている。また、制約もすべて満たせている。

8

最適な時間割を組むために、時間割グラフの頂点彩色問題を解き、ポッツ模型 (式 (1)) を用いてシミュレーテッドアニーリング法で最適解を見つける。先行研究の制約条件に、講義教室の希望選択ができるように制約条件を加えるとともに、PHP への実装をおこないWeb 上で実行ができるようにすることで、さらに実用性を高めることができた。また、各学年の制約の割合と時間割作成の成功率に注目することで、ネットワー
クの構造と時間割の組みにくさの関係性や制約の限界に気づくことができた。
今後は実際の運用を考え、情報科学科の主・強化プ
ログラムだけでなく、副・学際プログラム、また他学科や他学部への拡張に向け、研究を発展させたい。

図 2: 実行結果。緑：１年生、青：２年生、赤：3, ４年生対象のもの。[ ] 内は使用教室。

7

まとめ

制約の割合と時間割作成の成功率

時間割アルゴリズムの大きな特徴は、個別の科目に、式 (1) の第２項の wik を通じて制約をつけられることである。そこで、制約の割合と時間割作成の成功率との関係性に注目する。ここでいう制約の割合とは、
wik (1 ≤ k ≤ n slot, 1 ≤ i ≤ n node) を 0 または 1 で与えたときの、wik = 1 の割合である。2014 年度の情報科学科前期の時間割グラフ (図 1) について、1 年生科目、2 年生科目、3,4 年生科目で制約の割合を変え、時間割作成の成功率の統計をとった結果を図 3 に示す。
このとき、温度変化率 dT = 0.1、一定温度での繰り返し回数は 100 回とした。
制約の割合の最大値が 10%、30%、50%までであれば、１または１に近い成功率が得られた。一方で 70%、90%で成功率にばらつきが見られる。この２つのばらつきについて詳しく見ることにする。
最大値 70%のところでは、１年生のみが最大値をとるとき 0.9 以上の成功率、2 年生または 3,4 年生のどち

参考文献[1] 福島孝治, 「モンテカルロ法の前線」, 若手研究者・学生向けに最新技術をわかりやすく紹介する
講演会「確率的アルゴリズムによる情報処理」講義ノート, (2003)[2] R.J. ウィルソン (原著), 西関 隆夫 (翻訳)・西関裕子 (翻訳), 「グラフ理論入門」, 近代科学社,(2001)[3] たにぐちまこと, 「よくわかるＰＨＰの教科書
ＰＨＰ５．５対応版」, マイナビ, (2014)56