概要

バイト・コールセンター・工場など多くの現場で出てくる「人や時間をどう割り当てるか」を決める問題である シフトスケジューリング問題 は、現実の業務で頻出する組合せ最適化問題である。
本記事では QUBO（二次の二値最適化問題） の枠組みで簡単なシフト割当を作り、OpenJij で解く実装例を紹介する。

1. 問題定義

まず「シフトスケジューリング問題」を数理的にどう表現するかを整理する。

1.1 基本設定

従業員数 $E$: スケジュールを作る対象となる人数
日数 $D$: スケジュールを作る期間（日単位）
シフト種別 $S$: ここでは「朝 (Morning)」「夕 (Evening)」「夜 (Night)」の3種類とする

1.2 変数の定義

従業員 $e$ が日 $d$ のシフト $s$ に入るかどうかを表す変数を $x_{e,d,s}$ とする。

$x_{e,d,s} = 1$ : 従業員 $e$ が日 $d$ にシフト $s$ に入る
$x_{e,d,s} = 0$ : 従業員 $e$ はそのシフトに入らない

このように「0か1か」で表す 二値変数（バイナリ変数） を扱う。

1.3 制約条件

現実的なシフトにはさまざまな制約がある。ここでは代表的なものを取り上げる。

最低必要人数
例えば「朝シフトには最低2人必要」など。
$m_s$ をシフト $s$ の必要人数とすると、次の条件を満たす必要がある。

$$
\sum_{e=1}^E x_{e,d,s} \geq m_s
$$
1日1シフト制約
同じ従業員が1日に複数のシフトに入らないようにする。

$$
\sum_{s \in S} x_{e,d,s} \leq 1
$$
連続夜勤を避ける
同じ従業員が連続して夜勤に入るのは負担が大きいので、できるだけ避ける。

$$
x_{e,d,\text{Night}} + x_{e,d+1,\text{Night}} \leq 1
$$
過労防止（最大勤務日数）
1週間に勤務できる日数を $M$ 日までとする。

$$
\sum_{d=1}^D \sum_{s \in S} x_{e,d,s} \leq M
$$
希望シフトの尊重
従業員が希望するシフトが入っている場合は「報酬」として評価を高くする。

QUBOでは、解（スケジュール）の良し悪しを エネルギー関数 で評価する。
エネルギーが小さいほど「良い解」とみなされる。

制約条件は $(\text{制約式})^2$ の形で追加され、違反があるとペナルティが加算される。
つまり 制約を守れば $0$、違反するとエネルギーが増える という仕組み。

2. QUBOによる定式化

2.1 QUBOとは

QUBO（Quadratic Unconstrained Binary Optimization）は、
「二次式の形で書かれた二値最適化問題」を指す。

一般形は次の通り。

$$
\min_{x \in {0,1}^n} \Bigg( \sum_i a_i x_i + \sum_{i<j} b_{ij} x_i x_j + c \Bigg)
$$

ここで:

$x_i$ : 二値変数（0か1）
$a_i$ : 線形項の係数
$b_{ij}$ : 二次項の係数（変数同士の関係を表す）
$c$ : 定数項（オフセット）

2.2 制約をQUBOに変換する

制約を「満たさないと損をする」形で数式にする。
典型的には「二乗のペナルティ」として追加する。

例：シフトの最低人数を $m_s$ とした場合、

$$
(m_s - \sum_e x_{e,d,s})^2
$$

を目的関数に加える。
人数が足りないと値が大きくなるため、それを避ける方向に最適化が働く。

同様に:

1日1シフト: $(\sum_s x_{e,d,s} - 1)^2$
最大勤務日数: $(\sum_{d,s} x_{e,d,s} - M)^2$
希望シフト: 希望が満たされた $x_{e,d,s}$ に負の係数を加える（= 報酬）

こうしてすべての制約をQUBO形式に変換すれば、最適化アルゴリズムにそのまま渡すことができる。

次回、実際にプログラムを動かして検証を行う実装編に続く。