シフト自動作成はLLMか、貪欲法か、MIPソルバか：3方式を40人×31日で比べた

シフト表をLLMに書かせる経路は、撤去する時点でもコードに残っていた。ただ、画面からはもう呼ばれていなかった。作りを読み直すと、「LLMの案が使われるのは、貪欲法で残りを埋めた後に1枠も不足が出ないときだけ」だった。

美容室向けのシフト作成サービス Shift Bud の自動作成は、3つの方式を順に試してきた。最初はLLMに月のシフト表を書かせ、次に貪欲法で空き枠を埋め、今は混合整数計画（MIP）のソルバに解かせている。貪欲法は速いが、最短勤務時間のルールを全シナリオで破っていた。手元の計測では、ソルバは40人×31日を2.4秒で最適解まで解き、その違反を0にした。

この記事は、シフトの自動作成をこれから実装する、または作り直すエンジニアとプロダクト担当に向けて、3方式を同じ物差しで比べる。最小の実装例と、AIエージェントに実装させるときの指示も付けた。

先に結論：3方式の比較

	LLMに表を書かせる	貪欲法（空き枠を順に埋める）	MIPソルバ
ルールを必ず守るか	保証がない。検査と修正を後ろに置くことになる	埋めた後に破れたルールが残る	制約に書いたルールは必ず守る
人が足りない月	後ろの検査と修正に任せることになる	不足が残る。どこが何人足りないかは、埋めた後の検査で出せる	必要人数をソフト制約にすれば、不足の合計が最小になる表を、不足の時間帯・人数と一緒に返す
40人×31日の時間	貪欲法の時間にAPIの応答待ちが乗る	0.26秒	2.4秒（実装後のベンチでは約0.85秒）
ルールの足し方	プロンプトに書き足す	優先順位を決める定数を調整する	制約を1つ書き足す
同じ入力で同じ結果になるか	なるとは限らない	なる	なる。時間切れで打ち切ったときは除く
向く場面	表を組む部分には向かない	ルールが少なく、ミリ秒で返したい	守るべきルールがあり、今後も増える

LLMの経路は、後ろの検査と修正なしでは使えなかった

LLMには、時間帯ごとの必要人数、スタッフの入れる時間、予約で固定された枠を YAML で渡し、月のシフト表を YAML で返させていた。返ってきた表は、そのままは使わなかった。

• 読めない YAML なら捨てて、貪欲法で組み直す
• 読めたら貪欲法の初期値に入れ、残りを埋めさせる
• 1枠でも必要人数に届かなければ、LLMの案を丸ごと捨てて貪欲法で組み直す

LLMの案がそのまま表になる道は無く、どの道も最後は貪欲法を通る作りだった（正直、作った側としては認めたくない構造だった）。

こうなる理由はひとつで、シフトの割り当ては、たくさんのルールを同時に満たす組み合わせを探す問題だということだ。文章の生成は、出した表がすべてのルールを満たすことを保証しない。保証がない以上は、検査と修正を後ろに置くしかない。主役のつもりで置いたLLMは実際は下書き係で、必要人数を満たすかを確かめていたのは、後ろの検査と修正だけだった。

LLMの出力に検査と修正を重ねる設計は、シフト以外でもよく見る。あなたのシステムにも、LLMの案を後ろの処理が黙って捨てている箇所はないだろうか。その形なら、修正役がLLMの案を捨てた割合をログに出しておくといい。割合が高ければ、LLMは待ち時間を足しているだけかもしれない。

貪欲法：速いが、最短勤務時間を破る

貪欲法は、必要人数に届いていない枠を見つけては、入れる人を1人ずつ足していく。同じ1か月（2026年10月）の3シナリオで測った。

シナリオ	時間	必要人数の不足	最短勤務時間の違反	月の勤務時間のばらつき（標準偏差）
5人	50ms	0	22件	11.6時間
15人（予約の固定4・休暇3）	104ms	0	54件	4.8時間
40人（予約の固定6・休暇5）	259ms	0	67件	4.9時間

不足は0で、予約で固定した枠もすべて残っている。表だけ見れば完成品だ。実際は「1回の勤務は最短◯時間」のルールが全シナリオで破れていた。検査の関数は違反を見つけていたが、表を組む処理はそれを直さない作りだった（警報は鳴っているのに、誰も止めに行かない状態）。

ルールの足し方でも差が出る。空き枠に誰を足すかは25個の定数を使った点数で決めていて、ルールを1つ足すたびに、25個のつまみのどれを回すかを考えることになる。

MIPソルバ：決め手は変数の作り方

MIPは「スタッフsが日dに勤務の候補cで入るか」を0/1の変数にし、制約を満たす組み合わせのうち目的関数が最小のものを探す。ソルバは、HiGHS を WebAssembly にした npm パッケージ highs を Node のプロセス内で動かし、別のサービスは立てていない。

詰まったのは変数の数だ。40人×31日、Mac Studio で候補の作り方を比べた。

勤務の候補の作り方	0/1変数の数	結果
15分刻みの開始時刻×長さをすべて	634,891	メモリ不足（ヒープ12GBでも）
30分刻みですべて	173,043	3秒では解なし。63秒で実行可能解
型を6つに絞る	6,786	2.4秒で最適解
型を12に増やす	13,572	3.15秒で最適解。目的値の改善は0.2%

型の6つは、入れる時間帯の始まりから4・6・8時間と、終わりまでの4・6・8時間だ。細かく刻むほど良い表になると思いきや、15分刻みはメモリを使い切っただけで、型を倍にしても目的値は0.2%しか良くならない（変数を倍に払って、手に入ったのは誤差の範囲）。全部を並べると、メモリが足りないか、3秒では解が出なかった。

候補の型に加えて、効いた工夫が3つある。

• 守らせたいルールは、候補を作る段階で吸収する。入れない時間、休暇、1日の上限に掛かる候補は作らない。短すぎる候補も、営業時間そのものが短い日を除いて作らない
• 必要人数はソフト制約にする。足りない人数を表す変数を足して大きな重みを掛けると、解けない（Infeasible）という結果が出なくなり、不足が解と一緒に返る
• 必要人数の制約は、15分ごとではなく候補の境界で区切った区間ごとに書く。型を6つに絞ると、候補の境界で区切った区間は1日最大7つなので、営業時間が1本の日なら1か月約1,700本の制約が約220本で済む

最小の例：3人・1日を解く

ソルバの使い方だけを抜き出した例を、Node.js 24 と highs 1.15.3 で動かした。npm install highs@1.15.3 のあと node shift.mjs で実行する。引数に名前を渡すと、その人を欠勤として扱う。

// npm install highs@1.15.3 してから node shift.mjs で実行する
import loadHighs from "highs";

const OPEN = 10, CLOSE = 19;                 // 営業 10時〜19時
const need = (h) => (h >= 15 ? 2 : 1);       // 15時以降は2人
const staff = [
  { id: "A", from: 10, to: 19 },
  { id: "B", from: 10, to: 19 },
  { id: "C", from: 14, to: 19 },             // 14時以降だけ入れる
].filter((s) => !process.argv.slice(2).includes(s.id)); // 引数で欠勤者を外す

// 候補: 入れる時間帯の始まりから / 終わりまでの 4・6・8 時間（はみ出すものは作らない）
const candidates = staff.flatMap((s) => {
  const set = new Set();
  for (const len of [4, 6, 8]) {
    if (s.from + len <= s.to) set.add(`${s.from}_${s.from + len}`);
    if (s.to - len >= s.from) set.add(`${s.to - len}_${s.to}`);
  }
  return [...set].map((k) => {
    const [start, end] = k.split("_").map(Number);
    return { name: `x_${s.id}_${start}_${end}`, staff: s.id, start, end };
  });
});

const rows = [];
for (const s of staff) {                     // 1人1日1シフトまで
  const xs = candidates.filter((c) => c.staff === s.id).map((c) => c.name);
  if (xs.length) rows.push(` one_${s.id}: ${xs.join(" + ")} <= 1`);
}
for (let h = OPEN; h < CLOSE; h++) {         // 足りない人数は short_h に逃がす
  const xs = candidates.filter((c) => c.start <= h && h < c.end).map((c) => c.name);
  rows.push(` cover_${h}: ${[...xs, `short_${h}`].join(" + ")} >= ${need(h)}`);
}
const hours = candidates.map((c) => `${c.end - c.start} ${c.name}`);
const shorts = Array.from({ length: CLOSE - OPEN }, (_, i) => `1000 short_${OPEN + i}`);

const lp = `Minimize
 obj: ${[...shorts, ...hours].join(" + ")}
Subject To
${rows.join("\n")}
Binary
 ${candidates.map((c) => c.name).join(" ")}
End`;

const highs = await loadHighs();
const r = highs.solve(lp, { output_flag: false });
console.log(r.Status);
for (const [name, col] of Object.entries(r.Columns)) {
  if (col.Primal > 0.5) console.log(name, col.Primal);
}

目的関数は、不足1人・1時間に1000、勤務1時間に1を掛けた合計だ。同じバージョンなら、何度実行しても同じ結果が出る。

$ node shift.mjs
Optimal
x_A_13_19 1
x_B_10_14 1
x_C_15_19 1
$ node shift.mjs C
Optimal
short_10 1
x_A_11_19 1
x_B_15_19 1

Cが休むと、不足が1人・1時間で済む組み合わせを返す。この例では10時台を欠く案と18時台を欠く案の目的値が同じ1012で、highs 1.15.3 では short_10 の案が返る。時間帯に優先があるなら、時間帯ごとに不足の重みを変える（例: 18時台だけ2000）。必要人数をハード制約にして同じ入力を解くと、返るのは Infeasible だけで、どこが足りないかは分からない（ソルバに「無理です」とだけ言われても、店長には説明できない）。

本番の期限に収めるまでに直した3つのこと

本番の実装は2回に分けて解いている。1回目で必要人数と各ルールを満たす表を作り、2回目はその表を初期解にして勤務時間のばらつきを小さくする。

手元のベンチでは0.85秒でも、本番と同じ構成の検証環境（1 vCPU・512MiB）で40人の月を流すと9秒台かかり、8秒の期限を超えた。秒数が食い違うのは条件が違うからで、0.85秒は入れない日のある人を含む実装後のベンチ、2.4秒は実装前の試作、9秒台は全員が終日入れる重いケースを検証環境で流した値だ。

直したこと	起きたこと	対処
時間制限を超える	ソルバの時間制限が縛るのは探索だけ。モデルの読み込みと結果の変換は外で走り、検証環境の40人・約1.1万変数で1〜1.5秒かかった	呼び出し全体に8秒の期限を置き、ソルバには残り時間から2秒引いた分だけ渡す
時間切れで解が1つもない	時間制限をごく短くして試すと、初期解を渡していても、ソルバが登録する前に時間が来て「解なし」で返った	予約で固定した枠だけの表を返し、残りの枠はすべて不足として出す
2回目（勤務時間をならす段）が遅い	手元の40人・全員終日可のケースで、許容する最適性のギャップが5%だと、良い解を見つけた後も証明に予算を使い切った（8.15秒）	ギャップを10%に緩めて3.8〜4.1秒。勤務時間のばらつきは変わらない

貪欲法への切り替えは残したまま本番に出した。消す前の確認は、本番の件数を待つのではなく、本番と同じ構成の検証環境で40人規模の月を1回流し、期限に収まるかを見る形にした。本番の生成回数が少なく、待っても件数から言えることがほとんどないためだ。上の表の1行目と3行目は、この確認で見つかった。

AIエージェントに実装させるときの指示

シフトの自動作成をエージェントに書かせるなら、コードの書き方より先に、何で確かめさせるかを指示する。指示がないと、上で見た落とし穴にそのまま入ることになる。

指示すること	指示しないと起きること
ルール違反を種類ごとに数える検査と、小・中・大の入力を先に作らせ、違反0を完了条件にする	不足が0の表を見て「できた」で終わり、最短勤務時間の違反に気付かない
定式化の前に、0/1変数の数を見積もらせる	15分刻みの全列挙で63万変数になり、メモリが足りなくなる
必要人数はソフト制約にし、不足を時間帯と人数で返させる	人が足りない月に Infeasible だけが返る
時間制限は呼び出し全体の期限として持ち、解なしで切れたときの返し方を決めさせる	期限を守れず、時間切れのときに何も返らない
旧方式を切り替えで残し、消す前に本番と同じ構成で最大規模のケースを流させ、期限内に収まるかを確かめさせる	期限超過が、旧方式を消した後に本番で初めて見つかる

エージェントに渡す入力は、最初から3シナリオの固定データにしておくといい。同じデータで旧方式と新方式の違反数を並べさせれば、レビューする側もその表を見るだけで済む。

どれを選ぶか

• 貪欲法で足りる: ルールが少なく、勤務の長さのように組んだ後で崩れるルールがない。ミリ秒で返す必要がある
• MIPソルバにする: 破れないルールがあり、ルールが今後も増える。人が足りない月でも、不足が最小になる表を返したい
• LLMは表を組む部分に置かない: 要望の文章を設定値に直す、結果を説明する、といった外側の役割なら合う見込みがある。ただしこれは筆者の見方で、検証はしていない

MIPで表現しきれない制約が出てきたら、次の候補は制約プログラミングのソルバ（Google OR-Tools の CP-SAT など）になる。CP-SAT の公式の例は Python・C++・Java・C# で、Node から使うなら別プロセスか別サービスになる。

まとめ

シフト自動作成で差が出るのは、守るべきルールを守れるかと、人が足りないときに何を返すかだった。LLMは保証を持たず、貪欲法は速いが組んだ後に崩れたルールを直せない。MIPソルバは、勤務の候補を型で絞れば40人×31日でも秒単位で解ける。

これから作るなら、まず違反を数える検査と3つの固定シナリオを用意し、そこに貪欲法とソルバの両方を通して比べてみてほしい。どちらが合うかは、違反の件数がそのまま教えてくれる。Shift Bud の自動作成は、月次も日次もいまこの方式で動いている。