章 時間割編成問題

中央大学大学院理工学研究科情報工学専攻 修士論文

時間割編成問題に対する近似解法の研究

入学年度 年

学籍番号

久保田 敬

指導教員 田口東 教授

年月

概要

世界中の全ての高校 大学にとって時間割編成は重要な問題である

大規模な時間割を手作業で編成することは困難であるため 人間の負担を減らすために 計算 機をもちいて自動的に時間割を組む研究がなされている 年以上前からこの問題を解くための アルゴリズムの提案がされてきており 時間割編成問題に関する国際会議も開かれている しか し 授業時間割編成問題は 国による違い さらには大学による違いがあるため 汎用的な解決手 法を確立することは難しいといわれている

歳人口の減少に伴い 大学の選択に関する学生の目も厳しくなってきていることから 日本 の大学は 学生のニーズにより的確に対応したプログラムの提供が求められている その一つと して所属学科以外の教科を選択し履修することが可能な時間割という案があるが そのような時 間割を作成するには 学校全体で一括して時間割作成をおこなう必要がある しかし 対象規模が 大きくなるにつれ 計算量が増大してしまう このような問題が 授業構成を考える上で新しい時 間割を提案 作成することの足枷になっていると考えられる

本論文では 計算量を減少させるような教科 時間割モデルの提案 大規模な時間割作成問題に 対して 実用的な時間で良い結果を求めることができる探索手法の提案と実装をおこなう

キーワード 時間割編成問題 メタヒューリスティックス タブー探索法 近傍

目 次

第章 序章

研究背景と目的

本論文の構成

第章 時間割編成問題

時間割編成問題

組合せ最適化問題

多目的最適化問題

時間割編成問題の種類

第章 メタヒューリスティックスの基礎概念

メタヒューリスティックス

近傍

局所探索法

多スタート局所探索法

遺伝アルゴリズム

タブー探索法

ディスパッチング

第章 タブー探索法を用いた解法

制約条件の設定

制約条件

変数の設定

提案教科モデル

各学科の必修教科が重ならないように考慮

教室タイプの決定

教科の定義

時間割行列の作成

定式化

提案モデルの定式化

領域の定義

近傍の定義

実行不可能解

探索領域

初期解の生成

現在の解と近傍解の差分

現在の解と近傍解との差分値

時間割編成問題へタブー探索法の適用

近傍探索

提案手法

複数移動

実装

第章 中央大学理工学部を例とした実験

中央大学理工学部の時間割作成の現状

中央大学理工学部詳細データ

実験

タブー設定

パラメーターの設定

提案手法を適用し生成した初期解

初期解の値を変化させたときのによって得られる解

との比較

多スタート局所探索法を組み込んだ解法

各違反数の平均と分散

タブー長を変化させて実験

遺伝アルゴリズムを用いた研究との比較

教科が持つデータ 遺伝子情報

解を得るまでの全体の流れ

交配・突然変異

交配

突然変異 エリート選択

終了条件 実行 考察

生成された時間割の例

第章 結論

謝辞

第 章 序章

研究背景と目的

時間割編成問題（ は，スケジューリング問題の一種であるが，特に学校や 大学の講義の時間割，試験の時間割のようなスケジューリングをさすことが多い．

世界中の全ての高校 大学にとって時間割編成は重要な問題である

大規模な時間割を手作業で編成することは困難である 中央大学理工学部を例にすると人の 担当者が手作業で ヶ月の期間をかけて製作している 人間の負担を減らすために 計算機をもち いて自動的に時間割を組む研究がなされている 年以上前からこの問題を解くためのアルゴリ ズムの提案がされてきており 時間割編成問題専門の国際会議も開かれている^{! "} 時間 割編成問題は ^#$完全問題として知られ 厳密な最適解を求めることが困難であるので 厳密な 解にはこだわらず 実際の適用に差し支えない程度の解近似解 を効率的に求める試みがされて いる

歳人口の減少に伴い 大学の選択に関する学生の目も厳しくなってきていることから 日本 の大学は 学生のニーズにより的確に対応したプログラムの提供が求められている その一つと して所属学科以外の教科を選択し履修することが可能な時間割がある それぞれの学科で個別に 時間割を作成したあとに 学科を越えて自由に履修できる授業を配置するのでは より多くの都 合を考えることが困難になる 当然 全ての学科を一括して編成する方がより良い時間割になる ことが予想されるが 作成する時間割の規模が大きくなると計算量も爆発的に増えてしまう

時間割問題を解くにあたり 考慮に入れる要素が増えると 各教科に課せられる制約の数が増 える 例えば 連続授業を定義するには つの授業が連続しておこなわれるようにつの授業を 制約式で制御する必要があったり 複数のクラスが同じ授業を受講する場合も同様に 二つの授 業を同じ時間帯におこなわれるように制御する必要がある

逐次改良と変更をおこないながら時間割を作成していく場合 ある状態の時間割が良いものな のか判断するために 多くの制約を満たしているかどうか判定が必要であるため 判定する要素 の数が増えると計算量は増大する

本研究では 計算量を減少させるような教科 時間割モデルを開発すること 大規模な時間割作 成問題に対して 実用的な時間で良い結果を求めることができる探索手法を開発することを目的 とする

本論文の構成

章^% 本章では 研究の背景と目的を述べる

章^% 時間割編成問題を組合せ最適化問題の一種である 第章では 組合せ最適化問題に ついて説明 他の時間割編成問題の紹介をおこなう

章^% 近似解法であるメタヒューリスティック手法に関する説明をおこなう またその種類 である 近傍探索 多スタート局所探索法 遺伝アルゴリズム タブー探索法の紹介をおこ なう

章^% 第章ではまず大学授業の時間割編成問題の変数の定義 定式化をおこなう 次に教 科モデルの提案と 定式化した問題を解く手法を提案する

章^% 第 章で提案した手法の精度の比較実験 他の解法との比較実験をおこなう

章^% 第章では 結論を述べる

第

章 時間割編成問題

時間割編成問題

時間割編成問題は 組合せ最適化問題であり ^#$完全として知られる 以下本章は ^{! "}

を参考に説明する

組合せ最適化問題

組合せ最適化問題（ ^&$）は 変数 領域 制約 目的関数の

つの要素で定義される まず 個の変数 ^' とそれら変数のとる離散的な値の領 域を考える 次に変数に対して 目的関数 と 個の制約 ^' が与えら れているとする 組合せ最適化問題は これらの制約を満たすという条件のもとに 目的関数の最 適値を与える変数の値を決定する問題である

組合せ最適化問題とは 組合せ的な制約条件の下である目的関数を最小化（あるいは最大化）

する数理計画問題であり 一般に次のように記述される

()

は目的関数^{() *)} は基本空間 は実行可能領域^{* +}で こ れらの領域は 組合せ的 離散的なものである

可能領域が組合せ集合となる組合せ最適化問題では 実数集合を対象とした連続性や微分の概 念に基づく古典的な最適化手法を直接利用することはできない したがって 組合せ最適化問題 の解法は連続変数の最適化手法と本質的にことなるものとなり 一般に解を数え上げるという列 挙法的なアプローチとならざるを得ない しかし 組合せ最適化問題のほとんどは^#$困難とな ることがしめされており^{! "} 可能領域 の要素組合せの総数は膨大な数にのぼることが多 く これらをすべて列挙するのは現実に不可能である そこで厳密解を求めるのでは無く 限られ た時間で実用上差支えがない程度の解を求めようとする 近似解法が用いられる 最近では 計算 機の進歩に伴い 従来の近似解法をより高度に組み合わせるなどの方法により 多少時間はかかっ てもより良質の解を求めようとする メタヒューリスティックス^,)の研究が盛んで ある^!"

目的関数がなく制約を満たす解を発見する問題を 特に制約充足問題（^$%-

*)$）という ^$は 制約の充足度を目的関数と考えると 組合せ最適化問題と見 なすことができるが 次の特徴を有している

目的関数が明示的に表現できない

すべての制約を満たす完全解を求めることを目標とする（準最適解ではない）

解が得られたことを判定できる

多目的最適化問題

制約条件のもとでの最適化は 与えられた制約の集合のなかで満足する解を発見することであ り 解析的に定義された目的関数を最適化することである 問題の制約条件を満足する解が実行 可能解である 目的関数は 入力変数の各組み合わせに対して計算される 入力変数の値は ある 解から別の解へと探索が遷移するにしたがって変化してゆく 目的関数の値を最適にする解が最 適解である

単一制約条件つきの最適化問題は 実行可能解 の集合^.上で定義される 評価関数 を 最小化もしくは最大化することが目的である 以下最小化問題に関して説明する

実際の時間割編成問題の最適化問題は複数の目的関数をもつ問題である このような場合 通 常 たがいに相反する複数の評価関数 をどのように取り扱うかという 問題に直面する

単一目的関数をもつ最適化問題とは異なり 多目的最適化の場合には 普遍的に受け入れられ る最適化の概念というものが存在しない 実際の場合 個々の目的の順位が意思決定者の優先度 を決定する

多目的最適化問題を単一目的関数をもつ最適化問題に変換する際には 別の評価関数を定義し て 複数目的関数の個々の基準の重みつき和として表すことである

'

は正の重みで それぞれの基準の相対的重要度 または意思決定者の目からみた それぞれ の目標を表す より重要な基準には より高い重みが割り当てられる

時間割編成問題の種類

時間割編成問題の種類として 授業の時間割編成問題 試験時間割編成問題 ナーススケジューリング

などがある いずれも イベント授業や人 を時間帯×教室の空間に配置する問題である 制約 が多数存在するが それらは 時間帯×教室の上におかれる授業に関して 空間の部分空間上での 制約となる

第

章 メタヒューリスティックスの基礎概念

組み合わせ問題の最適解は実行可能解を全て調べあげることで 評価値が最も良くなる組み合 せを見つけることが出来る しかし組み合わせ問題のほとんどは実行可能解が無数に存在し 現 在のコンピュータでは全ての解を求めることは不可能であることが多い そこで厳密な最適解に はこだわらず 実際的な応用に差し支えない程度の解近似解 を効率的に求める近似解法が注目 され その研究が行われている このような中で 近年 基本的な近似解法のいくつかを組み合わ せる あるいは繰り返し適用することで より精度の高い近似解法を求めるための枠組みに対する 研究が盛んに行われている これらの枠組みに含まれる代表的な手法として 多スタート局所探 索法 シミュレーテッドアニーリング法 遺伝アルゴリズム タブー探索法などがあげられる こ れらはメタヒューリスティックスと総称される

本章では^{! "}を参考にして メタヒューリスティックス諸法の基礎となる近傍 局所探索法の 説明 上記の多スタート局所探索法 遺伝アルゴリズム タブー探索法について述べる

メタヒューリスティックス

最適解に近い近似解を実用的な計算コストで探索する手法の総称をメタヒューリスティックス

という 理論的な保証を持つものを近似解法 保証を持たないものをヒュー リスティックスとよぶ 信頼できるメタヒューリスティック手法は最適解が初期値の違いに影響 を受けにくいものである

近傍

解 になんらかのルールに基づいた 一つの遷移を施すことによって得られる解の集合を近傍

と呼ぶ

ほとんどの組合せ最適化問題では 遷移の数は問題の規模とともに 急激に増加する たとえば 単純な交換遷移の数は 問題の規模の乗で増加する より複雑な遷移の場合 遷移の数はさらに 急速に増加する可能性がある 問題 の近傍全体 が大きすぎて全てチェックすることが困 難な場合は 近傍の候補部分だけをチェックする チェックする近傍のサイズは 解の質と それを 得るための処理量とのトレードオフになる 通常近傍関係は対称であると仮定する すなわち が の近傍であれば は の近傍である

局所探索法

解 の近傍 において なんらかの順序で 内の解を探索し よりも良い解 目 的関数値を改善する解 があれば の更新をおこなう操作を繰り返す方法を局所探索法

とよぶ 局所探索法である降下法は最小化問題に対し常に最も改善される近傍解へ移動 させていく検索方法である 解^/ がその近傍解のなかで最も低い評価値をもつ場合 解^/ は局所 最小解となる 局所探索法により得られる解は 初期解に依存するため 初期解の設定を熟慮する 必要がある

図はある実行可能曲線を探索する様子をあらわしている この空間を例に局所探索法を説 明する ^{0 1} はそれぞれ局所最小解で 評価値は¹ の方が小さいとする 局所探索法により 評 価関数値が最も低くなる解の選択とその解への遷移を繰り返す探索に関して 同値の評価をもつ 点 と 点 ²を初期解としたとき 得られる解はそれぞれ ⁰と¹ になる 同評価値の初期解か ら探索をはじめた場合でも得られる解の評価値が同じようになるとは限らない

図 探索の例

多スタート局所探索法

なんらかの方法で生成した複数個の初期解に対して局所探索を繰り返しおこない 得られた解 の中でもっとも優れた解を出力する方法を多スタート局所探索法 という 探索により得られる解が初期解に依存してしまう局所探索法と比べ 複数の初期解を用 意することで 初期解の一部が良い解を得る可能性が高くなる 複数解の探索をおこなうので計 算量は増加する

今 図 の空間を探索することを例に説明する 初期解を ^{3 2 4} の個所としたとき

3 を初期解とした局所探索は ⁰に ^{2 4} を初期解とした局所探索は ¹ に収束する よって これらつの初期解から局所最適解¹ を得ることができる

遺伝アルゴリズム

生物界では 任意の生物種は移り行く環境変化への適応の善し悪しで何世代もかけて自然淘汰 される 結果として環境により良く適合した遺伝子を持った多数の個体からなる生物種が生き残 る この生物種の進化過程をほとんどそのまま真似る形で 数理的問題への適用を意図して解集 団を世代毎に逐次改良する解析方法を遺伝アルゴリズム （ ： ）という この手法は ⁵⁶ により考案された

遺伝アルゴリズムの個体解は記号列としてコード化することで表される 複数の解を集団と してもち その解に以下のような操作を加え改善していく

交叉^% 複数の解の要素を組み合わせ 新しい解を生成する

突然変異 ^% 集団の中から任意に解を選び それらの解を変形させて新しい解を生成する

選択^% 何らかの規則に従い次のステップに残す解を選択する 優秀な解を残すことや希少 な解を残すことなどがある 評価の低い個体は淘汰され除去される

この手法は 局所探索法や次節で説明するタブー探索法のように ある一点から規則に従い近傍 探索していく手法とは異なり 多点探索手法であるため 局所最適解に陥る確率が小さいという 利点をもつ しかし 解集団を保持し それらを同時に探索させることで 計算コストが高くなっ てしまうという欠点もある 図空間を例に遺伝アルゴリズムの探索を説明すると 点³と 点

を交叉させて点⁰が生成されるというようなプロセスで探索をしていく

タブー探索法

タブー探索法 は近傍探索を続けることにより 現在の解から近似解に到達で きる過程のもとで行うヒューリスティック手法である この手法は人間の脳の働きを真似た手法 で 探索経路を一定の間記憶することで ループして探索することを防ぎ 局所最適解を脱出する ことができる

記憶しておく期間は タブー探索法の重要なパラメーターであり タブー長 ^+,と 呼ばれる

タブー探索法は以下のような操作をおこない解を改善させていく

局所探索 ^%近傍内の最良解を選択して 遷移していく

最急降下^-最緩上昇 ^% 局所的探索手法とは異なり たとえ局所最適解に陥っても 改悪が最 も緩い解へ遷移し 近傍探索を続ける

記憶 ^% 探索がループすることを避けるために 遷移をおこなった解をタブーリストに書き 込みタブー長の間 その解への遷移を禁止する

図の空間を探索するにあたり初期解を³としたとき 局所探索によりまず局所最小解であ る ⁰点にたどり着く そこまでの道のりを記憶しておいて 改悪方向へ探索を続けていく

これらのヒューリスティックスは 探索が最適解に到達したのかどうか アルゴリズム自体が知 る術を持たないので これらのアルゴリズムに対して探索が終了する条件を設定しなければなら ない 以下^{! "}に従って述べる

「山登り」的性質をもっている すなわち これらのアルゴリズムは 山登り的評価関数を 悪化させる方向への遷移をときには採択する

プログラム化が容易である 必要なことは 解 評価関数 および探索空間を移動するメカ ニズムを 適切に表現することである

すべて「汎用的」である 実際 これらのアルゴリズムは どのような組合せ最適化問題に 対しても 適用可能である

すべて「よい」解からなる部分空間へ探索方向を向けてゆくために 問題に特有の経験的知 識を利用する 探索された部分空間の質は 利用した経験的知識量に大きく依存する 漸近的に最適解に収束するが 収束のスピードは 数多くのパラメーターをいかに適切に選 定するかに大きく依存する

ディスパッチング

ディスパッチング手法とは，作業者が仕掛かり待ちの作業の中から 任意の規則これを差し立 て規則という に従って 次に着手する作業を選ぶ差し立て方式に基づく手法である つまりディ スパッチングとは 未割り付け作業の集合を ^' ディスパッチングルール差し立て規則 を とすると から規則 を満足する一つの作業 を求めることである この手法は 解 の精度は良くないが計算量が少ない という特徴がありリアルタイムスケジューリング問題など に適用されている

ディスパッチングルール差立規則） の例

先着（⁴⁴，⁴⁷⁴）順^{!4 4 47 4"}

最小作業時間順（^$）^{!, $ )+"}

最早納期順（¹²²）^{!1 22"}

最小余裕時間順（⁸³⁹）

現時点より納期までの時間から残り総加工時間を差し引いた余裕時間 ⁸³⁹ が少ない ジョブを優先

'（納期現時点）残り総加工時間

第

章 タブー探索法を用いた解法

本章では タブー探索法を用いた大学の授業時間割のモデルと解法の提案をおこなう 対象は 月曜から土曜まで 限から限まで授業がある大学とする

制約条件の設定

制約条件

一般的に大学の時間割編成時に以下のような制約がある^{! "}

教師は同じ時間帯で重複して授業を受け持つことができない

クラスは同じ時間帯で重複して受講することができない

授業に適する大きさと適する種類の教室を選ばなくてはならない

教室数を超過して利用することはできない 教師の都合が悪い時間帯には教科を配置できない

連続授業は連続して配置しなければならない

ある授業を受け持つ教師が複数いるときは それぞれの教師の都合をあわせて授業を配置し なければならない

ある授業を受講するクラスが複数ある場合は それぞれのクラスの都合をあわせて授業を配 置しなければならない

全ての教科がスケジュールに組み込まれなければならない

教師の授業と授業の間隔はなるべく小さいほうが好ましい

クラスの授業と授業の間隔はなるべく小さいほうが好ましい

限にはなるべく授業を配置しない

同学科の低学年の必修科目と高学年の必修科目はなるべく重ならない方が好ましい

教師間での時間割に極端な優劣の差を無くす

クラス間での時間割に極端な優劣の差を無くす

上記のからまでは物理的に満たさなければならない制約条件である この制約条件のうち ひとつでも満たしていなければ 実行不可能な時間割となる このような制約をハード制約とい う から までは 必須では無いが なるべく満たすことが望ましい制約条件である このよ うな制約をソフト制約という ハード制約を完全に満たしながら ソフト制約を多く満たしてい る時間割が良い時間割となる

変数の設定 変数

% 行が曜日 列が時間帯を表す × 行列 この行列を時間割行列と定義する

% 教師の総数

% クラスの総数

% 教室のタイプの総数

% 一般教科の総数

% 教師可変型教科の総数 教師可変型教科とは 教師とクラスの組合せが指定されない 教科である 詳細は で説明する

% 教師可変型教科種の総数

% 学科の総数

% 曜日の集合

'% 月 ^% 火 ^% 土

% 時間帯の集合

'%限^%限 ^%限

% 教師の集合

'

'

% クラスの集合

'

'

% 教室タイプの集合

'

'

% 教科の集合

'!

' :

" # % 学科の集合

" # '$

$ '

% 行が曜日 列が時間帯を表す × 行列 この行列を時間割行列と定義する

%

% 教科^! を受け持つ教師群 ^%

% 教科^! を受講するクラス群

&

% 教科^! で使用する教室のタイプ ^&

'

% 教科^! の連続授業時間数

% 教師が 曜日 時間帯に受け持つ授業数

%

% %

'

を 行目 列に要素としてもつ行列

% クラスの曜日 時間帯に受講する授業数

%

'

を行目 列に要素としてもつ行列

% 教室タイプの曜日 時間帯における使用数

& % &

'

を要素としてもつ時間割行列

& % 教室タイプの数

(

% ! 教科が タイプの教室を使用する数

)%

% 教師 が 曜日に受け持つ授業時間帯の集合

)

% クラスが 曜日に受講する授業時間帯の集合

% $学科の必修科目授業が 曜日 時間帯で重複しておこなわれる数

* % 教師可変型教科種の集合

*'(

'

% 曜日 時間帯に教師可変型教科種⁽ を教えることができる教師の総数

%

%

を要素としてもつ時間割行列

* % 教師可変型教科^! の集合

% 教師可変型教科^! が所属する教師可変型教科種 ^(*

% 曜日 時間帯に教師可変型教科種⁽ の教師を必要とする数

*%

%

を要素としてもつ時間割行列

"

%

が所属する学科の集合

+

% 教師の時間割に関する最低限の水準値

+

% クラスの時間割に関する最低限の水準値

# % 制約数を表すベクトル^{# '}

% 各制約に課す重みベクトル 決定変数

% 各教科の授業開始時間をもつ行列 行目が曜日 行目が時間帯をあらわす ^* 教科の開始時間は

であらわされる

'

図 一般教科を構成する要素

提案教科モデル

各学科の必修教科が重ならないように考慮

学年の生徒が 学年 ^, の必修科目を 曜日 時間帯に再履修する状況において もし 学年において同じ曜日 時間帯に必修科目の教科履修が要求されている場合 学年 の生徒はどちらかの必修科目の履修をあきらめなくてはならない 必修教科の単位を修得するこ とは卒業条件でもあるので 速やかに履修できる状態であることが望まれる よって同学科間の 高学年の必修科目と低学年の必修科目の授業時間帯をなるべく重複させないほうが良い

曜日 時間帯に 学科 ^{$ " #} のクラスが受講する必修科目の授業数 を要素として もつ時間割行列を^" とする 必修科目教科^! を受講するクラス の所属する学科に対 し それぞれの学科が重複しないようにした集合を^"

" # と定義する 学科^$ の必修科 目の重複数 " "

が小さいほどよい時間割となる

教室タイプの決定

特別な機材を必要としない または特に使用する教室の指定のない教科 ^!は以下の方法で使用 する教室を決定する

&

'

#

-(

#

はクラスの在籍者数 ⁽ は教科 ^! が使用する教室の数を表す 教室タイプの収容人数 に関して 多い順番に ^{& &}

& とし その定員人数を ^{& &}

& と したとき 使用する教室タイプ ^&./ は ^&

0&

となる のうち最小の定員人数をもつ 教室タイプとして決定される

教科の定義

教科を 受け持つ教師が指定される一般教科と 受け持つ教師に指定が無い教科との 種類に 分ける

図 教師可変型教科を構成する要素 一般教科

一般教科は受け持つ教師があらかじめ取り決まっている教科であり 教師の数 受講するクラス の数 使用する教室の数 授業時間数 必修か選択かの 項目の要素からなる

一般教科 ^! は 受け持つ教師の集合 ^% 受講するクラスの集合 使用する教室タイプの 集合^& 受講するクラスの所属する学科の集合^" 連続授業時間数^' を要素として持つ構 造をしている 教師^% クラス 教室タイプ^&

$"

はそれぞれ各時 間帯に受け持つ授業時間数を表す時間割行列をもつ

教師可変型教科

ある教科を受け持つことができる教師が複数いる場合 誰がどのクラスを教えても良いことが ある 例えば 英語の教科などがある

教師可変型教科種は授業時間数をコマ 受講するクラスをクラスとする 教師可変教科種

( は複数の教師が受け持つことができ 特定の教師が特定のクラスの授業を受け持つように指定 されない

曜日 時間帯に教師可変型教科種 ^{( *} を教えることができる教師の数を

とする を要素としてもつ時間割行列を ^% とする 教師可変型教科 ^! はひとつのクラス を分割し 授業を複数おこなうことができる その分割する数を とする 教科 ^! が必要とす る教師可変型教科種 ⁽の教師の数を ⁽ とする

これらの変数には

'(

'(

(*

の関係がある

このつの教科モデルを合わせることで であげた の制約を 教科を定義する段 階で満たすことができることである 更に特殊な教科も一元的に扱うことができる上に 探索も 同時に行うことができる

図 一般教科の例

時間割行列の作成

各教科の授業開始時間帯を決定することで 以下の操作をおこない時間割行列を作成する

一般教科の場合

一般教科^! の授業開始時間が曜日 時間帯と決定すると その教科の構成要素である 教師

%

クラス の時間割行列^%

の 行目 列目から ^:'

列目まで を 同じく教室タイプの時間割行列 ^& の行目 列目から ^:'

列目まで⁽

を足す 必修 科目の場合 学科の時間割行列 ^"

$"

の行目 列目から^:'

まで足す 例として図 の教科について説明する この教科^! は ^{% ' '}

&

'で使用数 時間連続授業である 授業開始時間帯が木曜 限とあたえられた場 合 この教科を構成する各要素の時間割行列の 行目の 列目と 行目 列目の箇所に を 足す

教師可変型教科の場合

教師可変型教科 ^! の授業開始時間が 曜日 時間帯と決定すると 教科種 ^{( '} と 教 室タイプ ^& の時間割行列 の 行 列 に^{% &} に ⁽ を 教師 ^% クラス

の時間割行列^%

の 行目 列目に を足す 必修科目の場合 学科の時間割行列

"

$"

の行目 列目に足す

一般教科 教師可変型教科の全教科について以上の操作をおこなうことで 全ての教師 全ての クラス 全ての教室タイプ 全ての学科 の時間割行列を作成する 作成する様子をあらわしたも のが図 である

この時間割行列より各違反数を算出し 時間割の優劣を評価する

図 決定変数により各時間割が作成される様子 生成された時間割行列の例

%

'

定式化 目的関数

'

%

'

'

:

:

'

'

'

:'

%

,;

'

'

'

:'

,;

'

'

(

'

:'

&

,;

'

'

(

'

'

'(

,;

%

'

<

:

'

<

:

&

+

%

+

:

:

0

(*

は全教師の授業と授業の空き時間の合計 は全クラスの授業と授業の空き時間数の合計

は月曜から土曜の限 限と土曜日に受講するクラスの数 式 の は 曜日 時間 帯におこなわれる教師が受け持つ教科の和になる 式の は曜日 時間帯におこな われるクラス が受講する教科の和になる 式の は 曜日 時間帯におこなわれる 教室タイプ を使用される教科が必要とする教室数の和になる

式の は 曜日 時間帯におこなわれる教師可変型教科種 ⁽ の授業をおこなう教 師可変型教科 ^! が必要とする教師の数⁽ の和になる

曜日の教師 の授業間の空き時間数は 曜日に教師 が受け持つ最も遅い時間帯におこな われる授業の時限^<

から最も早くおこなわれる授業の時限

を引いてを 足し 曜日に受け持つ授業数を引くことで求まる 月曜から土曜までこの操作をおこなうことで 教師 の授業間の空き時間数 ^% が求まるということを式はあらわしている 式 は式と同様の操作をクラスに関しておこなうことで クラスの授業間の空き時間数 が 求まる

教師 は各時間帯で複数の授業を受け持つことができないということを式であらわし ている クラスは複数の授業を同時に受講することができないということを式であらわ している 教室タイプは教室数^& を超えて利用することができないということを式で あらわしている

式は 各々の教師の授業と授業の空き時間数 ^% に重み をかけたものは最低基準 値 ⁺ を下回らなくてはならないという制約式である 式 は 各々のクラスの授業と授業 の空き時間数と 限 土曜日に受講する授業数に重みを掛け合わせたものは最低基準値 ⁺

を下回らなくてはならないという制約式である 式と式 は 全体の時間割がよくな る変わりに 特定の個人 クラスが犠牲になることを防ぐ制約式である

曜日 時間帯において 教師可変型教科種 ⁽ の教師を必要とする数 は 曜日 時間 帯に⁽ を受け持つことが可能な教師数 を上回ることができないことを式はあらわし ている

提案モデルの定式化

本研究では ソフト制約にはその重要度に応じた重みを ハード制約には十分大きい重みをあた え 各々の違反数に重みを掛け 足し合わせた目的関数 を最小化する制約緩和問題として解く

各式は制約条件を違反した数をあらわす 教師が重複して受け持っている授業の数

" %

'

クラス が重複して受講する授業の数

"

'

1'

1

1 1,

教師の授業間の空き時間数

%

'

<

:

クラス の授業間の空き時間数

'

<

:

クラス の限と限 土曜日に受講する授業数

2

'

:

:

次に各教師 クラス 教室の違反点数を次のように定義する

教師の違反点数

' " %

: %

クラス の違反点数

'

"

:

:

2

教室タイプ を超過して使用する数

&3 '

)&

教師可変型教科種⁽ の不足数

*

'

)

学科^$ に関して 同学科間の低学年の必修科目と高学年の必修科目の授業時間が重なって いる授業数

" "

'

)14'

14

14 14

教師全体の授業重複数

'

"

クラス全体の授業重複数

'

"

教室タイプ全体の超過使用数

'

&3

教師全体の授業間の空き時間数

'

%

クラス全体の授業間の空き時間数

'

クラス全体で限 限 土曜日に受講する授業数

'

2

教師の満たすべき違反点数⁺ を超過した違反点数

'

)+

クラスの満たすべき違反点数⁺ を超過した違反点数

'

)+

教師可変型教科全種の教師不足数

'

*

全学科に関して 同学科間の低学年の必修科目と高学年の必修科目の授業時間が重なってい る数

'

" "

目的関数

'

例 各教科の授業開始時間帯より以下のように時間割行列が生成された ^{& '} とする

% '

%

'

'

'

'

& '

この場合の違反数は以下のようになる

" % %

" %

%

% %

%

%

" %

"

%

"

%

%

%

%

2 %

2

%

2

%

&3 %

'" % :" %

'

'% :%

'

'" :"

:"

'

' :

:

'

'2 :2

:2

'

'&3 '

領域の定義

近傍の定義

近傍 を以下のように設定する

一つの教科の配置時間帯が異なる状態 例

解

教科 ^{: :}

曜日

時間帯

解

教科 ^{: :}

曜日

時間帯

解

教科 ^{: :}

曜日

時間帯

と に関して 教科 の授業開始時間が異なり 他の時間帯は同じ値をもっているとする と と は近傍解である 同じように と は 教科^:の授業開始時間が 異なり 他の時間帯に関して同じ値をもっているとすると 近傍解となる と はつの教 科に関して授業開始時間が異なるため 近傍解ではない

実行不可能解

本研究の時間割編成モデルでは 実行不可能解を種類に分類する

複数教科の組合せによる実効不可能解

教師が重複して授業をうけもっている クラスが重複して授業を受ける 教室の数を超過して授 業がおこなわれるような状態には 複数の教科が組み合さることでなる

このような状態の時間割は 実際に実行することができないので実行不可能解となる ただし 重複した状態では実行不可能だが 重複の原因となっている教科を別の時間帯に移動させること で実行可能解となる

このような状態の時間割を複数教科の組合せによる実行不可能解と定義する

単一教科による実行不可能解

受け持つ教師の都合が悪い時間帯に教科が配置されている状態の時間割では 授業をおこなう ことができず実行不可能解となる 他には 連続時間授業の教科を開始時間限とした場合 学 校は限までしかないので 一時限分授業をおこなうことができない よって これらのような時 間帯には配置することができない

教師の都合または教科が連続授業であることにより 実行不可能解になるような解を 単一教 科による実行不可能解と定義する

探索領域

本研究では実行可能解と 複数教科の組合せによる実行不可能解で 探索 遷移をおこなう 一般教科を受け持つ教師 都合をあらわす時間割行列を ^% と定義する ^% の要素

は 変数で 教師の都合が良い時間帯は 悪い時間帯は で表す

教科 ^! が配置可能な時間帯は 受け持つ教師が全て都合がよく 且つ授業終了が限以前にな る時間帯である

'

'

'

,'

を要素としてもつ時間割行列 ^% は教科 ^! の配置可能な時間帯を表す時間割行列で ある 要素がの時間帯が決定変数 のとりうる範囲となる

例 ^!は^%

'の教師人で受け持つ教科であり時間連続授業であるとする ^%

と ^% が以下の場合の ^% を示す

%

'

%

'

%

'

近傍探索は全教科に関する近傍について行う 全教科の近傍移動の中から最も改善される移動 を選んでいく 近傍数は

:となる