お茶大情報科の時間割自動作成
大西結花

1(指導教官:浅井健一)

はじめに時間割を作る。それぞれの時間割に、未確定リストをセットにする。

お茶大情報科学科の時間割は、毎年情報科の教授達が多いに頭を悩ませて、作らなくてはならない。また、

3. 可能な場所が無くなってしまったら、一つ前に戻っそれを作る際には、考慮しなくてはならない条件が多て別の解を探索する。

数存在する。それら条件がきちんと反映された、実際に使える時間割を考えるのは頭の痛くなる問題である。

4. 可能な解があったら、２に戻って、その最初の一

そこで、本研究では、スムーズに時間割を作成するプつをとり、さらに未配置の科目を組み入れる。そログラムを作ることを目標にする。の他の時間割は、一つ目が後々行き詰まった時に使用する。

2

情報科の時間割の特徴

5. 全て配置できれば終了。

以下に情報科の時間割の特徴を述べる。

次に、各部で使うデータ構造について説明する。

• 平日の 12 限（9:00〜10:30） 、34 限（10:40〜

未確定リスト まず、(科目の全情報、開講可能な部屋12:10）、56 限（13:20〜14:50）、78 限（15:00〜16:30）、910 限（16:40〜18:10）までの 5 × 5=25と日時の候補リスト) という形のデータのリストを用意する。具体的に示すと次の様になる。

コマある• 授業数は、前期後期合わせて約 60（大学院まで含めると約 80）("関数型言語", [(409, 月 34);(409, 月 56); ‥(507, 月 34); ‥])• 専門（情報科）の授業は基本的に 12・910 限、水曜日には入れない。

（実際には、科目の担当や学年などの情報も入る。）
このようなデータのリストを、未確定リストと呼ぶ。

• 主に使用する部屋は、理学部３号館 504（計算機室）、理学部２号館 507、共通講義棟３号館 408・409（ただし 409 は人数の少ない授業のみ）

確定リスト また、すでに部屋と日時の決定した科目を集めたリスト（つまり時間割のこと）を確定リストと呼ぶ。例えば、“関数型言語” の授業を、月この他にも、細かい規則がいろいろと存在する。

3

曜 78 限の 409 に決定したのなら、それは時間割を組むとは‥("関数型言語", (409, 月 78))

時間割を組んでいる途中の段階を考える。まず、そとなる。確定リストは、このようなデータのリスれまでの時間割を見て、空いている日時と部屋の組みトである。

合わせを見つける。さらに、それぞれの科目によって、開講できない条件を考慮し、不可能な組み合わせを削

時間割問題を解くとは、未確定リストの中身が全て確除する。それから順番に、それまでの時間割に組み入定リストに移る、ということである。

れる。これを、組み入れる科目がなくなるまで続ける。

5

行き詰まったら、一つ前の可能性を調べてみる。

制約
上記のアルゴリズムだと同じ日時の同じ部屋に別の4アルゴリズムの概要授業が入ったりしてしまう。他にも沢山の不都合なことが起きる。考慮しなくてはならない条件として、以以下に、全体の流れを説明する。

下が挙げられる。

1. 開講可能な部屋と日時のリストを伴った、未配置• 同じ学年の授業は同じ日時にかぶってはいけないの科目を集めた未確定リストを準備する。

• 同じ先生の授業は同じ日時にかぶってはいけない

2. 一つ目の科目から、部屋と日時を決定する。開講
可能な全ての部屋と日時の組み合わせに基づいて、• 他の授業と同じ日時・部屋には入れられない9

• 12、910 限には情報科の授業を入れてはいけない

様々な必要をより反映させやすくなる。制約のみを記述することが出来れば、プログラムを変更しなくても• 主に使える部屋は、理学部３号館 504、理学部２号館 507、共通講義棟３号館 408、409

ユーザの意向を簡単に反映することができる。制約の具体例を示す。

• 二時間続きの授業は午後開講する(1) (同じ学年の授業 => 曜日か時限は別にする)(2) (同じ教官の授業 => 曜日か時限は別にする)• 各先生の都合

6

つまり、制約は制約をどう解決するか(二つの授業が条件に合致するか判断する関数 =>それぞれの時間割について、新たに埋まった部屋と時合致した場合何を行うかを指示する関数)

間に応じて、それ以降使用することの出来なくなった部屋と時間の組み合わせが発生する。それらを、未確という形で表される。二つの授業というのは、一つ目

定リストの未配置の各科目の候補リストから削除する。

は時間割に新たに組み入れられた授業のこと、二つ目

例として、関数型言語（２年生の浅井先生担当の授は未確定リスト中の授業のことを指す。未確定リスト業）という授業を時間割に入れることを考える。月曜

中にある全ての科目を順に調べていく。の 78 限、共通講義棟 3 号館 409 で開講すると決定し例えば、直前に時間割に入れた科目と、それと同じたとする。そうすると、他の未配置の科目の候補リス

学年で開かれる未配置の授業が、同じ日時にかぶらなトから（409、月曜、78 限）という要素が削除される。

いようにする制約は、(1) のように記述される。このまた、浅井先生担当の他の授業と２年生の他の授業の、ように書くと、一つの科目について部屋と曜日と時限

月曜 78 限の要素も削除される。

が決定すると、他の全ての同じ学年の未配置の科目のここまで進めると、実現可能な時間割が出力される、候補リストから、同じ曜日・時限の候補は削除される。

プログラムが出来上がる。

7

ここでは、他に、• 担当教官の同じ授業で、曜日・時限がかぶってい解空間の削減

ないか

何も方針を立てずに探索すると、探す範囲が広くな• 曜日・時限・部屋がかぶっていないかり、解が得られるまでに時間がかかる。また、良い解が求めにくくなる。そこで、以下のような工夫をした。

• 二時間続きの授業では続けて同じ部屋が確保出来るか• 探索する範囲を狭めるために、1 年生の授業は現在の（実際に今使われている）時間割で固定する。

• 計算機室と講義室を両方使用する授業では同じ曜日・時限で二室が確保出来るか（1 年生の授業をどう配置するかは基本的に自由なので、固定してしまって問題ない。）具体的には、未確定リストの中で、1 年生の授業の候補リなどの条件を考慮している。これ以外の制約も、上のよ

ストには一通りだけ部屋と日時の組み合わせを入うな形で制約を記述するだけで、加えることができる。

れておく。

9

• LA、体育、教職科目は開講日時が決まっているので、これも固定する。

このプログラムは OCaml を使い、Mac OS X バー
ジョン 10.5.2 （プロセッサ 2.4GHz、メモリ 2GB）に• 水曜日は非常勤講師の授業が入ることが多いので、候補リストから除外する。て実行した。上記の制約以外にも、各先生の希望を反映出来るよう色々な制約（午後の連続授業は避ける、一日に授業は一つまで、特定の曜日は都合が悪い、な• 授業が一つ決まる度に、未確定リストの中身を、ど‥）を入れた。大学院の授業も含めて探索しても、候補の少ない順に並べ替えた。これによって、早いずれもすぐに解が出てくる状態である。また、現状い段階で後々行き詰まることになる解を探索せず

は理学部３号館 504・理学部２号館 507・共通講義棟にすむ。

8

実験

３号館 408・409 以外の部屋も使用しているが、出力された時間割では、この四部屋で収まっている。

制約記述言語今後、膨大な解の中から、より良い解を探す方法を

うまくプログラムを再構成すると、制約のみを記述探してみたい。また、誰にでも使いやすいプログラムすることができる。先生の都合、各科目の都合‥など。となるよう、制約記述の方法を改善したい。

10