Shift Optimzation using SCOP (Solver for Constraint Programming)
YouTubeVideo("OmfDYolmT2g")
fig = plot_scop_for_shift("scop_out.txt")
plotly.offline.plot(fig);
day_df = generate_day('2020-5-1', '2020-5-5')
#day_df.to_csv(folder+"day.csv")
day_df.head()
jp_holidays = holidays.Japan()
#dt.date(2015, 1, 1) in jp_holidays
#print(jp_holidays)
day_df = pd.DataFrame(pd.date_range('2020-5-1', '2020-5-15', freq='D'),columns=["day"])
day_df["day_of_week"] = [('Holiday') if t in jp_holidays else (t.strftime('%a')) for t in day_df["day"] ]
n_day = len(day_df)
row_ = []
for row in day_df.itertuples():
if row.day_of_week =="Holiday":
row_.append("holiday")
elif row.day_of_week =="Sun":
row_.append("sunday")
else:
row_.append("weekday")
day_df["day_type"] = row_
day_df["id"] = [t for t in range(len(day_df))]
day_df = day_df.reindex(columns=["id", "day", "day_of_week", "day_type"])
day_df
start_time = pd.to_datetime("9:00")
end_time = pd.to_datetime("21:00")
period_df = generate_period(start_time, end_time, freq="1h")
period_df
n_period = 12
id_ = [t for t in range(n_period+1)] #最後のシフトの終了時刻まで入力するために1を加える。(ガントチャートの描画で使う.)
description_ = [f"{t}:00" for t in range(9,9+n_period+1)]
period_df = pd.DataFrame({"id":id_, "description":description_})
#period_df.to_csv(folder + "period.csv")
period_df
random.seed(1)
T = 13
break_prob = 0.3
period_, break_ = [], []
min_work_time = 3
for t in range(min_work_time, T):
period_.append(t)
if t == min_work_time:
break_ = [0]
else:
if random.random() <= break_prob:
break_.append(break_[-1] + 1)
else:
break_.append(break_[-1])
break_df = pd.DataFrame({"period":period_, "break_time":break_})
#break_df.to_csv(folder + "break.csv")
break_df
#description_ = ["break", レジ打ち", "バックヤード", "接客", "調理"]
description_ = ["break", "レジ打ち", "接客"]
n_job = len(description_)
id_ = [t for t in range(n_job)]
job_df = pd.DataFrame({"id":id_, "description":description_})
#job_df.to_csv(folder + "job.csv")
job_df
fake = Faker(['en_US', 'ja_JP','zh_CN','ko_KR'])
Faker.seed(1)
n_day = len(day_df)
n_job = len(job_df)
n_staff = 30
name_ = []
job_list = list(job_df["id"][1:]) #最初のジョブは休憩なので除く
for i in range(n_staff):
name_.append( fake.name() )
staff_df = pd.DataFrame( {"name": name_,
"wage_per_period": np.random.randint(low=850,high=1300,size=n_staff),
"max_period": np.random.randint(5,break_df.period.max()+1, n_staff),
"max_day": np.random.randint(1,3, n_staff),
"job_set": [ str(random.sample(job_list,random.randint(1,n_job-1) )) for s in range(n_staff) ],
"day_off": [ str(random.sample( list(range(n_day)), 1 )) for s in range(n_staff) ],
#"day_off": [ "[]" for s in range(n_staff) ],
"start": np.random.randint(low=0, high=len(period_df)//2 -1, size= n_staff),
"end": np.random.randint(low=len(period_df)//2 + 1, high=len(period_df)-1, size= n_staff)
} )
#staff_df.to_csv(folder+"staff.csv")
staff_df
n_period = len(period_df)-1
day_type = ["weekday", "sunday", "holiday"]
type_, job_, period_, lb_ = [],[],[],[]
for d in day_type:
for j in range(1,n_job): #ジョブ番号0は休憩なので除く
req_ = np.ones(n_period, int)
lb = 0
ub = n_period
for iter_ in range(4):
lb = lb + random.randint(1, 3)
ub = ub - random.randint(1, 3)
if lb < ub:
for t in range(lb,ub):
req_[t]+=1
for t in range(n_period):
type_.append(d)
job_.append(j)
period_.append(t)
lb_.append(req_[t])
requirement_df = pd.DataFrame({"day_type":type_, "job":job_, "period":period_,"requirement":lb_ })
#requirement_df.to_csv(folder+"requirement.csv")
requirement_df.head()
n_day = len(day_df)
n_job = len(job_df)
n_period = len(period_df)-1
work_hours = np.zeros( (n_job,n_day,n_period) )
for row in staff_df.itertuples():
job_set = ast.literal_eval(row.job_set)
day_off = set( ast.literal_eval(row.day_off) )
max_period = row.max_period #最大稼働時間/1日の稼働時間 だけ加算する
max_day = row.max_day #最大稼働日数/計画期間 だけ加算する.
ratio = max_period/n_period * max_day/n_day
#print(ratio)
for d in range(n_day):
if d not in day_off:
for j in job_set:
for t in range(row.start, row.end+1):
work_hours[j,d,t]+= ratio
work_hours[1]
requirement ={}
for row in requirement_df.itertuples():
requirement[row.day_type, row.period, row.job] = row.requirement
req = np.zeros( (n_job, n_day, n_period) )
for d, row in enumerate(day_df.itertuples()):
for j in range(1,n_job):
for t in range(n_period):
req[j,d,t] += requirement[row.day_type,t,j]
req[1]
import seaborn as sns
sns.heatmap(work_hours[1]/req[1], annot=True, fmt="1.2f");
fig = px.imshow(work_hours[1]/req[1], color_continuous_scale=px.colors.sequential.Viridis)
fig.update_xaxes(side="top")
plotly.offline.plot(fig);
fig = estimate_requirement(day_df, period_df, job_df, staff_df, requirement_df, days=[1,2,3])
#plotly.offline.plot(fig);
Image("../figure/estimate_requirement.png")
SCOP Model
制約最適化ソルバー SCOP を用いたモデルを記述する。
引数:
- period_df : 期間データフレーム
- break_df : 休憩データフレーム
- day_df : 日データフレーム
- job_df : ジョブデータフレーム
- staff_df : スタッフデータフレーム
- requirement_df : 必要人数データフレーム
- theta : 開始直後(もしくは終了直前)に休憩を禁止する期間数(既定値は1)
- lb_penalty : 必要人数を下回った場合のペナルティ(既定値は10000)
- ub_penalty : 必要人数を上回った場合のペナルティ(既定値は0)
- job_change_penalty : ジョブを切り替えたときのペナルティ(既定値は10)
- break_penalty : 開始直後・終了直前の休憩を逸脱したときのペナルティ(既定値は10000)
- max_day_penalty : 最大稼働日数を超過したときのペナルティ(既定値は5000)
- OutputFlag : 出力フラグ;ソルバーの出力を出す場合にはTrue (既定値はFalse)
- TimeLimit : 計算時間上限(既定値は10秒)
- random_seed : ソルバーで用いる擬似乱数の種(既定値は1)
- cloud: 複数人が同時実行する可能性があるときTrue(既定値はFalse); Trueのとき,ソルバー呼び出し時に生成されるファイルにタイムスタンプを追加し,計算終了後にファイルを消去する.
返値:
- x : 変数 $x$ を入れた辞書
- y : 変数 $y$ を入れた辞書
- sol : 解を表す辞書
- violated : 逸脱した制約を表す辞書
- day_off : 希望休日を入れた辞書
- requirement : 必要人数を入れた辞書
- status : 最適化の状態を表す数字;以下の意味を持つ。
status | 意味 |
---|---|
0 | 最適化成功 |
1 | 求解中にユーザが Ctrl-C を入力したことによって強制終了した. |
2 | 入力データファイルの読み込みに失敗した. |
3 | 初期解ファイルの読み込みに失敗した. |
4 | ログファイルの書き込みに失敗した. |
5 | 入力データの書式にエラーがある. |
6 | メモリの確保に失敗した. |
7 | 実行ファイル scop.exe のよび出しに失敗した. |
10 | モデルの入力は完了しているが,まだ最適化されていない. |
負の値 | その他のエラー |
period_df = pd.read_csv(folder+"period.csv", index_col=0)
break_df = pd.read_csv(folder+"break.csv", index_col=0)
day_df = pd.read_csv(folder+"day.csv", index_col=0)
job_df = pd.read_csv(folder+"job.csv", index_col=0)
staff_df = pd.read_csv(folder+"staff.csv", index_col=0)
requirement_df = pd.read_csv(folder+"requirement.csv", index_col=0)
cost_df, violate_df, new_staff_df, job_assign, status = shift_scheduling(period_df, break_df, day_df, job_df, staff_df, requirement_df, theta=1,
lb_penalty =10000, ub_penalty =10000, job_change_penalty = 10, break_penalty = 10000, max_day_penalty = 5000,
OutputFlag=False, TimeLimit=10, random_seed = 2)
#plotly.offline.plot(fig);
#plotly.offline.plot(fig);
if TEST:
print("Status",status)
if status ==0: #SCOPが失敗していないときのみ表示
fig = make_requirement_graph(day_df, period_df, job_df, staff_df, requirement_df, job_assign, day = 0)
plotly.offline.plot(fig);
Image("../figure/requirement_for_shift.png")
if TEST:
if status ==0: #SCOPが失敗していないときのみ表示
fig = make_gannt_for_shift(day_df, period_df, staff_df, job_df, job_assign, day=0 )
plotly.offline.plot(fig);
Image("../figure/gannt_for_shift.png")