論 文
授業時間割の作成に関する研究
渡辺禎文 吉川雅修 山下茂
田口東 新藤久和
（平成5年8月31日受理）
Research on Timetable Scheduling
YoshifumiWATANABE MasanobuYOSHIKAWA ShigeruYAMASHITAAzumaTAGUCHI HisakazuSHINDO Abstract Atimetable scheduling is regarded as one of combinatorial optimization problems． Some methods to solve the problems of this kind have been known． However， they are not always satisfactory since each university has its own circumstances and constraints． This paper proposes an index to evaluate the optimization of the timetable scheduling and applies it to composing the’93 timetable for the Department of Electrical Engineering and Computer Science．
1．序論
なお、ここでは平成4年度の山梨大学工学部におけ る時間割の作成を想定している。 時間割は学校運営上の根幹をなすものである。学生 はもちろん、教官、そして教室も時間割によって1週 間のスケジュールが定められ、管理されている。 時間割問題は、数多く存在する組合せ最適化問題の 中の一つである。組合せ最適化問題の解法については いくつか知られており、また、時間割問題についても 過去にいくつかの研究成果が報告されている1）’2）。 しかし、実際の時間割では、様々な要望や慣習を考 慮する必要があり、実用に耐えうる時間割を作成する ことは容易ではない。 本研究では、時間割とその制約条件に注目し、時間 割の最適解を探索する上での指標となる、評価式を求 めていく。 ＊電子情報工学科，Department of Electrical Engineering and Computer Science ”中央大学，Chuo Univercity2．時間割の作成に対する制約
時間割に対する制約としては、まず、実行可能とす るための基本条件が挙げられる。 また、科目に対しては、対象クラスや時限数など様 々な指定が有り、正しく対応していなければ実行可能 な時間割として受け入れられない。科目に対する指定 もまた、時間割作成の際の制約である。 基本的には、以上の基本条件と科目に対する指定を 満たせば時間割として実行可能である。しかし、実行 可能な時間割であればどれも同じというわけではない。 時間割に対しては様々な要望があり、それらをより多 く取り入れたものが、より良い時間割であると考えら る。したがって、時間割に対する要望も制約となる。 また、時間割を作成する上では、それぞれ慣例によ る決まり事があり、可能な限りこれに従うことが求められる。したがって、時間割の作成に関するルールも 制約となる。 以上の様な時間割に対する制約は、表1に示す4つ に大別することができる。すなわち、［1］基本条件・ ［2］科目に対する指定・［3］時間割に対する要望・［4］ 時間割の作成に関するルール、である。 中でも、［1］，［2］は必ず満たす必要がある。［3］は必 ずしもその必要はない。ただし、できる限り満たすこ とが求められるものと、満たすことが望ましいがその 必要性はあまりないものとがある。［4］については、 ［4−4］のように必ず満たさなければならないものもあ るが、［3］と同様、満たさなくてもよいものもある。 この様な満たす必要性の度合いは、制約条件の重要 表1 時間割の作成に対する制約 度Wconによって以下の様に表わすものとする。 ・必ず満たさなければならない制約条件a ［1］基本条件 ［1−1］全ての対象科目が割り当てられている。 ［1−2］教官のスケジュールに重複が無い。 ［1−3］教室のスケジュールに重複が無い。 ［1−4］クラスのスケジュールにおいて、必修科目が他の科目と重 複していない。 ［1−5］使用教室の収容人数が対象学生数より多い。 Wcon。 ； Max， できる限り満たすことが求められる制約条件b Wconb ＜ Max． ’満たすことが望ましい制約条件c Wcon、 〈 Wconb 〈 Max． ［2］科目に対する指定 ［2−1］対象クラスの指定。 ［2−2］担当教官の指定。 （担当候補の提示も含む） ［2−3］使用教室の指定。 （特別教室等） ［2−4］開講時限数の指定。 ［2−5］開講時限の指定。 （管轄外の科目等。例えば、教育学部の 教官・教室による外国語等） ［2−6］同時／分散開講の指定。 ［2−7コ連続／分割開講の指定。
3．時間割の評価式
時間割に対する評価Fを、以下の様に定めるものと する。 0≦ F ≦ 1 ・全ての制約条件に従う完全な時間割の場合 F ＝ 1 ［3］時間割に対する要望 ［3−1］クラスのスケジュールにおいて、重要度の高い科目と他の 科目とが重複していない。 ［3−2］重要度の高い科目が、良い時限に割り当てられている。 ［3−3］重要度の高い科目が1日に集中していない。 ［3−4］クラスの1日のスケジュールに隙間が無い。 ［3−5］使用教室にゆとりがある。 ［3−6〕教室の移動が少ない。 ［3−7］異なるクラスによって、同じ教室が連続して使用されてい ない。 （教室の入れ替えによる混乱の防止） ［3−8］教官のスケジュールにおいて、出席する会議等が度々開催 される時限に科目の担当が割り当てられていない。 （会議の出席等による休講を減らす） ［3−9］（各教官の希望に応じ）科目担当を、1日に集中／各曜日に 分散する。 ・実行不可能な時間割の場合 F ＝ 0 時間割は、各クラス・各教官・各教室毎の個別の時 間割からなる。時間割の作成とは、制約条件に従って それらの時間割に科目を割り当てていくことである。 したがって、時間割を評価する場合には、それぞれ の科目が、どの程度、制約条件に従って割り当てられ ているかを評価すればよい。 ここで、科目i（1≦i≦Nsub）に対する評価Fsubi を、以下の様に定める。 0 ≦ Fsub、 ≦ 1 ［4］時間割の作成に関するルール ［4−1］通年科目の場合、特に指定が無い限り、 各学期とも同じ時 限に、同じ教官・教室で開講する。 ［4−2］特に指定がない限り、担当教官と同じ所属の教室を使用す る。 ［4−3］特に指定がない限り、特別教室は使用しない。 ［4−4］連接関係＊にあるクラスで、必修科目が同時に開講してい ない。（同時に開講する必修科目を落としていると、自動 的に1年留年となるからである） ［4−5］分散開講の場合、特に指定が無い限り、同じ時限に割り当 てる。 ［4−6］分割開講の場合、同じ教官・教室で開講する。 ［4−7］分割開講の場合、単位時限数毎に分割する。 ［4−8］連続開講の場合、午前と午後に跨がって割り当てない。 ［4−9］連続開講の場合、異なる曜日に跨がって割り当てない。 ［4−10］関連科目＊＊と連続して開講する。 ［4−11］前学期の関連科目＊＊と、同じ時限に、同じ教室で開講する。 ［4−12〕共通科目は、各クラスに指定時限数以上割り当てる。 ［4−13］非開講科目は、各曜日の終わりの空いている時限に割り当 てる。 ［4−14］各教官の、科目の担当時限数がほぼ等しい。 ・全ての制約条件に従う場合 Fsubi＝ 1 ・実行不可能な場合 Fsub、＝ 0 また、科目iの重要度Wsub、を、以下の様に定める。 0＜ Wsub i ≦ 1 ・科目iが必修科目の場合 Wsubi＝ 1 1つでも実行不可能な科目があってはならない。そ の様な時間割は、当然、実行不可能とされなければな らない。 牛例：4年EI−＞3年EI パ例：ソフトウェア設計第一演習一〉ソフトウェア設計第一 例：ソフトウェア設計第ニー〉ソフトウェア設計第一また、時間割全体の評価に対し、重要度の高い科目 の評価は正確に反映させ、重要度の低い科目の評価は 余り影響を与えないものとしたい。 以上のことから、時間割に対する評価Fを以下の様 に定義することができる。
・一芭一…〕土…ω
すなわち、FはFsubiW＄“biの幾何平均である。 Fsubi＝0となる科目、すなわち、実行不可能な科目 が1つでもあれば、F＝0、すなわち、実行不可能な 時間割であると評価される。 ここで、FとWの関係によるFWの変化を図1に示 す。 FW 1 W・0．l@W・0．5
W・1 0 1 F図1 FとWとの関係によるFWの変化
Wの値に関係なく、F＝1の時はFW＝1であり、 F＝0の時は FW＝0である。しかし、0＜F＜1の 場合には、Wの値が小さい程 FW→1になることが分 かる。 この様に、重要度の低いWsub iの値が小さい科目は、 重要度の高いWsubiの値が大きい科目よりも、 Fsub、 に対してF subiWs”bi→1となる。つまり、時間割の 評価Fに対して、科目の評価Fsub、の影響が少なくな るのである。 続いて、科目iにおける制約条件j（1≦j≦Ncon）に 対する評価Aconi、を、以下の様に定める。 0 ≦ Acon i」 ≦ 1 ・制約条件jを満たしている場合 Acon i」＝ 1 ・部分的に満たしている場合 0 ＜ Acont｝ ＜ 1 ・満たしていない場合 Aconij＝ 0 また、制約条件jの重要度Wcon jを、以下の様に定 める。 0＜ Wcon、 ≦ 1 ・必ず満たさなければならない制約条件の場合 Wcon、＝ 1 Wcon j＝1の制約条件は、1つでも満たしていなも のがあってはならない。その様な科目は実行不可能と されなければならない。しかし、それ以外の制約条件 については、仮に満たしていなくても実行不可能では ない。 また、科目の評価に対し、重要度の高い制約条件の 評価は正確に反映させ、重要度の低い制約条件の評価 は余り影響を与えないものとしたい。 以上のことから、科目iに対する評価Fsubiを、以 下の様に定義することができる。・一
k茸（1−（1−一・）・−r
… （2） すなわち、 Fsub iは 1−（1− Acon、、）・Wconjの幾 何平均である。 AとWの関係による1−（1−A）Wの変化を図2に示 す。 1−（1−A）W）W 1 W・0．1 W・0．5 W・1 0 1 A 図2 AとWとの関係による1−（1−A）Wの変化 A＝1の時は、Wの値に関係なく 1−（仁A）W＝1である。A＝0の時は、W；1では1−（1−A）W＝0
であるが、0＜W〈1では0＜1−（1−A）W〈1である。また、0〈A〈1の場合には、Wの値が小さい程
1−（1−A）W→1 になることが分かる。 この様に、Wconj＝1の制約条件は、 Acon i、＝0 のとき、すなわち、満たしていない場合には、科目の 評価はF sub i＝0、すなわち、実行不可能であるとさ れる。しかし、0＜Wcon、＜1の制約条件では、実行 不可能であるとはされない。 また、Wcon iの値が小さい重要度の低い制約条件は、 Wcon、の値が大きい重要度の高い制約条件よりも、1−（1− Acon、j）・Wcon jの取り得る値の幅が小さく なる。すなわち、科目の評価F・sub iに対して、制約条 件の評価 Acon i、の影響が少ないということである。 以上のことから、評価式（1），（2）によって時間割を 適正に評価できるものと考えられる。
4．必要とされるデータ
時間割の作成時に提供されるデータを表2に示す。 ☆科目☆「
☆教官d
表2 提供されるデータ 科目名 科目番号 対象クラス 担当教官（候補の提示） 使用教室（科目による） 重要度 開講時限数 開講学期纏i慧㌃一［麟
同時／分散開講の指定 連続／分割開講の指定 開講／非開講の指定鞠抵＝τ鍵
学部名 学科名 学年 クラス・コース名 学生数 連接関係にあるクラス 教官名 所属 科目担当以外のスケジュール 教室名 所属 収容人数 普通／特別教室の指定 対象科目以外の使用スケジュール 時間割の作成処理、及び、評価の際には、データの 簡素化と、作成処理と評価の簡便化の為に、以下の様 な科目の細分化を行う。そして、時間割の作成と評価 は、細分化後の科目に対して行う。 ・分散開講の場合、クラス毎に分ける。 ・分割開講の場合、分割毎に分ける。 ・通年科目では、各学期毎に分ける。 分散開講の場合、対象クラスが異なる関連科目とし て扱う。 また、分割開講の場合、同じ対象クラスの、強い関 連度を持つ関連科目として扱う。 さらに、通年科目では、開講学期の異なる、強い関 連度を持つ関連科目として扱う。 ちなみに、表1の制約［4−8］で示す”関連科目”は、 同じ対象クラスの、弱い関連度を持つ関連科目とみな し、また、制約［4−9］で示す”前学期の関連科目”は、 開講学期の異なる、弱い関連度を持つ関連科目とみな す。 指定がない場合の使用教室は、一般教室の中から対 象学生数と担当教官の所属をもとに選出した候補を与 えるものとする。 また、指定がない場合の開講時限は、開講時限数に 応じた時限の組合せの集合を候補として与えるものと する。時限の組合せの集合は、単位時限数や、午前・ 午後の区切りを考慮して組み合わされる。これにより、 制約［4−8］，［4−9］を満たすことができる。 開講時限数をhとすると、時限の組合せの集合P，は 表3の様になる。 表3 時限の組合せの集合 P・ ・h＝1の時 P1＝｛1，2，3，4，5，6，7，8｝ ・h＝2の時 P2＝｛1・2，3・4，5・6，7・8｝ ・h＝3の時 P3＝｛2・3・4，5・6・7，7・8・9｝ ・h＝4の時 P4＝｛1・2・3・4，5・6・7・8｝ 表4 作成と評価に使用するデータ ☆科目iの入力データS、 ・ S、 ．C ：対象クラス ．T ：担当教官の集合 ，R ：使用教室の集合’叶；i i麟灘
・sτ：； ：麟目
※0〈S，．C．D≦1 ☆科目iの出力データs’ ，ぷ「 τ i簸難
☆クラスxの入力データC、 C．．C ：連接関係のクラス ☆教官yの入力データT， T，［S］［W］［p］ ：科目担当以外のスケジュール ※0≦T，［s］［w］［p］≦1 s：学期，w：曜日， p：時限 ☆教室zの入力データR、 R、［S］［W］［p］ ：管轄科目以外のスケジュール ※0≦Rz［slw］［p］≦1共通科目は、指定時限数÷単位時限数個の別々の 科目として扱う。これにより、制約［4−12］を満たすこ とができる。 また、非開講科目は、開講科目とは別に扱うものと する。したがって、制約［4−13］は評価に含まない。 以上のことから、時間割の作成と評価に必要とされ るデータをまとめたものが表4である。
