企業講習会日程の自動作成システムの試作
2011SE146 葛岡季絵

2011SE263 寺本剛

指導教員：鈴木敦夫

1

はじめにジューリングを経験の少ない担当者でも作成することができる.

企業は現在, さまざまな手法でコスト削減を目指してお本研究では、企業の講習会日程の自動作成システムの試り, そのひとつが, 作業効率向上のためのシステム導入であ作を考える. 講習会の講師の割り当てを考えるにあたって、る. またシステムのひとつの分野として, 最適化のアルゴリ

制約条件を満たすだけではなく担当者の意思を組み込めるズムが注目されている. 近年では, 高性能の最適化ソフトようなシステムを作成していく.

ウェアが安価で利用可能になっている. そのため企業は実問題の説明用的な規模の問題が短時間で解けるようになり、作業時間2の短縮によるコスト削減につながっている.

問題の概要

しかしながら, 現状では, 企業における最適化のアルゴリズムが幅広く使われるまでに至ってはいない. 現場の担当者がシステムをうまく扱えないことが大きな原因となっている. 実際の現場の担当者がシステムを利用するには, 彼らが持っている知識や経験をうまく取り入れる必要がある. 例として, 病院などの医療機関における手術室のスケジューリング支援システムがある. 条件を入力すると勤務シフトを自動的に作成するものの, そこに担当者の知識や経験を加えることが難しく, 結局のところ手作業で作ってしまう.OR の成果を取り入れて作成しても, 実用化に至らなければお互いに不利益な結果となってしまう.
実際に現場で使われるシステムを作成するには, 現場の担当者が直面している問題をシステム作成者がしっかりと理解し, その上で担当者がシステムに何を望んでいるのか,どうすればわかりやすく, 使いやすいシステムになるのかを考えることが大切である [3].
過去の我々の研究室では, スケジューリングについて, 時間割編成システムや生産計画問題に取り組んできた. 時間割編成問題では, ある学校において, すべての科目を各曜日に各時間帯および教室に矛盾なく割り当てる必要がある.
また, 教員に対しても, 担当科目やその他の時間割編成業務に関する制約などが存在する. そのためこの業務の担当者は, これまでの経験によって手作業で編成を行っていた.
しかしアルゴリズムを用いたシステムを導入し, 条件に対して優先順位を設定し, その上で制約条件満たしていくことで最適な時間割の作成を行うことができた. また, 生産計画問題では, 鉄鋼メーカーにおける鋳造工程の効率化を図った. 鉄鋼業界には,OR が実務に適応されている多くの実績がある. しかし, 実際には机上で作成された生産計画表と, 生産の実態に埀離があり, システム制作者と現場の担当者の間で常に認識の違いが生じているという実態があった. しかし, 最適化システムの導入と現場の担当者との綿密なヒアリングにより, これまでは現場の生産計画担当者が自身の経験や勘を頼りに計画していたが, 経験の少ない担当者でも, 短時間かつ客観的な計画が立てることができるようになった. このように最適化のアルゴリズムを用いることで, 長年業務を経験してきた担当者が作成するスケ

本研究における企業講習会日程の自動作成システムとは, 企業内で行われる講習会の講師の最適な割り当てを自動で行うシステムを考えることである.
ある企業では, 社員の教育の一貫として,1 回 50 人程度が参加する講習会が行われている. 講習会の講師は普段の業務に加えて, 講習会の日程を割り当てられており, その担当講師の割り当ては手作業で行われている. そのため, 完成には 2,3 日ほどの時間と手間がかかっていた. さらに, 講師によって担当できる講習会が異なること, 他の業務と並行して行っている講師がいるなど, 講師一人一人の条件が異なるため, 担当する講義数に偏りが生じてしまう. この様々な条件を考慮した日程を作成することは, 担当者にとって非常に負担のかかる作業となっていた.
そこで, この作業の負担を軽減するため, より最適な講師の割り当てを実現するため, シフト作成者が必要なデータを入力するだけで, 講習会日程を自動作成するシステムを考える. システムを作成するにあたって, シフト作成者の考えが最大限に反映されるような条件入力の仕方を考え, 経験の少ない作成者であっても利用しやすいシステムを考えることで, 実用化を目的とする.
また, この問題のモデルを設定するにあたって, 担当者と協議を重ねた結果, 以下にあげる制約が必要であると考えた.
講習会日程の各種条件について
企業講習会日程を作成するにあたって必要な条件を以下に述べる.

• 各単元は必ず１人の講師に割り当てられる• 各単元に対し講師の優先順位を決める各講師に対してポイントによる重み付けを行う. また, 各単元ごとの重みに偏りをなくすために上限を設定する. 各単元ごとの上限を 20 とする.

• 講習可能日に割り当てる各講師の予定を考慮し, 必ず担当可能日に割り振られるようにする.

• 各講師のスキルを考慮する

講師により現在担当できる単元が異なっている. 例
えは, 講師 A は各コースのイントロダクションのみを目的関数
ポイントの最大化担当し, 他の単元は担当できない.

∑∑• 講師が担当できる単元は増加する
現在担当できない単元であっても, 講師がその単元を受講することで, 受講した次の回から担当可能と(1)

制約条件なる.

∑• 担当可能になる単元は順番がある
いくつかの単元を受講しなければある単元を担当でxij = 1,j∈J(2)i∈Iきないなど, 単元間の先行関係がある.

Ki ≤• 講義数の均等化を図る∑xij ≤ Li ,i∈I(3)i ∈ I, j ∈ J

(4)

j∈J

担当講義数に偏りが生じないようにするため, 各講xij ≤ Pij ,師の上限数・下限数を定める.

xij ∈ {0, 1}, i ∈ I, j ∈ J

定式化

3nij xiji∈I j∈J

ここでは, 各講習の講師の最適な割り当てを求める問題

定式化の説明を考える. 0-1 整数計画問題として定式化することで各単・目的関数

元に必ず１人の講師を割り当てる. また各単元における各(1)：各講師の各単元に対する優先順位をポイントとして定め, その和を最大にする.

講師のポイントの合計を最大化することを目的関数とし,各講師の講義数の上限数・下限数を設けることにより, 講 ・制約条件
義数の偏りを緩和することができる. しかしこの際, 制約を (2)：単元 j が必ず一人の講師に割り当てられるための制満たすことができず, 実行不可能になることが考えられるので, ダミー講師を導入する. ダミー講師とは, 実在しない講師のことで, どの講師にも割り当てることができない場
合はダミー講師が割り当てられる. それを解消するためには, システム利用者が手作業で条件を変更するものとする.
また, 満たすべき条件である「講師が担当できる単元が変動する」と「担当可能になる単元には順番がある」に関しては, 企業において各講師の育成スケジュールを作成するため, Microsoft Excel 上に育成スケジュールを入力できるシートを作る. 定式化にあたり, 以下のように定義を行う.

3.1

記号の定義

定数

I : 講師の集合 I = {1, 2, …, 6}
J : 単元の集合 J = {1, 2, …, 177}
Ki : 講師の講義数の下限, i ∈ I
Li : 講師の講義数の上限, i ∈ I
nij : 講師 i の単元 j のポイント

約.
(3)：講師 i が単元 j を担当する講師の上限・下限.
(4)：講師 i が単元 j を担当可能であるときに割り当てられる.

4システム
本システムの実装にあたっては, Microsoft Excel のアドオンソルバーである「What’s Best !」を最適化エンジンとして用いた. その理由は, ユーザーが定式化や制約設定の詳細を知らなくても, 表計算の形式で制約条件や目的変数の設定が可能であること, また市販されているソルバーはGUI をもたない製品がほとんどであるが, Microsoft Excelの GUI をそのまま利用することにより, 普段からなじみのある画面を使って操作ができ, かつ GUI 開発に要する時間や費用も比較的少なく済むことからである.
現在試作中のシステム概要と使用方法について紹介する. システムを利用する際には, Microsoft Excel の各シー
ト上にあるボタンに沿って進行する. 企業講習会日程の自動作成システムの使用手順は以下に示す.

(1) 記入画面について
Pij ={
1 : 講師 i が単元 j を担当できるとき
0 : それ以外のとき

コース名・単元名・講師名の各項目を入力後,「シート作成」ボタンを押す. シート作成後, 単元名・単元数・講師名・講師数の変更が必要な場合は, 記入画面にて変更項目を修正し,「更新」のボタンを押す.

変数

コース名・コース数を変更する場合は, 変更項目を修正し,「シート削除」・「シート作成」のボタンを押す.

{
1xij =
0: 講師 i が単元 j を担当するとき: それ以外のとき

図 1 記入画面(2) 記入シートについて
講義開始時間・各単元の講義時間 (1 単位 30 分)・講義数を入力する. 各コースの詳細を入力後,「担当可能表」を押す.

図 4 ポイント表(5) 担当スケジュール表について
講師は担当できる単元が変動するため, 各回における, 各講師の担当可能となる単元を入力するある単元に対し担当不可能の講師が, 次回では担当可能となる場合がある. このシートでは, ある単元に対し担当不可能を表す「0」であった講師において, 担当可能になる回で担当可能を表す「1」を入力する. 入力後,「入力完了」ボタンを押す.

図 2 記入シート(3) 担当可能表について各単元に対して, 各講師が担当可能かどうかを入力する.
現時点で担当可能な場合は「1」を入力, 担当不可能な場合は「0」を入力後,「入力完了」のボタンを押す. 入力完了後

図 5 担当スケジュール表に担当可能・不可能の変更があった際は, 変更項目を修正し,「更新」のボタンを押す.

(6) 講師予定表について担当可能表, ポイント入力表, 担当スケジュール表によって作成された表に, 各講師のスケジュールを反映させる. 各回の各単元に対して, 各講師の都合上で担当不可能ならば「0」に変更する. 入力後「入力完了」ボタンを押す.

図 3 担当可能表(4) ポイント表について各単元の各講師に対して, 上限値 20 のポイントを割り振り, 重みをつける. この際, 現在は担当不可能な講師にも割り振ることができる. 入力後,「入力完了」のボタンを押す.

図 6 講師予定表

(7) 最適化実行表について
最適化画面では各講師の担当回数の上限・下限を設定する.

6

まとめ

この際, 各担当者の講習会担当回数の上限の合計は,「講師ある企業における企業講習会の日程のスケジューリングが必要な単元」を上回らなければならない. 入力後,「最適は手作業で作成されており, これまで担当者にとって負担化」ボタンを押す. 上限・下限を変更する際は, 変更完了後の大きい作業であった. そこで, 制約を可能な限り満たしたに「更新」のボタンを押す最適化実行後,「表作成」のボタスケジュールを自動的に作成するシステムを構築した. 今

ンを押す.

回試作したシステムをより実用化に近づけるためには, 以下の点を改善することにより, さらに使用しやすいシステムになると考えられる.

• 講師数, コース数, 単元数の最大値の設定の調整→現段階では, 各項目に上限値を設定しているが, より柔軟なシステムを構築するためには, 上限値の幅を広げなければならない. よってインターフェースの改良が必要.
• 特定のいくつかの単元に対して, 同じ講師が担当しなければならない時の講師の割り当て→担当者が最適化実行後に手作業で行っているため,
図 7 最適化最適化実行時に条件として追加する.

• 講習日が 2 日間続けて行われる時の講師の割り当ての調整(8) 完成表について→企業側の要望により, 講習日が 2 日間連続で行われ最適解にて導き出された講師のスケジュールを自動的に作る場合は,1 日目の午後と 2 日目の午前は, できる限り成する. この際, アウトプットの調節に関しては手作業で調同じ講師が担当するようにするため, 考慮制約として節しなければならない.

条件を追加する.

• 完成表のセル幅の自動調整→担当者が社内で完成表を使用する場合, 印刷用紙幅に合わせて自動調整できるよう, セル幅を計算するプ
ログラムを作成する.

• 初担当の講師の認識→初担当の講師を把握するために, 初担当する単元を入力するシートを作成する.
今後, この企業では本システムを他の講習会の日程作成にも適用する予定である.
図 8 完成表参考文献[1] 勝田綾奈, 中村衣里：『麻酔科医のソフトスケジューリングについて』．南山大学情報理工学部情報システム数

5

実行結果
平成 25 年度のデータを用いて, 企業講習会日程の作成を行った. 担当者が手作業で行った場合は 2,3 日かかっていたシフト作成が, 自動作成システムを使用することによっ

理学科,2013 年度卒論文,2014.

[2] 久世晋一郎, 都筑慎之, 山本佳奈, 鈴木敦夫：『鋳造工程における生産計画スケジューリングツールの試作』, 日
本オペレーションズ・リサーチ学会,2013 年秋季研究発表会アブストラクト集, 2013, pp.152-153.て, 入力を含め 30 分程度で完成することができた. また, 担[3] 鈴木敦夫, 藤原祥裕：『手術室のスケジューリング支援システムについて』. オペレーションズ・リサーチ,
義数と最小の講義数の差が 33 回から 8 回に減少し, 各講師
特集「現状とつながる OR」, 第 58 巻, 第 9 号, 2013,の講義回数の均等化を行うことができた. そして, 上限数・pp.515-523.
当回数の上限数・下限数設けることによって最大の担当講下限数を変化させることで最適化に大きく影響を与えるため, 制限の調整を繰り返すことによって, より最適な割り当てを導き出すことができた.

[4] 山本佳奈, 鈴木敦夫, 寺田尚広：『中高一貫校の時間割編
成支援システムの試作』．スケジューリング・シンポジ
ウム 2012 講演論文集, 2012, pp.145-150.