大学の定期試験時間割編成モデルの研究
M2012MM032 小野内雄一
指導教員：佐々木美裕

1

はじめに大学の定期試験時間割を作成する際には, 定められた試
験期間内に試験を実施するすべての科目を割り当て, 受験する全学生をはじめ, 試験監督を行う教員および使用する教室など, 同じ曜日時限に重複することがないように注意する必要がある. 試験時間割を大学職員の手作業で作成する場合, 膨大な時間がかかる. さらに, 近年, 試験期間が短縮されたことにより制約が厳しくなり, 手作業で時間割を作成することがますます困難になっている.
大学における時間割編成の関連研究として, 大学の通常講義の時間割編成モデルを扱ったものが挙げられる [1, 2,6]. 一方, MaCollun ら [3], 小野内ら [4], 田原 [5] は, 定期試験時間割編成のモデル化と解法について研究している.
しかしながら, 実用的な定期試験の時間割編成モデルについて, 研究が進んでいないのが現状である. 本研究は, 小野内ら [4] のモデルの改良版を提案し, 実データを用いた計算実験を行う.

2

定期試験時間割編成の現状

ここでは, 定期試験時間割編成の現状について, 南山大学を例として紹介する.

2.1

時間割編成の手順

定期試験時間割編成は大学職員の手作業で行っており,編成作業をする前に, 各科目の担当教員に試験を実施するかどうかを調査する. その後, 各科目に必要な試験室数を決定する (作業段階 1). 南山大学では試験監督者が 1 人で監督できる人数を 80 名程度としており, 1 室あたりの受験者数が 80 名以下となるように各科目に必要となる試験室数を決定する. したがって, 受講者が 80 名を超える科目は複数の教室で試験を実施する. 次に, 各科目の試験を実施する曜日時限の仮決定をする (作業段階 2). 最後に,同じ曜日時限に試験が重複している学生がいないかを確認する (作業段階 3). 全ての科目において試験を実施する
曜日時限が決定するまで作業段階 2 と作業段階 3 を繰り返す.

2.3

試験室は, 受験者数に合った収容人数の教室に割り当てること, すなわち, 受験者数の少ない科目にはなるべく収容人数の小さい教室を割り当てることが望ましい. さらに, 同じ科目を複数教室で試験を実施する場合, 隣どうしの教室や近くの教室に割り当てることが望ましい.

2.4

試験監督の割当

試験監督には, 主監督と応援監督の 2 種類がある. 科目担当教員が試験監督を行う場合, 主監督と呼び, 科目担当教員ではない教員が試験監督を行う場合, 応援監督と呼ぶ. 現在, 教員が試験監督を行う科目数をなるべく均等にするように時間割を決定している. ただし, 役職のある教員と非常勤講師は主監督のみを行う.
現在, 南山大学瀬戸キャンパスには, 総合政策学部と情報理工学部の 2 学部が存在し, 各教員が試験監督を行う科
目の種類は, 各々が所属している学部の科目および共通教育科目の 2 種類である.

時間割編成上の問題点

受験者の混乱を防ぎ, 円滑に定期試験を実施するためには, 各科目の試験は通常の講義時間割と同じ曜日時限に実施することが望ましい. しかしながら, 同じ講義を複数クラスに分けて異なる曜日時限に開講し, 同一試験問題で試験を実施する科目は, 原則に従った試験時間割の決定が難しい. この場合, 通常講義が開講されない土曜日や平日の5 限に試験を実施することが多いが, 教職員および学生の負担が多く, できる限り平日の 4 限までに試験を実施することが望まれている.

3

定期試験時間割編成モデルの定式化

3.1

問題の説明

本研究では, 2.1 節で説明した作業段階 2 から作業段階
3 にあたる各科目の試験を実施する曜日時限, 試験室, 試験監督者を決定する問題を 2 段階に分けて定式化する.
はじめに, 第 1 段階において, 科目の試験を実施する曜日時限と試験室を決定し, 第 2 段階において試験監督者を割り当て, 定期試験の時間割を作成する.
第 1 段階の問題は, できる限り講義時間割に近い定期試
験時間割を作成するために, 試験が講義時間割と異なる曜日時限に割り当てられた場合はペナルティを課し, その総和を最小化する問題として定式化する. その際, 試験室を仮決定をした後, 曜日時限ごとで試験室間の距離が小さくなるように再割当し, 試験室を決定する.
第 2 段階の問題は, 各教員が試験監督を行う日数を最小化する目的関数を導入し, 各教員に割り当てられる試験監督の回数が均等になるような試験監督の割当を求める.

3.2
2.2

試験室の割当記号の定義

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

D : 試験日の添字集合
T : 試験を実施する曜日時限の添字集合
E : 試験を実施する科目の添字集合
U : 教員の添字集合
L : 試験室として使用可能な教室の添字集合
Td : 試験日 d ∈ D に試験を実施する曜日時限の集合(Td ⊂ T )Et : 曜日時限 t ∈ T に試験を実施する科目の集合

3.3

第 1 段階第 1 段階では, はじめに, 各科目の受験者数と試験室数を考慮し, 試験を実施する曜日時限を決定し, 試験室を仮決定する. 続いて, 2.3 節で説明した試験室の割当を実現するために, 各科目の試験室における収容人数の総和と複数教室で試験を実施する科目の試験室間の距離を最小化する問題を解く.

wti + wtj ≤ bij + 1,
∑wte = 1,t ∈ T, i ∈ E, j ∈ E,

(3)e ∈ E,(4)fl xtel ≥ me wte ,t ∈ T, e ∈ E,

(5)xtel ≤ 1,t ∈ T, l ∈ L,(6)xtel = he wte ,t ∈ T, e ∈ E,(7)xtel ≤ kel ,e ∈ E, l ∈ L,(8)wte = {0, 1},t ∈ T, e ∈ E,(9)xtel = {0, 1},t ∈ T, e ∈ E, l ∈ L. (10)

t∈T

∑l∈L

∑

試験を実施する曜日時限の決定と試験室の仮決定e∈E

はじめに, 試験を実施する曜日時限の決定と試験室を仮決定する問題で用いる記号を定義する.


 1 : 教員 u ∈ U は曜日時限 t ∈ T に試験監督
ptu =を行うことが可能である
 0 : 上記以外

 1 : 教員 u ∈ U は科目 e ∈ E の科目担当教
reu =員である
 0 : 上記以外

 1 : 科目 i ∈ E と科目 j ∈ E は同時に試験を
bij =実施できる
 0 : 上記以外

 1 : 科目 e ∈ E は教室 l ∈ L を試験室としてkel =使用できる
 0 : 上記以外
me : 科目 e ∈ E の試験を受ける人数
he : 科目 e ∈ E の試験で使用する教室数
fl : 教室 l ∈ L の収容人数
cte : 科目 e ∈ E の試験が曜日時限 t ∈ T に割り当てられた時のペナルティbij は, いずれの学生にとっても同じ曜日時限に 2 つ以上の試験が重ならないような時間割を作成するうえで重要な役割を果たす. 科目 i ∈ E と科目 j ∈ E を両方履修している学生が 1 人でもいる場合は, これらの科目の試験を同時に実施することはできない. 逆に, そのような学生が 1 人もいない場合は, 同時に試験を実施することが可能である. この規則に従って, 学生の履修情報より bij を作成する.
次に, 以下の決定変数を定義する.
 1 : 科目 e ∈ E の試験を曜日時限 t ∈ T に実
wte =施する 0 : 上記以外

 1 : 科目 e ∈ E の試験を曜日時限 t ∈ T にxtel =試験室 l ∈ L で実施する
 0 : 上記以外以上の記号を用いると, 試験を実施する曜日時限の決定と試験室を仮決定する問題は次のように定式化できる.

Minimize∑∑cte wte

(1)t∈T e∈Esubject towte + reu ≤ ptu + 1,t ∈ T, e ∈ E, u ∈ U,∑l∈L∑t∈T

目的関数 (1) は, ペナルティの総和を表す. 式 (2) は, 各科目の試験は科目担当教員の都合の良い曜日時限に実施することを表す. 式 (3) は, 各学生は同時に複数の科目の試験を受験することができないことを表す. 式 (4) は, 各科目は 1 回ずつ試験を実施することを表す. 式 (5) は, 各科目の試験において受験者数は使用する試験室の総収容人数以下であることを表す. 式 (6) は, 1 室で同時に 2 科目以上の試験を実施できないことを表す. 式 (7) は, 各科目の試験に必要な数の試験室を割り当てることを表す. 式(8) は, 各科目の試験は使用できる試験室で実施することを表す. 式 (9)(10) は, 変数は 0-1 変数であることを表す.
試験室の再割当
はじめに, 試験室の再割当問題を定式化するにあたり,以下の新しい記号を定義する. なお, 他の記号については,前述したとおりである.

δij : 教室 i ∈ L と教室 j ∈ L の距離ペナルティ
α ： 任意のパラメータ値 (α > 0)
δij は, 教室間の実際の距離を用いてもよいが, 一般的には近い教室間のペナルティは小さく, 遠い教室間のペナルティは大きく設定すればどのような値でも構わない.
また, 各科目が試験を実施する曜日時限は 3.3 節で得られた結果を使用する. したがって, 試験室の割当は, 曜日時限ごとに独立な問題として考えることができる.
次に, 以下の決定変数を定義する.
 1 : 科目 e ∈ Et の試験を試験室 l ∈ L で実施
qel =する
 0 : 上記以外

 1 : 科目 e ∈ Et の試験を試験室 i ∈ L と試
seij =
験室 j ∈ L で実施する
 0 : 上記以外
以上の記号を用いると, 曜日時限 t ∈ T における試験室の再割当問題は次のように定式化できる.

Minimize(2)α∑∑e∈Et l∈Lfl qel +∑ ∑∑e∈Et i∈L j∈Lδij seij(11)ηu : 教員 u ∈ U が試験監督を行う回数の上限

subject toe ∈ Et , i ∈ L, j ∈ L,(12)e ∈ Et ,(13)qel ≤ 1,l ∈ L,

(14)

qel = he ,e ∈ Et ,(15)qel = {0, 1},e ∈ Et , l ∈ L,(16)seij = {0, 1},e ∈ Et , i ∈ L, j ∈ L.

(17)

qei qej = seij ,∑fl qel ≥ me ,l∈L∑e∈Et∑l∈L

目的関数 (11) は, 各科目の試験室における収容人数の総和と各科目で使用する教室間に発生する距離ペナルティの総和を表す. 目的関数 (11) を最小化することにより, 受験者数にあった収容人数の試験室に割り当てることができ, また, 複数教室で試験を実施する科目の試験室間の距離を小さくすることができる. 式 (12) は, 同一試験科目,かつ, 複数教室で試験を実施する科目は, 教室 i ∈ L と教室 j ∈ L で試験を実施することを表す. 式 (13) は, 各科目の試験において受験者数は使用する試験室の総収容人数以下であることを表す. 式 (14) は, 1 室で同時に 2 科目以上の試験を実施できないことを表す. 式 (15) は, 各科目の試験に必要な数の試験室を割り当てることを表す. 式(16)(17) は, 変数は 0-1 変数であることを表す.
制約式 (12) は非線形であるが,1qei + qej − 1 ≤ seij ≤ (qei + qej ),2e ∈ Et , i ∈ L, j ∈ L. (18)と書き換えることにより, 等価な線形計画問題が得られる. 計算実験で用いた定式化は,Minimize
subject to(11)(13) − (18)

ここで, ptu と reu は, 第 1 段階で用いたものと同じである. また, wte は第 1 段階では変数であるが, ここでは第 1 段階の問題を解いて得られた最適解を定数 wte として扱うことに注意する.
次に, 以下の決定変数を定義する.


 1 : 教員 u ∈ U は試験日 d ∈ D に試験監督
vdu =を行う
 0 : 上記以外

 1 : 教員 u ∈ U は曜日時限 t ∈ T に試験監
ytu =督を行う
 0 : 上記以外

 1 : 教員 u ∈ U は科目 e ∈ E の試験監督を
zeu =行う 0 : 上記以外
以上の記号を用いて, 第 2 段階の問題を定式化すると以下の通りとなる.

∑∑Minimizevdu(19)d∈D u∈Usubject toytu ≤ vdu ,∑ytu ≥ vdu ,d ∈ D, t ∈ Td , u ∈ U,

(20)d ∈ D, u ∈ U,

(21)

ytu ≤ ptu ,t ∈ T, u ∈ U,

(22)

zeu ≥ reu ,e ∈ E, u ∈ U,(23)u ∈ U,(24)zeu = ne ,e ∈ E,

(25)

wte zeu = ytu ,t ∈ T, u ∈ U,

(26)

t∈Tdρu ≤∑∑zeu ≤ ηu ,e∈Eである.
3.4 第 2 段階

u∈U

第 2 段階では, 第 1 段階で決定した科目の時間割を用いて, 各教員が試験監督を行う回数が均等になるように試験監督者を決定する. はじめに, 第 2 段階で用いる記号を定義する.

vdu = {0, 1},d ∈ D, u ∈ U,

(27)

ytu = {0, 1},t ∈ T, u ∈ U,

(28)

zeu = {0, 1},e ∈ E, u ∈ U.

(29)


 1 : 教員 u ∈ U は曜日時限 t ∈ T に試験監督
ptu =を行うことが可能である
 0 : 上記以外

 1 : 教員 u ∈ U は科目 e ∈ E の科目担当教
reu =員である
 0 : 上記以外

 1 : 科目 e ∈ E の試験を曜日時限 t ∈ T に実wte =施する
 0 : 上記以外
ne : 科目 e ∈ E の試験に必要な試験監督者数
ρu : 教員 u ∈ U が試験監督を行う回数の下限∑e∈E

目的関数である式 (19) は, 教員が試験監督を行う日数の最小化を表す. 式 (20)(21) は, 各教員は試験監督担当日(vdu = 1 となる試験日 d ∈ D) に少なくとも 1 回は試験監督を行い, 試験監督担当日でない日は試験監督を行わないことを表す. 式 (22) は, 各教員の都合の良い曜日時限に試験監督を行うことを表す. 式 (23) は, 科目担当教員は主監督を行うことを表す. 式 (24) は, 各教員が試験監督を行う回数を公平にすることを表す. 式 (25) は, 各科目に必要な数の試験監督者を割り当てることを表す. 式 (26) は,各科目の試験監督を行う教員は, その科目の試験が行われる曜日時限に試験監督を行うことを表す. 式 (27)(28)(29)
は, 変数は 0-1 変数であることを表す.

4

実行結果

2013 年度南山大学瀬戸キャンパス春学期定期試験の実データを使用し, IBM1 ILOG1 CPLEX1 12.5 を用いて解を求めた. 使用した計算機の CPU は Intel2 Pentium2
CPU B960(2.20GHz) で, メモリは 4GB である.
はじめに, 試験を実施する曜日時限数 30, 科目数 178,教員数 147, 教室数 45 で第 1 段階の試験を実施する曜日時限と試験室を仮決定する問題を解いた.
ペナルティは, 次のように設定した. 講義時間割と同じ曜日時限に実施する場合のペナルティは 0, 同じ曜日の 5限以外に実施する場合のペナルティは 5, 同じ曜日の 5 限に実施する場合のペナルティは 10, 土曜日以外の異なる曜日に実施する場合のペナルティは 100, 異なる曜日, かつ, 土曜日に実施する場合のペナルティは 200 をそれぞれ課した.
変数の数は 245,641, 制約式の数は 2,246,998, 計算時間は 7.61 秒であった. 最適値は 180 であり, 試験を実施する科目のうち, 93.2% が講義時間割と同じ曜日時限に試験を実施する結果となった.
その後, 曜日時限ごとで試験室の再割当問題を計算した.
全ての曜日時限において試験室の再割当にかかった計算
時間は約 5 分であった. 複数教室で試験を実施するすべての科目において試験室間の距離を小さくすることができ, 隣同士の教室や, 同じフロアの教室を使用する結果となった.
次に, 試験を実施する曜日時限数 30, 科目数 119, 教員数
72 で第 2 段階の問題を解いた. 変数の数は 10,144, 制約式の数は 36,372, 計算時間は 9.5 秒, 最適値は 116 であった.
試験を 1 室で行う場合は, 科目担当者のみが試験監督 (主監督) を行い, 応援監督を必要としない. このような科目は, 第 2 段階で試験監督者割当の対象から外したため, 第1 段階の問題と比較して科目数が減少している. 同様に,担当科目以外の試験監督を行わない非常勤講師および役職のある教員を試験監督担当の対象から外したため, 第 1段階の問題と比較して教員数も減少している.
第 1 段階の実行結果と, 実際に実施された 2013 年度春学期定期試験時間割と比較した結果を表 1 に示す. 実際の試験時間割では, 同じ曜日の 5 限に試験を実施する科目が全体の 9% であったのに対し, 実行結果では 1.7% となった. さらに, 実際の試験では土曜日に試験を実施する科目が 2 つあったが, 実行結果から, 土曜日には試験を実施しなくても時間割編成が可能であることがわかった.
表 1 講義時間割と異なる曜日時限に試験を実施する科目の数の比較

同じ曜日の 5 限以外で実施する科目
同じ曜日の 5 限に実施する科目
異なる曜日に実施する科目
土曜日に実施する科目

実行
結果

実際の試験時間割

336011662

図 1 定期試験時間割編成システム

5

おわりに

本研究では, 定期試験時間割編成モデルを提案し, 2013年度春学期の定期試験時間割実データを用いて, Excel3 上で作成中のシステム (図 1) を用いて定期試験時間割編成を行った. その結果, 実際の試験に比べて, 通常の講義時間割と異なる曜日時限に実施する科目の数が少ない実用的な時間割を短時間で作成することに成功し, 学生や教職員にとって負担の少ない定期試験時間割を作成することが可能となった. また, 試験室の再割当問題は, 国際会
議で関連した分野同士のセッションをなるべく移動距離の少ない近い教室に割り当てる問題等に応用できると考える.
今後は, 作成中のシステムを実際に時間割編成担当者に使用していただき, そのフィードバックを基に, 本格的な実用化を目指す.

参考文献[1] 茨木俊秀, 熱田光紀, 野々部宏司: 汎用ソルバーによる時間割作成―国際コンペティション ITC2007 に参加して―, スケジューリング・シンポジウム 2008 講演
論文集, pp. 173-176, 2008.
[2] 伊藤美登: 大学時間割編成モデルの研究, 南山大学大学院数理情報研究科 2011 年度修士論文, 2012.
[3] B. McCollun, P. McMullan, E.K. Murke, A.J.
Parkes, R. Qu: A New Model for Automated Examination Timetabling, Annals of Operations Research,
194(1), pp. 291-315, 2012.
[4] 小野内雄一, 内垣内智子: 南山大学の定期試験時間割作成問題, 南山大学数理情報学部 2011 年度卒業論文,
2012.
[5] 田原久嗣: 大学定期試験タイムテーブリング, 成蹊大学大学院理工学研究科 2012 年度修士論文, 2013.
[6] 吉川昌澄: 学校時間割り自動編成, オペレーションズ・リサーチ, 第 46 巻, 第 9 号, pp. 461-468, 2001.

——————–
1 IBM ILOG CPLEX は, IBM Corporation の登録商標である.
2 Intel, Pentium は, Intel Corporation および子会社の米国およびその他の国における登録商標である.
3 Excel は, 米国 Microsoft Corporation の米国およびその他の国における登録商標である.