概要
バイト・コールセンター・工場など多くの現場で出てくる「人や時間をどう割り当てるか」を決める問題である シフトスケジューリング問題 は、現実の業務で頻出する組合せ最適化問題である。
本記事では 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形式に変換すれば、最適化アルゴリズムにそのまま渡すことができる。
次回、実際にプログラムを動かして検証を行う実装編に続く。