日本の小学校・中学校・高等学校の週時間割を整数計画法で自動提案し、 人が画面上でドラッグ&ドロップで微調整して仕上げるためのWebアプリケーション。
- 学習指導要領の標準授業時数から、教科・週コマ数・教員・特別教室を自動生成する
- 制約を満たす時間割を数秒〜数十秒で提案する
- 提案結果を手で直せる。動かした瞬間に制約違反が赤／黄で表示される
- 気に入ったコマを**固定（ロック）**して、残りだけを組み直せる
詳しい背景と根拠は 要件定義、実装時に置いた判断は 仮定記録 にまとめてある。
backend/ FastAPI + SQLAlchemy + PuLP（整数計画ソルバー）
frontend/ Vite + React + TypeScript + @dnd-kit
e2e/ Playwright（提案 → 編集 → 再提案 の一連を通す）
docs/ 要件定義（requirements.md）と仮定記録（assumptions.md）
benchmarks/ 実態規模での求解時間の計測スクリプト
archive/ 2019年の強化学習による実験（現在は使用していない）
前提: Python 3.11 以上、Node.js 20 以上。
# バックエンド
cd backend
pip install -r requirements.txt
python -m uvicorn app.main:app --reload --port 8000
# フロントエンド（別ターミナル）
cd frontend
npm install
npm run dev # http://127.0.0.1:5173ブラウザで http://127.0.0.1:5173 を開き、校種と1学年あたりの学級数を選んで 「作成する」→「自動提案」を押す。
cd backend && python -m pytest # ユニット/統合 50件
cd frontend && npm run typecheck # 型チェック
cd e2e && npm install && npx playwright test # E2E（バックエンドとフロントを自動起動）学習指導要領の標準授業時数を授業週数で割ると、必要な週コマ数はこうなる。
| 学年 | 週コマ数 | 週の枠数（5日×6コマ） |
|---|---|---|
| 小1 | 25 | 30 |
| 小4〜6・中1〜3 | 29 | 30 |
| 高（全日制標準） | 30 | 30 |
空き枠は週0〜1コマしかない。ほぼ完全充填問題であり、少しでも条件を足すと ハード制約のままでは実行不可能になる。そのため次の設計を採っている。
ハード制約（H1〜H6）はすべて「1つも配置しない解」で充足できる形にしてある。
したがってモデルは常に実行可能で、Infeasible は返らない。条件が厳しすぎる場合は
「何コマ足りないか」が S1（週コマ数の未充足）として必ず数値で返る。
利用者の画面に「解が見つかりませんでした」とだけ出る状態を作らないための設計。
backend/app/solver/constraints.py の各制約クラスが2つの顔を持つ。
class TeacherOccupancy(Constraint):
def apply(self, spec, ctx): # 整数計画モデルに制約を追加する（自動提案）
def check(self, spec, places): # 既存の割当を検査して違反を返す（手編集の検証）ソルバーと検証器を別々に書くと「画面上はOKなのに再提案すると弾かれる」というズレが 必ず起きる。同じクラスに両方を持たせることで、構造的にそれを防いでいる。
高校の選択科目では、1つの学級の生徒が同じ時間帯に物理・化学・生物へ分かれる。 つまり学級と受講集団は一致しない。そこで時間割のセルに入るのは Course（講座）とし、 講座は「担当教員1名・受講学級1つ以上・週コマ数」を持つ。小中は「1学級＝1講座」に縮退する。
選択科目群（ParallelGroup）は学級から見れば1コマなので、学級の重複チェック（H1）は 群を1単位として数える。
実測すると、小・中学校は数秒だが高校は状況により20秒を超える。HTTPリクエストの中で 待たせられないため、求解はジョブID＋ポーリングにしている。一方、手編集の検証は ミリ秒で終わるので同期で返す。
benchmarks/solver_benchmark.py と、アプリが生成する実データでの計測。
| インスタンス | 講座数 | 求解時間 | 未配置 | ハード違反 |
|---|---|---|---|---|
| 小学校 19学級（3学級/学年＋特支） | 194 | 5.3秒 | 0 | 0 |
| 中学校 13学級（4学級/学年＋特支） | 156 | 4.2秒 | 0 | 0 |
| 高等学校 15学級（5学級/学年） | 205 | 19.8秒 | 0 | 0 |
解の品質は15秒で頭打ちになり、それ以降の時間はすべて最適性の証明に費やされる。 そのため相対ギャップ2%・時間制限30秒で打ち切っている。
ハード制約（違反しない）
| コード | 内容 |
|---|---|
| H1 | 1つの学級の同一コマに2つ以上の講座を置かない（選択科目群は1コマと数える） |
| H2 | 1人の教員が同一コマに2つ以上の講座を担当しない |
| H3 | 特別教室の同時使用数が保有数を超えない |
| H4 | 配置禁止枠には置かない |
| H5 | 教員の不在枠には置かない |
| H6 | 固定された割当は動かさない |
ソフト制約（重み付きで最小化。違反は画面に黄色で表示される）
| コード | 内容 | 重み |
|---|---|---|
| S1 | 講座の週コマ数を満たす | 1000 |
| S2 | 同じ講座を1日に置ける回数の上限（週内分散も兼ねる） | 100 |
| S3 | 教員の週持ちコマ数の上限（既定18コマ） | 50 |
| S4 | 選択科目群を同一コマに揃える | 500 |
| S8 | 実験・実習・体育を2コマ連続で配置する | 20 |
| S9 | 主要教科を午前（1〜4限）に寄せる | 5 |
特別支援学級の交流及び共同学習（要件書の S5）は、制約ではなく 「通常学級の講座に特別支援学級を追加する」というデータ構造で保証している。 教員の空きコマ分散（S7）と担任の自クラス滞在（S10）は未実装。
「細かく確認せず仮定を置いて進める」方針で実装したため、判断が必要だった箇所は
すべて docs/assumptions.md に A-01〜A-31 として記録してある。
各仮定には根拠と「見直し条件」を付けているので、実運用に載せる際はそこから確認できる。
実測の結果として当初の設計から変えた点（A-24〜A-29）も、変えた理由とともに残してある。
このリポジトリは2019年に強化学習（DQN）で時間割を解く実験として始まったが、
実問題は解けないまま止まっていた。同時期に試された線形計画法のノートブックだけが
最適解に到達していたため、そちらを土台としてWebアプリケーションに作り直した。
当時のコードは archive/ に残してある。
- 要件定義: docs/requirements.md
- 仮定記録: docs/assumptions.md