卒業研究発表会のスケジューリング問題
2010SE028 舟橋幸平 2010SE140 中川健太 2010SE276 安江直也
指導教員：佐々木美裕

1

はじめに
南山大学情報理工学部では, 毎年 1 月に開かれる卒業研究発表会において, 卒業研究の最終審査 (以下, 審査) が行なわれる. そのスケジュールは, 卒業研究発表会実行委員会の教員による手作業で時間をかけて作成されている. そこで, 本研究では, 南山大学情報理工学部における審査のスケジュールをオペレーションズ・リサーチの手法を用いて最適化を考える. さらに, 操作性の高いユーザインタフェースを作成することで, スケジュール作成者の負担を軽減することを目的とする.
大学におけるスケジューリング問題として, 過去に伊藤[2], 小野内・内垣内 [3] が研究している. それらの研究では,これまで手作業で膨大な時間をかけて作成していた時間割を短時間で作成した. また, 伊東 [1] は, スケジュール作成者が必要な修正を適切に行なうことができるシステムを試作した.

2

卒業研究発表会の現状

2012 年度に実施した審査のスケジュールを図 1 に示す.
情報理工学部にはソフトウェア工学科, システム創成工学科, 情報システム数理学科の 3 つの学科がある.
2012 年度の発表会では, 各専門分野につき部屋を 1 つ使用した. 例外として, ソフトウェア工学科は専門分野に分かれていないが, 部屋を 2 つ使用した. 審査は主査 1 人, 副査 2 人の審査員で行う. 主査は, 発表する学生が所属する研究室の教員が担当し, 副査は発表する学生の所属する研究室と同じ専門分野である教員が担当するのが望ましい.
現状, 各研究室の審査を担当する教員 (審査員) はあらかじめ決まっている. 発表時間については, ソフトウェア工学科が 1 人につき 9 分, システム創成工学科が 1 人につき 9分, 情報システム数理学科が 1 人につき 8 分である. これらの発表時間には質疑の時間を含む. 図 1 中の研究室名にある数字は各研究室の発表人数を示す. また, 昼休憩の時
間が各部屋において最大で 90 分, 最小で 40 分あり, ばらつきがある. 昼休憩の際に, 委員会に出席しなければならない教員がいることから, 全ての部屋で昼休憩の時間を固定することが望ましい.

3モデルの説明大学におけるスケジューリング問題として, 過去に伊藤[2], 小野内・内垣内 [3] が研究している. これらの研究では,定式化するにあたり割り当て変数を用いてスケジュールを作成した. しかし, 本モデルでは, 各研究室によって発表時間が異なるため, 通常の時間割編成問題のように各時限に各研究室を割り当てる方法を用いることができない. そ図 1

2012 年度に実施された卒業研究発表会のスケジ

ュールのため, 各研究室の審査の開始時刻を決定する変数を用いる. 定式化するにあたり審査員が同時に複数の審査を担当できない制約条件が重要となる. 例えば, 図 2 に示すように, 研究室 i の審査を時刻 t に開始するとき, 研究室 i の審査員は時刻 t − nj から時刻 t + ni , 時刻 maxT−nj から時
刻 maxT までは他の研究室の審査を担当できない. 制約式
は以下のようになる.

∑(yjt′ r + yitr ) ≤ 1,r∈Ri ∈ P, {j ∈ P |bij = 0}, t ∈ T,t′ ∈ max{0, t − nj }, · · · , min{t + ni , maxT }(10)

また, モデルを考える上で, 2012 年度審査を参考にした.

PP+TTlTm
R
4.2

研究室の添字集合.
(研究室を持つ教員の添字集合).
P ∪ { 副査のみ担当する教員 }.
審査を開始する時刻の添字集合

:
:
:
:

T = {0, 1, · · · , maxT }.
: 昼休憩の時刻の添字集合 Tl ⊂ T.
: 午前に行なう審査の開始時刻の添字集合
Tm ⊂ T.
: 審査を行う部屋の添字集合.

第 1 段階第 1 段階では, 各研究室の審査員に専門分野が同じ教員を割り当てる. はじめに, 第 1 段階で用いる記号を定義する.

図 2 審査員の制約

卒業研究発表会のスケジューリングにあたり考慮すべき点
は, 審査員の割り当て, 研究室, 時刻, 部屋の 4 つである.
審査員の割り当てについて
・ 審査は主査 1 人, 副査 2 人で担当する.
・ 研究室を持つ教員は, 自身の研究室の主査を担当する.
・ 研究室を持たない教員は, 副査のみ担当する.
・ 発表する研究室と, 同じ専門分野の教員が審査を担当することが望ましい.
研究室についてwpl : 教員 p ∈ P + が研究室 l ∈ P の審査をするときに課されるペナルティ.
{
1 : 教員 p ∈ P + が研究室 l ∈ P の主査を担当する.
spl =0 : 上記以外.
ここで, ペナルティについて説明する. 他分野の教員が審査員になる場合はペナルティを課し, ペナルティの最小化を目的とする. 次に, 以下の決定変数を定義する.

{: 教員 p ∈ P + が研究室 l ∈ P の審査を担当する.
: 上記以外.

1

xpl =0以上の記号を用いると, 第 1 段階は以下のように定式化できる.

・ 研究室によって発表人数が異なる, つまり発表時間がMinimize異なる.

∑ ∑wpl xpl(1)

p∈P + l∈P

時刻について・ 審査間は 10 分以上の休憩時間がある.

s.t.

部屋について・ 学科, 専門分野によって審査に使用する部屋数が異

xpl ≥ spl ,∑1≤
xpl ≤ 3,p ∈ P +, l ∈ Pp∈P(2)+(3)l∈P∑なる.
問題を 2 段階に分けて考える. まず, 第 1 段階においてxpl = 3,l∈P(4)xpl = {0, 1},

p ∈ P +, l ∈ P(5)p∈P +は, 各研究室の審査員に専門分野が同じ教員を割り当てる.
現状では, 審査員の割り当てはあらかじめ決められているが, 審査員を割り当てることにより, スケジュール作成者の負担を軽減できる場合もあると考え, 第 1 段階の問題を考える. 他分野の教員が審査員を担当する場合はペナルティを課し, ペナルティの総和を最小化をすることにより実現する. 次に, 第 2 段階においては, 各研究室の審査の開始時刻と部屋を決定する. その際, 審査員が同時に複数の審査を担当することのないスケジュールを作成する. また, 審査の終了時刻の総和を最小化することにより, 不要な空き目的関数および制約式は以下のとおりである.

(1) ペナルティの最小化を目的とする.
(2) 教員 p ∈ P + は, 研究室 l ∈ P の審査を担当する.
(3) 教員 p ∈ P + が審査を担当する研究室の数は1 以上 3 以下である.
(4) 研究室 l ∈ P の審査は 3 人の教員で担当する.
(5) xpl は, 0-1 変数である.

時間のないスケジュールを作成する.

4定式化

4.1

記号の定義

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

4.3

第 2 段階第 2 段階では, 全ての部屋で同じ時刻に昼休憩を固定した. 審査の終了時刻の総和を最小化することにより, 不要な空き時間のないスケジュールを作成する. はじめに, 第 2

段階で用いる記号を定義する.

はじめに, 2012 年度の審査員の組合せを用いて計算する. 使用したデータと計算時間を以下に示す. スケジュー

Us : 昼休憩の開始時刻.
nl : 研究室 l ∈ P の発表人数.
{
1 : 研究室 i ∈ P と研究室 j ∈ P の審査を同時に行うことが可能である.
bij =0 : 上記以外.
{
1 : 研究室 l ∈ P の審査を部屋 r ∈ R で行うことが可能である.
clr =0 : 上記以外.

ル対象となる研究室数は 24, 審査の開始時刻を 10 時 10 分から 20 時 10 分の 10 分ごとに 60 個, 審査を行なう部屋数は 7 である. 変数の数が 10249, 制約式の数が 2568458,最適値が 663 であり, 計算時間は 0.80 秒であった. なお,計算に使用したコンピュータの CPU は Intel Core Duo

2.53GHz, 搭載されているメモリは 2.00GB である.

次に以下の決定変数を定義する.

{: 研究室 l ∈ P の審査を時刻 t ∈ T に部屋 r ∈ R で開始する.
: 上記以外.

1yltr =0以上の記号を用いて定式化する.

Minimize(∑ ∑∑l∈P

∑

s.t.

)
tyltr + nl(6)t∈T r∈R∑l ∈ P (7)yltr = 1,t∈{0,··· ,maxT −nl } r∈R∑t∈Tyltr ≤ clr ,∑{i∈P |t+ni >Us }∑l ∈ P, r ∈ R (8)∑yitr +yjt′ r = 0,t′ ∈Tlr ∈ R, t ∈ Tm , j ∈ P (9)(yjt′ r + yitr ) ≤ 1,r∈Ri ∈ P, {j ∈ P |bij = 0}, t ∈ T,t ∈ max{0, t − nj }, · · · , min{t + ni , maxT }(10)yjt′ r + yitr ≤ 1,i ∈ P, j ∈ P \{i}, t ∈ T′t ∈ t, · · · , min{t + ni , maxT }, r ∈ R (11)yltr = {0, 1},l ∈ P, t ∈ T, r ∈ R (12)′各制約式は以下のとおりである.

(6) 不要な空き時間を減らすため,審査の終了時刻の総和を最小化する.
(7) 各研究室の審査は 1 回である.
(8) 各研究室を審査可能な部屋に割り当てる.
(9) 昼休憩の時間に審査を割り当てない.
(10) 異なる部屋で, 同時に複数の審査を割り当てない.
(11) 同じ部屋で, 同時に複数の審査を割り当てない.
(12) yltr は, 0-1 変数である.

5

計算結果
2012 年度, 2013 年度の審査員の組合せを用いて, 最適化

図 3 専門分野ごとに部屋を指定した場合 (2012 年度)

図 3 は審査に使用する部屋を専門分野ごとに指定した場合の計算結果である. 図 1 は, 図 3 と同様に, 使用する部屋が専門分野ごとで指定されているため適切な比較ができるといえる. 本モデルでは, 昼休憩の時間を 12 時から 13時に固定したが, 各部屋の審査の終了時刻にあまり差がない結果となった. また, 昼休憩を固定する時刻を変更して計算を繰り返した結果, 昼休憩を 12 時から 13 時と固定することで, 審査の終了時刻の総和を最も短縮できる結果となった.

計算ソフトウェア IBM ILOG CPLEX で計算し, 審査の次に, 2013 年度の審査員の組合せを用いて計算する. 使

スケジュールを作成した. 以下, 審査に使用する部屋数を,用したデータと計算結果を以下に示す. スケジュール対専門分野ごと, 学科ごと, 部屋分けなしの 3 つに分けて考象となる研究室数は 25, 審査を行なう部屋数は 7 である.

察する.

図 4 は, 審査に使用する部屋を専門分野ごとに指定した場

図 4 専門分野ごとに部屋を指定した場合 (2013 年度)

図 5 2013 年度に実施されるスケジュール合の計算結果であり, 最適値は 658, 計算時間は 0.71 秒であった. 図 6 は, 審査に使用する部屋を学科ごとに指定した場合の計算結果であり, 最適値は 658, 計算時間は 1.39秒であった. 図 7 は, 審査に使用する部屋を学部全体で指定した場合の計算結果であり, 最適値は 651, 計算時間は6.3 秒であった.
図 5 は図 4 と比べ, 同じ部屋で研究室の審査が前後するものの, 図 4 の計算結果を一部参考にして作成された. しかし, ソフトウェア工学科においては, 午前の空き時間, 昼休憩の時間が異なる. スケジュール作成者の意図を全て反映できるようなモデル, システムの改善が必要である.
図 6 は図 4 と比べ, すべての審査の終了時刻にあまり差がない結果となった. しかし, 一部の審査員が複数の部屋を移動する必要がある.
図 7 は最適値が 651 となり, 図 4 と図 6 に比べ, 最も審査の終了時刻の総和を短縮できる結果となった. 図 7 の部
屋 5 では, 審査員が同時に複数の審査員を担当できないた
め, 審査間に 20 分の空き時間がある. しかし, 図 6 と同様に, 審査員が複数の部屋を移動する必要があるため, 審査

図 8 は, 審査に使用する部屋を学部全体で 6 つに指定した計算結果であり, 最適値が 712, 計算時間が 2.48 秒である. 図 8 は図 7 に比べ. 使用する部屋数を 1 減らしたにもかかわらず, 審査の終了時刻が 19 時 10 分と変わらない結果となった. このことから, 審査に使用する部屋を学部全体で６つに指定した場合も, 現実的なスケジュールを作成できることが分かった.

6システムの試作
卒業研究発表会のスケジュールを自動で作成できるシステムを試作した. 本システムは, 計算処理に CPLEX, データ処理に VBA を用いることで, すべて Excel 上で操作可能である.
システムの画面の一部を図 9 に示す. スケジュール作成者は, 5 つのボタン「審査員データ入力完了」, 「専門分野ごと」, 「学科ごと」, 「学部全体」, 「CPLEX 起動」を操作する. また, Excel ファイルは, 「入力」, 「データテーブル 1」, 「データテーブル 2」, 「出力結果」の 4 枚のシー

員の部屋の移動数を最小化できるようなモデルの改良が必トで構成されている. システムの簡単な操作手順は, 以下要である.のとおりである.

図 6 学科ごとに部屋を指定した場合 (2013 年度)

図 7 学部全体で部屋を指定した場合 (2013 年度)

入力する. 入力を終えたら, 図 9 に示す「専門分野ごと」,
手順 1. 研究室名, 学科名, 専門分野名, 発表人数, 審査員の組合せを入力し「, 審査員データ入力完了」
ボタンを押す.
手順 2. 使用する部屋数を専門分野ごと, 学科ごと, 学部全体の 3 つから 1 つ選択, 入力し, 対応するボタンを押す.
手順 3. 「CPLEX 起動」ボタンを押し, スケジュールを作成する.

「学科ごと」, 「学部全体」の 3 つの中から対応するボタン

以下では, スケジュール作成者がシステムの操作をする減が目的であった. 審査のスケジュールを自動で作成する際の注意点を踏まえながら, 操作手順に沿って説明する.

を押す.
手順 3 では, 図 9 に示す「CPLEX 起動」ボタンを押すと, CPLEX を起動し計算を行い, Excel 上に計算結果を出力する.

7

おわりに本研究では, 審査のスケジュール作成における作業の軽システムを試作したところ, 計算に必要なテーブルの作成

手順 1 では, 図 10 に示す入力シートに, 研究室名, 学科を含めた一連の作業時間を短縮することができた. また,名, 専門分野名, 発表人数, 審査員名を入力する. すべての昼休憩の時間を固定したことによって委員会に出席する教項目の入力を終えたら, 図 9 に示す「審査員データ入力完員の都合を考慮できた. しかし, 図 5 は図 4 を全て参考に了」ボタンを押す.

して作成されたわけではない.

手順 2 では, 図 11 に示す入力シートに, 審査に使用する今後の課題として 2 点挙げる. 1 点目は, モデルの改良部屋数を入力し, 各研究室の審査を行なう部屋を指定する.

である. より良い審査のスケジュールを作成するため, 審専門分野ごとに使用する部屋を指定する場合は, 「専門分査に使用する部屋を, 専門分野, 学科ごと, 学部全体の 3 つ野ごと」の列に入力する. 学科ごとに使用する部屋を指定の場合を考えた. 実施された審査では, 2012 年度, 2013 年

する場合は, 「学科ごと」の列に入力する. 情報理工学部全度ともに使用する部屋は専門分野ごとで分けていた. これ体で使用する部屋を指定する場合は, 「学部全体」の列には, 審査員が部屋を移動する手間を考慮したからであると

図 10 「入力」シートの一部

図 11 使用する部屋数
図 8 学部全体で部屋を 6 つ指定した場合 (2013 年度)

参考文献[1] 伊東美奈：手術部看護師のスケジューリング支援システムの試作，南山大学大学院数理情報研究科 2011 年度
修士論文，2012.
[2] 伊藤美登，佐々木美裕，鈴木敦夫，伏見正則：大学時間割編成モデルの研究，南山大学紀要『アカデミア』情報理工学編，第 12 巻，pp. 87-98.

[3] 小野内雄一，内垣内智子：南山大学の定期試験時間割作成問題，南山大学数理情報学部 2011 年度卒業論文，2012.
図 9 メニュー画面

考える. そのため, 審査に使用する部屋数を専門分野ごと,学科ごとに指定せず, なるべく審査員の部屋の移動を最小にするような目的関数を設定する必要がある.

2 点目は, システムの改良である. 昼休憩の時間に委員会に出席する教員を考慮するため, 昼休憩を固定した. しかし, 実際のスケジュールでは, ソフトウェア工学科において昼休憩の時間がばらばらである. そのため, ステム上で昼休憩の時間を自由に設定するなど, スケジュール作成者の意図を反映できるような改良が必要である.