5
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2021-05-17

##前置き

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

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

主題

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

定式化をするには、3 つの要素を決める必要があります。

1. 何を決めたいのか?	
2. どうなるとうれしいのか?
3. 守らないといけないことは?

初心者なのでこれに沿って素直に進めていく。

1. 何を決めたいのか?

1ヶ月の勤務シフト表に対し、誰がどこのシフトに入るのかを決めたい

勤務シフト表は1ヶ月単位で作られており、昼勤と夜勤に別れている。
勤務者は勤務希望を出し、管理者はそれを見て勤務調整を行う

2. どうなるとうれしいのか?

必須事項が全て通った上で、管理者の希望と勤務者の希望がなるべく多く通ると嬉しい

必須事項は「日勤夜勤ともに最低必要人数を満たすこと」
「新人二人だけでは夜勤をしないこと」などである。

管理者の希望とは「AさんとBさん二人だけでの勤務は良くない」
「Cさんはかなり疲れているので夜勤を減らしたい」などである。

勤務者の希望は「この日は有給が欲しい」「この日は夜勤に入りたくない」
「あの人とは絶対に二人で仕事したくない」などである。

管理者希望が優先されるため、全ての勤務者の希望は通せないが、なるべく全員が同程度に希望を通すようにしたい。

勤務者ABCDがいて、各3個、合計12個の要望がある場合、
①「AとBの希望は3個ずつ通り、CDの希望は全て却下」=6個の希望が通った
②「全員の希望が1個ずつ通る」=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

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

5
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?