前置き
シフト表作成が大変なので、組み合わせ最適化を使って定量的な評価を付けた上で書けないか？との相談があったので挑戦することに。
理論の時点でかなりつまずきを感じる・・・まあ、やってみるものとする。
ざっくり読んだページのメモ：
https://tech.unifa-e.com/entry/2019/06/21/064243
https://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721
https://qiita.com/SaitoTsutomu/items/a33aba1a95828eb6bd3f
今回の問題は勤務スケジューリング問題であり、上述のサイトを見た限りではpulpが使いやすそうだったので、まずはpulpを使った設計で考えてみる。
環境
動くようになるまではgoogle colaboratory を使用。
最終的にはpython-embedで動かせるようにし、データはxlsxファイルから取り込む形にしたい。
主題
組合せ最適化では、数理モデルを定式化する。
定式化をするには、3 つの要素を決める必要があります。
1. 何を決めたいのか？
2. どうなるとうれしいのか？
3. 守らないといけないことは？
初心者なのでこれに沿って素直に進めていく。
1. 何を決めたいのか？
1ヶ月の勤務シフト表に対し、誰がどこのシフトに入るのかを決めたい
勤務シフト表は１ヶ月単位で作られており、昼勤と夜勤に別れている。
勤務者は勤務希望を出し、管理者はそれを見て勤務調整を行う
2. どうなるとうれしいのか？
必須事項が全て通った上で、管理者の希望と勤務者の希望がなるべく多く通ると嬉しい
必須事項は「日勤夜勤ともに最低必要人数を満たすこと」
「新人二人だけでは夜勤をしないこと」などである。
管理者の希望とは「AさんとBさん二人だけでの勤務は良くない」
「Cさんはかなり疲れているので夜勤を減らしたい」などである。
勤務者の希望は「この日は有給が欲しい」「この日は夜勤に入りたくない」
「あの人とは絶対に二人で仕事したくない」などである。
管理者希望が優先されるため、全ての勤務者の希望は通せないが、なるべく全員が同程度に希望を通すようにしたい。
勤務者ABCDがいて、各3個、合計12個の要望がある場合、
①「AとBの希望は3個ずつ通り、CDの希望は全て却下」＝6個の希望が通った
②「全員の希望が１個ずつ通る」＝4個の希望が通った
①と②ならば②の方が良い、というような形で最適化したい。
また、誰の希望がどれだけ通ったか、というのも定量化しておきたい
（先月はAさんが多く要望を通ったので、今月はBさんが多めに通るようにする、などの調整がしたい）。
3. 守らないといけないことは？
これはもうそのまま上述の必須事項が該当する。
また、夜勤翌日の日勤は無し、というのも労基法上の必須事項である。
1日に夜勤したら、2日は休みになる。
仮仕様
まずは小規模な所から作り始めることとする。
日程：7日間（1日目昼勤から7日目昼勤まで。0日目や7日目の夜勤は考えない）
勤務者：8名（新人が内2名）
最低人数：昼勤2名、夜勤2名
必須事項：最低人数に足りること、新人だけで昼勤・夜勤を埋めないこと、夜勤直後の昼勤はしないこと
管理者希望：無し
勤務者希望：勤務者は全て夜勤忌避日を1日出せる
有給希望や管理者希望はひとまず全て取っ払い、シンプルにする
仮データ
| 日付 | 昼夜 | 必要人数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 昼 | 2 | ||||||||
| 1 | 1 | 夜 | 2 | 忌避 | 忌避 | ||||||
| 2 | 2 | 昼 | 2 | ||||||||
| 3 | 2 | 夜 | 2 | ||||||||
| 4 | 3 | 昼 | 2 | ||||||||
| 5 | 3 | 夜 | 2 | 忌避 | |||||||
| 6 | 4 | 昼 | 2 | ||||||||
| 7 | 4 | 夜 | 2 | 忌避 | 忌避 | ||||||
| 8 | 5 | 昼 | 2 | ||||||||
| 9 | 5 | 夜 | 2 | ||||||||
| 10 | 6 | 昼 | 2 | 忌避 | |||||||
| 11 | 6 | 夜 | 2 | 忌避 | 忌避 | ||||||
| 12 | 7 | 昼 | 2 |
※7番と8番が新人扱いとする。
プログラム作成
まずは参考ページ https://tech.unifa-e.com/entry/2019/06/21/064243
の内容からなるべくそのまま流用を考えてみる。
目的関数も、まず動きが分からないといけないので、「8番の介入を最小限」にする
入力
import pulp
Member = ["1", "2", "3", "4", "5", "6", "7", "8"]
Day = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
Action = ["昼勤", "夜勤"]
#問題の宣言
ShiftScheduling = pulp.LpProblem("ShiftScheduling", pulp.LpMinimize)
#変数宣言
x = {}
for m in Member:
for d in Day:
for a in Action:
x[m, d, a] = pulp.LpVariable("x({:},{:},{:})".format(m,d,a), 0, 1, pulp.LpInteger)
#目的関数：新人8番のを最小限に抑える
ShiftScheduling += pulp.lpSum(x['8', d, a] for d in Day for a in Action), "Target"
#出力
results = ShiftScheduling.solve()
print("optimality = {:}, target value = {:}".format(pulp.LpStatus[results], pulp.value(ShiftScheduling.objective)))
出力結果
optimality = Optimal, target value = 0.0
さて、問題としてこの出力だと「できました」としか出力されず、「スケジュール表が出てこない」というのは在るが、
ひとまず動くことは確認した。ここからのスタートとする