時間割編成問題に対する近似解法の研究
情報工学専攻 久保田 敬
はじめに
全ての大学にとって時間割編成は重要な問題である 大 規模な時間割を手作業で編成することが困難であることから 計算機をもちいて自動的に時間割を編成する研究がなされて いる
時間割問題を解くにあたり 考慮に入れる要素が増えると 各教科に課せられる制約の数が増える 例えば連続授業を定 義するにはつの授業が連続しておこなわれるようにつの 授業を制約式で制御する必要があったり複数のクラスが同じ 授業を受講する場合も同様に 二つの授業を同じ時間帯におこ なわれるように制御する必要がある 逐次改良と変更をおこな いながら時間割を作成していく場合 ある状態の時間割が良い ものなのか判断するために 多くの制約を満たしているかどう か判定が必要であるため 判定する要素の数が増えると計算量 は増大する
本研究では 計算量を減少させるような教科 時間割モデル を開発すること大規模な時間割作成問題に対して 実用的な 時間で良い結果を求めることができる探索手法を開発すること を目的とする
大学の時間割・教科モデル
本研究では月曜から土曜まで限から限まである時間割 を対象にする 教師クラス教室のそれぞれの時間割を最適化 するうえで以下のような制約条件が用いられる
制約条件
一般的に大学の時間割編成時に以下のような制約がある
教師は同じ時間帯で重複して授業を受け持つことができ ない
クラスは同じ時間帯で重複して受講することができ ない
授業に適する大きさと適する種類の教室を選ばなくては ならない
教室数を超過して利用することはできない 教師の都合が悪い時間帯には教科を配置できない
連続授業は連続して配置しなければならない
ある授業を受け持つ教師が複数いるときは それぞれの 教師の都合をあわせて授業を配置しなければならない
ある授業を受講するクラスが複数ある場合は それぞれ のクラスの都合をあわせて授業を配置しなければなら ない
全ての教科がスケジュールに組み込まれなければなら
図一般教科を構成する要素
図教師可変型教科を構成する要素
ない
教師の授業と授業の間隔はなるべく小さいほうが好ま しい
クラスの授業と授業の間隔はなるべく小さいほうが好ま しい
限にはなるべく授業を配置しない
同学科の低学年の必修科目と高学年の必修科目はなるべ く重ならない方が好ましい
教師間での時間割に極端な優劣の差を無くす クラス間での時間割に極端な優劣の差を無くす
上記のからまでは物理的に満たさなければならない制 約条件である この制約条件のうちひとつでも満たしていなけ れば 実行不可能な時間割となる このような制約をハード制 約という から までは必須では無いがなるべく満たす ことが望ましい制約条件である このような制約をソフト制約 という ハード制約を完全に満たしながら ソフト制約を多く 満たしている時間割が良い時間割となる
教科の定義
教科を 受け持つ教師が指定される一般教科と 受け持つ教 師に指定が無い教師可変型教科との種類に分ける このつ の教科モデルを合わせることで であげたの制約 を教科を定義する段階で満たす
一般教科
一般教科 は 受け持つ教師の集合 受講するクラスの 集合 使用する教室タイプの集合 受講するクラスの 所属する学科の集合 連続授業時間数 を要素として 持つ構造をしている
図決定変数により各時間割が作成される様子
教師可変型教科
ある教科を受け持つことができる教師が複数いる場合 誰が どのクラスを教えても良いことがある 例えば 英語などが ある 教師可変教科種は複数の教師が受け持つことができ 特定の教師が特定のクラスの授業を受け持つように指定され ない
教師可変型教科は授業時間数をコマ 受講するクラスを クラス クラスが所属する学科 使用する教室タイプとその使 用数 教科種の教師を必要とする数を要素としてもつ
時間割行列の作成
本研究では ひとつの解を各教科の授業開始時間帯の組合せ であらわす 解が決定すると以下の操作をおこない各時間帯に おこなわれる授業数を要素とする時間割行列を作成する
一般教科の場合
一般教科 の授業開始時間が 曜日時間帯と決定すると その教科の構成要素である 教師 クラス の時間割行列
の 行目 列目から 列目ま でを同じく教室タイプ の時間割行列の 行 目 列目から 列目まで を足す 必修科目の 場合学科の時間割行列
の 行目列目から
まで足す
教師可変型教科の場合
教師可変型教科 の授業開始時間が 曜日 時間帯と決定 すると 教科種 と 教室タイプ の時間割行 列
の 行 列 に をクラス の時間 割行列 の 行目 列目にを足す 必修科目の場合学科 の時間割行列
の 行目 列目に足す 一般教科 教師可変型教科の全教科について以上の操作をお こなうことで全ての教師 全てのクラス 全ての教室タイプ 全ての学科の時間割行列を作成する 作成する様子をあらわ したものが図である
作成された時間割行列より各違反数を算出し 時間割の優劣 を評価する
以下教師の時間割行列の例を示す
目的関数の定義
ソフト制約にはその重要度に応じた重みをハード制約には 十分大きい重みをあたえ 各々の違反数に重みを掛け 足し合 わせた目的関数 を最小化する制約緩和問題として解く 以下 に関数 と違反内容の対応を記述する
最小化
教師全体の授業の重複数
クラス全体の授業の重複数
超過して必要されている教室の数
教師全体の授業間の空き時間数
クラス全体の授業間の空き時間数
クラス全体が月曜から土曜の限土曜日に授業が配 置されている数
教師全体で最低基準を満たしていない違反点数
クラス全体で最低基準を満たしていない違反点数
教師可変型教科全体で教師の不足数
全学科に関して低学年の必修科目と高学年の必修科目 の授業時間が重なっている数
領域の定義
近傍の定義
解 の近傍解 £ を以下のように設定する
つの教科の配置時間帯が異なる時間割の解 例
解
教科
曜日
時間帯
解
教科
曜日
時間帯
解
教科
曜日
時間帯
と に関して教科 の授業開始時間が異なり 他の 時間帯は同じ値をもっているとすると と は近傍解で ある 同じようにと は 教科の授業開始時間が 異なり 他の時間帯に関して同じ値をもっているとすると近 傍解となる と はつの教科に関して授業開始時間が 異なるため近傍解ではない
実行不可能解
実行不可能解を種類に分類し定義する 複数教科の組合せによる実効不可能解
教師が重複して授業をうけもっているクラスが重複して授 業を受ける教室の数を超過して授業がおこなわれるような状 態には複数の教科が組み合さることでなる
このような状態の時間割は 実際に実行することができない ので実行不可能解となる ただし 重複した状態では実行不可 能だが重複の原因となっている教科を別の時間帯に移動させ ることで実行可能解となる
このような状態の時間割を複数教科の組合せによる実行不可 能解と定義する
単一教科による実行不可能解
受け持つ教師の都合が悪い時間帯に教科が配置されている状 態の時間割では 授業をおこなうことができず実行不可能解と なる 他には 連続時間授業の教科を開始時間限とした場 合学校は限までしかないので 一時限分授業をおこなうこ とができない よって これらのような時間帯には配置するこ とができない
教師の都合または教科が連続授業であることにより 実行不 可能解になるような解を 単一教科による実行不可能解と定義 する
解の要素のとりうる範囲
一般教科を受け持つ教師 の都合をあらわす時間割行 列を と定義する の要素は変数で教 師の都合が良い時間帯は悪い時間帯はで表す
教科 が配置可能な時間帯は受け持つ教師が全て都合がよ く且つ授業終了が限以前になる時間帯である
¾
Ú
を要素としてもつ時間割行列 は教科 の配置 可能な時間帯を表す時間割行列である 要素がの時間帯が解
のとりうる範囲となる
タブー探索法を用いた解法
タブー探索法
タブー探索法は近傍探索による遷移を繰り返す 現在の解か ら近似解に到達できる仮定のもとでおこなうヒューリスティッ ク手法である 近傍移動を繰り返すことで解の更新をおこなっ ていくがタブーとなる状態行動を記憶しそれを禁止するこ とでループして探索することを防ぐ
探索領域
本研究では実行可能解と 複数教科の組合せによる実行不可 能解で探索遷移をおこなう
一般的に問題 の近傍全体 が大きすぎて全て探索す ることが困難な場合は 近傍の候補部分だけを探索する 探索 する近傍のサイズは 解の質と それを得るための処理量との トレードオフになる 近傍探索は全ての教科に関しておこなう
探索終了条件は 規定探索回数の探索完了するか
を満たしながら規定回数の更新が無い場合とする
現在の解と近傍解の差分値
本研究では 近傍探索時の近傍解の評価を現在解と近傍解の 目的関数値の差分値 でおこなう の値が大きい解ほど 改善される 教科数教師数 クラス数程度の問題 を最適化する問題の近傍解を評価するにあたり 差分値を用い て評価する場合は解全体の評価をおこなう場合に比べ約 分のの計算量で済む
提案手法
本研究では 遷移した教科とそのの移動を記録する長期記憶 タブーリストと 遷移した教科のみを記録する短期記憶タブー リストの種類用意する 長期記憶は ステップ 短期記憶 はステップの間記憶し続けその間記憶されている移動を 禁止することで探索中のループを防ぐ 近傍探索により得ら れた目的関数の差分値が大きい移動を上位選び出しタブーリ ストと照らし合わせリストに無い場合はその遷移を採用する リストにある場合は その教科の遷移を見送り 次点の目的関 数の差分値をもつ遷移の判定に移る リストにある場合でも 過去最良解を更新するなら遷移を許可する
複数移動
探索する近傍領域を広くとり且つ計算量を減らす手法を提 案する 一般に近傍探索により得られた近傍解のうち 採用さ れたもの以外の近傍解は全て棄却されるが本研究ではこの棄 却する近傍遷移に着目した 目的関数の差分値を比較する場合 この棄却する探索解は一定の規則を満たせば同時に複数移動す ることができる
移動を教科 の授業開始時間帯が 曜日 時間帯に移る ことと定義する 各移動の教科の要素が異なる移動の集合
の移動を同時におこなった解と現在解との目 的関数の差分値 は 各移動の目的関数の差分値を足し合 わせたものと等しくなり
¾
となる
よって! の移動終了後の目的関数の値は以下のようになる
¾
近傍探索を目的関数の差分値でおこなうことで 回の近傍 探索の中から複数の移動をおこなうことができる 以下 回 の近傍探索でつの移動をおこなう手法を手法複数移動さ せる提案手法を手法と記述する
移動可能である教科を選択する手順
近傍探索毎に各移動済みリストの初期化をおこなう
近傍探索により得られた目的関数の差分値リストの最上 位の差分値 の値が正だった場合" に
"に "に "に# を追加し移動リスト$ %に移動内容を追加する
が大きい方から順番に 各移動済みリストと移動の 構成要素を照らし合わせる
" & " & " &
" & だった場合各移動済みリストに要素 を追加する 移動リスト$ % に移動内容を追加する
の操作をの間続ける
計算機実験
年度中央大学理工学部を対象とし一般教科を教える教 師数クラス数 教室の種類種類一般教科教 師可変型教科 その他の教科 のべ授業時限のデー タを用いて手法と手法の比較をおこなった 本実験では 初期解を全ての教科の授業開始時間が月曜限の状態とした
章で述べた制約条件に対応する重みは以下のように設定した
表実験結果
最良解に辿りついたステップ
初期解
手法
手法
実際の時間割
図年度情報工学科年の時間割
図 本手法で得られた情報工学科年の時間割
考察
結果は表のようになった 回の近傍探索でつの解の更 新をおこなう手法に比べ 回の近傍探索で複数の解の更新 をおこなう手法 は最良解にたどりつくまでのステップ数に 関して手法の半分以下となった 全ての教科の授業開始時間 が月曜限という状態の初期解から探索をはじめても手法 手法により得られた解の目的関数値はともに年現在使 われている時間割の目的関数値よりも低いものとなった 図 は本実験の手法による探索における各ステップでの移動教 科数である 初期解が悪い状態から探索を開始しても 近傍を 広く設定したため手法手法ともに実行可能解を得るこ とができた
本手法により得られた結果の一部が図 である 良い時間割 の基準を全て考慮に入れることは難しい 本研究で設定した制 約条件その違反数に課す重みが適切なものである保証がない ため得られた結果が必ずしも現在の時間割よりもよいものに なっているとは言えない しかし 今現在中央大学理工学部の 時間割は人の担当者により ヶ月間かけて製作しているこ とを考えると 本手法を用いて自動的に短い時間で完成度の高 い時間割を作成することは大変有意義であるといえる
計算実験には !" #$%&' メモリ ()コンパイラに*+, -+*+のマシンを用 いた 計算時間は手法が最適解に達するまで秒 手法
は 秒かかった
図手法と手法の探索比較
図手法の各探索における移動する教科数
謝辞
本研究を進めるにあたり ご多忙の中熱心に御指導 御指摘 をして頂いた田口東教授には心から感謝致します また 大学
年生からの年間御指導 御助言頂いた伊理正夫教授には心 から感謝致します
参考文献
平田敦 極値理論を用いたメタヒューリスティック諸法 の性能評価 中央大学大学院理工学研究科情報工学専攻
年度修士論文伊理研究室
柳浦睦憲 茨木俊秀 著 伊理正夫編 組合せ最適化 メタ戦略を中心として朝倉書店東京
吉川昌澄学校時間割り自動編成 オペレーションズ・リ サーチ学会誌第巻第号..
/ )#01 23 /04 /35
, 6#0 7 5
87$.# 06 6 .09 0) 0!
