学校の時間割の作成を自動化 — Claude CodeとOR-Toolsで制約を解く

学校の時間割は、条件を書き出せば「解ける形」にできます。学級ごとの週時数、教員の持ち時数、理科室や体育館が同じ時間に1つしか使えないこと。これらを制約として並べ、Googleの最適化ライブラリOR-Toolsに解かせます。

コードはClaude Codeに書かせます。ただし時間割は、条件が1つ抜けても表がそれらしく出てしまう種類の問題です。この記事では、解を出すスクリプト、別コードによる検算、解けないときに違反を数える診断の3本を作ります。解けない原因を探る2通りの方法を実際に走らせた結果も載せます。

作るもの — 4学級・5教科・教員5人の週時間割

題材は、1年生4学級、月〜金の1日5コマ、5教科です。教員は教科ごとに1人で、全学級を1人で受け持ちます。実際の学校より単純にしてあり、条件の足し方は後半で説明します。

週の上限は、週時数に4学級を掛けた値です。理科と体育は担当が1人ずつなので、この例では特別教室の重なりと教員の重なりが同じ結果になります。

1学級あたり18コマで、枠は25コマです。残る7コマは空きコマになります。理科の担当は4学級で週12コマを受け持つ計算で、不在の水・木を除いた3日、15コマの中に収める必要があります。

実行環境は手元のMacで、Python 3.12.2、OR-Toolsは9.15.6755です。インストールは公式がPipパッケージを勧めています。

python3 -m venv v && ./v/bin/pip install ortools

時間割の条件を、制約の種類に分ける

条件は、解の形を決めるものと、数を合わせるものに分けると整理しやすくなります。

変数は「学級c・教科s・曜日d・時限pに授業があるか」という真偽値です。4学級×5教科×5日×5コマで500個になります。

OR-Toolsには整数計画向けのCP-SATソルバーがあり、制約は整数で書きます。小数が混じる条件は、整数に直してから渡します。時間割の条件はほぼ整数なので、そのまま書けます。重なりの制約には add_at_most_one、ちょうど1つの制約には add_exactly_one を使います。公式のシフト割当の例も、同じ2つで「1シフトに1人」「1人は1日1シフトまで」を表しています。

Claude Codeに渡す指示とCLAUDE.md

最初の依頼は、コードそのものより「何を守らせるか」を具体的に書くのが肝心です。

timetable.py を作ってください。
- ortools の CP-SAT で、4学級・5教科・月〜金の1日5コマの週時間割を組む
- 制約は上の表のとおり(週時数、教員の持ち時数上限と不在曜日、理科室・体育館の同時使用不可)
- 学級・教員・教科の一覧はファイル冒頭の辞書だけで変えられるようにする
- 解けたら 1-1 の時間割を表で出す
- 別ファイル check.py で、解から制約を数え直して違反件数を出す

セッションをまたいで守らせたいことは、CLAUDE.mdに置きます。Claude Codeは、CLAUDE.mdを毎回のセッション開始時に読みます。公式は、指示が検証できる具体さであるほど従われやすいと説明しています。「テストを走らせる」ではなく「npm test を実行する」と書く、という例が挙がっています。時間割向けには、次のように書けます。

## 時間割スクリプト
- 解の表示: `python timetable.py`
- 検算: `python check.py`(違反件数が0でなければ終了コード1)
- 制約を足したら、先に check.py に同じ制約の検算を足す
- INFEASIBLE / UNKNOWN のときは原因を推測せず、`python relax.py` で
  違反コマ数を出してから報告する
- 学級・教員・教科の追加は冒頭の辞書だけを編集する

CLAUDE.mdは短いほど従われやすく、1ファイル200行以内が目安とされています。時間割に関する決まりごとはこの程度で収まります。

制約をコードに落とす

Claude Codeが書いたものを読むときは、制約ごとのブロックが分かれているかを見ます。次は、手元で走らせた timetable.py の核になる部分です。

x = {(c, s, d, p): m.new_bool_var(f"x_{c}_{s}_{d}_{p}")
     for c in CLASSES for s in SUBJECTS for d in range(5) for p in PERIODS}
 
# 学級×教科の週時数
for c in CLASSES:
    for s, (hours, _) in SUBJECTS.items():
        m.add(sum(x[c, s, d, p] for d in range(5) for p in PERIODS) == hours)
# 学級は同じコマに1教科まで
for c in CLASSES:
    for d in range(5):
        for p in PERIODS:
            m.add_at_most_one(x[c, s, d, p] for s in SUBJECTS)

教員の「同時に1学級まで」「不在曜日」「持ち時数上限」と、特別教室の「同時に1学級まで」も、同じ形のブロックです。

for t, v in TEACHERS.items():
    for d in range(5):
        for p in PERIODS:
            m.add_at_most_one(x[c, s, d, p] for c in CLASSES for s in v["subjects"])
    for d in v["absent"]:
        for p in PERIODS:
            for c in CLASSES:
                for s in v["subjects"]:
                    m.add(x[c, s, d, p] == 0)
    m.add(sum(x[c, s, d, p] for c in CLASSES for s in v["subjects"]
              for d in range(5) for p in PERIODS) <= v["cap"])

実行すると、解が見つかった旨と、1-1の時間割が出ました。

./v/bin/python timetable.py

status: OPTIMAL
[1-1]
1限 -   数学  英語  英語  -  
2限 数学  国語  -   英語  体育 
3限 理科  理科  体育  数学  体育 
4限 国語  -   -   数学  国語 
5限 国語  -   英語  -   理科 

列は月〜金、「-」は空きコマです。目的関数を置いていないので、これは「条件を満たす表の1つ」にすぎません。空きコマの偏りや、同じ教科が続く並びを良くしたいなら、別の制約か目的関数を足します。

解けても信用しない — 別コードで数え直す

ソルバーが解を返したことと、条件が全部入っていることは別の話です。制約の式を1行書き忘れても、ソルバーはエラーを出さずに別の表を返します。そこで、解の表だけを受け取って条件を数え直す check.py を、解く側とは別に書かせます。

bad = 0
for d in range(5):
    for p in T.PERIODS:
        for t, v in T.TEACHERS.items():
            n = sum(s.value(x[c, sj, d, p]) for c in T.CLASSES for sj in v["subjects"])
            bad += n > 1 or (n and d in v["absent"])
        for sj, (_, r) in T.SUBJECTS.items():
            if r:
                bad += sum(s.value(x[c, sj, d, p]) for c in T.CLASSES) > 1
print("違反件数:", bad)

出力は次のとおりです。

違反件数: 0
佐藤 16 / 16
鈴木 16 / 16
高橋 12 / 12
田中 12 / 12
伊藤 16 / 16

持ち時数の列は、実際に置かれたコマ数と上限の比較です。全員が上限ちょうどまで使われています。ここで余裕が無いことが分かるので、後で1人の上限を下げると、すぐ解けなくなります。

配送ルートの検算の考え方は、配送ルート最適化をOR-ToolsとClaude Codeで作る手順にまとまっています。時間割も「ソルバーの出力を信じず、別の経路で数える」点は同じで、数える対象が積載量から教員とコマに変わります。

解けないとき、衝突している制約をどう出すか

教員の持ち時数上限は、年度の途中で変わる条件です。理科の高橋先生の上限を12から8に下げると、理科の必要コマ(週12)に4コマ足りません。条件を知っている人なら一目で分かりますが、条件が数十になると、画面の前では分かりません。

衝突を出す方法は2通りあります。両方を同じデータで走らせました。

緩める方法の核は、次のとおりです(relax.py)。

over = m.new_int_var(0, 20, "")
m.add(sum(x[c, s, d, p] for c in T.CLASSES for s in v["subjects"]
          for d in range(5) for p in T.PERIODS) <= cap + over)
pen.append((f"持ち時数上限 {t}(上限 {cap})", over))
...
m.minimize(sum(v for _, v in pen))

週時数の側にも「足りない分」の変数を同様に置いてあります。実行結果は次のとおりです。

status: OPTIMAL 違反の合計: 4.0
 - 持ち時数上限 高橋(上限 8): 4 コマ分

違反の合計は4コマで、すべて高橋先生の上限に集まりました。「理科の担当を増やす」「上限を12に戻す」「理科の週時数を減らす」のどれを選ぶかは、学校側の判断です。選ぶための材料が、数字で出ます。

CLAUDE.mdに「INFEASIBLE / UNKNOWNのときは relax.py で違反コマ数を出してから報告する」と書いたのは、このためです。Claude Codeが「条件が厳しすぎるようです」と推測で答えるのを防ぎます。

検算を終了条件にする — Stop hook

「検算をしてから終わる」と書いても、Claude Codeが毎回守る保証はありません。公式のベストプラクティスは、確実に守らせたいチェックを Stop hookにする方法を挙げています。Stop hookはClaude Codeが応答を終えようとするたびに走り、スクリプトが終了コード2を返すと、Claude Codeは作業に戻されます。

公式の例は型チェックですが、検算スクリプトにも使えます。.claude/settings.json に次のように書きます。

{
  "hooks": {
    "Stop": [
      {
        "hooks": [
          { "type": "command", "command": "python check.py 1>&2 || exit 2" }
        ]
      }
    ]
  }
}

標準エラーに出した内容が、Claude Codeに「まだ終われない理由」として返ります。check.py が違反件数や、どの教員のどのコマが重なったかを出力していれば、それがそのまま次の修正の手がかりになります。同じ理由で止まり続けたときの上限も公式に書かれていて、連続8回止めると、Claude Codeの側が打ち切ります。

このモデルに入っていない条件

実際の時間割にはもっと多くの条件があります。このモデルが扱っていない例を挙げます。

• 担当教員が学級ごとに違う(教科に複数の教員がいる)
• 学年合同の授業や、複数の教員が入る授業
• 実技教科の連続2コマ
• 教員の1日の持ち時数の上限や、同じ曜日の連続コマ数
• 隔週の授業、行事で使えない時間帯

どれも「コマの重なり」「数の合わせ込み」「使えないコマ」のどれかに分類できます。足すときは、先に check.py に検算を足し、その検算が失敗する状況を作ってから、制約を書かせます。この順番にしておくと、制約が効いていることを自分で確かめられます。

つまずきやすい箇所

自分の学校のデータで回すとき

手順は4つです。

塾の講習の時間割を、表計算ソフトとClaudeで組む場合の考え方は、塾の夏期講習の時間割と講師割当をClaude for Excelで組む手順で扱っています。条件が少なく、表で見渡せる規模なら、そちらのほうが手軽です。学級数と教員数が増えて、重なりの確認を人の目で続けられなくなったところから、ソルバーに任せる意味が出てきます。アルバイトの希望を集計するシフト表は、Claudeでシフト表を作成する手順にあります。

時間割の最終的な確定は、学校の責任者が行うものです。スクリプトが出すのは、条件を満たす候補と、満たせないときの違反の数字までです。