学生研究室割り当てシステムの開発
2009SE266 鈴木まみ

2009SE318 安西将貴

指導教員：佐々木美裕

1

はじめに

1.1

背景

毎年 4 月に南山大学情報理工学部所属の新 3 年生と数理情報研究科所属の修士新 1 年生は学部教員の研究室に配属となる. このとき学部教員は, 手作業で新 3 年生と修士新 1 年生が使用する学生研究室を決め, 各学生研究室に割り当てられた学部生の学生数, 院生の学生数に応じて学部生用の机, 院生用の机の再配置を行っている. しかし, 近年 2 点の問題が発生している. それは, 割り当てられる学生の人数と定員との差が学生研究室ごとで大きくばらついていることと, 学部生用の机が余っているにもあるにもかかわらず, 学部生に院生用の机が割り当てられることである.
林, 水野 [1] は, 各研究室の学生の学生研究室への割り当てを決めるモデル, 学生研究室ごとに割り当てられた学生の人数に応じて机の配置を決めるモデルを作成し, それぞれの作業の自動化を行った.

1.2

概要

本研究は 2 点の問題を解決するため林, 水野のモデル[1] に改良を行う. この改良に加え, ユーザインタフェー
スを作成する. 本研究では学生研究室のことを部屋, 各研究室の学生を学生研究室に割り当てる作業を自動化する
モデルを部屋割りモデル, 学生研究室ごとに割り当てられた学生の人数に応じて机の配置を行う作業を自動化する
モデルを机の配置モデルと定義する. 部屋割りモデルと机の配置モデルを行うシステムを学生研究室割り当てシステムとする.

2

部屋割りモデルの定式化

2.1

部屋割りモデルの留意点

各研究室の学生を部屋に割り当てるとき, 3 点のことを考慮しなければならない. 1 点目は, 各部屋の定員である.
2 点目は, 複数の研究室で 1 つの部屋を共有するときの研究室の組み合わせである. これを考慮する理由は, なるべ
く同じ領域に属する研究室同士を割り当てることが好ましいとされているからである. 3 点目は 1 つの研究室の学生が複数の部屋に割り当てられた時の部屋間の距離である. これを考慮する理由は, 1 つの研究室の学生をなるべく近くの部屋に割り当てることが好ましいからである.
本研究は, これら 3 点のことを考慮したうえで, 各部屋の定員と割り当てられる学生の人数の差を小さくするモデルを提案する.

2.2とである. こうすることで, 各研究室の学生が使用できる部屋の数が増え, 各部屋の定員と割り当てられる学生の人数の差は小さくなると考えられる. 2 点目は, 各部屋の容量制約がソフト制約であったのをハード制約にすることである. こうすることで, 割り当てられる学生の数が定員よりも大幅に上回ることはなくなると考えられる. 3 点目
は, 各研究室の各学年の学生を全員同じ部屋に割り当てていたのを複数の部屋に割り当てることを可能にすることである. こうすることで, 部屋に割り当てられる学生の人数と定員との差が均等化されると考えられる. 4 点目は,各研究室の学生を全員部屋に割り当てていたのを 3 年生と修士 1 年生のみを部屋に割り当てることである. すな
わち, 4 年生と修士 2 年生は, それぞれ 3 年生時, 修士 1年生時に使用していた部屋から移動しない. その理由は,4 年生と修士 2 年生を移動させた場合, 研究室の備品の移動も含まれ, 大掛かりな作業となるからである. また本研
究では, 新たにダミー部屋を定義する. ダミー部屋とはす
べての部屋との距離が 0 の部屋とし, 新たに新設された研究室すなわち 4 年生がいない研究室の 4 年生が割り当てられていると仮定する. ダミー部屋を設けることにより, 既存の研究室と新 4 年生がいない新設の研究室を同じ枠組みで扱うことが可能となり, 制約条件も簡潔に記述することができる.

2.3

モデルの説明本モデルを実現するために, 各研究室の新 3 年生を複数のグループに分ける. グループ分けの条件は 3 人以上のグループであることと各研究室を 4 つ以上に分けないことの 2 つである. この条件の下で各研究室でグループ分けを行い, 部屋割りを行う. 例えば学生数が 9 人の研究室の場合, 3 人グループが 3 つの組み合わせ, 3 人グループと 6 人グループが 1 つずつの組み合わせ, 4 人グループと 5 人グループが 1 つずつの組み合わせ, 9 人グループが 1 つの組み合わせの計 4 つが考えられる. 図 1 は研究室 1 の学生を 3 人グループと 6 人グループに分け, 部屋1 と部屋 3 に割り当てる例を示している.

林, 水野のモデルの改良点

部屋割りモデルでは, 林, 水野のモデルに 4 点の改良を行う. 1 点目は, 学部生, 院生共に学科ごとに部屋割りを決めていたのを学部全体, 大学院全体で部屋割りを行うこ

図 1 モデルの考え方
また, 複数の研究室で 1 つの部屋を共有する時の研究室の組み合わせを考慮するために, 各研究室が同室になった時のペナルティを用いる. ただし, 4 年生が割り当てられている部屋は, その部屋に割り当てられている 4 年生と同じ領域 (学科) に属する研究室の 3 年生しか割り当てることができないとする. 1 つの研究室が複数の部屋に割り当てられた時の部屋間の距離を考慮するために, 林, 水野の卒業論文から引用した距離データを用いる [1].

2.4[{1(∑∑∑vil +vjlp1
dij sil vjl +p1
dij2i∈R1 j∈R l∈Li∈R j∈R l∈L][{1(∑∑ ∑)})}
o l1 l2
vrl1 +vrl2 −zrl1 l2−wijl+p22r∈R l1 ∈L l2 ∈L]∑+ ol1 l2 srl1 vrl2 + p3yr (1)∑ ∑∑r∈R

定式化

定式化にあたり，記号を以下のように定義する．
Li : 領域 i ∈ E1 の研究室の集合
E1 : 領域の集合 (1 : OR, 2 : 統計, 3 : 数学, 4 : シス
テム工学, 5 : 通信, 6 : ソフトウェア)
E2 : 学科の集合 (1 : 情報システム数理学科, 2 : システム創成工学科, 3 : ソフトウェア工学科)
R : ダミー部屋以外の部屋の集合
R1 : ダミー部屋を含めたすべての部屋集合
R2 : 4 年生が割り当てられている部屋の集合
I : グループの人数の集合
G : グループ番号の集合
Fi : i 人グループの集合
a : 研究室の分割数
h : 研究室の組み合わせを考える際に必要な定数
cr : 部屋 r ∈ R の定員
δr : 部屋 r ∈ R の定員増加分
ml : 研究室 l ∈ L の 3 年生の学生数
bg : グループ g ∈ G の人数
srl : 部屋 r ∈ R1 に研究室 l ∈ L の 4 年生が 1 人でもいるとき 1，いないとき 0 をとる定数
trl : 部屋 r ∈ R1 にいる研究室 l ∈ L の 4 年生の人数
ol1 l2 : 研究室 l1 ∈ L の学生が研究室 l2 ∈ L の学生と同室になったときのペナルティ
dr1 r2 : 部屋 r1 ∈ R1 と部屋 r2 ∈ R1 の距離
p1 , p2 , p3 : 目的関数の重み
次に変数を定義する．
xrlg : 研究室 l ∈ L の 3 年生のグループ g ∈ G が部屋r ∈ R に割り当てられるとき 1 ，そうでないとき0 をとるバイナリ変数
vrl : 研究室 l ∈ L の 3 年生が 1 人でもいるとき 1 , そうでないとき 0 をとるバイナリ変数
wijl , yr , zrl1 l2 : 目的関数の線形化に必要な変数定式化は以下の通りである．
最小化∑ ∑∑∑∑∑
p1
dij sil vjl + p1
dij vil vjl
i∈R1 j∈R l∈L+ p2∑∑ ∑(r∈R l1 ∈L l2 ∈Li∈R j∈R l∈Lol1 l2 vrl1 vrl2 + ol1 l2 srl1 vrl2)

制約条件


∑
∑
trl +bg xrlg  ≤ cr + δr(r ∈ R)(2)

g∈Gl∈L∑∑bg xrlg = ml∑trl +∑(l ∈ L)(3)

r∈R g∈Gbg xrlg  ≥ 1 (r ∈ R)

(4)

xrlg ≤ a (l ∈ L)

(5)

g∈Gl∈L∑∑∑r∈R g∈Gvrl ≤ h(e ∈ E1 , r ∈ R2 )(6)

xrlg ≤ 1 (i ∈ I, r ∈ R, l ∈ L)

(7)

l∈Le

∑

∑srll∈Leg∈Fi∑xrlg ≤ vrl(r ∈ R, l ∈ L)

(8)vil − vjl ≤ wijl(i ∈ R, j ∈ R, l ∈ L)

(9)−vil + vjl ≤ wijl(i ∈ R, j ∈ R, l ∈ L)

(10)(r ∈ R, l1 ∈ L, l2 ∈ L)

(11)

−vrl1 + vrl2 ≤ zrl1 l2 (r ∈ R, l1 ∈ L, l2 ∈ L)∑∑trl +bg xrlg  − cr ≤ yr (r ∈ R)

(12)g∈Gvrl1 − vrl2 ≤ zrl1 l2l∈Lg∈G∑∑l∈L−trl −(13)bg xrlg  + cr ≤ yr

(r ∈ R)(14)g∈G{ }
xrlg ∈ 0, 1
(r ∈ R, l ∈ L, g ∈ G)

(15)

{ }
vrl ∈ 0, 1
(r ∈ R, l ∈ L)

(16)

{ }
wijl ∈ 0, 1
(i ∈ R, j ∈ R, l ∈ L)

(17)

{ }
zr1 l2 ∈ 0, 1
(r ∈ R, l1 ∈ L, l2 ∈ L)

(18)

1(vil + vjl − wijl ) ≥ 0 (i ∈ R, j ∈ R, l ∈ L) (19)2∑∑∑trl ++ p3
bg xrlg  − cr1
(vrl1 + vrl2 − zrl1 l2 ) ≥ 0 (r ∈ R, l1 ∈ L, l2 ∈ L)r∈R l∈Lg∈G2(20)式が非線形となるため, 次のように線形の式に書き直す．
式 (1) の第 1 項目は, 各研究室の 4 年生が割り当てら最小化れている部屋と 3 年生が割り当てられる部屋間の距離の合計, 第 2 項目は, 各研究室の 3 年生が割り当てられる部


屋間の距離の合計, 第 3 項目は, 研究室 l1 の学生が研究室 l2 の学生と同室になったときのペナルティの総和, 第4 項目は, 割り当てられる学生の人数と定員の差の絶対値の合計を表す. 式 (2) は各部屋の容量制約を表す. 式 (3)はすべての 3 年生を部屋に割り当てる制約を表す. 式 (4)は空き部屋をつくらない制約を表す. 式 (5) は各研究室の分割数を a 個までとする制約を表す. 式 (6) は 4 年生が割り当てられている部屋には割り当てられている 4 年生と同じ領域に属する研究室の 3 年生しか割り当てられない制約を表す. E1 を E2 に変えることで同じ領域だけでなく同じ学科まで割り当てることができる. 式 (7) は各研究室において i ∈ I 人グループは同じ部屋に１つしか割り当てられない制約を表す. 式 (8) は研究室 l の 3 年生
が部屋 r に割り当てられるとき vrl が 1 になることを表す制約を表す. 式 (9), 式 (10), 式 (11), 式 (12), 式 (13),式 (14) は目的関数の線形化に必要な制約を表す. 式 (15),式 (16), 式 (17), 式 (18) はバイナリ制約を表す. 式 (19),式 (20) は非負制約を表す.

3

机の配置モデルの定式化

3.1

モデルの説明机の配置作業を行うモデルでは，部屋割り作業を行うモデルで得られた各部屋の学生数をもとに机の配置を行う．各部屋に割り当てられた学生数に応じて学部生用の机と院生用の机の過不足数を計算し，輸送問題として定式化する．

3.2

林, 水野のモデルの改良点

机の配置作業では, 林, 水野のモデルに 2 点の改良を行う. 1 点目は学部生用の机, 院生用の机をそれぞれ各部屋に割り当てていたのを学部生用の机, 院生用の机を一括で各部屋に割り当てることである. 2 点目は学部生が使用する机は学部生用, 院生用どちらを使用してもよいとしていたのを学部生用の机の数が学部の学生数に満たない分だけ学部生に院生用の机を割り当てるようにすることである.

3.3

定式化

本問題を定式化するにあたり，記号を以下のように定義する．
R : 部屋の集合
nij : 部屋 (i, j) 間の距離
dr : 部屋 r ∈ R における院生用の机の需要量
er : 部屋 r ∈ R における学部生用の机の需要量
sr : 部屋 r ∈ R における院生用の机の供給量
tr : 部屋 r ∈ R における学部生用の机の供給量
a : 学部生が院生用の机を使う人数
次に変数の定義を行う．
xij : 部屋 i ∈ R から部屋 j ∈ R に移動する院生が使用する院生用の机の個数
yij : 部屋 i ∈ R から部屋 j ∈ R に移動する学部生が使用する学部生用の机の個数
zij : 部屋 i ∈ R から部屋 j ∈ R に移動する学部生が使用する院生用の机の個数定式化は以下の通りである．
最小化∑∑(nij xij + nij yij + nij zij )(21)i∈R j∈R

制約条件∑(xij + zij ) ≤ sij∈R∑(i ∈ R)(22)

yij ≤ ti(i ∈ R)(23)

xij ≥ dj(j ∈ R)(24)

j∈R∑i∈R∑(yij + zij ) ≥ eji∈R∑∑(j ∈ R)

zij = a(25)(26)

i∈R j∈R

xij ≥ 0 (i ∈ R, j ∈ R)(27)

yij ≥ 0 (i ∈ R, j ∈ R)(28)

zij ≥ 0 (i ∈ R, j ∈ R)

(29)

式 (21) は机の総移動距離を表す. 式 (22) は各部屋の院生用の机の供給量に関する制約を表す. 式 (23) は各部屋の学部生用の机の供給量に関する制約を表す. 式 (24) は各部屋の院生用の机の需要量に関する制約を表す. 式 (25)は各部屋の学部生用の机の需要量に関する制約を表す. 式(26) は学部生が院生用の机を使用する人数に関する制約を表す. 式 (27), 式 (28), 式 (29) は非負制約を表す.

4使用したデータ

部屋割りモデルで用いた各研究室が同室になったときのペナルティの一例を表 1 に示す. 本学部は, 情報システム数理学科, システム創成工学科, ソフトウェア工学科の 3学科で構成されている. 情報システム数理学科は, OR 領域, 統計領域, 数学領域の 3 領域で構成され, システム創成工学科は, システム工学領域, 通信領域の 2 領域で構成されている. そこで, 本研究はペナルティの値を同じ研究室同士の場合 0, 研究室の属する領域が同じ研究室同士の場合 5, 研究室の属する学科が同じ研究室同士の場合 30,研究室の属する学科が異なる研究室同士の場合 100 と設定した.
表 1 ペナルティの例
OR
統計数学
システム工学
佐々木美 鈴木 松田 木村 小藤 杉浦 高見 大石OR佐々木美0530303030 100 100鈴木
5030303030 100 100
統計松田
3030053030 100 100木村3030
503030 100 100
数学小藤3030303005100 100杉浦30303030
50100 100
システム工学高見100
100 100 100 100 10005大石100
100 100 100 100 100
505

実行結果と考察参考文献

5.1

部屋割り作業の実行結果と考察[1] 林美咲, 水野友貴：『学生研究室の引越しスケジューリングについて』, 南山大学数理情報学部情報システム数理学科，2011 年度卒業論文，2012．

a = 3, P1 = 1, P2 = 1, E1 のときの実行結果を表 2 にまとめた. 計算時間は, 学部生の部屋割りでは約 13 分, 院生の部屋割りでは約 10 秒である. また, 分割された研究室は学部生の部屋割りで 4 研究室, 院生の部屋割りで 2 研究室あった. 各部屋の最大収容人数を定員以下とする場
合, 院生の部屋割りは最適解を求めることができたが, 学部生の部屋割りは最適解を求めることができなかった. そこで学部生を割り当てる部屋は, 各部屋の最大収容人数を定員の 1 割増としたところ, 最適解を求めることができた. 林, 水野のモデルで部屋割りを行うと, 院生の部屋割りで割り当てられる学生が定員以上となった部屋が 1 つあり, 学部生の部屋割りで割り当てられる学生が定員の 1割以上となった部屋が 3 つあった. 本モデルでは容量制約を加えたので, 各部屋の最大収容人数を超えることはな
い. この結果より, 学部生, 院生ともに各部屋に割り当てる学生の人数と定員との差が小さくなったといえる.
5.2

机の配置作業の実行結果と考察

林, 水野のモデルの部屋割り作業実行後のデータ [1] を用いて机の配置を行った結果を表 3 にまとめた. 本モデルを用いて机の配置を行うと総移動距離は, 3822m となり, 林, 水野のモデルを用いて机の配置を行うと総移動距離は, 3674.5m となった. 本モデルと林, 水野のモデルを比較すると, 総移動距離が 147.5m 増加した. 原因として次のことが考えられる. 本モデルでは, 院生は院生用の机を使用しなければならないが, 学部生は, 学部生用の机の数が学生数未満であるときのみ, 足りない分だけ院生用の机を使用できるとした. しかし, 林, 水野のモデルでは, 院生は院生用の机を使用しなければならないが, 学部生は,院生, 学部生用どちらの机を使用してもよいとしていた.
そのため, 本モデルでは学部生の部屋に院生の机があっても, 他の部屋で学部生用の机が余っていれば, その机を移動させなければならない. この机の移動が, 本モデルの移動距離に加わったため机の総移動距離が増加したと考えられる.

6

おわりに

本研究では, ユーザインタフェースを含めた学生研究室割り当てシステムを提案した. 部屋割りモデルでは, 割り当てられる学生の数と定員との差のばらつきを減らすことができ, 机の配置モデルでは, 院生用の机を使用していた学部生に対し, 余っている学部生用の机を割り当てることができようになった. したがって, 2 点の問題を解決することができたといえる. しかし, 課題が 2 点ある. 1 点目は 2011 年度のデータでしか計算を行わなかったので,別のデータで計算を行うことである. こうすることで, 林,水野のモデルとの違いを明確化させることができると考えられる. 2 点目は部屋割りモデルにおいて, 重みの付け方によって計算時間が長くなる場合があるので, 計算時間の短縮を図ることである.

表 2 部屋割りモデルの実行結果
部屋研究室

H405
H406
H410
H411
H414
H415
H305
H306
H308
G402
G403
G404
H204
H205
H208
H209
H212
H213
H310
H311
H315
G301
G302
G401
H403
H404
H407
H413
H302
H303
H309
H312
H313
H314
H201
H202
H210
H211

佐々木美 (B4)
白石 (B3)
木村 (B3,B4)
松田 (B3,B4)
杉浦 (B3,B4), 小藤 (B3), 佐々木克 (B3)
小藤 (B3,B4), 杉浦 (B3)佐々木克 (B3,B4)
陳 (B4)
市川 (B3,B4)
高見 (B3,B4), 大石 (B3)
腰塚 (B3,B4), 鈴木 (B3,B4)
尾崎 (B4), 澤木 (B3,B4), 佐々木美 (B3)
蜂巣 (B4), 吉田 (B4)吉田 (B3), 蜂巣 (B3)
野呂 (B4)
張 (B4)
野呂 (B3), 張 (B3)石崎 (B3), 奥村 (B3)市川 (B3), 陳 (B3)奥村 (B4)
石崎 (B4)
青山 (B3,B4), 横森 (B3)
河野 (B3,B4), 宮澤 (B3)
後藤 (B3,B4)
佐々木克 (M2), 杉浦 (M2)木村 (M1)
尾崎 (M2), 澤木 (M1)松田 (M1)
高見 (M2,M1)
高見 (M1)
奥村 (M1,M2)
鈴木 (M1)
鈴木 (M1,M2), 腰塚 (M2)澤木 (M1), 石崎 (M1)
野呂 (M1,M2)
河野 (M1,M2)
青山 (M1)
青山 (M2), 吉田 (M1)

学生数

部屋の定員

部屋の定員
−学生数

111122222222211315334344302212112222152316363625
54491010881061814109141420202020202014404040
2420101020201414204040401010101010101410102020141010-3-322221-71-7346221221
9-4-4-4-15-5-6-6-1
00-6-20-14-200-1

表 3 机の配置モデルの実行結果
供給部屋

院生用机
需要部屋

個数

供給部屋

H407
H405
H407
H413
H413
H302
H302
H312
H313
H314
H205
H208
H209
H209
H211
H414*1
H309*1
H311*1

H201
H210
H210
H404
H201
H303
H210
H210
H201
H201
H201
H202
H201
H202
H210
H410
H308
H308

1
41
122
11
1
333
1
9311
8

H406
H314
H314
H315
H315
H315
G301
G301
G301
G301
G301
G302
G302
H202
H202
H204H210
H210
H210*1 学部生が使う机とする.

学部生用机
需要部屋 個数

H405
H311
H415
H311
H305
H306
H410
H415
G402
G403
G404
H415
H205
H205
H209
H205
H410
H212
H213

47612321131354101325