病院・介護施設向けのシフト最適化 SaaS ShiftMaster LM を開発しています。月次シフトの初期解生成エンジンで、貪欲法が引き起こす「不足の集中」問題を 4 フェーズアルゴリズムで解決した記録です。典型シナリオの充足率を 87.5% → 100% に改善し、500 件のランダムストレステストで中央値 +0.9% を確認しました。実装は PHP 7.4、57 件の既存テストで後退ゼロです。
システム構成と初期解の位置づけ
[自然言語] → [AI 解析] → [正規化] → [初期解生成] → [SA 最適化]
↑ 今回の対象
初期解の品質が低いと後段の焼きなまし法 (SA) が局所最適解から抜け出せません。初期解生成は「SA に渡す出発点」であり、ここでの欠員はそのまま最終品質に響きます。
問題: 不足の集中
早期停止型貪欲法の構造的欠陥
素朴な実装では、日付順にスタッフを割り当て、月間勤務日数上限 (desiredMax) に達した時点で停止する。これが「不足の集中」を生みます。
月前半で上限に達したスタッフは後半に入れません。総容量は足りているのに、割当の順序によって特定の日付に欠員が集中します。
ミニマル例題
| 項目 | 値 |
|---|---|
| 期間 | 12 日間 |
| 勤務種別 | 早番のみ |
| 必要人数 | 2 人/日 × 12 日 = 24 スロット |
| S1 上限 | 12 日 |
| S2 上限 | 6 日 |
| S3 上限 | 6 日 |
| 総容量 | 24（需要と一致） |
理論上は全スロットを埋められます。しかし貪欲法では S2・S3 が月前半に 6 日ずつ使い切り、後半は S1 だけが稼働する状態になります。S1 も前半に 6 日使っているため、後半 6 日のうち 3 日は 2 スロット目を埋められず欠員になります。結果は 21/24 = 87.5% です。
4 フェーズアルゴリズム (v2)
Phase 1: Generous Fill ソフト制約を緩めて貪欲充填
↓
Phase 2: Repair 再充填可能性スコアで削除選択
↓
Phase 3: Refill 不足比率の高い順に再充填
↓
Phase 4: Top-up Fill 規定勤務日数への積み増し
↓
後段 SA へ
Phase 1: Generous Fill
制約を満たそうとするから不足が偏る——まず制約を無視して埋める。
月間勤務日数上限 (desiredMax)・月間時間上限 (monthlyHoursLimit)・夜勤上限 (nightShiftMax) を一時的に無効化し、必要人数の多いスロットから貪欲に割り当てます。
softLimitMode = true // H5, H7, H10 を無効化
for each (日, パターン) in need降順:
while 未充足:
cand = 最良の候補スタッフ // H1〜H4, H6, H8, H9 のみ評価
if cand == null: break // 真のハード制約違反のみ停止
割当実行
softLimitMode = false
この時点では多くのスタッフが上限を超過しています。
Phase 1 終了時:
S1: 8日, S2: 8日 (上限 6 超過), S3: 8日 (上限 6 超過)
Phase 2: Repair
超過分を削除します。ここで「どの割当を削除するか」が結果を左右します。
削除候補ごとに 再充填可能性スコア を計算します。
refillScore(d, p, s) = 「スタッフ s の代わりに
日付 d のパターン p に入れる他のスタッフの人数」
スコアが高い（= 代わりが見つかりやすい）スロットから優先して削除します。同点の場合は充足率の高い順です。
S2 の超過 2 日 → S1 が未割当の日を優先削除 → 日4, 日6
S3 の超過 2 日 → S1 が未割当の日を優先削除 → 日4, 日12
freedSlots = {日4×2, 日6, 日12}
Phase 3: Deficiency-sorted Refill
解放されたスロットを不足比率 (1 − filled/need) の高い順に埋め直します。
不足比率: 日4 (0/2 = 100%) > 日6 (1/2 = 50%) = 日12 (1/2 = 50%)
S1 が 日4, 日6, 日12 に入る → S1: 8→12日
最終: S1: 12日, S2: 6日, S3: 6日 → 24/24 = 100% ✅
Phase 4: Top-up Fill
Phase 3 までで需要は満たされましたが、スタッフの契約上の規定勤務日数 (desiredMax) に未達のケースが残ります。総需要 < 総容量の場合、需要を満たした時点で割当が止まるためです。
未達スタッフを over-fill 許容で余剰スロットに追加配置します。スコア関数は over-fill が最小のスロットを優先するよう設計し、特定日への集中を防ぎます。
各未達スタッフについて:
deficit = target - 現在の勤務日数
deficit の大きい順に最良スロットへ配置
進捗がなければ終了
設計上の判断
連続勤務上限 (H3) は緩めない
Phase 1 では月間上限系を緩めましたが、連続勤務上限（例：連続 5 日まで）は常時 enforce します。
月間上限の超過は 1 日削除すれば解消しますが、連続上限の超過は分割が必要で、隣接する合法な連続はそれ自体が削除対象に選ばれにくい。修復コストが根本的に違うため、最初から緩めない判断をしました。
ストライド interleaving
貪欲法は「前から順に埋める」ので front-loading が起きやすいです。Phase 1・2・3 の各所でスロットの処理順序にストライドを入れます。
通常: 日1, 日2, 日3, 日4, 日5, 日6 ...
ストライド: 日1, 日4, 日7, 日2, 日5, 日8, 日3, 日6 ...
Phase 4 の over-fill は意図的
需要を超えた配置は充足率 100% 超になりますが、バグではありません。現場では「1 人多めに入る」ことは許容されても「規定日数に達しない」ことは問題になります。
後段 SA がこの over-fill を剥がさないよう、ペナルティ重みを非対称に設定しています。
| 違反種別 | 重み | 意図 |
|---|---|---|
| 不足 | 500 | 絶対に避けたい |
| 過剰 | 200 | 不足の 40%。over-fill は許容 |
| 目標日数未達 | 220 | over-fill より高く設定し、Top-up を剥がさせない |
Phase 2 の肝: なぜ再充填可能性スコアが必要か
当初は「充足率の高いスロットから削除する」だけで実装しました。結果は 84.4% です。
再充填可能性スコアを加えたところ 93.8% に改善し、さらにシナリオを調整して 100% に到達しました。
「充足率が高い = 削除しても被害が少ない」だけでは不十分で、「削除した後に誰が埋めるのか」の先読みが決定的に効きました。
計算量は O(overLimitSlots × |S|) ですが、500 件のストレステストで増加した実行時間は 1 シナリオあたり平均 0.75ms で実用上の問題はありません。
評価
典型シナリオ
| アルゴリズム | 充足率 |
|---|---|
| v1（早期停止型貪欲） | 87.5%（21/24） |
| v2（4 フェーズ） | 100.0%（24/24） |
500 件ストレステスト
スタッフ数 2〜25 名、期間 28〜31 日、パターン 1〜3 種のランダムシナリオです。
| 指標 | v1 | v2 | 差分 |
|---|---|---|---|
| 充足率 中央値 | 61.8% | 62.7% | +0.9% |
| 充足率 p75 | 84.8% | 85.4% | +0.6% |
| 充足率 95%未満 | 435 件 | 428 件 | −7 件 |
| 実行時間（500 件合計） | 2378ms | 2755ms | +16% |
min・p25 が変化しないのは、スタッフ絶対数が need を下回る「構造的不足」のケースで v2 でも救えないためです。中央値〜p75 の改善は、ソフト上限が binding だったシナリオで Repair が機能したことを示しています。
57 件の既存テストは v1/v2 ともに全件 PASS でした。既存 fixture の不足は workPattern 由来の hardOff（ハード制約）起因で、v2 が効くケースではありませんでした。理論的な予想と一致しています。
まとめ
貪欲法の不足集中問題に対し、Relax-and-Repair の考え方を軸に 4 フェーズアルゴリズムを設計しました。
核心は Phase 2 の 再充填可能性スコア——削除前に「誰が代わりに入れるか」を定量化する先読み指標です。単純な被害最小削除では到達できなかった 100% 充足を可能にしました。
この設計は制約付き割当問題全般に使える考え方で、「まず密に埋めて後から整形する」アプローチが制約の厳しい局面で有効なことを改めて確認しました。
動作環境: PHP 7.4、さくらレンタルサーバー、Windows 11（開発・テスト）