1 中高一貫校における教員の休日決定支援プログラム A0878334 黒河健司 2 目次 I. 研究背景 II. 時間割作成手法 III. 休日決定問題 IV. 結果 V. まとめ 3 目次 I. 研究背景 II. 時間割作成手法 III. 休日決定問題 IV. 結果 V. まとめ 4 Ⅰ-ⅰ 時間割作成時間割作成とは，クラス，教員，施設等に元づく制約を考慮し，1週間分の授業予定を決定する作業のこと 5 Ⅰ-ⅱ 時間割作成の現状時間割作成についての研究は数多くあるにもかかわらず，中高一貫校では未だ手作業による時間割作成が行われているその原因は，各学校における制約条件が複雑だから 6 目次 I. 研究背景 II. 時間割作成手法 III. 休日決定問題 IV. 結果 V. まとめ 7 Ⅱ 時間割作成手法時間割作成は年に1回の作業である各教員へ担当授業配分時間割作成開始例)田中先生は高2(A,B,C):数B 各週2コマ高3(A,D) :数C 各週2コマ各教員の出勤希望日集計繰り返し作業！全教員の出勤日決定例) 専任教師:休日希望提出講師 :出勤可能日提出細かい制約条件を考慮できる教員の出勤日を決定する手法を提案する 8 目次 I. 研究背景 II. 時間割作成手法 III. 休日決定問題 IV. 結果 V. まとめ 9 Ⅲ-ⅰ 出勤日を決める為に学校教員 専任教師: 担任するクラスがある・月~土に1日休日を決められる・休日決定→出勤日が決まる 講師 : 非常勤の教師・出勤不可能日がある・担当授業日を決める 10 Ⅲ-ⅱ 専任の休日が決まるまで各専任教師の休日にしたくない曜日の希望度 (＝不満度) 学年教科中1 理科月 50 0 0 70 0 0 0 0 0 0 火 0 30 0 0 0 0 20 0 0 0 水 0 0 0 0 0 0 0 0 0 0 各制約条件を満たし，数学希望通りの休日につける様にする国語社会不満度の合計値を最小化英語体育木 0 0 0 0 0 0 20 0 0 0 金 0 0 0 0 100 0 20 0 0 0 土 0 0 0 0 0 0 50 0 0 100 11 Ⅲ-ⅲ 研究手法 • 休日決定問題を数理計画として定式化 • 定式化した問題を数理計画ソルバーに入力 • 数理計画ソルバーで求解可能か判定 • 求解可能なら出力結果から休日・出勤日を得る 12 Ⅲ-ⅳ 制約条件 1. 2. 3. 4. 5. 各専任は月曜から土曜までのうち1日休日を設ける専任により，休日にできない日がある同学年を担当する専任が同日に休めるのは3人まで水曜日は全員出勤(学年会議) 水曜日以外に各教科ごとにその教科の専任が全員出勤する日が1日以上存在する 6. 出勤している専任・講師を合わせて1日に担当できる授業時間数がクラスの総授業数を上回る 7. 制約条件6の元，各教科ごとに1日の授業数を満たす 8. 講師によって出勤できない日がある 13 • 制約条件5 水曜日以外に各教科ごとにその教科の専任が全員出勤する日が1日以上存在する表1：制約条件5例月火水国語科全員出勤数学科英語科全員出勤全教員出勤木金土社会科体育科理工科全員出勤全員出勤全員出勤 14 • 制約条件6 出勤している専任・講師を合わせて1日に担当できる授業時間数がクラスの総授業数を上回る例) 中学6クラス・高校8クラス 1日6時間授業の日この日の総授業数は以下に示すものとなる 6 クラス数 × 3 学年数 + 8(クラス数) × 3(学年数) × 6 時間 = 252(総授業数) この252時間分を行えるだけの教員が出勤する (専任教師は1日3時間，講師は1日6時間まで働ける) 15 • 制約条件7 制約条件6の元，各教科ごとに1日の授業数を満たす各教科ごとに1週間の全授業数から平均して1日当たりの授業数を算出．その教科の担当教員が授業を行えるだけ出勤する表2:制約条件7概略図概略を右の表2に示す． ※この制約は後の時間割作成への影響が大きいため，使用するかどうかはその都度決める月火水木金土数学総授業数国語理科社会英語その他 16 • 制約条件7 ただし，体育等の場所を使う教科に関しては，1日に行える授業数に制限がある為，この制約を常に満たす必要がある月火水木金土数国そ理他理総学語の科科国授他語業社数会英英語語英数語学社会制約条件が整ったので定式化へ体育はこのように偏りが出てはいけない 17 [前出] Ⅲ-ⅱ 専任の休日が決まるまで各専任教師の休日にしたくない曜日の希望度 (＝不満度) 各制約条件を満たし，希望通りの休日につける様にする不満度の合計値を最小化 18 例) 中学1年担当数学科田中先生 Ⅲ-ⅴ 目的関数 x中1,数学,1,曜日 x中1,数学,2,曜日目的関数は専任の休日振り分けに対する中学1年担当数学科鈴木先生 ⇒ 不満度の最小化なので以下の様に設定する x中2,国語,1,曜日中学2年担当国語科山田先生 ⇒ ⇒ Minimize f   H pqij x pqij 田中先生は月曜日が休み学年， q  教科， i {1,2,3}， j  曜日 x中1,数学,1,月曜  1, xp中 1,数学,1,火曜  0, x中1,数学,1,水曜  0, 変数 xpqij は以下のようにする x中1,数学,1,曜日 1:学年p, 担当教科qの教員iは曜日jが休日 x pqij   数学科鈴木先生 ⇒ x中1,数学, 2,曜日中学1年担当 0:学年p, 担当教科qの教員iは曜日jに出勤 x中2,国語,1,曜日中学2年担当国語科山田先生 ⇒ 例) 中学1年担当数学科田中先生 ⇒ Hpqij は教員の希望度を表している田中先生は月曜日が休み今回はある日を休日にしたい場合の上限値を0 x中1,数学休日にしたくない場合の上限値を100とした ,1,月曜  1, x中1,数学,1,火曜  0, x中1,数学,1,水曜  0, 19 Ⅲ-ⅵ 制約式本研究で使用した制約式を以下に示す x j曜日 pqij  1,  x q教科 i番号 pqij  x p学年 q教科  k q教科 t番号  3, pqi水曜 qtRqt   k q教科 t番号 j曜日  0,  0, qtj  Wqt , p  学年, q  教科, i  番号 (1) p  学年, j  曜日 (2) i  番号 (3) Rqt  講師の出勤できない日 (4) Wqt  講師の最低出勤日数 (5) 20 • 制約条件5 (6)式は，変数Zqjを決めている．左辺で，ある教科全体の人数からその日に水曜日以外に各教科ごとにその教科の休んでいるある教科の教員の人数を引いた値が，元の人数に等しい時だけ，等号成立．専任が全員出勤する日が1日以上存在する例) 休みありについての制約式は以下のようになる 12 zqj 12 1 zqj  0 mq zqj  mq  yqj , z j曜日 qj  2, 休みなし 12 zqj 12  0 zqj  1 q  教科, j  曜日 (6) q  教科 (7) 1: 曜日jに教科qの教員全員が来ている zある教科の教員が全員出席する日が水曜日以外に1日  qj  0,1 0 : 曜日jは教科qの教員1人以上が休み yqj  曜日 jに休んでいる教科 qの教員の人数 ⇒1週間のうちに2日以上Z qj =1となる日があればいい ⇒(7)式 mq  教科 qの教員の総人数　21 • 制約条件6 出勤している専任・講師を合わせて1日に担当できる授業時間数がクラスの総授業数を上回る例) 中学6クラス・高校8クラス 1日6時間授業の日この日の総授業数は以下に示すものとなる教員全員数  休んでいる教員数  3  出勤講師数 6  252  例)  6 クラス数 × 3 学年数 + 8(クラス数) × 3(学年数)  S  252(総授業数) x kqtj  6  252 × 6 時間 = pqij  3      p学年 q教科 i番号    q教科 t番号この252時間分を行えるだけの教員が出勤する (専任教師は1日3時間，講師は1日6時間まで働ける) 22 • 制約条件7 制約条件6の元，各教科ごとに1日の授業数を満たすここでは，制約条件7に該当する式の例を挙げる m  y数学, j  3  m  y社会, j  3  数学社会   k 数学,t , j  6  48 k 社会,t , j  6  40 t番号 t番号 yqj  曜日 jに休んでいる，教科 qの教員の人数 mq  教科 qの教員の総人数　23 目次 I. 研究背景 II. 時間割作成手法 III. 休日決定問題 IV. 結果 V. まとめ 24 Ⅳ-ⅰ 入力情報月火水木金土今回は以下の情報を入力して計算を行った 1 2 • • • • • • 専任教師数講師数学年数教科数授業日総授業数 • 1日の担当可能授業数 • 「体育」平均授業数 • 専任の希望度上限値 3 ：60人 4 ：30人 5 ：6学年 6 ：7教科：5日：252時間(月，火，木，金)， 168時間(水，土) ：専任3時間・講師6時間：15時間(月，火，木，金)， 8時間(水，土) ：その日を休日にしたい場合0 その日を休日にできない場合100 25 Ⅳ-ⅱ 専任の休日希望度と出力結果提出された教員の希望度学年教科数学国語中1 理科社会英語体育月 50 0 0 70 0 0 0 0 0 0 火 0 30 0 0 0 0 20 0 0 0 水 0 0 0 0 0 0 0 0 0 0 木 0 0 0 0 0 0 20 0 0 0 金 0 0 0 0 100 0 20 0 0 0 土 0 0 0 0 0 0 50 0 0 100 26 Ⅳ-ⅱ 専任の休日希望度と出力結果各制約条件は守られており青い部分が得られた休日となった学年教科数学国語中1 理科社会英語体育月 50 0 0 70 0 0 0 0 0 0 火 0 30 0 0 0 0 20 0 0 0 水 0 0 0 0 0 0 0 0 0 0 木 0 0 0 0 0 0 20 0 0 0 金 0 0 0 0 100 0 20 0 0 0 土 0 0 0 0 0 0 50 0 0 100 ・・・休日 27 Ⅳ-ⅲ 講師の出勤不可能日と出力結果講師から，あらかじめ集計した出勤不可能日教科月 × 火 × 水 × × 木金 × 数学 × × × × × 土 × × 28 Ⅳ-ⅲ 講師の出勤不可能日と出力結果制約条件の守られた講師の出勤表教科数学月火 × 出勤 × 出勤出勤出勤 × × 出勤出勤出勤水 × × 木金土出勤出勤出勤出勤 × 出勤 × 出勤出勤 × 出勤 × 出勤 × × 29 月火水木金土また，今回使用した数値だと， • 制約条件7 各教科ごとに1日の授業数を満たす数学総授業数国語理科社会英語その他を考慮した場合，最適解が求まらない結果となった．よって，今回は体育のみを全日，平均的に存在するように制約を行った． 30 目次 I. 研究背景 II. 時間割作成手法 III. 休日決定問題 IV. 結果 V. まとめ 31 Ⅴ まとめ本研究の目的であった，教員の出勤日を決めるプログラムを実装することができた今まで手作業で行っていた時間割作成開始時間割作成を支援する第一歩として期待が持てる結果を得た全教員の出勤日決定 32 今後の課題今後の課題としては，既存研究を元に更に細かい制約を考慮しながら時間割作成を支援できる時間割作成開始汎用性のあるプログラムを実装することが考えられる全教員の出勤日決定