時間割変更アプリの説明

作成サイト: http://timetable.torimari.site:8080/
コード: https://github.com/moririn2528/timetable

背景

学校の先生は急な出張が入ることがあります。その出張と授業が被っていたとき、その授業を時間割変更する必要があります。この時間割変更を自動的に行うアプリがこちらです。
これはある学校においてかなり難しいことです。その理由は以下の 2 つです。

• クラス分けが複雑であること。
  ある高校の 3 年 A 組の授業は、数学の授業は A 組と I 組合同、英語は A 組、国語は 2 次試験に必要かどうかで分かれ A 組と I 組合同、理科は物理か生物どちらを取るかで分かれて A 組と I 組合同、社会は地理、日本史、世界史、倫理政経どれを取るかで分かれて A,B,C 組合同という風にかなり複雑です。
• 研究日、非常勤講師など、授業できない時間帯が多いこと。
  ある高校では、非常勤講師が 1/3 くらいいます。また、常勤講師においても週 1 で研究日があり、その日は休みです。さらに、出張日など授業できない時間帯がもともと存在します。

これらの理由によって、外注しても断られる状態であったと聞いています。ほとんどの人ができないようなことをやりたいと思っている私からしたらとてもやりがいのある製作だと感じ、挑戦することにしました。

技術選定

バックエンド

時間割変更において、計算量が結構大きくなると推定されるため、実行速度が速い言語がよいです。今まで使ってきた言語、学習コストも考慮して Go 言語を使うことにしました。
構造はクリーンアーキテクチャのように作成、長く使うことを考えて標準ライブラリ以外を極力使わないようにしました。
時間割などデータを蓄積する必要があるためデータベース、mysql を用いました。

フロントエンド

型がついている方が好きなため、typescript を用います。また、時間割部分は生徒にも利用してほしく、その際に ios, android アプリ化するため、React を用いました。

アルゴリズム

クラスの包含関係をグラフ化します。ある高校の高 3 のクラスすべてをグラフ化した図が以下です。¹

時間割変更するクラス自身とそのクラスの祖先に対して、そのクラスで時間割をまとめられるかどうかを判定し、まとめられるもので動かして変更できるかを考えます。あるコマ、そのクラスでまとめられる、というのは、そのクラスに対応する生徒は、そのクラスの子孫となるクラスの授業を受けているコマのことを指しています。動かして変更できるかどうかは、ダイクストラを用います。動かすルートは最後の辺を除けばパスになるという性質から使うことができます。また、状態は、現在のパスの最後となるコマとパスの長さとして実装します。パスの長さを状態として含める理由は、動かすコマ数はクラス構造のためある程度(10 個以内くらい) は許せるが、それ以上は許さないようにしたいため、動かすコマ数に対して追加するコストを変えるためです。
このとき、最初から 1 人の先生が同じコマで 1 つのクラスの授業を持つという制約を付けていると 1 割ほどが時間割変更できなくなります。ですので、最初この制約を緩和してコストに入れ、複数クラス持ってしまう先生がいた場合、最初から時間割として入っていた方のクラスを上記制約を入れた時間割変更をするという仕組みにしています。

計算量

クラス数 $N_c \sim 400$、動かすコマ数制限 $L = 10$、考慮するコマ数 $N_u \sim 420$、祖先のクラス数 $N_a \sim 10$

• クラスでまとめられるか $O(N_c^2)$
• ダイクストラ $O(N_u^2 L \log N_u)$
• 時間割変更全体 $O(N_a N_u^2 L^2 \log N_u)$
  となり、実際はもう少し早いため、おそくとも 1 秒程度で結果が出ます。

現在の進捗

バックエンドの時間割変更計算部分はある程度完成しました。この後学校側と対話し、パラメータの設定、チューニングを行う予定です。
フロント側について、バックエンド側がちゃんとうまくいっているかを調べるために作成しているため、UI 設計はしっかり行っていません。

時間割

生徒用の時間割です。
クラス: クラス47... と書かれている部分が今選択しているクラスで、その選択したクラスに対応する時間割が表示されています。現在選択されているクラスは"クラス47"と"クラス50"です。今日を 2021/4/12 としています。

クラス選択の右側、プラスマークをクリックすると検索欄が出てきて、クラス名を入力すると候補が下に出てきます。候補から選択するとそのクラスが選択されます。

先生用時間割

先生用の時間割です。時間割変更はこちらからできます。

時間割のコマをクリックして、授業できないコマを指定します。

このあと計算ボタンを押すと図のように時間割変更の詳細が出力されます。

このあと描画ボタンを押すと、選択している先生に対して、授業が追加されるところが青色、削除されるところが赤色、変更されるところが黄色に描画されます。

クラスグラフのヴィジュアライザ

ドラッグで全体を移動させたり、クラス単体を移動させたりできます。いい感じに描画するアルゴリズムは入っておらず、自分でいい感じに配置し、save ボタンを押すことでその配置を記録できます。

注釈

1. 時間割は非公開データのため、非公開データに近いもの(クラス名など)にはモザイク処理を、非公開データは仮名に変更しています。 ↩