書籍紹介
リンク先の近代科学社HPの紹介文をそのまま
”ナース・スケジューリングとは、「ナースの勤務表作成」問題のことをいう。 勤務表は、与えられた条件下での作成が難しいだけでなく、人間の暗黙的な評価や制約が存在することから、その評価も難しい。この問題は、求解困難な組合せ最適化問題としてもよく知られている。
現実問題を解決するために様々な角度から問題を把握することは、それ自体がモデリングであるとも言える。本書では、ナース・スケジューリングと最適化モデリングの両方の視点から、問題解決のための手法について解説する。
同問題に関心のある読者はもちろん、最適化に関心のある研究者、技術者、大学院生、学部生には必携の書である。”
この記事で何を書くか
きっかけは何にせよ
ナーススケジューリング問題に取り掛かるため書籍を購入しようとググると
この書籍(以下、本書)だけ がヒットしますよね。
自分も購入しました。
頭の弱い文系の自分には、いかんせん文字や記号、数式が多く読むのがなかなか辛く
数秒で閉じました。
自分が欲しかった 図 と Pythonコード を記す
本書を読むうえで（個人的に）欲しかった図やPythonコード をかき残します。
この記事のゴール
書籍「ナース・スケジューリング: 問題把握とモデリング」を読みながら
- ナーススケジューリング問題における定式化(3章部分)を視覚的に把握できる。
- 自分が解きたいスケジューリング問題に応用させPythonで解を求られる。
ゴール範囲をミニマムに抑えるために3章以外の内容には基本的に割愛します。
pythonの基本的な文法や使用する数理最適化モジュールPulpについても詳しい説明はいたしません。
別途調べていただくか参考の書籍に目を通してください。自分も購入した書籍です。
都度、参考になるQiita記事やwebページも紹介します。
お断り
あくまで本書（ナース・スケジューリング: 問題把握とモデリング)の内容に沿って記事を書きます。
そのため本記事の想定読者は本書を購入したものの文字や記号が多く気が滅入ってしまった最適化問題初心者の方々です。
本書を購入されていない方にも分かるように書くつもりではありますが、カバーしきれないことがあるやもです。
▼参考の書籍
1章・2章の内容を "失礼なほど" ざっくりまとめる
まとめ
看護師の勤務表作成は考慮する条件が多いだけでなく暗黙知も織り込まれることから人間が行うには非常に難しい。
組み合わせの数が膨大という意味では計算機械にとっても難しい最適化問題である。
実際はより詳細かつ具体的に記載されていますが超ざっくりと。
また、本書では触れていませんがナーススケジューリング問題は難しさがNP困難と呼ばれる部類に入るそうです。
▼この問題が難しいということを難しく説明してくれています。
3章 組み合わせ最適化問題としての定式化
最適化問題の事前知識
簡単な最適化問題の具体例
簡単な具体例-クリックすると開きます-
要点
組み合わせ最適化とは読んで字のごとく変数の最適な組み合わせを見つける問題。
最適化問題は計算で解くことができる。
本書の内容に入る前に
まず最適化問題の事前知識として簡単な例題を記述します。
| 価格表 | 値段 | 個数 |
|---|---|---|
| りんご | $120円$ | $x_1$ |
| みかん | $70円$ | $x_2$ |
| ジュース$100cc$あたり | 必要個数 |
|---|---|
| りんご | $1.5個$ |
| みかん | $1個$ |
最適化問題とは
予算$1000円$で出来るだけたくさんのジュースを作るにはりんごとみかんをいくつ購入すればよいでしょうか。
といった問題になります。
ジュースの量を$Y$としりんご、みかんの個数をそれぞれ$x_1,x_2$とすると、$Y$を最大化するような$x_1,x_2$の組み合わせ
この組み合わせこそが最適となります。
この組み合わせを見つける作業を最適化と言い
今回のように、ある値を最大化や最小化することが一般的です。
定式化の具体例
要点
・最大化（最小化）したい目的変数
・守らなければいけない制約条件
・変数の取りうる範囲
これらを数式で表現する。
先ほどのジュースを作る最適化問題を定式化してみます。
①みかん$1個$（とりんご$1.5個$）につき$100cc$のジュースを作れる。このジュース量を最大化させる。
②りんごはみかんの$1.5倍$の個数が必要。
③購入金額は$1000円以下$で抑える。
④⑤りんご、みかんの個数はマイナスの値をとらない。
\begin{align}
目的関数\hspace{150pt}\\
Maximum\hspace{50pt}Y= 100x_2 ・・・①\\\\\\\\
制約条件\hspace{150pt}\\
subject\;to\hspace{50pt} x_1=1.5x_2・・・②\\
120x_1 + 70x_2 \leqq 1000・・・③\;\\
x_1 \geqq 0\hspace{16pt}・・・④\\
x_2 \geqq 0\hspace{16pt}・・・⑤
\end{align}
となります。
制約条件②を制約条件③に代入すると
\begin{align}
120*1.5x_2 + 70x_2 \leqq 1000\\
180x_2 + 70x_2 \leqq 1000\\
250x_2 \leqq 1000\\
(0\leqq)\hspace{5pt}x_2 \leqq 4\hspace{15pt}
\end{align}
となります。$x_2$が$0$以上$4$以内の範囲で$Y=100*x_2$を最大化させるには
$x_2$が$4$のとき$Y$が$400$となりYを最大化できます。
ということは
みかん$4つ$で$280円$
りんご$6つ$で$720円$
ピッタリ$1000円$です。
結果、りんごを$6つ$、みかんを$4つ$購入すれば予算$1000円$以内でジュースの量を最大化することができました。
シンプルな最適化問題は中学生でも手計算で解くことができるものです。
イメージが湧きましたでしょうか。
これを勤務表作成にも利用してやろうというのです。
3-1 組み合わせ最適化問題(p.35)
ざっくりまとめ
ナーススケジューリング問題は組み合わせ最適化問題であり0-1整数計画問題として定式化できる。
目的関数はシフト制約条件の違反度合を表す式を最小化させる。
制約条件にはシフト制約条件とナース制約条件の2種類が存在する。
最適化問題として
- 線形計画問題（LP:linear programming problem）
- 整数線形計画問題（ILP:integer linear programming problem）
- 混合整数計画問題（MIP:mixed linear programming problem）
- 0-1整数計画問題（0-1 integer linear programming problem）
など変数の取りうる範囲によって分類されています。
▼組み合わせ最適化問題をもっと詳しく知りたい方はこちらの記事が参考になるかと思います。
0-1整数計画問題とは変数の取りうる値が0または1のみの最適化問題です。
勤務表作成においては0が休み、1が出勤となる組み合わせとなります。
| 1日 | 2日 | 3日 | 4日 | 5日 | 6日 | 7日 | |
|---|---|---|---|---|---|---|---|
| Aさん | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| Bさん | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| Cさん | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| Dさん | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1日 | 2日 | 3日 | 4日 | 5日 | 6日 | 7日 | |
|---|---|---|---|---|---|---|---|
| Aさん | 休 | 休 | 出勤 | 出勤 | 出勤 | 出勤 | 休 |
| Bさん | 出勤 | 出勤 | 出勤 | 休 | 休 | 休 | 出勤 |
| Cさん | 出勤 | 出勤 | 休 | 休 | 休 | 出勤 | 出勤 |
| Dさん | 出勤 | 休 | 休 | 出勤 | 出勤 | 出勤 | 休 |
2種類の制約条件
制約条件は大きく2つ
シフト制約条件：各日の各シフトにおいて支障が起きないようにナースを揃えるための条件
ナース制約条件：各ナースの勤務負荷や健康を考慮するための条件
制約条件には大きく2種類ありシフト制約条件とナース制約条件と著者は呼んでいます。
シフト制約条件
筆者は縦の条件とも呼んでいましたが
具体的には
- 必要人数
- スキルレベル的に問題のないメンバー構成
- 相性や慣れあいに対する考慮
を挙げています。
ナース制約条件
対して横の条件として
- 休みや勤務シフトの数
- 休みや勤務の希望
- セミナーなどの予定
- 夜勤が何日も続く厳しいシフトを避ける
などが挙げられています。
制約条件の優先度合という分け方では
ハードな制約(絶対守る必要がある)
ソフトな制約（できるだけ守らなければいけない）
の2つに分けられます。
3-2 定式化におけるパラメタ(p.38)
この節からいきなり記号が大量に出るので辛い場所ですが
本記事はこれらを図解することがメイン目的でもあります。
本書を手に取りながら眺めていただければと思います。
2章3節 勤務表作成のための制約条件（p.19）から
著者が取り組んでいる勤務表における具体的な条件が記載されています。
それら条件を定式化する上で必要となる記号を本書と同じように列挙しています。
それぞれ書いてあることは本書と同じため「記号の図解」へスキップ していただいても構いません。
記号
M=｛1,2,...,m｝:ナースの集合.\\
N=｛1,2,...,n｝:スケジューリング対象日の集合.\\
W=｛shift_1,shift_2,...,shift_w｝:シフト（例：日勤,夜勤,休み）の集合.\\
W^+=W∪｛他勤務｝:集合Wにその他の勤務（他勤務）を加えた集合.\\
R=｛r|rはグループ｝:スキルレベルや担当患者で分けられたグループの集合.\\
G_r=｛i|ナースiはグループrに所属｝,r∈R:グループrに所属するナースの集合.※_1\\
F_1=｛(i,j,k)|i∈M,j∈N,k∈W^+|ナースiの日jはシフトkに確定｝:確定勤務の集合.※_2\\
F_0=｛(i,j,k)|i∈M,j∈N,k∈W^+|ナースiの日jはシフトkに不可能｝:不可能勤務の集合.※_3\\
Q=｛(k_0,K_1,.,k_t),k_0,K_1,.,k_t∈W^+|k_0,K_1,.,k_t連続勤務は禁止｝:禁止シフト並びの集合.※_4\\
a_{rjk},b_{rjk},r∈R,j∈N,k∈W:日jのシフトkに対するグループrからの人数のそれぞれ下限と上限.\\
c_{jk},d_{jk},i∈M,k∈W:ナースiのシフトkの回数のそれぞれ下限と上限.\\
e_k,f_k,k∈W:シフトkの連続日数のそれぞれ下限と上限.\\
u_k,v_k,k∈W:シフトkの間隔日数のそれぞれ下限と上限.\\
※_1\hspace{10pt}R=｛全員,A,B,Aベテラン,Bベテラン,B準ベテラン,B準新人,夜間禁止ペア｝\\
G_{全員}=M=｛1,2,...,m｝,\\
G_A=｛1,...,13｝,\\
G_B=｛4,...,25｝,\\
G_{Aベテラン\hspace{10pt}}=｛1,...,6｝,\\
G_{Bベテラン\hspace{10pt}}=｛14,...,18｝,\\
G_{B準ベテラン\hspace{10pt}}=｛14,...,18,25｝,\\
G_{B準新人\hspace{5pt}}=｛19,...,25｝,\\
G_{夜間禁止ペア}=｛1,9｝\\
※_2\hspace{10pt}F_1=｛(2,1,深夜勤務),(2,2,休み),(2,9,休み),...,(24,25,休み),(24,26,休み)｝\\
※_3\hspace{10pt}F_0=｛(i,j,他勤務)|ナースiの日jは他勤務に指定されない｝\\
※_4\hspace{10pt}Q=｛(深夜勤,日勤),(深夜勤,他勤務),(深夜勤,準夜勤),(準夜勤,日勤),\\(準夜勤,他勤務),(深夜勤,休み,日勤),(深夜勤,休み,他勤務)｝\\
記号の図解
自分はそもそも数学記号が読めなかったうえに
集合？なんだっけ？といったレベル感だったので高校数学をさらっと復習すると理解の助けになりました。
ナースの集合
M=｛1,2,...,m｝
$m$人のナースが病院で勤務しており、ナース一人一人に$1$~$m$までの番号が割り振られています。
スケジューリング対象日の集合
N=｛1,2,...,n｝
一度に作成するシフト表の日数のことです。$1$日目から始まり、最終日を$n$日目としています。
基本的に一か月分の勤務表を作る機会が多いと考えます。その場合nは$30$や$31$になります。
シフト（例：日勤,夜勤,休み）の集合
W=｛shift_1,shift_2,...,shift_w｝
勤務表に記入する具体的なシフトの種類です。$shift_1＝日勤$といった形で$w$種類のシフトがあるという意味です。
日勤、夜勤、休みの3種類のほかに「早朝」であったり「夜勤A」「夜勤B」など
病院によってさまざまな種類の働き方があると考えられます。
集合Wにその他の勤務（他勤務）を加えた集合
W^+=W∪｛他勤務｝
本書ではベースとなるシフト以外（セミナーなど）は「他勤務」として扱っています。
例えば $W=｛日勤,夜勤,休み｝$ だった場合
$W^+=W∪｛他勤務｝$ は $W^+=｛日勤,夜勤,休み,他勤務｝$の$4$種類のシフトを意味します。
スキルレベルや担当患者で分けられたグループの集合
R=｛r|rはグループ｝\\
R=｛全員,A,B,Aベテラン,Bベテラン,B準ベテラン,B準新人,夜間禁止ペア｝\\
G_r=｛i|ナースiはグループrに所属｝,r∈R:グループrに所属するナースの集合\\
G_{全員}=M=｛1,2,...,m｝,\\
G_A=｛1,...,13｝,\\
G_B=｛4,...,25｝,\\
G_{Aベテラン\hspace{10pt}}=｛1,...,6｝,\\
G_{Bベテラン\hspace{10pt}}=｛14,...,18｝,\\
G_{B準ベテラン\hspace{10pt}}=｛14,...,18,25｝,\\
G_{B準新人\hspace{5pt}}=｛19,...,25｝,\\
G_{夜間禁止ペア}=｛1,9｝\\
ナースをスキルのレベルやチーム、特定のペアなどで分類したグループとそのメンバーになります。
確定勤務の集合
F_1=｛(i,j,k)|i∈M,j∈N,k∈W^+|ナースiの日jはシフトkに確定｝\\
F_1=｛(2,1,深夜勤務),(2,2,休み),(2,9,休み),...,(24,25,休み),(24,26,休み)｝\\
これは確定しているシフト（希望のシフト）を表しています。
例えば $F_1=(2,1,深夜勤務)$ であればナース2の1日目は深夜勤務で決定（確定）しているという意味です。
確定勤務の一覧はp.28の表2.8に記載されています。
不可能勤務の集合
F_0=｛(i,j,k)|i∈M,j∈N,k∈W^+|ナースiの日jはシフトkに不可能｝\\
F_0=｛(i,j,他勤務)|ナースiの日jは他勤務に指定されない｝\\
先ほど説明したのが確定勤務、言い換えれば入りたいシフトの希望
今回はその逆、入りたくないシフトの希望 となります。
例えば$(2,2,日勤)$の場合ナース2の2日目は日勤に割り当てない（ことが確定）。という意味です。
禁止シフト並びの集合
Q=｛(k_0,K_1,.,k_t),k_0,K_1,.,k_t∈W^+|k_0,K_1,.,k_t連続勤務は禁止｝\\
Q=｛(深夜勤,日勤),(深夜勤,他勤務),(深夜勤,準夜勤),(準夜勤,日勤),\\(準夜勤,他勤務),(深夜勤,休み,日勤),(深夜勤,休み,他勤務)｝\\
シフトの並び順としてNGなパターンを列挙しています。
例えば$(深夜勤,日勤)$は深夜勤の翌日のシフトに日勤を割り当ててはいけない。という意味になります。
夜勤後の日勤はナースの体力的に酷なためNGパターンとしてリストアップしているのです。
著者が現場で作成された勤務表（p.12 表2.1）を見て作られていないシフトパターンを列挙しています。（p.29 図2.1）
日jのシフトkに対するグループrからの人数のそれぞれ下限と上限
a_{rjk},b_{rjk}\;,r∈R,j∈N,k∈W
例えば何らかの理由で
3日の深夜勤はチームAから1人以上、2人以下の出勤が必要な場合
a_{チームA,3,深夜勤}=1\;,b_{チームA,3,深夜勤}=2
と表現します。
これらをすべて網羅した表が本書p.26の表2.6になります。
ナースiのシフトkの回数のそれぞれ下限と上限
c_{jk},d_{jk}\;,i∈M,k∈W
夜勤や休みシフトなどの回数下限と上限です。
例えばナース1は新人のため深夜勤の回数を少なめに設定します.
(例として2回~4回)
c_{4,深夜勤}\;=2\;,d_{4,深夜勤}\;=4
と表現します。
これらをすべて網羅した表が本書p.27の表2.7になります。
シフトkの連続日数のそれぞれ下限と上限
e_k,f_k\;,k∈W
同じシフトが連日続く際、その下限と上限です。
例えば深夜勤が最低2日連続、最大3日連続の場合
e_{深夜勤務}=2,f_{深夜勤務}=3
と表現します。
これらをすべて網羅した表が本書p.29の表2.9になります。
シフトkの間隔日数のそれぞれ下限と上限
u_k,v_k\;,k∈W
例えば休みの間隔日数における下限と上限です。
休みの間隔が最低3日、最大5日である場合
u_{休み}=3\;,v_{休み}=5
と表現します。
これらをすべて網羅した表が本書p.29の表2.9になります。
3-3 各ナースの各日程の勤務内容を組み合わせる定式化(p.40)
意思決定変数
おさらい
おさらい-クリックすると開きます-
本記事において勤務表を0と1で表現したことを思い出してほしいです。
| 1日 | 2日 | 3日 | 4日 | 5日 | 6日 | 7日 | |
|---|---|---|---|---|---|---|---|
| Aさん | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| Bさん | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| Cさん | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| Dさん | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
この0と1の最適な組み合わせを見つける問題とみなせる。
➡0-1整数計画問題（0-1 integer linear programming problem）として定式化できる。
と説明しました。
意思決定変数とは
| 1日 | 2日 | 3日 | 4日 | 5日 | 6日 | 7日 | |
|---|---|---|---|---|---|---|---|
| Aさん | $X_{11}$ | $X_{12}$ | $X_{13}$ | $X_{14}$ | $X_{15}$ | … | … |
| Bさん | $X_{21}$ | … | … | … | … | … | … |
| Cさん | … | … | … | … | … | … | … |
| Dさん | … | … | … | … | … | … | $X_{ij}$ |
スケジューリング問題ではその日、その人が勤務するか否か表現する0または1が入る変数でした。
勤務する、しない という意思を決定するので意思決定変数と呼んでいます。
しかしこれでは出勤か休み（1,0）の2パターンのシフトしか割り当てることができません。
意思決定変数の制約式
著者が取り扱っている勤務表は
W^+=｛日勤,準夜勤,深夜勤,休み,他勤務｝
の5パターンあります。
各ナースは各日において、いずれかのシフトが割り当てられます。
ナースiが日jのシフトkに勤務するとき1,そうでないとき0となる0-1意思決定変数$X_{ijk}$を使う。
1日に可能な勤務は（休み含む）は1つなので、各ナースの各日について、以下の関係を忘れてはいけない。\sum_{k∈W^+}x_{ijk}=1
この制約式を視覚的に解りやすくすると3次元の勤務表になります。
2次元の勤務表ではなく、3次元の勤務表（0-1の並び）にすることで0と1だけで
いつ、だれが、なんのシフト、に割り当てられたかを表現することができます。
図では「ナース3」の「1日目」は「日勤」が割り当てられている、という見方です。
先ほどの式は図における赤い部分の変数Xの合計が1という意味です。
x_{ij日勤}\;+x_{ij準夜勤}\;+x_{ij深夜勤}\;+x_{ij休み}\;+x_{ij他勤務}\;=1\\
X_{ij}∈{0,1}\\
入りたい、入りたくないの希望が事前に指定されていた場合
F_1={(3,1,日勤)}:確定勤務\\
F_0={(3,2,深夜勤)}:不可能勤務
制約式として表現します。
x_{3,1,日勤}\;=1\\
x_{3,2,深夜勤}\;=0\\
意思決定変数の制約式は以下のように値が代入されます。
1+x_{3,1,深夜勤}+x_{3,1,準夜勤}+x_{3,1,休み}+x_{3,1,他勤務}\;=1\\
x_{3,2,日勤}+0+x_{3,2,準夜勤}+x_{3,2,休み}+x_{3,2,他勤務}\;=1\\
多くの式において$x_{IJ他勤務};＝0$ (後述のナース制約条件（2）で$F_0$の要素に対し0に設定)であり、以下の意味になっている。
x_{i,j,日勤}+x_{i,j,深夜勤}+x_{i,j,準夜勤}+x_{i,j,休み}\;=1\\これに加えて、例えば準夜勤や深夜勤が禁止しされている日は、後述のナース制約条件（2）で対応する変数が0に設定され以下の意味を持つ式になる。
x_{i,j,日勤}+x_{i,j,休み}\;=1
ナース3の1日目に反映させました。
つまり、このナースはこの日は日勤か休みしか許されないことになる。
続き