大学の時間割自動編成システムの研究
M2009MM014 光部翔太
指導教員：鈴木敦夫

1

はじめに

2

時間割編成の現状

大学の時間割編成は，一般に教職員の手作業によって本節では，時間割の自動編成を行う対象とする南山大行われ，膨大な時間を要することが多い．しかも，時間 学情報理工学部における時間割編成の現状と問題点につをかけて編成した時間割でもさまざまな問題点を持つこ いて述べる．とが多く，教員や学生から不満の声が上がることもある． 南山大学は名古屋キャンパスと瀬戸キャンパスに分か
このような現状を改善するために，近年，時間割自動編 れており，キャンパスごとに時間割編成を行っている．瀬成システムの開発に関する研究が進んでいる．堀尾 [1, 2] 戸キャンパスには，情報理工学部と総合政策学部の 2 学
は，汎用プロジェクトスケジューラ SEES を用いた大学 部がある．時間割編成の際には，はじめに共通教育科目時間割編成システムを開発するために，時間割編成問題 (英語，体育など) の開講曜日時限を決定し，それらが決を RCPSP の枠組みで表現する方法を提案し，実データ 定したのち，各学部において学部および学科科目の時間を用いて時間割編成を行った結果を示している．また，茨 割編成を行う．
木ら [3] は，メタヒューリスティクスに基づく汎用ソルバ
時間割編成を難しくする要因の 1 つは，頻繁に時間割を用いて時間割編成を行ない，その性能評価のために国 の調整の必要が生じることである．すでに開講曜日時限
際コンペティション ITC2007 に参加した内容と結果を示 を決定した共通教育科目や教職科目でも，担当教員 (主にしている．太田ら [4, 5] は，小中高等学校の時間割編成 非常勤講師や名古屋キャンパス所属教員) の都合などで再問題を 0-1 混合整数計画問題として定式化し，最適化ソ 調整が必要となることがある．1 つの科目の開講曜日時フトウェアを用いて解くことにより，実用的な時間で時 限が変更になることで，他の多くの科目が影響を受ける間割編成が可能であることを示している．このように多 ことは多々あり，変更や調整があるたびに，時間割編成
くの時間割自動編成システムに関する研究があるが，汎 担当者は試行錯誤を繰り返しながら，時間割の調整・確用性の高いものはあまり多くない．そこで，本研究では 認作業に膨大な時間を割いている．この作業は，時間割汎用性の高い時間割自動編成システムを開発することを の提出期限ぎりぎりまで続けられることも少なくない．
目指し，光部ら [6, 7] の研究を発展させ，実用化に向けて時間割編成を難しくするもう 1 つの要因は，異なるカ
時間割自動編成システムを作成する．
リキュラムを履修する学生が混在することである．カリ
時間割自動編成システムの実用化のためには，操作性 キュラムは，おおむね 4〜5 年に 1 度の頻度で改正されての高いユーザインタフェースの開発が重要であることは おり，常に 2 つ以上の異なるカリキュラムを考慮して時いうまでもないが，システムそのものの柔軟性も重要で 間割編成を行う必要がある．また，取得すべき単位数のある．一般に，時間割自動編成システムが出力する時間 多い教職課程履修者，JABEE コース履修者等にとって不割をそのまま使用できる可能性は低い．なぜなら，時間 利にならない時間割を作成することも重要である．
割が満たすべき条件には，時間割編成担当者の経験に基時間割編成に関する作業は，数名の学部時間割編成担づく条件等が含まれることが多いからである．このよう 当者と教務事務担当者の間で協力して進められる．しかな条件は，最適化問題の制約条件としては記述すること しながら，上記に述べたように考慮すべき制約が非常にが難しいことが多い．したがって，実用化にあたっては， 多く，時間割編成はますます困難になっているのが現状
システムが出力する時間割に対して，各科目の開講曜日 である．
時限の調整を時間割編成担当者が適宜行いながら，自動3 モデルの説明編成を再度行うことのできるフィードバック機能を備え時間割編成モデルを作成するためには，実際の時間割た柔軟性の高さが望まれる．
本研究では，南山大学情報理工学部 (旧：数理情報学部) 編成で考慮している点を知ることが重要である．時間割の時間割編成問題を制約充足問題として定式化し，最適 編成にあたり考慮すべき点は，環境，教員，科目の 3 つ化ソフトウェアを用いて許容解を求める．大学全体での の観点から考えることができる．それぞれの観点から以時間割編成問題は大規模になり，許容解を求めることが 下の制約が挙げられる．
難しくなるので，はじめに，情報理工学部のみの時間割 環境の制約編成を対象とする．将来的に大学全体や他大学の時間割編成にも利用できることを目的とし，情報理工学部固有の条件等を可能な限り一般化した時間割編成モデルを提案する．

1. 各曜日時限で使用できる教室数を超える数の授業を開講できない．
2. 1 つの教室で同じ曜日時限に 2 つ以上の授業をすることができない．
3. 教室の定員が決まっている．
4. 特別な設備のある教室で授業をしなければいけない

科目がある．
教員の制約

1. 教員は担当可能科目以外の授業は行なわない．
2. 教員は同じ曜日時限に 2 つ以上の授業を担当することはできない．
3. 教員は都合の悪い曜日時限に授業を担当することはできない．
4. 教員の希望日程を考慮する．
5. 教員の 1 日の授業における負担を考慮する．
6. 担当教員が同じで複数クラス開講する科目は連続して授業を開講する．
科目の制約
1. 各科目で決められた数の授業を毎週開講する．
2. オムニバス形式の授業など，複数の教員が 1 つの授業を担当することがある．

番号によって分けられた 2 つのクラス (1 年次前半クラス，1 年次後半クラス，2 年次前半クラス，2 年次後半クラス)ごとに，また，3 年次以上は学科 (情報通信学科，情報システム数理学科) ごとに，合計 6 つの時間割を作成している．クラス・学科ごとに履修できる科目が定められており，これらの科目を同一曜日時限に開講しないように時間割編成を行っている．したがって，時間割編成を行う単位であるクラスや学科ごとに履修できる科目の集合を1 つのグループとみなすことができる．
さらに，履修対象者が同じで同一曜日時限に開講すべきでない科目があれば，それらの科目であらたにグループを設定することができる．これにより，教職課程や JABEEコースなどの選択コースを併設している場合，適切にグループを設定することで柔軟な時間割編成を行うことができる．

4

定式化

時間割編成問題を定式化するにあたり，以下の記号を定義する．
S： 科目の添字集合．
4. 履修対象者が同じである 2 つの異なる必修科目など，
V： 変動科目の添字集合 (V ⊂ S)．
同じ曜日時限に開講することはできない科目がある．
D： 定置科目の添字集合 (D ⊂ S)．
5. 2 時限連続で授業を開講する特別科目（実習科目なJ： グループの添字集合．
ど）がある．
Sj： グループ j ∈ J に含まれるの科目の添字集合
6. 開講できない時間帯のある科目がある．
(Sj ⊂ S)．
時間割編成モデルを作成するためには，これらの制約を
Vj： グループ j ∈ J に含まれる変動科目の添字集合考慮することが重要である．
(Vj = Sj ∩ V )．
また，定式化する際に「定置科目と変動科目」，「グルーDj： グループ j ∈ J に含まれる定置科目の添字集合プ」という概念を用いるので，それらについて説明する．
(Dj = Sj ∩ D)．
はじめに，「定置科目と変動科目」について述べる．時
W： 2 時限連続科目の添字集合 (W ⊂ S)．
間割編成を行う際，科目によっては，大学や学部の都合
Wj：グループ j ∈ J に含まれる 2 時限連続科目の添字などで担当教員と開講曜日時限が固定される場合がある．
集合 (Wj = Sj ∩ W )．
このような科目を「定置科目」と呼び，時間割の自動編成
T： 時間帯の添字集合．の対象とはしない．一方，時間割自動編成の対象とする
T̂： 2 時限連続科目の割り当てが可能な時間帯の集合科目を「変動科目」と呼ぶことにする．科目を定置科目(T̂ ⊂ T )．と変動科目に分けることは，時間割編成担当者による時
F： 教員の添字集合．
間割の調整の際にも役立つ．たとえば，変動科目の担当
rt： 時間帯 t ∈ T に使用できる教室数．
者変更により開講曜日時限を固定する必要が出た場合な
es： 科目 s ∈ V に必要な教員数．
{
ど，その科目を定置科目に修正後，再度時間割自動編成
1： 教員f ∈ F が科目s ∈ V を担当できる，を行なうことによって対応可能である．このことは，膨 asf =0： 教員f ∈ F が科目s ∈ V を担当できない．

大な時間を必要とする時間割の調整作業の軽減に役立つ
1： 教員f ∈ F が時間帯t ∈ T に授業を担当でと考えられる．

きる，
次に，「グループ」について述べる．時間割編成の際に btf =
0：教員f ∈ F が時間帯t ∈ T に授業を担当で
は，同じ曜日時限に開講することのできない科目がある．
きない．
たとえば，履修対象者が同じである 2 つの異なる必修科
1： 教員f ∈ F が時間帯t ∈ T に定置科目を担
目を同じ曜日時限に開講することはできない．このよう当する，に，互いに同じ時間帯に開講することができない科目の ctf = 0： 教員f ∈ F が時間帯t ∈ T に定置科目を担
集合を「グループ」と呼ぶことにする．提案するモデル当しない．
では，グループを適切に作成することにより，教職課程
 1： 時間帯t ∈ T に定置科目d ∈ D を開講する，や JABEE コースなどの選択コースを履修する学生にも
gdt =0： 時間帯t ∈ T に定置科目d ∈ D を開講しな履修しやすい時間割編成が可能となる．以下では，グルーい．
プ作成の例を示す．
{
1： 時間帯t ∈ T に科目s ∈ V を開講できる，一般に，授業時間割は，学年学科やクラスなどの単位 h =st
0： 時間帯t ∈ T に科目s ∈ V を開講できない．
ごとに作成される．数理情報学部では，1，2 年次は学生

3. 複数クラスを開講する科目の中には，そのすべてあるいは一部を同じ曜日時限に開講するものがある．

5
決定変数は以下のように定める．

{
xst =1：時間帯t ∈ T に科目s ∈ V を開講する，0：時間帯t ∈ T に科目s ∈ V を開講しない．


1：教員f ∈ F が時間帯t ∈ T に科目s ∈ V を担当する，
ystf =
0：教員
f ∈ F が時間帯t ∈ T に科目s ∈ V を担当しない．
本研究では目的関数は設定しない．制約条件は以下のとおりである．
∑xst ≤ rt ,t ∈ T,
(1)
s∈V

∑

ystf ≤ asf ,s ∈ V \W, f ∈ F,(2)

ystf ≤ 2asf ,s ∈ W, f ∈ F,(3)

ystf + ctf ≤ btf ,t ∈ T, f ∈ F,(4)s ∈ V, t ∈ T,

(5)

xst = 1,s ∈ V \W,(6)

xst = 2,s ∈ W,(7)

gdt ≤ 1,j ∈ J, t ∈ T,(8)xst = xs(t+1) ,∑∑ys(t+1)f ,ystf =s ∈ W, t ∈ T̂ ,(9)s ∈ W, t ∈ T̂ ,(10)

t∈T

∑
t∈T

∑

s∈V

es xst =∑∑ystf ,時間割自動編成システムは Microsoft Excel で作成し，データ処理には VBA，実行可能な時間割を求めるために最適化ソフトウェア IBM ILOG CPLEX を用いる．Excel
ファイルは，「main」，「入力 1」，「入力 2」，「時間割表」の 4 つのシートで構成されている．入力 1 シートと入力
2 シートに入力されたデータをもとに，main シート (図1 参照) から 3 つのプログラム「data ファイルの作成」，「CPLEX での計算」，「時間割表の作成」を順次呼び出して時間割を作成する仕様になっている．
「data ファイルの作成」では，CPLEX の入力形式に変換したデータを作成し，外部ファイルに出力する．
「CPLEX での計算」では，CPLEX を起動して計算を行ない，結果を外部ファイルに出力する．ここで出力される結果は 0-1 変数の最適解 (図2 参照) であり，このままでは時間割として機能しない．
したがって，最後に「時間割表の作成」では，CPLEX で出力された結果をもとに時間割の形式にしたものを時間割表シートに出力する (図 3 参照)．

f ∈Ft∈T∑

時間割自動編成システムの概要

t∈T

∑

s∈Vj

xst +∑

図 1 main シートd∈Dj

図 2 CPLEX の実行結果

以下では，時間割編成担当者がシステムを用いて時間割編成を行う際の手順について説明する．はじめに，入xst ≤ hst ,s ∈ V, t ∈ T,
(11)
力 1 シートでグループの設定を行い，授業を行う曜日とxst ∈ {0, 1},s ∈ V, t ∈ T,(12)時限数，教員名等を入力する (図 4(上) 参照)．入力 1 シー
ystf ∈ {0, 1},s ∈ V, t ∈ T, f ∈ F.
(13) トで入力した情報をもとに，入力 2 シートには科目に関する情報 (必要教員数，定置科目/変動科目の区分，担当
制約条件 (1) は，各時間帯で教室数を超える数の授業可能教員名，開講曜日時限に関する制約等) を入力するを開講することができないことを示している．制約条件(図 4(下) 参照)．入力 1 シートと入力 2 シートにデータ入(2)(3) は，各教員が担当可能な科目のみを担当することを力後，main シートに用意されている「data ファイルの作表し，制約条件 (4) は，各教員の担当できない時間帯には成」，「CPLEX での計算」，「時間割表の作成」の 3 つのボ
授業を担当しないことと各教員が時間帯ごとに 1 つの科
タンを順に押してプログラムを実行し，時間割自動編成目しか担当できないことを表している．制約条件 (5) は，を行なう (図 1 参照)．
各科目に必要な教員数を割り当てることを示している．制
約条件 (6)(7) は，各科目は指定された時限数だけ開講す 6 計算結果ることを示している．制約条件 (8) は，同じグループに2011 年度情報理工学部の春学期と秋学期の時間割編成
含まれる科目同士は同じ時間帯に開講しない制約である．
実データを使用し，作成した時間割自動編成システムを用
制約条件 (9)(10) は，科目 s ∈ W を 2 時限連続で割り当いて時間割の自動編成を行った．使用した計算機は，Intelてることを表しており，制約条件 (3)(7) は科目 s ∈ W が
Core2 Duo プロセッサ（3.32GHz）搭載の DELL Optiplex
時間帯に 2 時限割り当てることを可能にしている．制約960，メモリは 1GB である．
条件 (11) は各科目は開講不可能な時間帯には開講しない春学期の問題に含まれる変数の数は 27,900，制約式の数ことを示している．制約条件 (12)(13) は，変数の 0-1 整
は 3,955 で，計算時間は 0.01 秒であった．また，秋学期の数制約である．
問題に含まれる変数の数は 32,400，制約式の数は 4,480，計算時間は 0.03 秒であった．春学期・秋学期共に各学年
f ∈F

f ∈F

図 3 時間割表シート (○が定置科目，空欄が変動科目)
いインタフェースを開発することが必要である．
また，より時間割編成担当者の意図を柔軟に反映させるために，教員や学生にとっての満足度を考慮できる目的関数などを入れて，拡張した時間割編成モデルを考える必要もある．

参考文献

図 4 入力 1 シート (上) と入力 2 シート (下)学科・クラスで，すべての制約条件を満たす実行結果を得ることができた．また，教職課程コースや JABEE コー
スについても，グループを設定することで，すべての制約を満たす時間割編成ができた．時間割編成の結果の一例として，図 3 に春学期の時間割表を示している．

7

おわりに

[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．
[2] 堀尾正典：汎用プロジェクトスケジューラの大学時間割問題への適用，名古屋学芸大学教養・学際編・研究
紀要第 4 号，2008，pp．61-74．
[3] 茨木俊秀，熱田光紀，野々部宏司：汎用ソルバによる時間割作成−国際コンペティション ITC2007 に参加して−， スケジューリング・シンポジウム 2008 講演
論文集，2008，pp．173-176．

2011 年度情報理工学部の春学期と秋学期の科目・教員[4] 太田正和，鈴木敦夫：時間割自動編成システムの研究，の実データを用いて，本研究で作成したシステムで時間
日本 OR 学会 2006 年秋季研究発表会アブストラクト
割自動編成を行なった結果，実用的な計算時間で時間割集，2006，pp．58-59．
を編成することができた．さらに，開講科目データ等をCPLEX で扱うデータ形式に変換する作業も自動化する [5] 太田正和：時間割自動編成システムの研究，南山大学大学院数理情報研究科修士論文，2007．
ことにより，時間割編成作業を大幅に短縮できた．
今後は本システムの汎用化に向けて，時間割編成担当 [6] 光部翔太，伏見正則：大学の時間割自動編成システム
者にとって利用しやすいシステムへの改善が重要である．の研究〜数理情報学部を対象として〜，南山大学数理さらに，大学全体や他大学でも汎用的に利用できるよう情報学部卒業論文，2008．に本システムを発展させていく必要もある．そのため，時 [7] 光部翔太，佐々木美裕，鈴木敦夫，伏見正則：大学時間割編成担当者の経験に基づく条件を加えることを可能
間割の自動作成について， スケジューリング・シンとする機能や，フィードバック機能を備えた操作性の高ポジウム 2010 講演論文集，2010，pp．123-128.