病院・介護施設向けのシフト最適化 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（開発・テスト）