大学時間割編成モデルの改良
2009SE090 伊藤喜紀
指導教員：佐々木美裕
た CPLEX の 計 算 時 間 が 約 26 分 で あ る.

はじめに

1

計算環境

は, CPU:Intel(R)Core(TM)i7-3770K CPU @ 3.50GHz

大学の時間割編成作業の多くは手動で行われている. こ

3.50GHz, OS; Windows7, メモリは 16GB である.の作業の部分的または全体の処理を自動化させたシステム

様々な大学の時間割作成に対応するためにも計算時間のが, 時間割編成システムである. 伊藤 [1] のモデル (以下既短縮が必要となる. よって目的関数や制約に変更を加えて,存モデル) は IBM ILOG CPLEX と VBA を用いた時間計算時間の短縮を行う.

割編成システムであり, 計算実験のため 2012 年度南山大
学情報理工学部の春学期と秋学期の実データを使用してい科目同士のペナルティテーブル

3.2

る. 本研究では伊藤 [1] のモデルを引き継ぎ, 様々な大学の既存モデルの同じ曜日時限に開講しないことが望ましい

データに対応できるより汎用性の高いシステムの完成を目

科目のグループ設定では, 実際に計算結果で出力される, 同指す. 既存システムの計算時間の問題や, 科目の開講時限じ曜日時限に開講しないことが望ましい科目同士の重複結のペナルティ設定などに変更の余地があり, その改善に取果をあまり考慮しない設定になっていた.

り組んだ.

その問題を解決するために, 新たに本研究で科目同士の2既存モデルの概要

2.1科目の分類ペナルティテーブルを作成する. 2 つの科目が, 同じ曜日時限に開講しないことが望ましい科目同士であった時, ペナルティである 1 を, そうでないなら 0 を与える. このペ

本節でモデルで使用する科目の分類について簡単に説明

ナルティテーブルを作成することで, 同じ曜日時限に開講を行う. それぞれの科目を, 表 1 のように「定置科目」「変しないことが望ましい科目同士の重複数を考慮したペナル動科目」「担当者変動科目」の 3 つのタイプに分類する.

ティ設定となる.

表 1 科目の分類不要な変数の削除

3.3

開講時限

担当教員

既存モデルでは, 時間割表を作成するためだけに計算と定置科目

指定

指定

は全く関係のない変数を 2 種類定義し, その決定変数を扱

変動科目

可変

可変

うために制約式内に制約を加えている.

担当者変動科目

指定

可変

これらの最適化に不要な変数はモデルから削除し, 後処理で対応する. 本研究で使用している情報理工学部の実ある科目が開講時限と担当教員の 2 つの項目に対し, 可変であるか否かで上記のように分類している.

2.2

科目のグループ化

時間割編成を行ううえで, 同じ曜日時限に開講できない科目同士の開講曜日時限を考慮することは必要であり, さらに同じ曜日時限に開講しないことが望ましい科目同士の開講曜日時限も考慮したほうが良い.
既存モデルでは, 2 種類のグループの設定することで, これらの科目同士の開講曜日時限の制約を扱っている. 1 つが「同じ曜日時限に開講できない科目のグループ」であり,もう 1 つが「同じ曜日時限に開講しないことが望ましい科目のグループ」である.

3

改良点

3.1

計算時間の短縮

既存モデルでは, 秋学期データを用いた CPLEX(IBMILOG CPLEX Optimization Studio 12.4) の 計 算 時
間 が 約 1 秒 で あ る の に 対 し て, 春 学 期 デ ー タ を 用 い

データでは, 約 4〜5 ％の変数が削除できた.

4モデルの定式化
問題を定式化するにあたり, 以下の記号を定義する.

S : 科目の集合
V : 変動科目の集合 (V ⊂ S)
D : 定置科目の集合 (D ⊂ S)
Q : 担当者変動科目の集合 (Q ⊂ S)
Ps1 s2 : 科目 s1 ∈ V ∪ D ∪ Q と変動科目 s2 ∈ V が同じ曜
日時限に開講された時のペナルティ

T : 開講時限の集合{
1 : 時間帯 t∈T に定置科目 s∈D を開講する
gst =0 : 上記以外{
1 : 時間帯 t∈T に担当者変動科目 s∈Q を開講する
nst =0 : 上記以外
以下は決定変数である{
1 : 時間帯 t∈T に変動科目 s∈V を開講する

xst =0 : 上記以外
VVP ∈Rその他の定数と変数については, 割愛する.
以下, 目的関数と制約条件は既存モデルとの差異がある

6

考察
既存モデルでの春学期の計算時間が長くなってしまう点部分のみ記述する.の理由としては, 同じ曜日時限に開講しないことが望ましい変動科目同士の重複の割合が多くなっている点があげら

Minimize
VVP +

∑ ∑ ∑

れる. 開講時限と担当教員の両方が可変である変動科目同Ps1 s2 gs1 t xs2 t士の重複の割合が多くなっていることが, 春学期データのs1 ∈D s2 ∈V t∈T+∑ ∑ ∑Ps1 s2 ns1 t xs2 t(1)

s1 ∈Q s2 ∈V t∈Ts.t.
∑ ∑計算時間を膨大にしている要因ではないかと考えられる.
また, 既存モデルの秋学期データの最適値は 24 であり,実際の同じ曜日時限に開講しないことが望ましい科目の重複数は 15 となっていた. 本研究で導きだした秋学期の同Ps1 s2 xxs1 s2 t ≤ V V P,t ∈ T (2)じ曜日時限に開講しないことが望ましい科目の重複数は目的関数 (1) の第 1 項は, 各曜日時限における, 同じ曜日時限に開講しないことが望ましい変動科目同士が同じ曜日13 であるので結果が改善されている. これは本モデルのペナルティの設定が, 実際の同じ曜日時限に開講しないことが望ましい科目同士の重複数を考慮し, 重複数に関しても時限に割り当てられた場合のペナルティの最大値を示して計算結果を見ればすぐに判断できるよう変更したためであいる. また, 第 2 項は同じ曜日時限に開講しないことが望ると考えられる.

ましい変動科目と定置科目, 第 3 項は同じ曜日時限に開講

重複数 13 という解は, 既存モデルではその解の最適値が24 以上であったために, えられていなかった.

s1 ∈V s2 ∈Vしないことが望ましい変動科目と担当者変動科目が同じ曜日時限に割り当てられたときのペナルティの総和を示している.
制約条件 (2) は, 各曜日時限における, 同じ曜日時限に開7

おわりに講しないことが望ましい変動科目同士が同じ曜日時限に割計算時間の短縮や科目のペナルティの設定, 既存モデルり当てられた場合のペナルティの合計が V V P 以下になるの実行結果より良い解がえられたことは本研究での改善でことを示している.

ある. また, 同じ曜日時限に開講しないことが望ましい科
目同士のペナルティの重みを考慮できる時間割編成は, 南2012 年度情報理工学部実データの実行結果

山大学の時間割編成作業だけでなく, 他大学でも必要とさ2012 年度情報理工学部春学期と秋学期の時間割編成実データを使用し, IBM ILOG CPLEX Optimization Studio 12.4 を用いて時間割の自動編成を行った. 使用した計算機の計算環境は CPU:Intel(R)Core(TM)i7-3770K CPU@ 3.50GHz 3.50GHz, OS;Windows7, メモリは 16GB である. 問題に含まれる変数の数は双方ともに約 55,000, 制
約式の数は約 23,000 となり, 教員数は 44 名, 科目数はそれ
ぞれ変動科目が 30, 定置科目が 135 前後, 担当者変動科目が 20 前後となっている.

本モデルに残る問題点としては, 1 つは, 教室の容量制5れる編成要素の 1 つであると考えられる.
約を設けることである. 既存モデルでは計算時間の問題があったために, 新しく教室制約を加えることが難しくなっていた. その問題が解決した本研究では, 新たに変数を加える, このモデルを 2 段階の問題にするなどして教室制約を加えることが考えられる.
もう 1 つは春秋データを 1 度の計算で処理するシステムに改良することである. 現在のモデルは春学期データと秋学期データを取り扱う際に, 別々のデータとして, 計算も計算時間は春学期データと秋学期データに大きな差異は別々に行っている. これを 1 つのデータとして, 計算結果なく, 共に約 2 秒である. 最適値や V V P の値, 同じ曜日時も同時に出せるように改善できれば, 時間割編成者にとっ限に開講しないことが望ましい科目同士の重複数を表 2 にて, 時間割編成システムが使いやすいものになる.

記載する.

以上 2 点を大まかな改善目標として取り組み, より使いやすく, 汎用性の高い時間割編成システムを完成させることが今後の課題となる.

表 2 計算結果

春学期
秋学期

最適値

V V P の値

重複数21012813

それぞれに差異があるのは, V V P が各曜日時限における同じ曜日時限に開講しないことが望ましい変動科目同士のペナルティの最大値を示しているためである.

参考文献[1] 伊藤美登: 大学の時間割自動編成モデルの研究, 南山大学大学院数理情報研究科 2011 年度修士論文, 2012.