【高大連携・豊島岡3】 数理最適化を用いた文化祭のシフト組みシステムの作成

1　はじめに

豊島岡女子学園の文化祭「桃李祭」では，多くの生徒が部活動や委員会など複数の仕事を掛け持ちしている。
そのため，シフト調整作業は極めて複雑であり，担当者にとって大きな負担となっているのが現状である。
既存のシフト作成手法では，各団体が求める細かな条件に合致しない場合が多く，運用が困難であった。

そこで本研究では，数理最適化の手法を用いて，桃李祭の実情に即した使いやすいシフト組みシステムを構築することを目的とする。
本システムにより，公平かつ効率的なシフトを自動生成し，生徒およびシフト作成者の負担を軽減することを目指す。
具体的には，必要な機能を検討して数理モデル化を行い，Google Colaboratory および Streamlit を用いてツールを作成した。
さらに，今年度の桃李祭のシフト作成に実際に本システムを導入し，その有用性と課題を検証した。

2　問題設定

本研究では，シフト作成における様々な制約条件を満たしつつ，全体の勤務量や希望との乖離を最小化する最適化問題を考える。

2.1　集合と定数の定義

まず，モデルで使用する集合を定義する。

• S：全ての生徒の集合
• S^senior ⊆ S：高校生の集合
• S^committee ⊆ S：委員の集合
• T：シフトの時間帯の集合（30 分単位に分割）
• T^lunch ⊆ T：昼休み時間帯の集合（11:00-14:00）
• R：担当可能な役割の集合（例：受付，案内など）
• R_s ⊆ R：生徒 s が担当可能な役割の集合

次に，定数（パラメータ）について以下のように定義する。

• N_t：時間帯 t に必要な生徒の総人数
• N_t^senior：時間帯 t に必要な高校生の人数
• N_t^committee：時間帯 t に必要な委員の人数
• N_s^lower, N_s^upper：生徒 s の最小および最大勤務回数
• ω：最大連続勤務回数
• r_s,t,r：生徒 s が時間帯 t に役割 r を担当することへの希望度
  （-2 から 2 の整数集合で，値が大きいほどその業務を避けたがっていることを表す）
• α：生徒の希望を無視した際のペナルティ係数
• β：連続勤務に対するペナルティ係数

2.2　決定変数

最適化に使用する決定変数を以下の通り定義する。

• x_s,t,r ∈ {0,1}：生徒 s が時間帯 t に役割 r を担当する場合に 1，そうでない場合に 0 をとる変数。
• z_s,t ∈ {0,1}：生徒 s が時間帯 t に何らかの役割を持つ場合に 1，持たない場合に 0 をとる補助変数。

2.3　定式化

上記の定義を用いて，本問題を以下のように定式化する。

目的関数

目的関数は以下の式 (1) で表される。

式 (1) の第 1 項は全生徒の総勤務量を表し，これを最小化することで全体の負担を減らすことを目指す。
第 2 項は，生徒の希望に反したシフト配置に対するペナルティ項であり，希望度 r_s,t,r と決定変数の積の総和をとっている。
第 3 項は連続勤務に対するペナルティ項であり，連続してシフトが入ることを抑制するためのものである。

制約条件

本モデルでは，以下の制約条件 (2)〜(9) を考慮する。

まず，人員配置に関する制約である。

式 (2) は各時間帯に必要な総人数，式 (3) および式 (4) はそれぞれ高校生と委員の必要人数を満たすことを保証する制約である。

次に，個人の勤務回数に関する制約である。

式 (5) は，各生徒の総勤務回数が，定められた下限 N_s^lower 以上かつ上限 N_s^upper 以下になるように制限している。

また，連続勤務と休憩に関する制約を以下のように定める。

式 (6) は，最大連続勤務回数が ω 未満になること（すなわち，連続勤務が ω 回に達しないこと）を保証し，
十分な休憩を取れるようにするためのものである。
式 (7) は，昼休み時間帯 T^lunch の間に，少なくとも 1 回（30 分）以上の休憩を確保するための制約である。

最後に，変数の定義および整合性に関する制約である。

式 (8) は，生徒が担当不可能な役割 r には割り当てられないことを示し，式 (9) は決定変数 x と補助変数 z の関係を定義している。

3　実装とアプリケーション

3.1　実装の流れ

本研究では，数理最適化ソルバーとして Python のライブラリである PuLP を使用し，Web アプリケーションフレームワークの Streamlit を用いてユーザーインターフェースを構築した。
具体的な処理の流れは以下の通りである。

1. 生徒やシフトの希望などのデータをランダムに生成する。
2. 生成したデータに基づき，集合・変数・パラメータを設定し，制約条件と目的関数をモデルに追加する。
3. ソルバー（PuLP）を実行し，最適解を求める。
4. Streamlit アプリ上で最適化されたシフト表を表示・作成する。
5. 結果を CSV ファイルとしてダウンロードする。

3.2　アプリケーションの構成と機能

本研究で開発したアプリケーションは，専門的な知識がないユーザーでも直感的に操作できるよう，
以下の 3 つの主要な機能ブロックで構成されている。

1．パラメータ設定とデータ生成
アプリケーションのサイドバーには，最適化モデルの挙動を制御するための各種パラメータ設定項目を配置した。
具体的には，希望を無視した際のペナルティ係数 α や，連続勤務に対するペナルティ係数 β などをスライダー等で細かく調整可能とした。
また，シフト作成の基礎となるデータはボタン操作によりランダムに生成し，即座にモデルへ適用できる仕様とした。

2．最適化の実行とステータス表示
「最適化実行」ボタンを押下することで，PuLP による計算処理が開始される。
計算終了後には，ソルバーの実行にかかった計算時間（秒）が表示され，パフォーマンスを確認することができる。

3．結果の可視化とダウンロード
導き出された最適シフトは，メイン画面上にテーブル形式で可視化される。
シフトが割り当てられた箇所は強調表示され，全体のバランスを視覚的に把握しやすいデザインとした。
また，生成されたシフト表を CSV 形式でダウンロードする機能を実装し，事後の微調整や共有を容易にした。

4　数値実験と結果

4.1　実験設定

構築したシステムを用いて，実際に今年度の桃李祭におけるシフト作成を行った。実験データの規模は以下の通りである。

• 対象人数：266 名
• シフト時間帯：8:20 ～16:30
• 役割数：7 個

4.2　結果

ソルバーによる計算の結果，総シフト数は 643 個となった。
計算に要した時間はわずか 1 分 45 秒であり，従来の手作業によるシフト作成が数時間を要していたことと比較すると，劇的な時間の短縮を実現した。
作成されたシフト表の一部や，アプリケーションの実行画面を以下に示す。

Figure 1: 作成されたアプリケーションの入力画面

また，作成されたシフト表は，各時間帯で必要な人数を十分に満たしており，複数の団体に重複して立候補している生徒についても，
勤務時間が重ならないよう自動で調整されていた。

Figure 2: 計算されたシフト表の可視化結果

5　考察

本実験を通じて，数理最適化を用いたシフト作成の有効性が確認された一方で，いくつかの課題も浮き彫りとなった。

まず成果として，シフト作成にかかる時間を大幅に削減できた点が挙げられる。
また，複雑な制約条件を自動で満たすことができ，公平性の担保にも寄与した。

しかし，出力されたシフト表を精査したところ，一部のシフトで生徒の希望する休憩時間が十分に反映されていないケースや，
シフトに入ることが可能な生徒が未割り当てとなっているケースが確認された。
その結果，間違ったシフト数は 143 個に上り，手作業での修正に約 5 時間を要した。
これは，ペナルティ係数の調整や制約条件の設定が十分でなかった可能性を示唆している。

また，システム利用面においても，シフト表作成時にアップロード用ファイルの準備に手間がかかる点や，
プログラムの操作が初心者にとってやや複雑である点などが改善点として挙げられた。

6　おわりに

本研究により，数理最適化を用いたシフト作成の有用性が示されたが，本格的な実運用に向けては解決すべき課題も残されている。
今後は以下の 3 つの観点からシステムの改良を進める方針である。

1．アルゴリズムの精度向上：
今回の実験では，一部の生徒において希望する休憩時間が十分に確保されない，あるいは勤務可能な生徒が未割り当てとなるケースが発生した。
これは，制約条件やペナルティ係数（α, β）の設定が，実際の運用要件と完全に適合していなかったことに起因すると考えられる。
今後は，これらのパラメータチューニングをより精緻に行うとともに，制約条件の見直しを行い，手作業による修正が不要なレベルまで出力精度を高めることを目指す。

2．アプリケーションの操作性と機能拡張：
現在のシステムは，データのアップロード形式や操作手順がやや複雑であり，初心者が扱うにはハードルが高いという課題がある。
この点を解消するため，入力データをより直感的に作成できる「入力ファイル自動生成機能」の実装に取り組む。
また，エラー時のフィードバックを分かりやすくするなど，UI（ユーザーインターフェース）の改善も進める。

3．汎用性とスケーラビリティの確保：
本実験では約 260 名規模のデータを使用したが，全校生徒規模（約 1,500 名）での適用を想定した場合，計算時間やメモリ使用量などの性能検証が十分ではない。
今後は大規模データを用いた負荷テストを実施し，処理速度の最適化を図る。
また，文化祭のシフトだけではなく，より多くの部活動や委員会活動のシフト作成にも応用できるよう，
役割や時間帯の設定を柔軟に変更できる汎用的なプログラム設計へと改良を行っていく。

参考文献

[1] 池上敦子「ナース・スケジューリングー調査・モデル化・アルゴリズムー」『統計数理』53 巻 2 号，2005，p.231-259.

[2] 岩永二郎ほか『Python ではじめる数理最適化』オーム社，2021.

[3] 株式会社ビープラウドほか『Python で学ぶ数理最適化による問題解決入門』翔泳社，2024.

[4] 鈴木敦夫ほか「大学業務におけるシフトスケジューリング」『オペレーションズ・リサーチ：経営の科学』54 巻 12 号，2009，p.768-773.