107

計算機による時間割自動生成に関する検証伊藤 芳浩＊・金山 将人＊＊・小林 寛明＊＊＊・松原 一樹＊＊＊＊・宮本 克史＊＊＊＊＊

Computational Verification of Automatic Generation forTimetabling problem
Yoshihiro Ito＊, Masato Kanayama＊＊, Hiroaki Kobayashi＊＊＊,Kazuki Matsubara＊＊＊＊ and Katsushi Miyamoto＊＊＊＊＊
Abstract
It is diffcult to make the timetable in general. In case of creating the timetable, we have to consider many
constraints. Thus, it has been said that it is not possible to create the timetable in our college by softwares on themarket. This paper proposes to create our school timetable by using the genetic algorithm. Genetic algorithm isoften applied to timetabling problems in a kind of optimization problems. As the result, the timetable only of thedepartment of information science and technology was created by the genetic algorithm program which wasdeveloped. On the other hand, free software which is named Time assignor was able to make the timetable ofthree departments that excluded the advanced engineering course.
Keywrods: Timetabling problem, Genetic Algorithm

１

はじめに

学校において時間割作成は大変に手間と時間がかかる作業である．本校の時間割は全てマニュアルで作成されており，非常に時間がかかり，担当教員に高い負荷を与えている．作成支援ソフトウェアが幾つか販売されているが，導入されていない．その理由の一つとして，本校の作成時に要求される条件の多さが挙げられる．そのため市販の時間割作成ソフ
トでは対応が難しいといわれてきた．時間割の自動生成は，ナーススケジューリング問題と似た問題として分類されており，このような条件付き組み合わせ最適化問題に対して有効な手法として遺伝的アルゴリズム（Genetic Algorithm：GA）が挙げられる［1, 2, 3］．GAでは，各種条件をペナルティが最小になるという評価法を用いて組み込むことができるた
め，GAを用いて最適な解を求めることが期待できる．そこで，GAによる時間割自動作成のプログラムの作成を目的とする．本報告では，単純GAと呼＊情報工学科＊＊ソニーイーエムシーエス株式会社小見川テック＊＊＊オムロンフィールドエンジニアリング株式会社＊＊＊＊新綱エンジニアリング＆メンテナンス＊＊＊＊＊株式会社ダイキンエンジニアリング

ばれる基本的なGAを用いて，手始めに情報工学科のみの場合の時間割作成を試みた．これについて報告する．また，比較検証のために既存のソフトウェアであるTime Assignorを用いて時間割生成を行うことを試みた．
２

本校の時間割について

本校の時間割は，本科である情報工学科，電子機械工学科，商船学科の３科と専攻科の生産システム工学専攻と海上輸送システム工学専攻からなる．時
間割作成では，様々な拘束条件を満たさなくてはならない．時間割そのものが成立するための条件をHard 条件と呼ぶ［3］．これは，教員が同じ時間に講義を持たないこと，教室などの資源が重ならないことなどの条件である．次にSoft 条件と呼ばれる拘束条件がある．実験は連続していなければならない，同じ科目が同一の日にあってはならない等の条件である．このような多種にわたる拘束条件があるため
平成20年９月30日受理

108

弓削商船高等専門学校 紀要 第31号（平成21年）

表1

拘束条件こと時間割作成は難しいものとされている．次に，本校の時間割の特徴を具体的に述べる．
２．１ 本校の特徴
本校の時間割作成は大学などに比べると難しいといわれている．その要因として，教員数に比べ開講時間数が多いこと，非常勤講師の曜日の指定に拘束されること，その他にも多くの拘束条件があることが挙げられる．
現在の時間割作成は全て人手で行われている．支援ソフトを用いず，Microsoft社のExcel上でマニュアルにて作成されている．次に，時間割作成時に考慮する条件，すなわち拘束条件について述べる．
２．２ 拘束条件
本校の拘束条件について述べる．本報告では，拘束条件を４種類に分類した．第０考慮条件から第３考慮条件と呼ぶことにする．これを表１に示した．
第０考慮条件は，先に述べたHard条件のことであり，時間割としての最低限機能するために必要な条件である．第１考慮条件から第３考慮条件が先に述べたSoft条件に相当する．第１考慮条件は，時間割として機能するために守るべき条件としている．第２考
慮条件は，必ずしも守らなくても良いが，なるべく守れるように努力する条件であり，作成された時間割に対する満足度に影響するものである．第３考慮
条件は，曖昧な条件であり，強いていうならば作成時の心構えといえる．
３GAの設計GAにおいて全ての問題に対応できるような汎用的な設計手法は存在しない［1］．GAは解く問題にあわせて個別に設計しなくてはならない．特に染色体と交叉の設計が重要である．この設計が対象としている問題に対して適切であれば問題が解けることになる．また大きなアルゴリズムの流れは同じでも，細かい部分では解く問題毎に普通は異なっている．以下に本報告でプログラムを作成するときに用いた設計を説明していくが，設計が問題に対して有効であるかを判定することが難しいのもGAの特色である．
３．１ 染色体の設計
文献［4］に従い，授業の並びそのものを染色体とした．学年によっては８時間目があるため，個体の配列の大きさを200とした．染色体は，担当教科名と担当教員名を格納した二つの配列変数から構成される．

計算機による時間割自動生成に関する検証（伊藤・金山・小林・松原・宮本）

３．２ 交叉の設計
GAで最も基本的な交叉は，二つの個体の染色体を部分的に入れ換えることである．入れ換える位置,範囲は一般的に乱数によって決められる．授業の並びそのものを染色体としている場合，上記の交叉では，ほとんどの交叉後の遺伝子は致死遺伝子となる．
つまり，正常な状態では授業は各一回のみ染色体に含まれているが，交叉によってこの規則が守られなくなるからである．これを致死遺伝子として扱わずに，ペナルティ値の高い個体として取り扱うことも考えれるが，本報告では，致死遺伝子として考え,交叉の方法は文献［4］に従い，各クラスの切れ目のみで交叉する．これにより，交叉後, 致死遺伝子となることが無くなる．表１の第０考慮条件に違反する個体が生成される可能性が無くなっていないが，これはペナルティ値の高い個体として取り扱い致死遺伝子とはしない．ただし，この方法では解空間の探索がうまくいかないことが容易に想像できる．文献［4］でうまくいっているのは，合同授業の修正を交叉後に行っているからと考えられる．
３．３ 突然変異の設計
通常，交叉終了後に突然変異を行う．交叉での解空間の広い探索が期待できないため，通常のGA よりも多く変異を起こさせる．突然変異を交叉終了後にペナルティ値で昇順に並べた個体の上位５個を残し，残り全てに突然変異を起こさせる．突然変異は乱数で指定された遺伝子の値のみを変化される行為を一般的には示すが，この場合の突然変異は，授業位置の入れ換えを行う行為となる．乱数により突然変異を起こさせる二つの遺伝子座を選出し，授業を入れ換える．ただし，同じクラス内で変異させないと致死遺伝子となる．交換後，連続授業の条件を崩さないように修正を行う．
３．４ ペナルティ値の設計
個体の優劣をつけるためには，個体を評価し数値化する必要がある．時間割作成問題の場合には，表１に載せた拘束条件に従ってペナルティを課していく評価法が妥当と考えられる．本報告で作成したGAのプログラムでは，第０〜２考慮条件を評価している．各条件に対してどの程度のペナルティ値を課すかは，数値実験を繰り返さなければ決定できないが，本報告では，情報工学科のみであることから拘束条件違反が無くなるまで計算を行った．そのため各条件に異なるペナルティ値を割り振ったが根拠のあるものではない．感覚上クリアしにくいと思われる条件に対して大きい値を与えた．

４109

作成したGAプログラム

性能評価を行っていないので，統計的にはなにもいえない．数時間で答えが求まる場合もあるが，一日以上かかる場合もある．このように準最適解にたどり着くまで計算量が大きく異なる理由は，おそらく解空間の探索がうまくいっていないからである．
その原因は交叉の設計にある．交叉によって有効なbuilding blockを積み上げていくことができないため，初期集団によって収束性が大きく左右されている．それでも，条件を満たす解にたどり着けるのは，突然変異率が通常のGAに比べて非常に高い設定にしているからと推察される．
計算例として，表２にGAにより作成された情報工学科の時間割を示す．開講科目，担当教員，拘束
条件は，平成18年度のものを用いている．個体数は100であり，エリート戦略で20を残す．この20個体が全て親となり80個体の子供を生成する．突然変異率は50％とした．以上の条件で，計算時間は2.13GHzのCore2duoを搭載したPCで約１時間であった．コンパイラはgccを用い，並列化などの最適化はなされていない．
５

既存のソフトウェアでの時間割作成

既存のソフトウェアで本校の時間割作成を試みた．できれば市販のソフトウェアを試したかったが，予算の関係からフリーウェアまたはシェアウェアのソフトウェアの中から優秀なものを選択した．結果として，土居誉生氏のTimeAssignor Version 0.31を用いた．これは，大学・短大用の時間割作成システムとして公表されているものである．そもそも高専専用のソフトウェアは無く，高専の時間割が要求するものは大学・短大に近い．TimeAssignorの特徴は，時間割作成を完全に自動で行うことに主眼を置かずに，入力された制約条件をある程度満たす準最適解を求める．この後に，時間割をエディットできるGUIを用いて人手で修正する．この修正を反映して次の準最適解を計算する．これを繰り返すことにより，要求される制約条件を満たす解を最終的に求める．この繰り返しは本校のケースでは10回程度で終了する．また準最適解を求めるまでが非常に早いため作業中にストレスを感じることもない．
専攻科が無いこと並びに資料が一番揃っていた平成13年度のデータを用いて拘束条件を入力したとこ
ろ時間割が作成できた．しかし，拘束条件を増やしていくと動作は不安定となり，現時点のversionでは本校での使用は厳しい．また，専攻科を含めた時間割作成はできないと予想される．
TimeAssignorの最後の更新は2001年であり，そ110

弓削商船高等専門学校 紀要 第31号（平成21年）

表2

GAにより作成した情報工学科の時間割例

計算機による時間割自動生成に関する検証（伊藤・金山・小林・松原・宮本）の後更新されていない．おそらく作者が勤務する大学の時間割はこのversionで安定して組めているのであろう．このことは本校の時間割の拘束条件が厳しいことを示しているかもしれない．
６

まとめGAを用いて情報工学科のみの時間割作成を試みて，作成することができた．また，TimeAssignorを用いて専攻科が無い場合の時間割を作成することができた．ただし，TimeAssigorと比較するとGAを用いて仮に全時間割が自動作成できたとしても実用上は問題があるように感じた．それは，GAでは作成する度に時間割が大きく異なることである．現
実では，時間割を仮組みしてから，拘束条件にいれなかった各教員の要望を反映させる．その際には仮の時間割からなるべく大きな変更無しに修正をかけなければならない．GAでこのような機能を実現するには，修正用に別のGAのプログラムを用意する必要がある．つまり，修正をかけるほどペナルティ値が高くなるように設計したGAである．
TimeAssignorはこの課題を意識して設計されているように思われる．
今後の目標として，GAの結果が作成毎に大きく異なることは，情報工学科単独で作成しているためである可能性もあり，専攻科を含めた学校全体の時間割作成に取り組む．
謝辞
本報告の作成において資料，情報を提供してくださいました電子機械工学科の中山恭秀准教授に深く感謝いたします．
参考文献［1］北野宏明：遺伝的アルゴリズム1；産業図書.
［2］北野宏明：遺伝的アルゴリズム2；産業図書.
［3］相吉英太郎・安田恵一郎：メタヒューリスティ
クスと応用；電気学会.
［4］上田祐彰・大内大輔・高橋健一・宮原哲浩：遺伝的アルゴリズムの時間割作成問題への適用に関する一考察；電子情報通信学会論文誌D-I
Vol. J86-D-I No.9 pp.691-701 (2003).

111