3. 単純化したシフトスケジューリング問題#
3.1. 背景#
非常に単純化したシフトスケジューリング問題を題材に, 実務で要求される定式化の入門的解説を述べる.
ここでいう「実務」の意味合いは,必ずしも定式化そのものだけではなく, 「顧客が本当に必要だったもの」を作り上げていくサイクルのことも含意する.
3.2. 設定#
3.3. 読み取り#
設定された仮想要件 だけ を手掛かりに,どのような定式化が可能かを考えてみる.
数理最適化問題として扱うことを前提とすれば,「変数」「制約条件」「目的関数」を明らかにしなければならない. これらは仮想要件から次のように読み取れる.
3.3.1. 変数#
3.3.1.1. 変数を設定する.#
「曜日 (日付など) \(d\),人 \(p\),シフト \(s\) の組を選択するかどうか.」を決定すればよい. よって変数として,\(x[d,p,s]\) というバイナリ変数を立てる.
3.3.1.2. 添字の粒度を決定する.(集合・要素の決定)#
\(d\in D\) は一週間のシフトを決めたいことと,シフトが一日単位で与えられていそうなので,\(D\) は曜日集合 \(D := \{日,月,火,水,木,金,土\}\) とする.
\(p\in P\) は \(6\) 名の店員が要件から判明しており,定員集合を \(P := \{店長,副店,鈴木,田中,佐藤,山田\}\) とする.
\(s\in S\) は日勤と夜勤の二つなので,シフト集合を \(S :=\{日勤,夜勤\}\) とする.
注意
あれ,ちょっと待って.
店長は出勤回数を減らしたかったはず.つまり「休日」を定式化の中に表現する必要がある. しかし店長に関する変数は \(x[d,店長,日勤]\) と \(x[d,店長,夜勤]\) の二つ. これらで「休日」をどう表現すればよいか考えればよいのだろうか.
もしその方針ならば,\(x[d,店長,日勤]=x[d,店長,夜勤]=0\) を休日と定義するべきだろうか. これはできなくはないが,大変そうだ. ともに \(0\) であることを判定するための変数を立てる必要がある. 何より拡張性に乏しそうである.
シフトに「休日」を追加しよう.
3.3.1.3. 変数の数を推定して問題規模を把握する.#
\(x[d,p,s]\) はバイナリ変数で,その総数 \(N\) は \(N=|D||P||S|=7\cdot 6\cdot 3=126\) である. 密な記述だが小規模といえる.よって,現状の変数で定式化を進めてもよいと判断できる.
Tip
もし,1 か月・百人・\(10\) 種シフトで密な記述ならば, \(N=|D||P||S|=30\cdot 100\cdot 10=30000\) であるから, このまま密な定式化を進めてよいか,再検討が必要である.
3.3.2. 目的関数#
変数を決定できたので,目的関数を数式に起こせる.
3.3.3. 制約条件#
制約条件を数式へ直すために,制約条件だけを切り出した文章を作成する.
シフトは日勤・夜勤または休日のいずれかである.
ワンオペを避ける.
副店が店番する場合は店長の代理のため,二人が一緒に店番をする必要はない.
重要
制約条件文の作文には以下の点に注意すると,制約条件を立式し易くなる.
「曜日」「日勤」「店員」など,定式化で使用した用語に徹する.
添字を使用して具体的に記述する.
「ワンオペ」「店番」など,業界用語を使用しないか,定式化の中で明確に定義したうえで使用する.
「必ず 1 つ」「以上・以下」「選択する」など,定式化しやすい語句に揃える.
「店長代理のため」など,定式化に無関係な論理関係をそぎ落とす.
上記に留意して,書き直すと例えば次のようになる.
曜日 \(d\) で店員 \(p\) は何かしらのシフト \(s\) を必ず一つ選択する.
曜日 \(d\) で日勤および夜勤シフトを各店員のうち二人以上が選択する.
曜日 \(d\) で店長と副店は同時に日勤および夜勤シフトを選択しない.
これからそれぞれの制約条件式は以下のようになる.
重要
要件に記載された事柄は網羅できた. しかし他に制約条件はないだろうか.
要件に表れていないが,このまま最適化計算すると,「無休」や「一週間全休」という解が出る可能性がある. 出勤日数についての制約条件が課されていないからだ. このような解が運用上許容されることも十分に考えられるが,出勤日数の上下限が設定されることもまた十分に考えられる. よって,要件定義には表れていはないが,出勤日数上下限制約は 暗黙の制約条件 と認識して,予め定式化に組み込んでおくとよい.
ここで \(U[p]\) と \(L[p]\) はそれぞれ店員 \(p\) の出勤上限日数と出勤下限日数である.
3.4. 求解#
あらためて定式化と対応する PySIMPLE をすべて書き出すと次のようになる.
PySIMPLE Sample Code
1def showTable(result_x):
2 table = []
3 cols = {}
4 rows = {}
5 vals = {}
6 for key in result_x:
7 l = list(key)
8 table.append(l)
9 cols[l[0]] = True
10 rows[l[1]] = True
11 vals[l[2]] = True
12 cols = list(cols.keys())
13 rows = list(rows.keys())
14 vals = list(vals.keys())
15
16 s = ' '.join([''.ljust(4, ' ')] + list(map(lambda x: x.ljust(4, ' '), cols))) + '\n'
17 for r in rows:
18 s += r.ljust(3, ' ')
19 for c in cols:
20 for v in vals:
21 if (c,r,v) in result_x:
22 s += v.ljust(3, ' ')
23 s += '\n'
24 print(s)
25
26def optimize(**kwds):
27 from pysimple import Problem, Set, Element, BinaryVariable, Sum, Parameter
28
29 D = Set(value=['1', '2', '3', '4', '5', '6', '7']) # 曜日集合
30 P = Set(value=['鈴木', '田中', '佐藤', '山田', '副店', '店長']) # 人集合
31 S = Set(value=['休日', '日勤', '夜勤']) # シフト集合
32
33 d = Element(set=D)
34 p = Element(set=P)
35 s = Element(set=S)
36
37 x = BinaryVariable(index=(d,p,s)) # 曜日 d,人 p,シフト s の組を選択するかどうか
38
39 prob = Problem(name='shift', type=min)
40 # 目的関数
41 ## 店長出勤日数
42 s_ = s != '休日'
43 prob += Sum(x[d,'店長',s_], (d,s_))
44
45 # 曜日 d に人 p は必ず一つのシフトに入る.
46 prob += Sum(x[d,p,s], s) == 1
47
48 # 必要人数制約
49 REQ = Parameter(index=s_, value=2) # シフト s_ を回すのに必要な最低人数
50 prob += Sum(x[d,p,s_], p) >= REQ[s_]
51
52 # 同時シフト不可制約
53 ## 店長副店同時不可
54 prob += x[d,'店長',s_] + x[d,'副店',s_] <= 1
55
56 # 勤務日数上下限希望制約
57 L = Parameter(index=p, value=0)
58 U = Parameter(index=p, value=5)
59 prob += Sum(x[d,p,s_], (d,s_)) >= L[p]
60 prob += Sum(x[d,p,s_], (d,s_)) <= U[p]
61
62 prob.solve(**kwds)
63
64 print('店長の出勤日数:', prob.result.optValue)
65 result_x = x[x[d,p,s].val==1]
66 resulttable = dict(result_x.val.items()) # dump as dict
67 showTable(resulttable)
68 return resulttable
69
70optimize()
上記を実行すると次の結果を得る.
Result
1
2[About Nuorium Optimizer]
3Nuorium Optimizer 24.1.0 build:614ca4b
4 <with META-HEURISTICS engine "wcsp"/"rcpsp">
5 <with Netlib BLAS>
6, Copyright (C) 1991 NTT DATA Mathematical Systems Inc.
7
8[Problem and Algorithm]
9PROBLEM_NAME shift
10NUMBER_OF_VARIABLES 126
11(#INTEGER/DISCRETE) 126
12NUMBER_OF_FUNCTIONS 83
13PROBLEM_TYPE MINIMIZATION
14METHOD SIMPLEX
15
16[Progress]
17<preprocess begin>.........<preprocess end>
18<iteration begin>
19Coefficient Statistics (original problem)
20 Coefficient range [min,max] : [1.00e+00,1.00e+00]
21 RHS and bounds [min,max] : [1.00e+00,5.00e+00]
22 Objective [min,max] : [1.00e+00,1.00e+00]
23Coefficient Statistics (after scaling)
24 Coefficient range [min,max] : [1.00e+00,1.00e+00]
25 RHS and bounds [min,max] : [1.00e+00,5.00e+00]
26 Objective [min,max] : [9.00e+00,9.00e+00]
27 Row scaling range [min,max] : [1.00e+00,9.00e+00]
28 Column scaling range [min,max] : [1.00e+00,1.00e+00]
29
30<<wcsp tabu search begin>>
31 number of column singleton : 0
32 number of column selection : 42
33 Modify coefficients
34
35<preprocess begin>..........<preprocess end>
36preprocessing time: 0(s)
37<iteration begin>
38--- TryCount = 1 ---
39# random seed = 1
40(hard/semihard/soft) penalty= 11/0/5, time= 0.00(s)
41<greedyupdate begin>..........<greedyupdate end>
42greedyupdate time= 0(s)
43(hard/semihard/soft) penalty= 0/0/4, time= 0.00(s), iteration= 0
44--- End Phase-I iteration ---
45(hard/semihard/soft) penalty= 0/0/3, time= 0.00(s), iteration= 53
46# (hard/semihard/soft) penalty= 0/0/3
47# time = 0.00/0.00(s)
48# iteration = 53/1000
49<iteration end>
50# (hard/soft) = 0/3
51# iteration = 1000
52# time = 0.00 (s), succ = 1
53<<wcsp tabu search end>>
54
55#sol upper lower gap(%) time(s) list mem(MiB)
56#1 3 -inf +inf 0.0 0 744 sol: wcsp
57
58 .12
59
60 3 3 0.000 0.0 0 744
61
62<iteration end>
63
64[Result]
65STATUS OPTIMAL
66VALUE_OF_OBJECTIVE 3
67SIMPLEX_PIVOT_COUNT 144
68PARTIAL_PROBLEM_COUNT 1
69ELAPSED_TIME(sec.) 0.00
70店長の出勤日数: 3.0
71 1 2 3 4 5 6 7
72鈴木 休日 日勤 夜勤 日勤 休日 夜勤 日勤
73田中 夜勤 夜勤 日勤 夜勤 休日 日勤 休日
74佐藤 休日 夜勤 夜勤 夜勤 日勤 休日 夜勤
75山田 日勤 日勤 休日 休日 夜勤 夜勤 夜勤
76副店 日勤 休日 日勤 休日 夜勤 日勤 日勤
77店長 夜勤 休日 休日 日勤 日勤 休日 休日
78
求解結果を抜粋すれば,次のシフトスケジュールを得られたことが確認できる.1なお実行環境によっては 解の安定性 が必ずしも保証されてはいないので,異なる結果が得られているかもしれない.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
---|---|---|---|---|---|---|---|
鈴木 |
休日 |
日勤 |
夜勤 |
日勤 |
休日 |
夜勤 |
日勤 |
田中 |
夜勤 |
夜勤 |
日勤 |
夜勤 |
休日 |
日勤 |
休日 |
佐藤 |
休日 |
夜勤 |
夜勤 |
夜勤 |
日勤 |
休日 |
夜勤 |
山田 |
日勤 |
日勤 |
休日 |
休日 |
夜勤 |
夜勤 |
夜勤 |
副店 |
日勤 |
休日 |
日勤 |
休日 |
夜勤 |
日勤 |
日勤 |
店長 |
夜勤 |
休日 |
休日 |
日勤 |
日勤 |
休日 |
休日 |
制約条件をすべて満たし,最適解が得られた.
さて「これでよいか」と店長に早速結果を見せてみると,首を傾げている.
「こんなバラバラなシフトは組めないなぁ」
と.
3.5. 検証#
「バラバラ」とはなんだろうか. 最適解を実務と照らし合わせると,違和感が認められる. 背後にある規則を明確にするために, この違和感の説明を数理最適化の文脈で言語化する必要がある.
3.5.1. バラバラとは#
今回,バラバラとは「一週間の中でシフトが散らばらずに連勤すること」ということにする.
例えば「休日・日勤・夜勤・日勤・日勤・休日・夜勤」というのは夜勤が日勤の間 (または日勤が夜勤の間) に入っていて,同じシフトが連勤になっていない. 代わりに「休日・日勤・日勤・日勤・休日・夜勤・夜勤」というようなものが,「バラバラではない」を意味し望ましいと考える.
3.5.2. 制約条件の追加#
ルールベース化ができたら,式に直す作業に移行する. 対象となる制約条件は単純な上下限制約ではないため,少し難しいと言えるだろう. このように,すぐに分からない場合には,\(0,1\) の並びでどのようになっていればよいかを考えてみるとよい. それは次のとおり.
- \(..\) を \(0\) の \(0\) 回以上の繰り返し,\(**\) を \(1\) の \(0\) 回以上の繰り返しとすると,次の並びであればよい.
- (6)#\[0 .. 0 1**1 0 .. 0\]
\(1**1\) は,「\(1\) が二つ立てば,その間の \(1\) が立つ」と言える.
「\(d1<d2<d3\) について,\(x[d1]=x[d3]=1\) ならば,\(x[d2]=1\) である」と表現できる.
- \(N=M=2\) の場合を考えて次を得る.
- (8)#\[x[d1] - x[d2] + x[d3] \leq 1\]
- 他の添字の自由度を明示的に書いて,所望の制約式表現が得られる.
- (9)#\[x[d1,p,s] - x[d2,p,s] + x[d3,p,s] \leq 1,\quad s\in\{日勤,夜勤\}\]
3.5.3. 再度の求解#
シフトがバラバラにならないための制約条件式を追加して,再度,求解しよう. PySIMPLE は次のようになる.
PySIMPLE Sample Code
1def showTable(result_x):
2 table = []
3 cols = {}
4 rows = {}
5 vals = {}
6 for key in result_x:
7 l = list(key)
8 table.append(l)
9 cols[l[0]] = True
10 rows[l[1]] = True
11 vals[l[2]] = True
12 cols = list(cols.keys())
13 rows = list(rows.keys())
14 vals = list(vals.keys())
15
16 s = ' '.join([''.ljust(4, ' ')] + list(map(lambda x: x.ljust(4, ' '), cols))) + '\n'
17 for r in rows:
18 s += r.ljust(3, ' ')
19 for c in cols:
20 for v in vals:
21 if (c,r,v) in result_x:
22 s += v.ljust(3, ' ')
23 s += '\n'
24 print(s)
25
26def optimize(**kwds):
27 from pysimple import Problem, Set, Element, BinaryVariable, Sum, Parameter, SoftConstraint
28
29 D = Set(value=['1', '2', '3', '4', '5', '6', '7']) # 曜日集合
30 P = Set(value=['鈴木', '田中', '佐藤', '山田', '副店', '店長']) # 人集合
31 S = Set(value=['休日', '日勤', '夜勤']) # シフト集合
32
33 d = Element(set=D)
34 p = Element(set=P)
35 s = Element(set=S)
36
37 x = BinaryVariable(index=(d,p,s)) # 曜日 d,人 p,シフト s の組を選択するかどうか
38
39 prob = Problem(name='shift', type=min)
40 # 目的関数
41 ## 店長出勤日数
42 s_ = s != '休日'
43 prob += Sum(x[d,'店長',s_], (d,s_))
44
45 # 曜日 d に人 p は必ず一つのシフトに入る.
46 prob += Sum(x[d,p,s], s) == 1
47
48 # 必要人数制約
49 REQ = Parameter(index=s_, value=2) # シフト s_ を回すのに必要な最低人数
50 prob += Sum(x[d,p,s_], p) >= REQ[s_]
51
52 # 同時シフト不可制約
53 ## 店長副店同時不可
54 prob += x[d,'店長',s_] + x[d,'副店',s_] <= 1
55
56 # 勤務日数上下限希望制約
57 L = Parameter(index=p, value=0)
58 U = Parameter(index=p, value=5)
59 prob += Sum(x[d,p,s_], (d,s_)) >= L[p]
60 prob += Sum(x[d,p,s_], (d,s_)) <= U[p]
61
62 # シフト連結制約
63 d1 = Element(set=D)
64 d2 = Element(set=D)
65 d3 = Element(set=D)
66 ddd = (d1 < d2) & (d2 < d3) # 曜日を漢字にしてしまうと,Unicode コードポイントで比較してしまう.
67 prob += x[ddd(0),p,s_] - x[ddd(1),p,s_] + x[ddd(2),p,s_] <= 1
68
69 # prob.options.method = 'wcsp'
70 # prob.options.maxTime = 3
71 prob.solve(**kwds)
72
73 print('店長の出勤日数:', prob.result.optValue)
74 result_x = x[x[d,p,s].val==1]
75 resulttable = dict(result_x.val.items()) # dump as dict
76 showTable(resulttable)
77 return resulttable
78
79optimize()
上記を実行すると次の結果を得る.
Result
1
2[About Nuorium Optimizer]
3Nuorium Optimizer 24.1.0 build:614ca4b
4 <with META-HEURISTICS engine "wcsp"/"rcpsp">
5 <with Netlib BLAS>
6, Copyright (C) 1991 NTT DATA Mathematical Systems Inc.
7
8[Problem and Algorithm]
9PROBLEM_NAME shift
10NUMBER_OF_VARIABLES 126
11(#INTEGER/DISCRETE) 126
12NUMBER_OF_FUNCTIONS 503
13PROBLEM_TYPE MINIMIZATION
14METHOD SIMPLEX
15
16[Progress]
17<preprocess begin>.........<preprocess end>
18<iteration begin>
19Coefficient Statistics (original problem)
20 Coefficient range [min,max] : [1.00e+00,1.00e+00]
21 RHS and bounds [min,max] : [1.00e+00,5.00e+00]
22 Objective [min,max] : [1.00e+00,1.00e+00]
23Coefficient Statistics (after scaling)
24 Coefficient range [min,max] : [1.00e+00,1.00e+00]
25 RHS and bounds [min,max] : [1.00e+00,5.00e+00]
26 Objective [min,max] : [9.00e+00,9.00e+00]
27 Row scaling range [min,max] : [1.00e+00,9.00e+00]
28 Column scaling range [min,max] : [1.00e+00,1.00e+00]
29
30<<wcsp tabu search begin>>
31 number of column singleton : 0
32 number of column selection : 42
33 Modify coefficients
34
35<preprocess begin>..........<preprocess end>
36preprocessing time: 0.001(s)
37<iteration begin>
38--- TryCount = 1 ---
39# random seed = 1
40(hard/semihard/soft) penalty= 42/0/5, time= 0.00(s)
41<greedyupdate begin>..........<greedyupdate end>
42greedyupdate time= 0(s)
43(hard/semihard/soft) penalty= 7/0/2, time= 0.00(s), iteration= 0
44(hard/semihard/soft) penalty= 6/0/2, time= 0.00(s), iteration= 1
45(hard/semihard/soft) penalty= 5/0/2, time= 0.00(s), iteration= 2
46(hard/semihard/soft) penalty= 4/0/2, time= 0.00(s), iteration= 3
47(hard/semihard/soft) penalty= 3/0/2, time= 0.00(s), iteration= 4
48(hard/semihard/soft) penalty= 2/0/3, time= 0.00(s), iteration= 13
49(hard/semihard/soft) penalty= 1/0/3, time= 0.00(s), iteration= 16
50(hard/semihard/soft) penalty= 0/0/3, time= 0.00(s), iteration= 18
51--- End Phase-I iteration ---
52# (hard/semihard/soft) penalty= 0/0/3
53# time = 0.00/0.00(s)
54# iteration = 18/1000
55<iteration end>
56# (hard/soft) = 0/3
57# iteration = 1000
58# time = 0.00 (s), succ = 1
59<<wcsp tabu search end>>
60
61#sol upper lower gap(%) time(s) list mem(MiB)
62#1 3 -inf +inf 0.0 0 746 sol: wcsp
63
64 .12
65
66 3 3 0.000 0.0 0 746
67
68<iteration end>
69
70[Result]
71STATUS OPTIMAL
72VALUE_OF_OBJECTIVE 3
73SIMPLEX_PIVOT_COUNT 172
74PARTIAL_PROBLEM_COUNT 1
75ELAPSED_TIME(sec.) 0.01
76店長の出勤日数: 3.0
77 1 2 3 4 5 6 7
78鈴木 日勤 日勤 休日 休日 夜勤 夜勤 夜勤
79田中 夜勤 夜勤 休日 休日 日勤 日勤 日勤
80佐藤 日勤 日勤 日勤 日勤 休日 休日 夜勤
81山田 夜勤 夜勤 夜勤 夜勤 日勤 休日 休日
82副店 休日 休日 夜勤 夜勤 夜勤 日勤 日勤
83店長 休日 休日 日勤 日勤 休日 夜勤 休日
84
求解結果を抜粋すれば,次のシフトスケジュールを得られたことが確認できる.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
---|---|---|---|---|---|---|---|
鈴木 |
日勤 |
日勤 |
休日 |
休日 |
夜勤 |
夜勤 |
夜勤 |
田中 |
夜勤 |
夜勤 |
休日 |
休日 |
日勤 |
日勤 |
日勤 |
佐藤 |
日勤 |
日勤 |
日勤 |
日勤 |
休日 |
休日 |
夜勤 |
山田 |
夜勤 |
夜勤 |
夜勤 |
夜勤 |
日勤 |
休日 |
休日 |
副店 |
休日 |
休日 |
夜勤 |
夜勤 |
夜勤 |
日勤 |
日勤 |
店長 |
休日 |
休日 |
日勤 |
日勤 |
休日 |
夜勤 |
休日 |
今度はシフトがバラバラになっておらず,シフトが連結している.
3.6. プロジェクトを成功へと導くために#
今回扱った問題は非常に簡素なものであった. しかし実際の現実問題を扱うプロジェクトが成功するためのエッセンスは垣間見えている. これらを振り返ろう.
3.6.1. ブラッシュアップ#
新たに追加した制約条件を考慮して得られた最適解で, 果たして店長は満足してくれるだろうか. 得られた結果はより実務に近い結果へと前進したが,おそらくまだ改良の余地がある. 例えば次のようなことを指摘できるだろう.
山田さんが \(4\) 日連続夜勤となっている.連続夜勤日数に上限はあるか.
前の週や次の週とのつながりは整合性をもっているか.
これらのことを再び加味して,制約条件式として記述して,また改めて求解する. そして得られた結果を検討・吟味する.
定式化ではこのようなフェイズを繰り返すことで, 精密に言語化 (ルールベース化) され,運用を任させられる綺麗な解に仕上がっていく.
3.6.2. 実際の計画立案者の重要性#
「顧客が本当に必要だったもの」へと着実に進めていくためには, 初期要件の定式化は勿論のこと,暗黙の制約条件を洗い出していく作業が必要であった
定式化を繰り返す中で,結果を検討するフェイズが必ず必要になる. このために大前提として業務推進者もしくは連絡窓口だけでなく, 実際に計画を立案されている担当者がステークホルダーとして参加している必要がある.
3.6.3. テストデータの重要性#
今回はデータ入力の自由度がほとんどなかった. 勤務日数の上下限値くらいである.このためテストデータの作成は非常に容易である.
しかし現実の定式化では入力データが多岐にわたることになり, 従ってテストデータの作成は重要な工程となって,意味のあるテストデータを作成することが必要となってくる. 「意味のある」という部分は計画立案者に委ねられるため,求解品質への直結を考えれば,ここでも担当者の協力が重要となる.
以上の内容は一般論に近いか,経験的なもので,マニュアル化は難しいものだが,およそ共通項と考えられるものである. 本話題と関係するであろう,興味深い議論が [1] でもなされており,参考になる.
技法集
参考文献
JakobS. What are the reasons OR industry projects fail? 2019. URL: https://or.stackexchange.com/questions/2953/what-are-the-reasons-or-industry-projects-fail.
引用書式
BibTeX