シフト自動割り当てを、整数計画法ではなく貪欲法+山登り法で書いた(TypeScript、依存ライブラリなし、シフっと)

文化祭やサークルのシフトを自動で割り振るWebアプリ「シフっと」の、割り当て部分だけを書きます。

アプリ全体の話は前の記事に書いたので、ここではソルバーの中身に絞ります。ファイルは1本で、約570行です。外部のソルバーには頼っていません。

解きたい問題

幹事が決めるのは、時間枠(30分や1時間)、役割(受付、調理など)、枠×役割ごとの必要人数です。参加者は枠ごとに ○ / △ / × を答えます。ここから、誰をどの枠のどの役割に入れるかを決めます。

絶対に破れないものと、できれば守りたいものに分けました。

種類	内容
絶対	×の枠には入れない
絶対	同じ枠には1役割まで
絶対	本人ができない役割には入れない
絶対	1人あたりの上限枠数、1日の上限、連続枠数の上限を超えない
絶対	幹事が固定(📌)した割り当てを動かさない
最小化	人の不足、△への割り当て、担当数の偏り、細切れ、役割の切り替え

後者は重み付きの和にして、小さいほど良い案とします。

整数計画法はやめた

最初は整数計画法(MILP)で解くつもりで、javascript-lp-solver を入れました。変数は「人×枠×役割」の0/1です。1イベント最大で100人×200枠×6役割くらいを想定していて、制約の書き方とチューニングに時間がかかりそうなので、やめました。

いまは package.json に残っているだけで、使っていません。消し忘れです。

代わりに、貪欲法で初期解を作って、山登り法で良くしています。最適解の保証はありません。ただ、幹事が見るのは「不足が赤く出た表」で、そこから手で直すので、数学的な最適より、速く返ってきて、制約を絶対に破らないことのほうが大事でした。

重み

const WEIGHTS = {
  shortage: 1000,
  maybe: 50,
  spread: 20,
  fragmentation: 20,
  roleSwitch: 1,
};

不足の1000は、ほかの項目より桁違いに大きくしてあります。人が足りない枠を作るくらいなら、△の人を入れるし、偏りも許します。

fragmentation(細切れ)は最初5でした。この重みだと、1時間入って1時間空いてまた1時間入る、というシフトが出ます。人数は合っているので、組む側からは正しい答えです。でも入る側は、空いた1時間では帰れないし、何もできません。使ってくれた人から「できるだけ連続して入れてほしい」と言われて、20に上げました。

細切れの数え方も、最初は「1枠だけ空いた飛び飛び」だけでした。いまは、同じ日の中で連続していない箇所をすべて数えます。日をまたぐ分は数えません。

状態の持ち方

人数と枠が増えても遅くならないよう、状態はオブジェクトではなく添字ベースの配列で持ちました。

const avail = new Int8Array(N * W);            // 人×枠の回答。未回答は×扱い
const roleAt = new Int32Array(N * W).fill(-1); // 人×枠 → 役割(-1は未割り当て)
const dayCount = new Int32Array(N * D);        // 人×日の担当枠数
const filled = new Int32Array(W * R);          // 枠×役割の充足数
const loadHist = new Int32Array(W + 2);        // 担当枠数ごとの人数

割り当てと取り消しは、この集計値を一緒に更新する関数にまとめています。

function assign(p: number, s: number, r: number): void {
  const list = assigned[p];
  loadHist[list.length]--;
  loadHist[list.length + 1]++;
  list.splice(lowerBound(list, s), 0, s);
  roleAt[p * W + s] = r;
  dayCount[p * D + slotDay[s]]++;
  filled[s * R + r]++;
}

loadHist は、担当枠数ごとに何人いるかの度数表です。偏り(担当枠数の最大 − 最小)は、表の両端から0でないところまで読むだけで出ます。全員の担当数を数え直す必要はありません。

最初の実装は、1手動かすたびに目的関数を丸ごと計算し直していました。これで十分だと思っていたのですが、人数を増やすと見て分かるくらい遅くなりました。いまは、1手の評価を、入れ替えに関わる2人分の差分だけにしています。

貪欲法で初期解を作る

必要な(枠, 役割)の組を時間順に見て、その枠に入れられる人を次の優先順で並べ、必要人数に達するまで埋めます。

1. ○の人を△の人より先に
2. すでにその人が入っている枠の隣(連続になる)を先に
3. ここまでの担当枠数が少ない人を先に

入れられるかどうかは canAssign でハード制約を全部確認します。

function canAssign(p: number, s: number, r: number): boolean {
  if (roleAt[p * W + s] !== -1) return false;           // 同じ枠に1役割まで
  if (avail[p * W + s] === NG) return false;            // ×の枠
  if (!roleOk[p * R + r]) return false;                 // できない役割
  if (assigned[p].length + 1 > maxSlots[p]) return false;
  if (dayCount[p * D + slotDay[s]] + 1 > maxPerDay) return false;
  if (maxRunWith(assigned[p], s) > maxConsecutive) return false;
  return true;
}

制約の確認はこの関数に集めてあります。初期解も、このあとの改善も、必ずここを通してから割り当てます。なので、どの段階の解でもハード制約は破れていません。

山登り法で良くする

局所探索の操作は3つです。不足の補充、付け替え、交換の順で試します。

• 不足の補充: 足りない枠に、いま入れられる人がいれば入れる
• 付け替え: Aさんの1件を、別のBさんに移して、目的関数が下がれば採用
• 交換: AさんとBさんの1件ずつを入れ替えて、下がれば採用

付け替えは、後から足しました。最初は交換だけだったのですが、1人に集中していて、ほかの人が0枠、という状態から抜けられなかったからです。交換では担当枠数が変わらないので、偏りが直りません。

試して、ダメなら戻す、という書き方をしています。

unassign(pa, s);
if (canAssign(pb, s, r)) {
  assign(pb, s, r);
  const newA = participantCost(pa);
  const newB = participantCost(pb);
  const delta =
    newA - cost[pa] + newB - cost[pb] + WEIGHTS.spread * (spread() - spreadBefore);
  if (delta < 0) { /* 採用 */ break; }
  unassign(pb, s);
}
assign(pa, s, r); // 元に戻す

付け替えや交換で不足の数は変わらないので、delta には入れていません。変わるのは当事者2人のコストと、偏りだけです。

交換は組み合わせが多くて重いので、付け替えで改善が出なくなってから試します。どれも改善しなくなったら終了です。

while (!timeUp()) {
  const filledAny = fillShortages();
  if (movePass() || filledAny) continue;
  if (!swapPass()) break;
}

リスタートと時間制限

山登り法は局所解で止まります。最初の1秒に限って、乱数を変えて別の初期解からやり直し、いちばん良い案を採ります。30回続けて良くならなければやめます。全体の時間上限は9秒です。

大きな入力では、最初の1回でこの1秒を使い切るので、やり直しは実質起きません。

実際の速度

ランダムに作った回答で、自分のMacのNodeで測りました。3役割、各枠の各役割に2人必要で、1時間枠、連続は最大3枠、○は4〜5割、△は1割という設定です。

参加者	枠数	必要な(枠,役割)	時間	不足	担当数の偏り
15人	16枠	48	125ms	2	3
30人	16枠	48	152ms	0	2
60人	30枠	90	469ms	0	2
100人	48枠	144	約1.0秒	0	3

15人の行は、そもそも○の人が足りない設定で、不足2は人数の問題です。

本番のCloudflare Workersで同じ時間になる保証はなく、最大規模(100人×200枠)も測っていません。ここは自信がないところです。

弱いところ

• 自動テストがありません。ハード制約を破っていないか、ランダム入力で確かめるテストを最初に書くべきでした
• 重みは勘で決めています。細切れを5から20に上げたのも、触ってみて嫌だったからで、根拠はありません
• 「この人は、この人と同じ枠に入れたい」のような、人同士の条件は入れられません

触ってもらえると助かります

文化祭やサークルのシフトで困っている人が周りにいたら、教えてあげてください。ログイン不要で、無料です。

「この条件が入れられない」「この割り当て方はおかしい」といった指摘は、コメントでお待ちしています。ソルバーが変な結果を出す入力があれば、なお助かります。