こんにちは！Fusic 機械学習チームの塚本です。
機械学習モデルの開発から運用までなんでもしています。もし、機械学習で困っていることがあれば、気軽にお問い合わせください。
制約最適化ソルバーSCOPを利用して、シフトスケジューリングを行なってみます。
- SCOP: 大規模な制約計画問題を高速に解くためのソルバー
- 制約最適化: 制約充足問題を対象としていて、変数、領域、制約の３つからモデル化
- 重み付き制約充足問題: 制約充足問題を拡張し、制約違反のペナルティを重み付き和で表現してモデル化
といったものです。
今回は無料のトライアル版を利用します。 ドキュメント
問題設定
問題設定は、https://scmopt.github.io/opt100/81shift-minimization.html の看護婦スケジューリング問題を対象とします。
ただし、トライアル版では15変数のみに限られるため、色々設定をいじります。
- 従業員数: 5人
- 日数: 5日
- 従業員の指定休暇日: 10日
- 朝,夕など、複数の時間帯への勤務可能
指定休暇日の変数を作らないようにすることで、変数の数が15個（5x5-10）になります。
まあ、ちょっと無理やりですが、サンプル問題なので。
さらに、制約は以下を課します。
1. 毎日の各勤務（朝、昼、夕、夜）の必要人数を満たすこと
2. 禁止パターン：3連続夜勤務
3. 各日付ごと、朝、昼、夕、夜で戦力が偏らないようにする
3つ目は曖昧なもので、一般の数理最適化においては目的関数となります。
制約最適化においては、全てが制約関数になるので、これも制約にして、モデリングします。
問題設定コード
workers = ["A", "B", "C", "D", "E"]
D = list(range(1, 6))
time_dict = {
0: "朝", 1: "昼", 2: "夕", 3: "夜",
4: "朝,昼", 5: "朝,夕", 6: "朝,夜", 7: "昼,夕", 8: "昼,夜", 9: "夕,夜",
10: "朝,昼,夕", 11: "朝,昼,夜", 12: "朝,夕,夜", 13: "昼,夕,夜",
14: "休暇"
}
times = [0,1,2,3]
holiday = 14
morning = [key for key in time_dict if time_dict[times[0]] in time_dict[key]]
daytime = [key for key in time_dict if time_dict[times[1]] in time_dict[key]]
evening = [key for key in time_dict if time_dict[times[2]] in time_dict[key]]
night = [key for key in time_dict if time_dict[times[3]] in time_dict[key]]
domain = time_dict.keys()
T = dict(zip(times,[morning,daytime,evening,night]))
# 必要人数 ... 朝: 1人, 昼: 3人, 夕: 2人, 夜: 2人
required_num = dict(zip(times, [1, 3, 2, 2]))
powers = dict(zip(
workers, [
dict(zip(times, [2,3,2,3])),
dict(zip(times, [1,1,3,3])),
dict(zip(times, [1,2,2,3])),
dict(zip(times, [2,2,2,2])),
dict(zip(times, [3,3,3,3]))
]
))
# 15変数にするため、指定休暇が10になるように設定
worker_holiday = dict(zip(workers, [[1,3,5],[2],[4,5],[],[1,2,3,4]]))
# 各日付と勤務可能な従業員を対応づけ
D_W = {d:[w for w in workers if d not in worker_holiday[w]] for d in D}
W_D = {w:[d for d in D if d not in worker_holiday[w]] for w in workers}
変数
前述しましたが、変数、領域、制約の３つからモデル化していきます。
通常、従業員
x = pulp.LpVariable.dicts("var", (W, D, T), cat=pulp.LpBinary)
SCOPでは変数の領域を定義できて、
今回、変数の取りうる領域を（朝、昼、夕、夜）および、'朝,昼'などの組み合わせをdomain(=T)とすると、下のような感じです。
x = [Variable(domain=T) for w in W for d in D]
領域で表せることで次元を一つ減らせる形となっていますね。
model = Model()
for d in D_W:
for w in D_W[d]:
model.addVariable(name=f"{w}_{d}", domain=domain)
x=model.varDict
制約
SCOPのモジュールの制約設定には線形制約、相違制約、2次制約からなります。
基本的にどの制約クラスにもweightがあり、これが、制約設定において重要になります。
weight="inf"でハード制約
weight=数値でソフト制約
となり、この重みと制約式でペナルティとして、モデリングしていくことになります。
制約式を定義したら、次に項を追加です。
項の追加はSCOPモジュールのConstraintにあるaddTerms(係数,変数,領域)の関数を使います。
ここから、1,2,3の制約について追加していきますが、
今回はサンプルで、業務によって仕様が変わっていくと思うので、説明等は省略。。。
一点、3についてですが、ここだけ少し書いておきます。
制約追加
# 1. 毎日の各勤務（朝、昼、夕、夜）の必要人数を満たすこと
for d in D:
for t in T:
wts = T[t]
R = required_num[t]
lc = Linear(
f'required_num_constraints_{d}_{t}',
weight='inf',
rhs=R,
direction='>='
)
for w in D_W[d]:
_len = len(wts)
lc.addTerms([1]*_len, [x[f"{w}_{d}"]]*_len, wts)
model.addConstraint(lc)
# 2. 禁止パターン：3連続夜勤務
day3 = [[D[i], D[i+1], D[i+2]] for i in range(len(D)-2)]
for w in workers:
for days in day3:
if not set(days).issubset(set(W_D[w])):
continue
lc = Linear(
f'night_constraints_{w}_{days[0]}_{days[-1]}',
weight='inf',rhs=2,
direction='<='
)
for d in days:
_len = len(night)
lc.addTerms([1]*_len, [x[f"{w}_{d}"]]*_len, night)
model.addConstraint(lc)
# 3. 各日付ごと、朝、昼、夕、夜で戦力が偏らないようにする
from itertools import product
day_time = product(D, times)
n = len(D) * len(times)
X = {}
for d, time in day_time:
for w in D_W[d]:
p = powers[w][time]
for t in T[time]:
X[f"{w}_{d}"] = {
"weight": p,
"variable": x[f"{w}_{d}"],
"domain": t}
keys = product(X,X)
V = Quadratic(f'power_V_objective',weight=1,rhs=0, direction='=')
for i, j in keys:
w = X[i]["weight"] * X[j]["weight"]
if i == j:
w *= (n-1)
else:
w *= -1
V.addTerms(
w,
X[i]["variable"],
X[i]["domain"],
X[j]["variable"],
X[j]["domain"])
model.addConstraint(V)
3. 各日付ごと、朝、昼、夕、夜で戦力が偏らないようにする
今回の問題設定では、戦力分散が大きくならないようにしていきました。
2次制約として、分散を計算して、0になるように制約を設定します。
また、SCOPのモジュールでは、項を追加していく形なので、この式を展開しておく必要があります。
一般に、分散の式は以下で表されます。
最適化と可視化
ここまでで、変数定義、制約の追加が完了したので、問題を解きます。
model.Params.TimeLimit=1
sol,violated=model.optimize()
schedules = {}
if model.Status==0:
for w in workers:
for d in D:
if f"{w}_{d}" in sol:
val = int(sol[f"{w}_{d}"])
else:
val = holiday
if w not in schedules:
schedules[w] = {}
schedules[w][d] = time_dict[val]
print ('violated constraint(s)')
for v in violated:
print (v,violated[v])
pd.DataFrame(schedules)
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | 休暇 | 朝,昼,夜 | 朝,昼,夕 | 昼,夕,夜 | 休暇 |
| 2 | 昼,夕 | 休暇 | 朝,昼,夜 | 昼,夕,夜 | 休暇 |
| 3 | 休暇 | 昼,夕,夜 | 昼,夜 | 朝,昼,夕 | 休暇 |
| 4 | 朝,昼,夜 | 朝,昼,夕 | 休暇 | 昼,夕,夜 | 休暇 |
| 5 | 休暇 | 朝,昼,夜 | 休暇 | 昼,夕,夜 | 昼,夕 |
グラフ描画コード
data = np.zeros((len(D),len(workers),len(times)), dtype=int)
time_key2val = {time_dict[key]:key for key in times}
for d in D:
schedule = {w:schedules[w][d] for w in schedules}
for key, val in schedule.items():
ts = val.split(",")
for t in ts:
if t == time_dict[holiday]:
continue
data[d-1, ord(key) - ord("A"), time_key2val[t]] = 1
# グラフの描画
fig, axs = plt.subplots(nrows=1, ncols=len(D), figsize=(12, 4))
for i, ax in enumerate(axs):
ax.set_title(f"{i+1}日")
ax.imshow(data[i], cmap="Blues", alpha=0.5)
ax.set_xticks(range(4))
ax.set_yticks(range(5))
ax.set_xticklabels([time_dict[t] for t in times])
if i == 0:
ax.set_yticklabels([worker_name[w] for w in workers])
else:
ax.set_yticklabels([])
ax.hlines([0.5, 1.5, 2.5, 3.5], -0.5, 3.5, colors="gray")
ax.vlines([0.5, 1.5, 2.5], -0.5, 4.5, colors="gray")
fig.suptitle("Employee Schedule")
plt.show()
{'A': '佐藤', 'B': '鈴木', 'C': '高橋', 'D': '田中', 'E': '伊藤'}と仮置きして表示しています。
色のついている部分が出勤部分です。
一番確認しやすい部分として、必要人数 ... 朝: 1人, 昼: 3人, 夕: 2人, 夜: 2人 です。
ちゃんと満たせていますね。
その他として、初期解の設定やパフォーマンスのグラフ化なども提供されていますが、
今回はとりあえず、求解までが目標なので省略。
最後に宣伝になりますが、機械学習でビジネスの成長を加速するために、Fusicの機械学習チームがお手伝いしています。機械学習のPoCから運用まで、すべての場面でサポートした実績があります。もし、困っている方がいましたら、ぜひFusicにご相談ください。
Discussion