Journal of National Fisheries University 72（2）53-66（2023）

本論文

水産大学校の授業時間割の自動編成に関する基礎研究
徳永憲洋1†

Basic research for automatic constructionof course timetables
in National Fisheries UniversityKazuhiro Tokunaga1†
Abstract : Since the construction of class timetables in the university requires a great deal of effort and time, manystudies have been conducted in Japan and abroad on the automatic construction of class timetables. Similarly, at
the National Fisheries University, labor and time are devoted to the creation of class timetables. Therefore, authoraims to conduct basic research on automatic timetable construction with the simulated annealing method in thisstudy. This paper describes the proposed method and algorithm for generating timetables using the simulatedannealing method. The generated timetables by the proposed method are also reported.
Key words : timetabling problem, simulated annealing, automatically construction, optimization problem

序論

いる 2,3,4,5)。他方，シミュレーテッドアニーリングや遺伝的アルゴリズムなどの最適解探索法を用いた時間割編成も提高校や大学などの授業時間割の編成は，クラス，教員，施案されている 6,7)。シミュレーテッドアニーリング（SA:設（教室など）などについて各々の条件やスケジュールをSimulated Annealing）法や遺伝的アルゴリズムは，どち全て考慮し，なおかつ矛盾なく組み立てる必要がある。まらも代表的な確率的最適化法として知られており，どちらた，授業間の教室の移動距離や必修科目と選択科目の配置の方法も局所解に陥りにくく大域的最適解を求めやすい特バランスなどの配慮や学校特有のルールなども考慮して編徴を持つ。

成をする必要も出てくる。このように授業の時間割編成で水産大学校における授業時間割編成においても教職員のは上記のような制約を全て考慮し矛盾なく時間割を組み立時間と労力が割かれている。水産大学校の教員は，教員やてる必要があり，その編成においては多くの時間と労力が教室の数などのリソースに相当の制約がある中で授業を担費やされている。このため，編成の労力と時間を短縮する当・実施せざるを得ない状況にある。例えば，教員は他学ために国内外において授業時間割の自動編成についての研科あるいは所属学科も含めた複数学科で開講される授業を究が多くなされている。一般的に授業時間割の編成に関わ担当する場合がある。さらにこの場合は多数の受講人数をる課題は，時間割編成問題（Timetabling problem）と呼収容できる教室が必要だが，そのような大規模な教室は少ばれており，組み合わせ最適化問題として捉えて研究がなない。さらに足りない講師については非常勤講師を雇うこ1)されている 。時間割編成の自動化方法のひとつとしては，とで対応するが，非常勤講師は曜日や時間などの制約があ時間割編成問題を目的関数と制約条件に定式化し整数計画る。このように，水産大学校の授業編成では，制約条件の問題として解を求める方法があり，多数の研究がなされて縛りが厳く編成の自由度が低いため，すべての条件をクリ

2023年10月31日受付，2024年1月26日受理
1 水産大学校海洋機械工学科（Department of Marine Mechanical Engineering, National Fisheries University）† 責任著者（Corresponding author）: tokunaga@fish-u.ac.jp

54

徳永憲洋

アする解はそう多くない。そこで本研究では時間割の最適解の探索法としてシミュレーテッドアニーリングを採用

水産大学校の時間割についてし，水産大学校の時間割編成を自動化するシステムの基盤

水産大学校は 5 つの専門学科（水産流通経営学科，海技術の開発・検証を目的とする。多くの最適化方法がある

洋生産管理学科，海洋機械工学科，食品科学科，生物生産

中でシミュレーテッドアニーリングに着目した理由は，大学科）と専攻科 2 課程（船舶運航課程，船舶機関課程），域的最適解を求めやすい特徴を持っていることと，プログ研究科で構成されている。このうち時間割編成に関わってラミング技術を持っているならば方法論を理解しやすく自くるものは，5 学科（以下，本科と呼ぶ）と専攻科 2 課程

動時間割編成のソフトウェアを自ら開発しやすいこと，のである。研究科の時間割編成は，本科と専攻科の時間割編二つが挙げられる。特に後者に関しては，筆者以外の教職成が終わったのちに，研究科担当教員の都合を考慮して作員が時間割編成の自動化に関わりたいと考えた場合に理解成される。本研究は，自動時間割編成のシステムの基盤開と開発が容易になると考えたためである。本稿では，
シミュ発を主目的としているため，まず本科の時間割編成だけにレーテッドアニーリングを用いた水産大大学校の授業時間焦点を当てる。次に時間割について説明する。時間割は割の自動編成について枠組みやアルゴリズムの説明をす

90 分の授業を 1“コマ” と定義すると，平日月曜日から金る。また開発したアルゴリズムで作成された時間割の結果

曜日までの曜日毎に大きく 5 個のコマに分割でき１週間についても示し，時間割の自動生成について検討をする。

では 25 コマとなる（図 1 参照）。また本科は 4 学年 5 学科の体制なので，本研究ではクラス数が 20 クラスあると

Figure 1 Timetable structure in National Fisheries University

水産大学校の授業時間割自動編成

55考える。以上を踏まえると，時間割の編成とは 25 × 20成する。前，後学期ともに全クラスで約 100 の授業が開のマス目にそれぞれ授業を配置していくことに等しい。こ講される。また教員の数は法非常勤講師の数も含めると約こで，実際の水産大学校の時間割は，1 時限を 45 分で分100 名である。ここで，水産大学校では，コース科目と呼けているが，ほとんどの授業が上記のように 90 分を 1 コばれる授業がある。これは 1，2 年生で開講される共通科マとする単位で授業配置が行われているため，本研究につ目をまとめた科目である。共通科目とは英語や体育など学いても 90 分を 1 コマとして，時間割編成を考慮する。

科毎の専門科目ではない一般科目に相当する授業であり，時間割は前学期と後学期の 2 学期それぞれで別々に作

特に 1，2 年生で多く開講される。学科毎それぞれで一般科目を開講するとなると多くの授業担当教員が必要となるが，水産大学校においては一般科目を担当できる教員の人数が限られていることから，1 学年の学生を 4つのコース（グループ）に分け，授業単位ではなくコース単位で時間割に組み入れている。例として，令和 4 年度の前学期の 1年生の授業時間割の一部を図 2 に示し，図を使いながら以下説明をする。図 2 の赤太枠で囲った表がコース科目である。表の行方向に A 〜 Dの４コース，列方向に６個のコース科目（I）〜（VI）がある。各コースには共通科目である外国語や体育などの授業が配置されている。そして，時間割にはそれぞれのコース科目を１コマとして当てはめている（図 2 青太枠で囲ったコマ）。このコース科目の時間割への配置が特殊であるため，本研究における授業時間割作成は単純に 25 × 20 のマス目に授業を割り当てることができず，自動化を困難とさせている要因の一つである。また教室については，授業ごとに受講する人数が異なるうえに，講義棟の教室の数やキャパシティが限られていることも，授業配置における制約のひとつとなる。例えば，水産大学校の1学年当たりの学生数は約 200 名である。
よってコース科目内の一部の科目や全学科で開講される科目は約 200 名の学生が入る教室が必要となるが，そのような教室は 1 室しか存在しない。また新型コロナウイル
ス感染症などの感染症への対応では室内が密とならないような配慮も必要となり，さらに教室のキャパシティによる制限は厳しくなる。また非常勤講師においては出勤できる曜日や時間帯が限られることから，教員毎の授業可能日時の制約も考慮して時間割を編成する必要がある。

時間割編成の評価関数の定式化について先に述べたように，本研究で取り扱う時間割編成は 25× 20 のマス目に授業を割り当てる作業である。しかし各マス目には，授業科目，教員，教室の情報も入ることになる。これを数学的に考えると，時間割とは，クラス，コマ（時間），授業科目，教員，教室の 5 つのモードからなる
Figure 2 An example of a course class of timetable

56

徳永憲洋

テンソルとして考えることができる。具体的にはクラス，の元，目的関数が最小化，あるいは最大化するような Xコマ（時間），授業科目，教員，教室のそれぞれの概数が，を求める，ということになる。最適なX を求める方法は，

20，25，120，100，15 からなる巨大なテンソルである。

今日におけるまで様々に提案されている。X が連続的な

ここで，クラスは各学年の学科を表しており図１の行に相値を持ち，なめらかな関数（微分可能）の場合は，最急降当する。すなわち本テンソルは約 20×25×120×100×15

下法や山登り法などの勾配法に準じた方法を用いればよの要素があり，時間割が配置された要素に1が入り，他はい。時間割編成の場合は，X が 0-1 からなる変数である

すべて 0 となる，0 と 1 からなるスパースなテンソル（5ため，SA 法や遺伝的アルゴリズムなどの最適化法が適し次元の配列）だと考えることができる（図 3 参照）。ていると考える。本研究では，最も考え方が単純であり，すなわち，時間割編成とは，ある制約条件のもと，エネプログラミング開発も簡単だと思われる SA 法を時間割ルギー（ペナルティ）が最小となるように 0 と 1 の組み合編成の方法として導入した。次に，時間割編成問題におけわせを考慮する 0-1 組み合わせ最適化問題であり，その最る式 1 の目的関数と制約変数について説明をする。時間

適化の計算と更新プロセスは全てテンソルをもとに行うこ割編成問題を単純に考えると，ペナルティが最小となるよとが可能である。このような最適化問題では以下で示すラ

うな X を導出できれば良い。ここでペナルティとは，例

グランジュ関数を最小化する問題として考えることが多い。

えば，同時間帯のコマで一人の教員が複数のコマの授業を担当している，同一週内で同じ授業が複数回開講されている，など，時間割を編成するうえであってはならないような状況（罰則）を数値として定義したものである。すなわ

ここで，時間割編成問題で考えると，X は時間割を表

ち時間割編成における様々な制約条件を関数化したものがすテンソルであり，f(X) は目的 関数，g(X) は制約関数で制約関数であり，その制約関数は制約に従っていなければある。また λ はラグランジュ乗数と呼ばれる。制約関数

ペナルティの大きさを出力する関数だと考えれば良い。

Figure 3 Diagram of timetable tensor

水産大学校の授業時間割自動編成

57

よって単純に式 1 における制約関数をペナルティの総数素が 0 であるスパースなテンソルであるため，定義したとするだけでも良い。ペナルティの数値の求め方は定式化

式のまま実装をすると計算時間が無駄である．このため，することが好ましいが，難しい場合は開発者が独自で考え計算時間を向上させるのであれば，計算アルゴリズムを工た方法でもかまわない。本研究ではこの考えに従い，いく夫したほうが良い。

つかのペナルティ項を定式化し，ペナルティの総数をSA法で最小化する方法を使用する。具体的には，以下の式を評価関数とし，評価関数が最小化するような X を求めることとする。

(1) どの授業もどこかのコマに必ず配置される。
このペナルティ項は，用意されている全ての授業科目は週内のコマのどこかに配置されていなければならず，どこにも配置されていない授業が存在する場合は，その授業数をペナルティと定義する。今，X の要素を x,l,p,r,c,t とする。
l，p，r，c，t はそれぞれ，授業科目，教員，教室，クラここで, I はペナルティ項の総数を表し，Pi(X) は i 番目のペナルティ項から算出されたペナルティとする。またス（学科やコース），コマ（時間帯）のインデックスを表す。
本ペナルティ P1(X) は以下のように定義できる。

wi は i 番目のペナルティ項に対する重みを表す。重みの値が大きければそのペナルティを重要視するようになる。

(3)

本研究では次の４つのペナルティ項を定義した。
ここで，sign(・) は符号関数（signum 関数）である。
(1) どの授業も必ずどこかのコマに配置される。

符号関数を用いる理由は，授業科目によっては複数の教員(2) 同じ教員が同じ時間帯において複数のクラスで授業をが担当したり，複数の教室を利用する場合があるためであ受け持たない。

る。

(3) 同じ部屋で複数の授業は開講できない。
(4) 開講制約のかかっているコマには授業は配置できない（あるいはできる限り配置しない）。

(2) 同じ教員が同じ時間帯において複数のクラスで授業を受け持たない。
同じ教員が同じ時間帯で複数のクラスで授業を受け持っ(4) の制約では，授業によっては開講できない曜日，時間ている数をペナルティとして定義する。本ペナルティ帯があったり，教員によっては授業が困難となる曜日，時P2(X) は以下のように定義できる。

間帯があるので，それらをまとめて，本稿では開講制約と呼ぶことにする。
ほかにも，週内に同じ授業が複数回開講できない，同じコマに複数の授業は配置できない，といった強い制約を一(4)(5)

般的には定義する必要があるが，本研究では，これらの制約を後述するコマ配置のアルゴリズムで回避するようにしているため，ペナルティとして定義する必要がない。
また本研究では基礎的な研究が目的であるため，授業時

Re(・) は正規化線形関数（ReLU 関数）を表す。この式から導出される値は，同一時間帯のクラスにおいて複数の授業の担当が割り当てられた教員の数に等しい。

間割を生成する上で必要不可欠である制約条件だけを取りここで，コース科目や複数クラスで開講される授業科目扱う。しかし実際の運用を考えると，教室の移動距離や教については，別途対策が必要となる。これらの授業科目は員が連続して授業を行わないなどの人間的な配慮もペナル

同時間帯に複数クラスで開講されるため，テンソル X にティ項として含めたほうがより人間が編成する時間割に近は同時間帯において複数のクラスで同一教員の要素が1とくなると期待できる。

表現することとなる。このまま式 4 で計算をすると，コー以下にそれぞれのペナルティ項の定義を示す。なお本研

ス科目はペナルティとしてカウントされてしまうので別途究において，以下のペナルティ項については定義した式の対応が必要となる。対策の一例としては，このような複数ままプログラミングで実装をした。しかし X は多くの要のクラスで開講される授業科目については，Xの要素とし

58

徳永憲洋て 1 を入れるのではなく，1/Ncl（Ncl は l 番目の授業にシミュレーテッドアニーリング法おいて開講されるクラス数）とすることで，上式を利用した対応が可能となる。

SA 法は，S. Kirkpatrick, C. D. Gelatt, M.P.Vecchi ら，および V. Cerny が考案した方法 8,9) で，大域的最適化問題の解を見つけるための汎用的な確率的アルゴリズムであ(3) 同じ部屋で複数の授業は開講できない。
同じ部屋で複数の授業が開講されている部屋数をペナルり，大域的最適解に対して，良い近似解を得ることが分かっティとして定義する。本ペナルティ P3(X) は以下のようにている。SA 法は，金属の錬成における “焼きなまし” か定義できる。

ら名前が付けられており，解探索の初期では確率的に状態遷移する確率（温度）を高めに設定し，徐々に温度を下げ(6)ていくことで，大域的最適解を見つけやすくする，という方法である。一般的な勾配を利用した大域的最適解を探索(7)する方法に比べ局所解に陥ることが少なく，理論的には大域的最適解を見つけることが可能であることがわかってい

本ペナルティについても，複数のクラスで開講される授業科目についてはペナルティ項（2）と同様の対策が必要る。
具体的な方法論について説明する。SA 法の説明については様々あるが，本稿では 10) の解説を参考にした。まず，である。

求めるべき評価関数を E(x(k)) とする。x(k) は更新ステッ(4) 開講制約のかかっているコマには授業は配置できない

プ k における状態を表す。本研究の時間割編成を例とす（あるいはできる限り配置しない）。

れば，式 2 の L(X) が E(x(k))，テンソル X が x(k) に相当

授業，あるいは教員の都合により，開講が困難となるコする。SA 法の目的は，x(k) の状態を初期状態から次々とマも生じる。例えば，教員によっては，会議が火曜日の午確率的に推移させ，最終的に評価関数 E が最小（あるい前中に毎週入るため火曜日の午前中は授業を開講したくなは最大）となる x(k) を発見することである。SA 法のアルい，などの開講に関わる制約が生じる。このため，開講制ゴリズムでは，生成関数，受理関数，徐冷関数の 3 つの約を考慮した授業配置を考えなければならない。そこで開関数が重要な役割を果たす。

講制約のあるコマに授業が配置された場合はペナルティを算出するように定義をする。

まず生成関数は現在の状態 x(k) を与えられて，次に推移する状態 x′(k) を，確率分布 G(x,x′) に従って返す関数でまず，S を開講制約テンソルとして定義する。S = {sl,c,t}ある。組み合わせ最適化問題の場合は，x′(k) は x(k) の近は授業科目 l，コース c，コマ t からなる l × c × t テン傍となるように推移させるのが好ましい。もし状態推移がソルであり，l 番目の授業においてクラス c および t 番目等確率で推移する場合は，確率分布は以下の式となる。のコマに制約がかかる場合は 1，かからない場合は 0 が入る。また，ゆるい制約をかけたい場合は（できるだけ開講したくない，などの場合），0〜1 の間の数値を入れてもよここで n(x(k)) は状態 x(k) の近傍にある状態の数を表す。

い。
開講制約テンソルを利用し，ペナルティ項（４）のペナ等確率で推移する場合は，上式を用いて新しい状態を生成するのが一般的であるが，本研究における時間割編成のルティ P4(X) 計算は以下のように定義する。

場合は，組まれた時間割の状態の近傍を把握することが困(8)

難であることと，近傍の状態が通常はあり得ない時間割の状態になっていることも多いため，上式を利用した生成はしない。詳しくは後述する。
次に受理関数は，現在の状態 x(k) の評価関数 E と，状態 x′(k) の評価関数 E′を計算し，その差をもとに次の状態 x′(k) を受け入れるかどうか（真偽値）を返す関数である。

水産大学校の授業時間割自動編成

通常は以下の Metropolis の方法が受理関数として用いられる11)。

59

れば手順 1 に戻る。
手順 4

徐冷関数によって Tk を更新。

手順 5

基 底状態であるかどうか判定し，基底状態であれば終了，そうでなければ k = k+1として手順 1(10)に戻す。

T は温度であり，評価値が増大する方向への推移確率

アルゴリズムにおいて手順 1〜手順 3 は，現在の温度でに影響を与えるパラメータである。すなわち温度が高い場平衡状態が実現されるまで十分な探索を行う。各温度で十合は状態 x′(k) が状態 x(k) よりも評価値が悪くても，x′(k)分に探索を行うことで大域的最適解に至ることが保証されに推移する確率が高くなり，反対に温度が低い場合は，評る。一般的に，十分に多くの解が生成されたと考えられる価値が改善される状態へと推移する。上式は，評価値の差状態になれば平衡状態と呼び，さらに平衡状態となった場分が 0 より小さい場合は新しい状態を採択することにな合に収束された解が得られている状態を基底状態と呼ぶ。

る。一方で，評価値の差分が 0 以上の場合，式中の下段

通常は，一定回数手順 1〜手順 3 を繰り返すことで平衡状の確率 p で新しい状態が採択されることになる。これを態とし，各温度で平衡状態なった際に受理された解の個数プログラム上で実現する場合は，区間 [0,1] の一様乱数 ξが一定個数となったときに基底状態とする。本研究では手を発生させ，p > ξの場合に新しい状態を採択するように順 1〜手順 3を 30 回程度繰り返すことで平衡状態とした。

設計すればよい。
次に温度 T は徐冷関数によってスケジューリングされ時間割の自動編成のアルゴリズムについてる。徐冷関数として利用される関数は，最適解の漸近収束性を保証するためには，以下の式よりも急速に冷やしてはならない（T0 は初期温度を表す。）。

本研究では，時間割の自動編成法として SA 法をベースとしたアルゴリズムを提案する。本手法は SA 法に準じた手法ではあるが，生成関数における状態の生成は授業時間割編成に即した本研究独自の生成方法である。簡単に

しかし，上式でスケジューリングすると，長い時間計算を述べると，人間が時間割編成をするならば，時間割に配置する必要があるため，運用上は，以下の式を用いることがされた授業科目を制約に矛盾していないかを考慮し，矛盾多い。

しているようであれば，授業科目を別の授業科目と入れ替えをする。それを繰り返すことで，最終的に最適解が導き出される。この人間が行う授業配置のプロセスを本生成関数では取り入れているところが，本研究独自だと言える。

なるべく γ は 1.0 に近い値にし，ゆっくりと温度を下げまたコース科目については，コース科目の中まで考慮したるように設定したほうが最適解にたどりつきやすい。

生成はアルゴリズムが複雑になるため，本研究では複数教

SA 法の基本アルゴリズムの手順を以下に示す。

員，複数教室，複数学科で開講されるひとつの科目として扱うこととした。時間割の自動編成をする前に予めコース

手順 0

k = 0, 初期温度 T0 の設定，初期状態 x(0) の設定，科目の編成を手動で行う必要があるが，本自動編成アルゴ

初期評価値 E(x(0)) の計算。

リズムの枠組みでもコース科目を問題なく時間割編成に組

手順 1

生成関数で次に推移する状態 x′(k) を生成する。

み込むことが可能となった。

手順 2

受理関数に従い，新しい状態 x′(k) を採択するか以下に，時間割自動編成のアルゴリズムを示す。

どうかを決める。採択の場合は新しい状態へと推移させる。
手順 3

手順 0

k = 0, 初期温度 T0 の設定，初期時間割テンソル

現温度で平衡状態となったかどうかを判断する。

X(0) の設定，初期評価値 E(X(0))の計算。

平衡状態と判断されたら，手順 4へ，そうでなけ

手順 1 生成関数で次に推移する時間割 X′(k) を生成する。

60

徳永憲洋

手順 2

受理関数に従い，新しい時間割 X′(k) を採択する目なので，授業科目の配置とともに科目に紐付けられた教かどうかを決める。採択の場合は新しい時間割員の状態も 1 とする。(5) では，授業科目によって開講でへと推移させる。

きる教室が限られている場合については，(4) と同様に，現温度で平衡状態となったかどうかを判断する。

科目に紐付けられた教室の状態を 1 とする。このような平衡状態と判断されたら，手順 4へ，そうでなけ

授業科目には，例えばマルチメディアセンターを利用するれば手順 1 に戻る。

情報科学や実験室や実習工場などを利用する実験や実習，

手順 4

徐冷関数によって Tk を更新。

そして受講人数が 150 人を超えるような授業科目が挙げ

手順 5

基 底状態であるかどうか判定し，基底状態であられる。他の授業科目は受講人数の規模に応じて提案できれば終了，そうでなければ k = k+1として手順 1

るいくつかの講義棟教室をランダムに配置する。

手順 3に戻す。

初期時間割状態の設定と生成関数での状態設定において，上記のような制限をかけることで，探索する空間が制

通常，初期状態の設定は乱数を用いてランダムに設定さ限でき，基底状態を発見するまでの時間を短縮できる。

れる。しかし，時間割の場合，完全に乱数で設定すると，ただし，上記のような制限によって，生成関数のプログ基底状態になるまでかなり計算に時間がかかる。これは生ラム設計は工夫をする必要がある。通常では状態（0 と 1成関数での新しい時間割 X′(k) の生成においても同様であの配置）を乱数を利用してランダムに設定するだけでかまる。そのため，本研究の時間割編成においては次に挙げる

わないが（現状態の近傍でランダムに設定，という制限は制限の範囲でランダムに状態を設定するようにすることあるが），時間割の場合は上記のような制限をかけるため，で，計算時間を短縮するようにした。

そのような簡便な状態設定はできない。以下に生成関数の処理を処理 1，処理 2，処理 3 の３つに分割し，それぞれ(1) 授業科目の配置は開講されるクラス内に限定する。の具体的な処理内容を説明する。

(2) 週内に同じ授業が配置されないよう制限する。

生成関数：処理 1(3) 同じコマで複数の授業科目が重ならないように配置する。
(4) 担当教員は授業科目に紐付けて配置する。

どこのコマにも配置されていない授業科目があるかどうかで分岐をする。コマに配置されていない授業科目がある場合は処理 2 へ，ない場合は処理 3 へ進む。

(5) 教室が固定されている授業科目は科目に紐づけて配置する。もし固定されていなければランダムに教室を配置する。

生成関数：処理 2
時間割のコマに配置されていない授業科目がある場合は，その授業科目を開講クラス内でランダムに配置する。

(1) では，科目毎に開講されるクラスはすでに決まってい具体的には時間帯をランダムに選択し，開講されるクラスるので，決められたクラスの中でランダムに配置するようと選んだ時間帯のコマにその授業を配置する。もし，配置限定をする。(2) では，授業科目が週内で複数開講されるするコマにすでに他の授業科目が配置されている場合は置ことはないので，一度配置をした授業科目がほかのコマでき換える作業をする。具体的にはコマにもともと配置され配置されることがないよう限定をする。ここで (2) の限定ていた授業科目の情報（授業科目，担当教員，教室）を全をすることで，週内で複数の授業が開講されることがないて 0 にし，新しい授業科目の情報を 1 にする。そして，ようペナルティ項として設定をする必要がなくなる。言いもともと配置されたいた授業科目は，開講されるクラス内換えるとわざわざペナルティ項の計算をする必要もなくなの空コマ（授業が配置されていないコマ）がある場所に再り計算時間の短縮となる。(3) では，同じコマ（同一の時配置をする。もし空コマがない場合は何もしない。その後，間帯とクラス）において，複数の授業を配置しないよう制処理 3 へ進む。

限をする。状態の配置においてこのような制限をかけておけば，(2) と同様，ペナルティ項として制約条件を設ける

生成関数：処理 3

必要もなく，計算時間の短縮となる。(4) では，授業科目ここでもさらに処理の分岐がある。開講制約があるコマの担当教員はすでに決まっており，尚且つ，固定された項に配置されている授業科目が存在するならば，その授業科

水産大学校の授業時間割自動編成

61目を同開講クラス内においてランダムに配置させる。配置

できた。このことから，本提案手法は約 10% で時間割生処理の具体的な内容は処理 2 と同様である。また開講制成を失敗するが，約 90% 程度で最適解に収束することが約があるコマに配置されている授業科目が存在しないなでき，十分利用できることが示唆された。

ら，時間割に配置されている全ての授業科目からランダム計算時間については，本研究で利用した計算機ではに選択し，選択された授業科目を同開講クラス内において2000 回のシミュレーションで 30 分程度の時間を要した。

ランダムに配置させる。配置処理の具体的な内容は処理 2

そのため 300 回程度で最適解が生成された場合は約 10 分と同様である。ここの工夫は開講制約があるコマに配置さ程度で時間割が生成できた。

れた授業科目を優先的に移動配置させることで最適解を導きやすくさせている。

ま と め

以上が生成関数の処理の内容である。生成処理関数以外は SA 法と同じ処理となる。

本研究では，水産大学校の授業時間割の自動生成をする方法としてシミュレーテッドアニーリング法を採用し，そ提案したアルゴリズムを用いた時間割の自動生成の検証実験の授業時間割自動生成のアルゴリズム構築を試みた。その結果，提案した方法によって時間割が自動的に生成できることが確認できた。また本研究ではシミュレーテッドア

提案した自動時間割編成アルゴリズムを開発し時間割をニーリング法における生成関数部のアルゴリズムに工夫を生成させた。開発は Mathworks 社製の Matlab で行った。

加えることで，最適な授業時間割の解が生成しやすくさせ

開 発 お よ び 実 行 を し た 計 算 機 は，OS が windows 10た。また計算時間も抑えることができた。ただし解の生成64bit，プロセッサが Intel Core i9-9920X（3.50GHz），メにおいては，局所解に陥る場合もあった。局所解に陥った

モリ 128GB である。

場合は，再度，シミュレーションをし直すことで対応が可

また提案する自動時間割編成アルゴリズムで，時間割を能であるが，局所解になるべく陥らないようなアルゴリズ編成する際には，予め授業科目や担当教員，開講制約等のムの工夫も今後必要だと考える。本研究の今後の展開とし情報をデータベースとして作っておく必要があるため，ては，人間的な配慮を制約条件に含めること，実用化に向Microsoft Excel を用いてデータベースを作成した。本検けたユーザーインターフェースの開発をすることが挙げら

証では令和４年度の授業時間割を参考にデータベースを構れる。特に実際での運用を考えると，本手法の利用を前提築した。また非常勤講師などの授業可能日についても令和としたデータベース構築が必要となる。データベースの構４年度の情報を適用した。コース科目についても同様に令築は一般的には難しく入力ミスも多くなるので，ユーザー和４年度の時間割のコース科目編成を適用した。

インターフェースなどを利用することで運用がしやすくな

一方，SA 法においては，T0 = 100，γ = 0.99 と設定しると考えられる。てシミュレーションを行った． ステップ数 k が 2000 になるまでシミュレーションを繰り返すようにし，もし謝E(X(k)) が 0 となれば，その時点で基底状態になったとみなしシミュレーションを終了した．

辞伊澤瑞夫氏（当時，水産大学校特命准教授）には授業時生成した結果の一例を図 4 と図 5 に示す。図 4 は，本間割編成について多数の助言を頂いた。また水産大学校教提案手法で自動的に生成された前学期の授業時間割，図 5務課にも情報提供に関して協力を頂いた。この場でお礼をは後学期の授業時間割を示す。どちらにおいても本研究で申し上げる。

設定した制約条件の総ペナルティが 0 となる時間割が生成された。また 10 試行の生成を行ったうち 1 試行が2000 回のシミュレーションを行ってもペナルティが 0 に参考文献なることがなく，最適な授業時間割を生成できなかった。

1) Chen M C, Sze S N, Goh S L, Sabar N R, Kendall G: A

一方で 9 試行については約 300 回の繰り返しシミュレー

survey of university course timetabling problem:

ションでペナルティが 0 になり最適解に収束することがperspectives, trends and opportunities. IEEE Access, 9,

62

徳永憲洋

106515-106529 (2021)

7) Beligiannis G N, Moschopoulos C, Likothanassis S D: A

2) 大坪正和，倉重賢治，亀山嘉正，久保貴広: 中学校時間

genetic algorithm approach to school timetabling.

割編成問題における制約条件の重み付けの自動調整. 日

Journal of the Operational Research Society, 60(1), 23-42

本経営工学会論文誌，61(5), 293-301 (2010)(2009)

3) 柿本陽平, 高橋弘毅, 島川陽一: 制約充足問題を線形計画

8) Kirkpatrick S, Gelatt C D Jr., Vecchi M P: Optimization法で解く場合の制約条件の緩和とその評価-時間割編成

by simulated annealing. Science, 220(4598), 671-680を例に. 日本経営工学会論文誌，66(4)，348-354 (2016)(1983)

4) 堀 尾正典：汎用プロジェクトスケジューラの大学時間

9) Cerny V: Thermodynamical approach to the traveling割問題への適用．名古屋学芸大学教養・学際編・研究

salesman problem: An efficient simulation algorithm.

紀要，4，61-74 (2008)

Journal of Optimization Theory and Applications, 45, 41-51

5) 伊藤美登，佐々木美裕，鈴木敦夫，伏見正則: 大学時間割編成モデルの研究. アカデミア. 情報理工学編 : 南山大学紀要，12，87-98 (2012)(1985).
10) R osen B E, 中野良平: シミュレーテッドアニーリング :基礎と最新技術. 人工知能学会誌, 9(3), 365-372 (1994)

6) Aycan E, Ayav T: Solving the course scheduling11) M etropolis N, Rosenbluth A W, Rosenbluth M N,

problem using simulated annealing. In: Proceedings ofTeller A H, Teller E: Equation of state calculations byIEEE International Advance Computing Conference,

fast computing machines. Journal of Chemical Physics,IEEE, 462-466 (2009)21, 1087-1092 (1953)

水産大学校の授業時間割自動編成

Figure 4(a) Timetable for the first semester automatically generated by the proposed method

63

64

徳永憲洋

Figure 4(b) Timetable for the first semester automatically generated by the proposed method

水産大学校の授業時間割自動編成

Figure 5(a) Timetable for the second semester automatically generated by the proposed method

65

66

徳永憲洋

Figure 5(b) Timetable for the second semester automatically generated by the proposed method