大学時間割編成モデルの研究
M2010MM014 伊藤美登
指導教員：佐々木美裕
改良点 5: 同じ曜日時限に開講しないことが望ましい科目を考慮した自動編成を行う．
大学の時間割編成は，手作業で行われることが多く，非時間割編成を行ううえで，同じ曜日時限に開講でき常に手間と時間がかかる業務である．この業務の改善のない科目の配置に配慮することは必要不可欠である．
ために，時間割作成をテーマとした時間割作成国際コン
さらに学生にとって履修しやすい時間割編成を行うペティション（International Timetabling Competition
ためには，同じ曜日時限に開講しないことが望まし2007）が開催されるなど，時間割編成システムの開発にい科目にも配慮すべきである．このような科目が同注目が集まっている．
じ曜日時限に開講された場合はペナルティを与え，そ近年，堀尾ら [1, 2] ，茨木ら [3]，久保田 [4]，光部 [5]の総和を最小化するモデルとして定式化する．このによって時間割編成システムの開発がすすめられている．
改良により，学生にとって履修しやすい時間割編成
光部 [5] は，IBM ILOG CPLEX と VBA を用いて時間割が可能となる．
を自動で作成するシステムを開発し，2011 年度南山大学
情報理工学部の春学期と秋学期の実データを用いて，実 3 データ作成用的な計算時間で時間割編成した結果を示している．
本システムの入力データを作成する際には，「グループ
本研究では，光部 [5] の時間割自動編成システムに改の設定」，「科目の分類」，「教員グループの設定」，「担当授良を加え，汎用性の高い時間割自動編成システムを試作業数の設定」を行う必要がある．以下では，その定義にする．
ついて簡単に説明する．

1

はじめに

2モデルの改良提案モデルでは，光部 [5] のモデルに改良を加える (改良の一部は，伊藤ら [6] に記載されている)．主な改良点は以下の 5 点である．
改良点 1: 授業担当者の決定を行う．
既存のモデルでは，各科目の授業担当者を指定しておく必要があった．本モデルでは，科目ごとに指定された複数の授業担当可能教員の中から自動的に担当者を決定する．
改良点 2: 担当者変動科目 (開講曜日時限指定，担当者のみ自動割り当て) に対応する．
既存のモデルでは，開講曜日時限を決定する時間割編成問題を対象としていた．この改良により，開講曜日時限のみを決定する場合，授業担当者のみを決定する場合，双方を決定する場合のいずれにも対応できるようにする．
改良点 3: 教員の担当授業数のバランスを考慮した自動編成を行う．
授業担当者の自動割り当てを行うためには，各教員の担当授業数を考慮する必要がある．本モデルでは，担当授業数の上下限制約を設けることによってバランスのとれた時間割編成を行う．
改良点 4: オムニバス科目 (1 つの授業を複数の教員で担当する科目) を自動編成の対象科目とする．
本モデルでは，オムニバス科目を構成する各分野の授業担当可能教員を指定し，その中から担当者を決定することが可能である．また，オムニバス科目を担当した場合の担当授業数を厳密に計算する．既存のモデルでオムニバス科目を自動編成の対象としているものはない．

3.1

グループの設定グループとは科目の集合であり，グループの設定とは各科目をグループに分けることを指す．ただし，1 つの科目が複数のグループに含まれることもある．提案するモデルを用いて自動編成を行う際，グループを適切に設定することで時間割編成の複雑な制約を簡単に記述することができる．
提案するモデルでは，2 種類のグループの設定を行う．
1 つが「同じ曜日時限に開講できない科目のグループ」であり，もう 1 つが「同じ曜日時限に開講しないことが望ましい科目のグループ」である．すなわち，ある「同じ曜日時限に開講できない科目のグループ」に含まれる科目は，いずれも同じ曜日時限に開講することが許されない．また，ある「同じ曜日時限に開講しないことが望ましい科目のグループ」に含まれる科目は，いずれも同じ曜日時限に開講しないように時間割編成することが望まれる．前者はハード制約，後者はソフト制約に対応する．
図 1 にグループ設定の例を示す．グループ A1 ，A2 は

図 1 グループ設定の例

「同じ曜日時限に開講できない科目のグループ」であり，
表 2 教員グループごとの上下限値の例
それぞれ，「1 年次科目」，「2 年次科目」で構成されてい教員グループ
担当授業数 (上限値) 担当授業数 (下限値)
る．グループ B は「同じ曜日時限に開講しないことが望教員グループ
173ましい科目のグループ」であり，ここでは，A1 と A2 の教員グループ 263和集合で設定されている．これは，2 年次に 1 年次科目教員グループ 353を再履修する可能性を想定してグループ設定をしている
例である．A1 に含まれる科目同士および A2 に含まれる科目同士は，ハード制約により同じ曜日時限には開講さ は，週に 90 分の授業を半期で 15 回行う場合に担当授業れないので，実際には，A1 に含まれる任意の科目と A2 数を 1 とする．したがって，1 つの授業に複数の分野がに含まれる任意の科目が同じ曜日時限に開講されないよ 含まれ，それぞれ異なる教員が担当するオムニバス科目の担当授業数は，実際に授業を行った回数によって変化うに配慮すれば十分である．
する．
3.2 科目の分類
表 3 は，オムニバス科目の担当授業数の計算例を示し
開講曜日時限および授業担当教員が指定されているか ている．情報システム数理実習は，OR，統計，数学の 3
どうかによって，各科目を「定置科目」，「変動科目」，「担 つの分野に分かれている．分野ごとに授業担当可能教員
当者変動科目」の 3 つに分類する (表 1)．
が指定されており，この中から，分野ごとに，1 人ずつ選ばれる．1 つの分野につき 5 回の授業を行うため，この授業の 1 分野を担当した場合の担当授業数は 5/15=0.333...
表 1 科目の分類となる．
開講曜日時限 授業担当教員
定置科目
変動科目
担当者変動科目

指定
可変
指定

指定
可変
可変

表 3 南山大学におけるオムニバス科目の例
科目名

分野

授業担当可能教員

担当教員数

担当授業数

情報システム数理実習
情報システム数理実習
情報システム数理実習

OR
統計数学

笹山，鈴村，三村
松田，木村，白木小藤，佐々木1
1
10.3330.333
0.333「定置科目」は，開講曜日時限，授業担当教員ともに指定されている科目であり，時間割自動編成対象の科目ではない．
「変動科目」は，開講曜日時限，授業担当教員ともに自動編成する科目である．
「担当者変動科目」は，開4 モデルの定式化
講曜日時限は指定されており，授業担当教員のみ自動編
4.1 記号の定義
成で決定する科目である．
1 つの科目に対して担当可能な教員が複数いる場合，候時間割編成問題を定式化するにあたり，以下の記号を補者の中から実際に担当する教員を選ぶことになる．こ 定義する．のような科目は，「変動科目」あるいは「担当者変動科目」
定数に分類して担当可能教員を複数指定することにより，シ
S： 科目の集合．
ステムで自動的に担当者を決めることができる．
V： 変動科目の集合 (V ⊂ S)．
一方，担当教員は指定されているが開講曜日時限は自D： 定置科目の集合 (D ⊂ S)．
動編成したい科目については，「変動科目」に分類し，授Q： 担当者変動科目の集合 (Q ⊂ S)．
業担当可能教員を指定された教員のみとすることで対応
J： 同じ曜日時限に開講できない科目のグループの集可能である．
合．
I：
同じ曜日時限に開講しないことが望ましい科目の3.3 教員グループの設定
グループの集合．
時間割編成作業を行う際，担当授業数のバランスを考慮
Sj：グループ j ∈ J に含まれるの科目の集合した授業担当者の割り当てを行うことが必要となる．こ(Sj ⊂ S)．の作業を自動化するため，各教員の担当授業数に制約を
Vj： グループ j ∈ J に含まれる変動科目の集合設ける．
(Vj = Sj ∩ V )．
ここでは，教員グループを作成し，この教員グループ
Dj：グループ j ∈ J に含まれる定置科目の集合に担当授業数の制約を設ける．表 2 は，それぞれの教員(Dj = Sj ∩ D)．
グループにごとに設けた上下限値の例を示している．例
Qj：グループ j ∈ J に含まれる担当者変動科目
えば，教員グループ 1 に属する教員は，担当授業数が 3の集合 (Qj = Sj ∩ Q)．
以上 7 以下となる．
′Si：
グループ i ∈ I に含まれるの科目の集合
3.4 担当授業数の設定(Si′ ⊂ S)．
′Vi：グループi ∈ I に含まれる変動科目の集合
各教員が担当する授業数のバランスを考慮することは，′′(V=S∩V )．
ii
時間割を編成するうえで重要な点の 1 つである．ここで4.2 定式化
Di′：グループ i ∈ I に含まれる定置科目の集合′′(Di = Si ∩ D)．
この問題は次のように定式化できる．
Q′i：グループ i ∈ I に含まれる担当者変動科目の集合∑∑ ∑∑minimize
xs1 t xs2 t(Q′i = Si′ ∩ Q)．
′′t∈Ti∈Is1 ∈Vi s2 ∈Vi \s1
W：2 時限連続科目の集合 (W ⊂ S)．
∑∑ ∑ ∑Wj：グループ j ∈ J に含まれる 2 時限連続科目の集合+
ds1 t xs2 t(Wj = Sj ∩ W )．
t∈T i∈I s1 ∈Di′ s2 ∈Vi′∑∑ ∑ ∑T： 時間帯 (開講曜日時限) の集合．
ns1 t xs2 t ,(1)+T̂： 2 時限連続科目の割り当てが可能な時間帯の集合t∈T i∈I s1 ∈Q′i s2 ∈Vi′(T̂ ⊂ T )．
s.t.
O： オムニバス科目の集合 (O ⊂ S)．
Oi：オムニバス科目 i ∈ O に含まれる分野の集合．
∑∑∑
M：複数開講科目の集合 (M ⊂ S)．
∑s∈V ∩Oi xst +s∈D∩Oi gst +s∈Q∩Oi nst+
Mi：複数開講科目 i ∈ M に含まれるクラスの集合．
|Oi |i∈O
Bs：科目 s ∈ S の担当授業数．
∑∑∑
F： 教員の集合．
xst +gst +nst ≤ rt ,t ∈ T,s∈V \Os∈D\Os∈Q\O
rt： 時間帯 t ∈ T に使用できる教室数．
(2)
es： 科目 s ∈ V ∪ Q に必要な教員数．
∑P： 教員グループの集合．
ystf ≤ asf ,s ∈ V ∪ Q\W, f ∈ F, (3)up：教員グループ p ∈ P の担当授業数の上限．
t∈T∑
lp： 教員グループ p ∈ P の担当授業数の下限．
ystf ≤ 2asf ,s ∈ W, f ∈ F, (4){1： 教員f ∈ F が科目s ∈ V ∪ Q を担当できる，t∈Tasf =∑0： 上記以外．
ystf + ctf ≤ btf ,t ∈ T, f ∈ F, (5)s∈V∪Q
1：教員
f∈
Fが時間帯t∈Tに授業を担当
∑btf =できる，
es xst =ystf ,s ∈ V, t ∈ T, (6) 0： 上記以外．
f ∈F

∑

es nst =ystf ,s ∈ Q, t ∈ T, (7) 1： 教員f ∈ F が時間帯t ∈ T に定置科目を担
ctf =当する，f ∈F
∑ 0： 上記以外．
xst = 1,s ∈ V \W, (8){t∈T
1： 時間帯t ∈ T に定置科目s ∈ D を開講する，∑gst =0： 上記以外．
xst = 2,s ∈ W, (9){t∈T
1： 時間帯t ∈ T に変動科目s ∈ V を開講できる， ∑∑∑hst =xst +gst +nst ≤ 1,j ∈ J, t ∈ T, (10)0： 上記以外．
s∈Vjs∈Djs∈Qj 1： 時間帯t ∈ T に担当者変動科目s ∈ Q を開講
xst = xs(t+1) ,s ∈ W, t ∈ T̂ , (11)nst =する，
 0： 上記以外．
ystf = ys(t+1)f ,s ∈ W, t ∈ T̂ , (12){xst ≤ hst ,s ∈ V, t ∈ T, (13)
1： 教員f ∈ F が定置科目s ∈ D を担当する，
osf =∑ ∑0： 上記以外．
mf p lp ≤ mf p (ystf ∗ Bs +{s∈V∪Qt∈T
1： 教員f ∈ F が教員グループp ∈ P に属する，∑mf p =osf ∗ Bs ) ≤ mf p up , p ∈ P, f ∈ F, (14)0： 上記以外．
決定変数{∑1：時間帯t ∈ T に変動科目s ∈ V を開講する，
0：上記以外．

f ∈Fs∈D

ys1 tf =∑f ∈F

ys2 tf ,i ∈ O, s1 , s2 ∈ Oi , t ∈ T, (15)∑∑
ys1 tf =ys2 tf , i ∈ M, s1 , s2 ∈ Mi , t ∈ T, (16)
f
∈Ff
∈F

 1：教員f ∈ F が時間帯t ∈ T に科目s ∈ V ∪ Q
ystf =を担当する，
xst ∈ {0, 1},s ∈ V, t ∈ T, (17) 0：上記以外．
ystf ∈ {0, 1},s ∈ V ∪ Q, t ∈ T, f ∈ F. (18)
 1：時間帯t ∈ T に変動科目s1 ,s2 ∈ V を開講
目的関数 (1) は，同じ曜日時限に開講しないことが望ま
ks1 s2 t =する，
 0：上記以外．
しい科目が同じ曜日時限に割り当てられた場合にペナルティを与え，その総和を最小化することを意味する．
xst =目的関数 (1) の第 1 項は，同じ曜日時限に開講しないこ しないことが望ましい科目のペアのうち，24 ペアにおいとが望ましい変動科目同士が同じ曜日時限に割り当てら て科目が同じ曜日時限に割り当てられたことを意味する．
れたときのペナルティが 1 であることを示している．同 しかしながら，グループの設定によっては，1 つのペア
様に，第 2 項は定置科目と担当者変装科目，第 3 項は変 が 2 回以上数えられる場合があるため，実際に同じ曜日動科目と担当者変動科目が同じ曜日時限に割り当てられ 時限に開講された科目のペアは 15 であった．
たときのペナルティが 1 であることを示している．
6 おわりに制約条件 (2) は，各時間帯で教室数を超える数の授業を2012 年度秋学期の科目・教員の実データを用いて本研開講することができないことを表わしている．制約条件(3)(4) は，各教員が担当可能な科目のみを担当すること 究で試作したシステムで時間割自動編成を行なった結果，を表し，制約条件 (5) は，各教員の担当できない時間帯に 学生にとって履修しやすく，また，教員にとって担当授は授業を担当しないことと，同じ時間帯に 2 つ以上の科 業数のバランスのとれた時間割作成が可能となった．
目を担当できないことを表している．制約条件 (6)(7) は， 時間割編成作業自動化のベースとなるモデルを作成し各科目に必要な教員数を割り当てることを示している．制 たが，今後は本システムの汎用化に向けて，大学全体，さ約条件 (8)(9) は，指定された時限数だけ開講することを らには他大学において，汎用的に利用できるような時間表しており，制約条件 (10) は，同じグループに含まれる 割自動編成システムへの発展が必要となる．そこで今後科目同士は同じ時間帯に開講しない制約である．制約条 の課題として２つのことを考慮しなければならない．
1 つは，教室の容量についての制約を考慮することで件 (11)(12) は，科目 s ∈ W を 2 時限割り当てることを表わしている．制約条件 (13) は，各科目は開講不可能な ある．現在南山大学瀬戸キャンパスでは，科目に教室を時間帯には開講しないことを示し，制約条件 (14) は，教 割り当てる際に，教室の容量はあまり考慮されていない．
員が担当する授業数の上下限を表わしている．制約条件 これは，各科目に対して必要な容量の教室が十分に揃っ(15) は，オムニバス科目に含まれる科目 (分野) を同じ時 ていることが理由としてあげられる．しかし他大学では，間帯に開講することを表わし，制約条件 (16) は，複数開 時間割編成の際に教室の容量を考慮しなければならなく，講科目に含まれる科目 (クラス) を同じ時間帯に開講する 時間割編成において大きな問題となっている．
もう 1 つは，同じ曜日時限に開講しないことが望ましことを表わしている．制約条件 (17)(18) は，変数の 0-1い科目に対して優先度の設定を行うことである．優先度整数制約である．
この問題は非線形計画問題であるが，新たに 0-1 変数 の設定を行うことで，特に同じ曜日時限に開講したくない科目同士の開講を優先的に避けることができる．
ks1 s2 t (s1 ∈ Vi′ , s2 ∈ Vi′ ) を導入し，目的関数をこれらの問題についても自動化することで，さらに汎∑∑ ∑∑minimize
ks1 s2 t用的な時間割自動編成システムに改良することができる．
t∈T i∈I s1 ∈Vi′ s2 ∈Vi′ \s1+∑∑ ∑ ∑t∈T+

参考文献

ds1 t xs2 ti∈I s1 ∈Di′ s2 ∈Vi′∑∑ ∑ ∑ns1 t xs2 t(19)[1] M．Horio and A．Suzuki: Application to a University Course Timetabling Problem by a General
Project Scheduler，Lecture Notes in Operations Research，Vol．8，2008，pp．266-273．

(20)[2] 堀尾正典: 汎用プロジェクトスケジューラの大学時間割問題への適用，名古屋学芸大学教養・学際編・研究
紀要第 4 号，2008，pp．61-74．

t∈T i∈I s1 ∈Q′i s2 ∈Vi′と書きかえ，さらに制約条件

xs1 t + xs2 t − 1 ≤ ks1 s2 t ,ks1 s2 t ∈ {0, 1},i ∈ I, s1 , s2 ∈ Vi′ , t ∈ T,i ∈ I, s1 , s2 ∈ Vi′ , t ∈ T.

(21)[3] 茨木俊秀，熱田光紀，野々部宏司: 汎用ソルバによるを追加することにより，等価な線形計画問題が得られる．
時間割作成−国際コンペティション ITC2007 に参加
計算実験で用いた定式化は，して−， スケジューリング・シンポジウム 2008 講演
目的関数 (19)
論文集，2008，pp．173-176．
制約条件 (2)‐(18)，(20)‐(21)[4] 久保田敬: 時間割編成問題に対する近似解放の研究，である．
中央大学大学院理工学研究科情報工学専攻 2003 年度
修士論文，2004．
5 計算結果2012 年度情報理工学部秋学期の時間割編成実データを [5] 光部翔太: 大学の時間割自動編成システムの研究，南山大学大学院数理情報研究科 2010 年度修士論文，2011．
使用し，IBM ILOG CPLEX Optimization Studio 12.2を用いて時間割の自動編成を行った．使用した計算機の [6] 伊藤美登，光部翔太，佐々木美裕，鈴木敦夫，伏見正CPU は Intel Core2 Duo(2.53GHz)，OS は Windows7，
則: 大学授業時間割の自動編成システムについて，日搭載しているメモリは 2GB である．問題に含まれる変数
本オぺレーションズ・リサーチ学会 2011 年秋季研究の数は約 54,000，制約式の数は約 48,000 である．計算時
発表会，2011，pp. 152-153.
間は約 1 秒であり，最適値は 24 となった．これは，科目が同じ曜日時限に開講されたとき，同じ曜日時限に開講