日勤・夜勤の勤務表を QUBO で作る

勤務表のセルをクリックして休み希望を入れ、Solve を押します。QUBO++ が、どの勤務もちょうど必要人数になり、出勤日数・夜勤・休日出勤ができるだけ均等になるように、4 週間の勤務表を作ります。

解説: ケーススタディ: C++ 版（QUBO++）· Python 版（PyQBPP）· cons(): C++ 版· Python 版

Required staff (exactly)
Rule violations–
Fairness (sum of squares)–
Lower bound–
Working days per person–
Night shifts per person–
Holiday work per person–

Click a cell to request a day off: paid leave on a weekday, no holiday work on a weekend day. Other days can be off too: QUBO++ decides who works so that every shift has exactly the required staff.

How it works

The roster covers four weeks. Every day each person works a day shift, a night shift, or is off. The staff are managers, skilled workers and regular staff. The rules are:

  1. Nobody works on a requested day off (paid leave on a weekday, no holiday work on a weekend day). Other days can be off too.
  2. Each shift has exactly the required number of staff.
  3. A weekday day shift has a manager (for customers); a night shift and a weekend day shift have a manager or a skilled worker.
  4. Nobody works more than 6 days in a row (adjustable).
  5. There is a day off between a day shift and a night shift, in either order.

Among the rosters that follow the rules, QUBO++ looks for the one that spreads the working days, the night shifts and the holiday work most evenly: it minimizes the sum of the squares of the number of working days of each person, plus those of the night shifts and of the holiday shifts.

The model uses binary variables day[i][d] and night[i][d] (person i works the day or night shift on day d). Every rule is a linear equation or inequality written with cons(), for example cons(Σt=d..d+6 (day[i][t] + night[i][t]) <= 6) and cons(night[i][d] + day[i][d+1] <= 1). QUBO++ handles these constraints directly, so the model needs no slack variables, and the squares make the objective quadratic. The search stops early when it reaches the lower bound, which proves optimality.

QUBO++ model 
Press Solve to build the model.

使い方

このデモは資源の限られた AWS Lambda 上で動いています。 デスクトップ PC 上の QUBO++ は数倍速く動きます。

勤務表を QUBO にする

職員 $i$ が日 $t$ に日勤・夜勤をするとき 1 になるバイナリ変数 $d_{i,t}$・$n_{i,t}$ を使います。 休み希望の日の変数は作りません（その日は休みに決まります）。 日 $t$ の日勤と夜勤の必要人数を $r^{\mathrm{D}}_t$・$r^{\mathrm{N}}_t$、連勤の上限を $K$ とします。 日勤の責任者になれる職員の集合 $L_t$ は、平日なら管理職、土日なら管理職と熟練者で、 夜勤の責任者になれる職員の集合 $L’$ は管理職と熟練者です。 ルールは、すべての職員 $i$ と日 $t$ について次のとおりです。

\[\begin{aligned} & d_{i,t} + n_{i,t} \le 1 && \text{1 日 1 勤務まで}\\ & \textstyle\sum_i d_{i,t} = r^{\mathrm{D}}_t, \qquad \sum_i n_{i,t} = r^{\mathrm{N}}_t && \text{必要人数}\\ & \textstyle\sum_{i \in L_t} d_{i,t} \ge 1, \qquad \sum_{i \in L'} n_{i,t} \ge 1 && \text{責任者}\\ & \textstyle\sum_{u=t}^{t+K} (d_{i,u} + n_{i,u}) \le K && \text{連勤}\\ & n_{i,t} + d_{i,t+1} \le 1, \qquad d_{i,t} + n_{i,t+1} \le 1 && \text{日勤と夜勤の切り替え} \end{aligned}\]

責任者のルールは、その勤務の必要人数が 0 の日には付けません。 目的関数は、出勤日数・夜勤・休日出勤（土日の勤務）の回数の 2 乗和です。

\[\text{最小化}\quad \sum_i \Big(\sum_t (d_{i,t} + n_{i,t})\Big)^2 + \sum_i \Big(\sum_t n_{i,t}\Big)^2 + \sum_i \Big(\sum_{t\ \text{が土日}} (d_{i,t} + n_{i,t})\Big)^2\]

必要人数がちょうどに決まっているので、3 つの回数の合計はどの勤務表でも同じです。 合計が同じなら、2 乗和は回数がそろっているときに小さくなります。

QUBO++ では、ルールをすべて cons() で書きます。 重みは目的関数の取りうる最大値より大きくしてあるので、ルールを破る勤務表は、ルールを満たす勤務表より必ずエネルギーが大きくなります。 ソルバーはこれらの制約を直接扱うので、1000 本を超える不等式にスラック変数は要りません。 モデルの変数は $d_{i,t}$ と $n_{i,t}$ だけです（サンプルでは 598 個）。 このモデルを、QUBO++ の ABS3 ソルバーが CPU 上で解きます。 3 つの回数の合計を全員にできるだけ均等に配ったときの 2 乗和が下界で、 探索がこの下界に達すると、その勤務表が最適であることが示されるので、その時点で止まります。

自分のコンピュータで動かす

QUBO++ の Python 版である PyQBPP は、Linux（x86-64・ARM64）と、WSL 経由の Windows で動きます。

pip install pyqbpp

日勤・夜勤の勤務表のページ では、このデモのサンプルと同じ問題を短いプログラムで解いています（C++ 版 もあります）。 cons() は 制約のページ で説明しています。 詳しくは インストール を見てください。 QUBO++ で解く問題は、ほかのデモ にもあります。