この記事は
この記事は
「ナース・スケジューリング: 問題把握とモデリング」 を文系初心者にも分かるように図やイラストを追加する_2 の続きとなる記事です。
3章 組み合わせ最適化問題としての定式化
3-3 各ナースの各日程の勤務内容を組み合わせる定式化(p.44)
b)同一シフトが連続しない場合の間隔日数
$ナースi\in M$の$シフトk\in W$の間隔日数の下限$u_k$を守るために
＜中略＞
以下のように表す。x_{i,j-t,k}-\sum_{h=1}^{t-1}x_{i,j-h,k}+x_{ijk}\leqq1\\ t\in \{2,3,...,u_k\}
本書の例に倣って$u_k=4$（間隔下限が4日。下の図では休みの間隔下限として図解。）
休みの間隔を判定する条件式は複数の式を組み合わせて定式化します。
パターンが多いですが休みの間隔が最低4日の例を考えてみます。
4日間の間隔があいているか否かを調べるには5日間を見ればOKです。
OK…休みの間隔が4日以上またはその可能性
NG…休みの間隔が4日未満(休みと休みの間に出勤が3日以下)
0,1の5つの並びなので全部で32パターンです。
| 1日目 | 2日目 | 3日目 | 4日目 | 5日目 | 判定 | |
|---|---|---|---|---|---|---|
| パターン1 | 0 | 0 | 0 | 0 | 0 | OK |
| パターン2 | 0 | 0 | 0 | 0 | 1 | OK |
| パターン3 | 0 | 0 | 0 | 1 | 0 | OK |
| パターン4 | 0 | 0 | 0 | 1 | 1 | OK |
| パターン5 | 0 | 0 | 1 | 0 | 0 | OK |
| パターン6 | 0 | 0 | 1 | 0 | 1 | NG |
| パターン7 | 0 | 0 | 1 | 1 | 0 | OK |
| パターン8 | 0 | 0 | 1 | 1 | 1 | OK |
| パターン9 | 0 | 1 | 0 | 0 | 0 | OK |
| パターン10 | 0 | 1 | 0 | 0 | 1 | NG |
| パターン11 | 0 | 1 | 0 | 1 | 0 | NG |
| パターン12 | 0 | 1 | 0 | 1 | 1 | NG |
| パターン13 | 0 | 1 | 1 | 0 | 0 | OK |
| パターン14 | 0 | 1 | 1 | 0 | 1 | NG |
| パターン15 | 0 | 1 | 1 | 1 | 0 | OK |
| パターン16 | 0 | 1 | 1 | 1 | 1 | OK |
| パターン17 | 1 | 0 | 0 | 0 | 0 | OK |
| パターン18 | 1 | 0 | 0 | 0 | 1 | NG |
| パターン19 | 1 | 0 | 0 | 1 | 0 | NG |
| パターン20 | 1 | 0 | 0 | 1 | 1 | NG |
| パターン21 | 1 | 0 | 1 | 0 | 0 | NG |
| パターン22 | 1 | 0 | 1 | 0 | 1 | NG |
| パターン23 | 1 | 0 | 1 | 1 | 0 | NG |
| パターン24 | 1 | 0 | 1 | 1 | 1 | NG |
| パターン25 | 1 | 1 | 0 | 0 | 0 | OK |
| パターン26 | 1 | 1 | 0 | 0 | 1 | NG |
| パターン27 | 1 | 1 | 0 | 1 | 0 | NG |
| パターン28 | 1 | 1 | 0 | 1 | 1 | NG |
| パターン29 | 1 | 1 | 1 | 0 | 0 | OK |
| パターン30 | 1 | 1 | 1 | 0 | 1 | NG |
| パターン31 | 1 | 1 | 1 | 1 | 0 | OK |
| パターン32 | 1 | 1 | 1 | 1 | 1 | OK |
先ほどの制約式の振り返りです。
x_{i,j-t,k}-\sum_{h=1}^{t-1}x_{i,j-h,k}+x_{ijk}\leqq1\\
t\in \{2,3,...,u_k\}
上記の32パターンの意思決定変数をこの制約式の左辺に代入し、1以下と制約すれば取りうるパターンはOKパターンのみになります。
実際に見てみます。
t\in \{2,3,...,u_k\}\\
なので
t\in\{2,3,4\}
となり3つの制約式ができます。
u_k=4 , j=5 , t = 4 \\
x_{i,5-4,k}-(x_{i,5-1,k}+x_{i,5-2,k}+x_{i,5-3,k})+x_{i,5,k}\leqq1\\
x_{i,1,k}-x_{i,4,k}-x_{i,3,k}-x_{i,2,k}+x_{i,5,k}\leqq1…①\\
u_k=4 , j=5 , t = 3 \\
x_{i,5-3,k}-(x_{i,5-1,k}+x_{i,5-2,k})+x_{i,5,k}\leqq1\\
x_{i,2,k}-x_{i,4,k}-x_{i,3,k}+x_{i,5,k}\leqq1…②
u_k=4 , j=5 , t = 2 \\
x_{i,5-2,k}-(x_{i,5-1,k})+x_{i,5,k}\leqq1\\
x_{i,3,k}-x_{i,4,k}+x_{i,5,k}\leqq1…③
①②③の式を簡単に表現すると
(4日前)-(3日前)-(2日前)-(1日前)+(基準日)\leqq1…①\\
(3日前)-(2日前)-(1日前)+(基準日)\leqq1…②\\
(2日前)-(1日前)+(基準日)\leqq1…③\\
試しにパターン6を見てみます。ここでいう基準日とは$j$の値ですので$5日目$になります。
| 1日目 | 2日目 | 3日目 | 4日目 | 5日目 | 判定 | |
|---|---|---|---|---|---|---|
| パターン6 | 0 | 0 | 1 | 0 | 1 | NG |
それぞれの式に代入すると
0-0-1-0+1\leqq1…①\\
0-1-0+1\leqq1…②\\
1-0+1\leqq1…③\\
③の式が成り立ちません。ゆえにこの条件下でパターン6の意思決定変数の並びを作ることはできません。
ただこれだけでは足りません。
これら3つの式が見ている部分（守備範囲）は以下の図のようになるからです。
パターン19を見てみると
| 1日目 | 2日目 | 3日目 | 4日目 | 5日目 | 判定 | |
|---|---|---|---|---|---|---|
| パターン19 | 1 | 0 | 0 | 1 | 0 | NG |
①②③すべての式が成り立ってしまいます。
\begin{align}
0\leqq1…①\\
-1\leqq1…②\\
-1\leqq1…③
\end{align}
そのため5日間の内、前半部分でも同じように制約を付与します。
また、説明のため$j=4,t=2,3$と$j=3,t=2$に対する式も以下に示しておく
j=4,t=3\\ x_{i1k}-x_{i2k}-x_{i3k}+x_{i4k}\leqq1…④\\ \\ j=4,t=2\\ x_{i2k}-x_{i3k}+x_{i4k}\leqq1…⑤\\ \\ j=3,t=2\\ x_{i1k}-x_{i2k}+x_{i3k}\leqq1…⑥\\
日付軸に五つ並んだ意思決定変数がこれらの制約をすべて満たす限り、
5日間のどこにも「101」、「1001」、「10001」といった4日未満の間隔を作ることができません。
すなわち、休みの間隔を4日以上開けることができます。
先ほどは間隔日数の下限でした。
次は上限です。
休みと休みの間が離れずぎるのも避けたいという考えです。
次に、$ナース_i\in{M}$の$シフト_k\in{W}$の間隔日数の上限$v_k$を守るために$日_i\in{N}$までの$v_k+1$日分の変数を利用して、
以下のように表す。\sum_{h=0}^{v_k}x_{i,j-h,k}\geqq1<中略>
例えば、$v_k=6,j=7$で、この制約式を表してみると、x_{i1k}+x_{i2k}+x_{i3k}+x_{i4k}+x_{i5k}+x_{i6k}+x_{i7k}\geqq1
分かりやすくすると
(6日前)+(5日前)+(4日前)+(3日前)+(2日前)+(1日前)+(基準日)\geqq1
これは非常にシンプルです。
7日間の内、最低でもどこか1日は休みのシフトを割り当てるということです。
$v_k=6$であれば休みが離れていいのは最大6日という意味です。
それを超えた連続勤務（休み以外のシフトを勤務とした場合）は「7日間休みなし(=制約式左辺が0)」になるためそれを制限します。
c)異種勤務を含む禁止シフト並びを禁止する
$ナース_i\in{M}$の$日_j\in{N}$までの日が、禁止シフト並び$(k_0,k_1,...,k_t)\in{Q}$にならないよう、対応する変数がすべて一緒に1になることを禁ずる。\sum_{h=0}^{t}x_{i,j-t+h,k_h}\leqq t例えば$(深夜勤,休み,日勤)$が禁止されているならば(集合$Q$の要素ならば)、$j=3$でこの制約式を表してみると、
x_{i1深夜勤}\hspace{5pt}+x_{i2休み}\hspace{5pt}+x_{i3日勤}\hspace{5pt}\leqq2
これも非常にシンプルです。
禁止並びの長さによって右辺の$t$の値が変わります。
3日間の並びであれば$t$の値は$並びの長さ-1$であるため$t=2$となります。
続き
書いています。