# シフトスケジューリング問題
:::{container} prog-cpp
以下の**シフトスケジューリング問題**を考えます.この問題は,総労働者コストを最小化するスケジュールを見つけることを目的とします.
- 6人の労働者と,1日目から31日目までの31日間の計画期間があります.簡単のため,すべての労働者は0日目と32日目は休みであると仮定します.
- 1日目から31日目まで,各日にちょうど4人の労働者をスケジュールする必要があります.
- 各労働者について以下の制約を満たす必要があります：
- 20日間または21日間勤務する,
- 連続勤務は6日以内,
- 連続勤務は3日以上,
- 孤立した休日がない（休日は連続でなければならない）.
## シフトスケジューリング問題のQUBO定式化
QUBO定式化では,$6\times 33$ のバイナリ変数行列 $X=(x_{i,j})$ ($0\leq i\leq 5, 0\leq j\leq 32$) を使用します.労働者 $i$ が $j$ 日目に勤務するのは $x_{i,j}=1$ のときかつそのときに限ります.
すべての労働者は0日目と32日目は休みであるため,次を固定します：
$$
\begin{aligned}
x_{i,0}=x_{i,32}=0 & &(0\leq i\leq 5).
\end{aligned}
$$
制約は以下のように定式化されます.
### 日次配置制約
各日にちょうど4人の労働者をスケジュールしなければなりません：
$$
\begin{aligned}
\sum_{i=0}^{5} x_{i,j} = 4& &(1\leq j\leq 31)
\end{aligned}
$$
### 総勤務日数制約
各労働者は20日間または21日間勤務しなければなりません：
$$
\begin{aligned}
20\leq \sum_{j=0}^{32} x_{i,j} \leq 21& &(0\leq i\leq 5)
\end{aligned}
$$
### 最大連続勤務日数制約
どの労働者も7日以上連続で勤務してはなりません：
$$
\begin{aligned}
x_{i,j}x_{i,j+1}x_{i,j+2}x_{i,j+3}x_{i,j+4}x_{i,j+5}x_{i,j+6} = 0 & &(0\leq i\leq 5, 0\leq j\leq 26)\\
\end{aligned}
$$
### 最小連続勤務日数制約
各勤務期間は少なくとも3日連続の勤務日で構成されなければなりません：
$$
\begin{aligned}
\bar{x}_{i,j}x_{i,j+1}x_{i,j+2}\bar{x}_{i,j+3} = 0 & &(0\leq i\leq 5, 0\leq j\leq 29)\\
\bar{x}_{i,j}x_{i,j+1}\bar{x}_{i,j+2} = 0 & & (0\leq i\leq 5, 0\leq j \leq 30)
\end{aligned}
$$
### 孤立休日禁止制約
どの労働者も2つの勤務日の間に1日だけの休日を持ってはなりません：
$$
\begin{aligned}
x_{i,j}\bar{x}_{i,j+1}x_{i,j+2} = 0 & &(0\leq i\leq 5, 0\leq j\leq 30)\\
\end{aligned}
$$
### 総労働者コスト
$C=(c_i)$ をコストベクトルとし,$c_i$ は労働者 $i$ を配置する1日あたりのコストを表します.
総労働者コストは次のように定式化されます：
$$
\begin{aligned}
\sum_{i=0}^5\sum_{j=0}^{32} c_i x_{i,j}
\end{aligned}
$$
この目的関数を上記の制約のもとで最小化します.
## シフトスケジューリングのHi-QUBOプログラム
上で定義したシフトスケジューリング問題は,Hi-QUBOを用いて以下のように定式化・求解できます：
```{literalinclude} /../programFiles/cppPrograms/example/real/shift-scheduling-program1.cpp
:language: cpp
:caption: shift-scheduling-program1.cpp
```
このプログラムでは,変数と式は以下のように定義されています：
- `x`: $6\times 33$ のバイナリ変数行列.
- `workers_each_day`: `x` の列方向の和を含む配列で,各日に配置された労働者数を表します.
- `each_day_4_workers`: 各日にちょうど4人の労働者が配置されているときかつそのときに限り最小値0をとる制約式.
- `workers_working_days`: `x` の行方向の和の配列で,各労働者の総勤務日数を表します.
- `work_20_21_days`: 各労働者が20日間または21日間勤務しているときかつそのときに限り最小値0をとる制約式.
- `no_more_than_6_consecutive_working_days`: どの労働者も7日以上連続で勤務していないときかつそのときに限り最小値0をとる制約式.
- `no_less_than_3_consecutive_working_days`: すべての勤務期間が少なくとも3日連続の勤務日で構成されているときかつそのときに限り最小値0をとる制約式.
- `no_single_day_off`: どの労働者も2つの勤務日の間に1日だけの休日を持っていないときかつそのときに限り最小値0をとる制約式.
- `constraints`: すべての制約式の和.
- `total_worker_cost`: 総労働者コストを表す式.
### QUBO構築と求解
`total_worker_cost` と `constraints` をペナルティ係数10000で加算することにより,シフトスケジューリング問題のQUBO定式化を表す式 `f` を得ます.
`qbpp::MapList` オブジェクト `ml` は,0日目と32日目に対応する変数の値を固定するために使用されます.
`qbpp::replace()` 関数を `f` に `ml` を適用することで,新しい式 `g` が得られます.
次に,Easy Solver が `g` に適用され,得られた解が `sol` に格納されます.
得られた解は以下のとおりです：
```{include} /../programFiles/markDown/example/real/shift-scheduling.md
:start-after:
:end-before:
```
総労働者コスト `1465` の実行可能なシフトスケジュールが得られ,すべての制約が満たされていることがわかります.
:::
:::{container} prog-python
以下の**シフトスケジューリング問題**を考えます.この問題は,総労働者コストを最小化するスケジュールを求めることを目的とします.
- 6人の労働者がおり,計画期間は1日目から31日目までの31日間です.
簡単のため,すべての労働者は0日目と32日目は休みとします.
- 1日目から31日目までの各日に,ちょうど4人の労働者を配置する必要があります.
- 各労働者について以下の制約を満たす必要があります：
- 20日または21日勤務する,
- 連続勤務日数は6日以下,
- 連続勤務日数は3日以上,
- 孤立した休日がない（休日は連続でなければならない）.
## シフトスケジューリング問題のQUBO定式化
QUBO定式化では,$6\times 33$ のバイナリ変数行列 $X=(x_{i,j})$ ($0\leq i\leq 5, 0\leq j\leq 32$) を使用します.労働者 $i$ が $j$ 日目に勤務するのは $x_{i,j}=1$ のときかつそのときに限ります.
すべての労働者は0日目と32日目は休みであるため,次を固定します：
$$
\begin{aligned}
x_{i,0}=x_{i,32}=0 & &(0\leq i\leq 5).
\end{aligned}
$$
制約は以下のように定式化されます.
### 日次配置制約
各日にちょうど4人の労働者をスケジュールしなければなりません：
$$
\begin{aligned}
\sum_{i=0}^{5} x_{i,j} = 4& &(1\leq j\leq 31)
\end{aligned}
$$
### 総勤務日数制約
各労働者は20日間または21日間勤務しなければなりません：
$$
\begin{aligned}
20\leq \sum_{j=0}^{32} x_{i,j} \leq 21& &(0\leq i\leq 5)
\end{aligned}
$$
### 最大連続勤務日数制約
どの労働者も7日以上連続で勤務してはなりません：
$$
\begin{aligned}
x_{i,j}x_{i,j+1}x_{i,j+2}x_{i,j+3}x_{i,j+4}x_{i,j+5}x_{i,j+6} = 0 & &(0\leq i\leq 5, 0\leq j\leq 26)\\
\end{aligned}
$$
### 最小連続勤務日数制約
各勤務期間は少なくとも3日連続の勤務日で構成されなければなりません：
$$
\begin{aligned}
\bar{x}_{i,j}x_{i,j+1}x_{i,j+2}\bar{x}_{i,j+3} = 0 & &(0\leq i\leq 5, 0\leq j\leq 29)\\
\bar{x}_{i,j}x_{i,j+1}\bar{x}_{i,j+2} = 0 & & (0\leq i\leq 5, 0\leq j \leq 30)
\end{aligned}
$$
### 孤立休日禁止制約
どの労働者も2つの勤務日の間に1日だけの休日を持ってはなりません：
$$
\begin{aligned}
x_{i,j}\bar{x}_{i,j+1}x_{i,j+2} = 0 & &(0\leq i\leq 5, 0\leq j\leq 30)\\
\end{aligned}
$$
### 総労働者コスト
$C=(c_i)$ をコストベクトルとし,$c_i$ は労働者 $i$ を配置する1日あたりのコストを表します.
総労働者コストは次のように定式化されます：
$$
\begin{aligned}
\sum_{i=0}^5\sum_{j=0}^{32} c_i x_{i,j}
\end{aligned}
$$
この目的関数を上記の制約のもとで最小化します.
## シフトスケジューリングのPyQBPPプログラム
上で定義したシフトスケジューリング問題は,PyQBPPを用いて以下のように定式化・求解できます：
```{literalinclude} /../programFiles/pythonPrograms/example/real/shift-scheduling-program1.py
:language: python
:caption: shift-scheduling-program1.py
```
このプログラムでは,変数と式は以下のように定義されています：
- `x`: $6\times 33$ のバイナリ変数行列.
- `workers_each_day`: `x` の列方向の和を含む配列で,各日に配置された労働者数を表します.
- `each_day_4_workers`: 各日にちょうど4人の労働者が配置されているときかつそのときに限り最小値0をとる制約式.
- `workers_working_days`: `x` の行方向の和の配列で,各労働者の総勤務日数を表します.
- `work_20_21_days`: 各労働者が20日間または21日間勤務しているときかつそのときに限り最小値0をとる制約式.
- `no_more_than_6_consecutive_working_days`: どの労働者も7日以上連続で勤務していないときかつそのときに限り最小値0をとる制約式.
- `no_less_than_3_consecutive_working_days`: すべての勤務期間が少なくとも3日連続の勤務日で構成されているときかつそのときに限り最小値0をとる制約式.
- `no_single_day_off`: どの労働者も2つの勤務日の間に1日だけの休日を持っていないときかつそのときに限り最小値0をとる制約式.
- `constraints`: すべての制約式の和.
- `total_worker_cost`: 総労働者コストを表す式.
### QUBO構築と求解
`total_worker_cost` と `constraints` をペナルティ係数10000で加算することにより,シフトスケジューリング問題のQUBO定式化を表す式 `f` を得ます.
Pythonの `dict` オブジェクト `ml` は,0日目と32日目に対応する変数の値を固定するために使用されます.
`qbpp.replace()` 関数を `f` に `ml` を適用することで,新しい式 `g` が得られます.
次に,Easy Solver が `g` に適用され,得られた解が `sol` に格納されます.
固定された変数を参照する元の式を評価するために,
`full_sol = qbpp.Sol(f).set(sol, ml)` を構築します.これは `ml` の固定値と `sol` の値を統合したものです.
得られた解は以下のとおりです：
```{include} /../programFiles/markDown/example/real/shift-scheduling.md
:start-after:
:end-before:
```
総労働者コスト `1465` の実行可能なシフトスケジュールが得られ,すべての制約が満たされていることがわかります.
:::