Quantum Annealing for Staff Scheduling in Educational Environments

技術概要：教育環境におけるスタッフスケジューリングのための量子アニーリング

問題定義
本研究は、イタリアの公立学校システムに特有の複雑なスタッフ配置問題、特に非教職の学校協力者のスケジューリングに焦点を当てている。この問題には、複数の教育施設（幼稚園、小学校、中学校）にまたがって、3 つの自治体に分散した多様な労働力（正社員とパートタイム、男性と女性）を割り当てる作業が含まれる。計画期間は、午前と午後のシフトを含む標準的な 5 日間の労働週をカバーする。

この問題は、以下の密な運用および規制制約によって特徴づけられる：

• カバレッジ： 各施設のすべての稼働シフトには、少なくとも 1 人の協力者が配置されなければならない。
• 労働量制限： 正社員は週 36 時間、パートタイムは週 18 時間を上限とする。
• 休憩ルール： 1 日の労働時間が 7.2 時間を超える場合、30 分の強制休憩が必要である。
• 性別制約： 各幼稚園施設には、少なくとも 1 人の女性協力者を割り当てなければならない。
• 継続性と希望： スタッフには、特定の施設への割り当てを義務付ける拘束条件、または推奨されるが必須ではない施設割り当ての希望（ソフト制約）が存在し得る。
• 目的： 目標は、3 つの基準をバランスさせることで対立を最小化することである。すなわち、複数の施設への割り当てを減らすこと（通勤の制限と継続性の確保）、契約上の週労働量からの逸脱を最小化すること、そしてスタッフの施設希望を尊重することである。

方法論
著者は、この問題を組み合わせ最適化モデル、具体的には制約付き二次モデル（CQM）として定式化する。数式化には以下が含まれる：

• 決定変数： 日々のシフト割り当て（$x_{c,s,d,j}$）、週次施設指標（$y_{c,s}$）、および休憩指標（$b_{c,d}$）のための二値変数。
• 目的関数： 3 つの正規化された成分の重み付き和：
  1. 複数の施設で働くことに対するペナルティ。
  2. 標準的な週労働量からの逸脱に対するペナルティ。
  3. 希望しない施設への割り当てに対するペナルティ。
• 制約： 線形制約により、カバレッジ、1 日 1 シフトの制限、労働量上限、性別要件、および日次変数と週次変数間の論理的整合性が強制される。

この NP 困難な問題を解決するために、著者は D-Wave の LeapCQMHybrid ソルバーを用いて**量子アニーリング（QA）**を採用する。このハイブリッド手法は、古典的なヒューリスティック手法と量子誘導探索（重ね合わせとトンネリングの利用）を組み合わせ、解空間をナビゲートする。実験は D-Wave Advantage2 システム（4596 量子ビット）で行われ、厳密解ソルバーである Gurobi Optimizer と比較された。

主要な貢献

1. 新規応用： イタリアの学校協力者に対する特定最適化モデルを提案する初の研究であり、この文脈に特有の組織的、空間的、規制上の特殊性（例：幼稚園の性別要件や多キャンパス管理）に対処する。
2. 実世界事例研究： 9 つの施設にわたる 20 名の協力者に関する Istituto Comprensivo di Cerisano の実データを用いてモデルをテストした。
3. スケーラビリティ分析： 著者は、特定事例研究を超えて量子インスパイアード手法の堅牢性とスケーラビリティを評価するため、より大規模な合成インスタンス（最大 40 名の協力者まで拡張）を生成した。
4. CQM 定式化： この研究は、非工業的な公共部門の環境において、線形制約を伴う混合整数問題に対する D-Wave の CQM フレームワークの実用的応用を実証する。

結果

• 実世界インスタンス（20 名の協力者）： LeapCQMHybrid ソルバーは、5 回の独立した実行全体で、一貫して最適解（Gurobi によって検証済み）に到達した。目的関数値は 0.070602 であり、平均実行時間は約 15.16 秒であった。これらの結果は、すべての制約を尊重し、バランスの取れた実行可能なスケジュールを生成するモデルの能力を確認した。
• 大規模インスタンス：
  • 25 名および 30 名の協力者の場合、ソルバーは一貫して最適解を発見し（成功率 100%）、
  • 35 名の協力者の場合、ソルバーは高品質な解を発見したが、真の最適解に到達したのは 20% の実行のみであり、難易度の増加を示している。
  • 40 名の協力者の場合、ソルバーは 10 秒の時間制限内で実行可能な解を生成できず、非常に大規模なインスタンスにおける現在のスケーラビリティの限界を浮き彫りにした。

意義と主張
本論文は、量子アニーリングに基づくハイブリッド最適化手法が、教育スケジューリングにおける複雑な組み合わせ問題に対して実用的に適用可能であると主張する。結果は、これらの手法が中規模の実世界インスタンスに対して、短時間でバランスの取れた割り当てを生成し得ることを示している。

著者は、この研究を理論的な量子最適化研究と実世界の組織計画の間のギャップを埋める一歩として位置づけている。彼らは、大規模インスタンスには依然として重大な課題が残っているが、提案された手法は従来の工業分野を超えた量子コンピューティング技術の汎用性を示していると強調する。本研究は、ハイブリッド量子インスパイアードソルバーが、厳密手法が非現実的となるリソース配分タスクに対して競争力のある代替手段を提供すると結論づけているが、現在のハードウェアの限界により、さらなるアルゴリズム的またはアーキテクチャ的な進展なしには非常に大規模なインスタンスの解決が制限されることを控えめに認めている。