課題整理と要件定義
概要
この記事では、「学校の授業の時間割」をモチーフに要件定義（課題検討）の段階でどのような情報整理をするか解説します。
情報整理をすると課題の特徴が見えやすくなり、組合せ最適化であることが理解しやすくなります。
課題を最適化問題としてコンピュータに入力するために、問題を明確にしていきましょう。
テーマ：「学校の授業の時間割」を自動で作る
学校で時間割を組んでいる先⽣たちは、専⽤のソフトウェアを使っている場合もありますが、多くは⼿を動かして⽭盾なく条件を考慮できるように検討しています。
今回はある程度複雑な条件でありながら、考えやすさを考慮した設定のため、架空の中⾼⼀貫校で教科担任制を前提として、組合せ最適化問題である「授業の時間割作成」を考えてみましょう。
「教科担任制」であるため、Aクラスの特定のコマに教科担任の先生を割り当てる必要があります。となるとその先生がそのコマで、他のクラスを担当せずに空いている状態でなければいけません。
そういった条件と制約を考慮すると、１週間に存在するすべてのコマそれぞれに、ある先生を割り当てるか（$+1$）否か（$-1$）の組合せ最適化問題と捉える事ができます。
続いて、この問題を解くために考慮すべき条件を考えてみましょう。
STEP1. 問題の言語化(要件定義)
要件定義とは、現実の問題を言語化することです。最終的にコンピュータで時間割作成の処理を行いますが、ITの活⽤においては、コンピュータは⼈間ではないので曖昧な指⽰では動いてくれません。 やりたいことを正確に伝えるために、まずは現実の問題である時間割作成の前提情報について丁寧に言語化することから始めます。以下のように、与えられた情報を整理していきます。
教科と担当教員の数について
教科は国語・英語・数学・理科・社会・体育・美術・音楽・生活の9つ。このすべてが専門教員によって実施される。国語・英語・数学は各8人の教師がいて、それ以外の教科は4人ずついる。
時間割が必要なクラスの数
- 6学年で2クラスずつ、計12クラスの時間割が必要
- 但し科目数と教科担当者は学年間、クラス間で変わりない。
勤務時間について
- 1人あたり最低週5時間以上勤務する
時間割について
- 1日で実施できる授業は最大6コマまで
- 月曜日から金曜日の時間割を作る
考慮すべき制約条件
- 国語、英語、数学は週に5時間、他の教科は週に2時間ずつ平等に配分されている必要がある。
- 同じクラスで同じ科目が連続するのは、2時間までとする。
- 過度な負担を避けるために、同じ教員が連続して5時間以上登壇することはしない。
このように、問題を言語化することで、ルールが明確になります。ルールを言葉で明確にしておくと、教員の異動やちょっとした追加・変更があった時にも対応しやすくなります。
STEP 2. コンピュータに処理してほしいことを書き出し、定義する
①全教科の担当教員をAグループとして、各教科の教員に番号割り当てる
- 国語A01~A08、英語A09~A18、数学A19~A27
- 理科A28~31、社会A32~A39・体育A40~A44・美術A45~A49・音楽A50~A54・生活A55~A59
②時間割をBグループとして、各クラスのコマに番号を割り当てる
- クラス番号01～12
- コマに番号をつける月曜1限=01、 2限=02、 火曜1限=07、金曜6限=30
- クラス1、月曜1限=B0101、 2限=B0102、 火曜1限=B0107、金曜6限=B0130と表現
③B0101～B1230にA01～A40を割り付ける処理をする
④その際、制約条件は以下となる
- 同じ時限に同じ先生が入ることはない
- 同じクラスの時間割に、A01～A08は5つ、A09～A16は5つ、A17～A20は2つ、…入る
- 同じ先生が同じクラスに3つ連続してはいることはない
- 同じ先生が連続した時間に入れるのは4時間まで
コンピュータに処理してほしいことを明確にする事ができました。
STEP 3. 必要なビット数を推定する
今回の問題を解くのに必要なビット数とアニーリングマシンは計算できる規模の上限があります。
アニーリングマシンは1つの要素に1つのスピンを充ててあるパターンのエネルギーが最も良いことを導き出す手法のため、$+1$か$-1$に割り当てる要素がいくつあるかを事前に知っておく必要があります。
ここでは、先生が40人いて、1週間のコマ数が30限あり、クラスが12あります。
この12クラスで同時に授業が行われるのが学校であるから、割り当てを行うためには$40×12×30=14,400$の要素（各クラスのコマへどの授業を割り当てるかのパターン）、つまりスピンが必要と想定する事ができます。
まとめ
- 時間割作成をコンピュータで解くための言語化（要件定義）を⾏う
- コンピュータに処理してほしいことを明確にする
- スピン（$+1/-1$のイジング変数に該当する）要素がいくつ必要なのかを推定する
関連リンク
ACWスキルロードマップ
この記事はACWスキルロードマップの一部です。スキルロードマップを使ってACWを学んでみてください。
SNS共有
記事が役に立ちましたか？他の人に共有してみてください。
関連記事
組合せ最適化問題とは
組合せ最適化を身近な組合せ最適化問題として分かりやすい2つの例を用いて解説します。また、IoT社会における組合せ最適化処理の高速解法の重要性について述べます。
COVID-19感染対策を考慮し研究員シフトを最適化する
COVID-19の流行に伴い、感染リスクを考慮した制約条件の下、研究員のシフト作成をアニーリングマシンで行うユースケースを紹介しています。
保険会社の再保険ポートフォリオを最適化する
自然災害リスクに対応するため、保険会社が保有する膨大なデータを活用した再保険ポートフォリオ策定をアニーリングマシンで行うユースケースを紹介しています。
アニーリングマシンのための数学
アニーリングマシンが得意とする問題の特徴である「二次」「離散」を中心に、知っておくべき数学的前提を易しく解説します。