組合せ最適化への挑戦録（勤務スケジューリング）1.丸写しからのスタート

##前置き

シフト表作成が大変なので、組み合わせ最適化を使って定量的な評価を付けた上で書けないか？との相談があったので挑戦することに。
理論の時点でかなりつまずきを感じる・・・まあ、やってみるものとする。

ざっくり読んだページのメモ：
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ファイルから取り込む形にしたい。

## 主題

``` https://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721　より抜粋
組合せ最適化では、数理モデルを定式化する。

定式化をするには、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番の介入を最小限」にする

###入力

```python
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
```

さて、問題としてこの出力だと「できました」としか出力されず、「スケジュール表が出てこない」というのは在るが、
ひとまず動くことは確認した。ここからのスタートとする