Shift Optimzation using SCOP (Solver for Constraint Programming)
YouTubeVideo("OmfDYolmT2g")

モデルの定式化

集合・パラメータ・変数を以下に示す.

集合:

  • $I$ : スタッフの集合 $= \{1,2, \ldots , i, \ldots|I|\} $
  • $J$ : スタッフが就く業務の集合 $= \{1,2, \ldots , j, \ldots|J|\} $ ;この中には休憩を表す $r$ が含まれるものとする。
  • $D$ : 計画日の集合 $= \{1,2, \ldots , d, \ldots|D|\} $
  • $T_{d}$ : 計画日$d$における計画期(時間帯;例えば1時間や30分を1単位とする)の集合 $= \{0,1, \ldots , t, \ldots|T_{d}|-1\} $
  • $T'_{id}$ : スタッフ$i$の日$d$における勤務可能期の集合 $= \{t \mid o_{id} \leq t \leq e_{id}, t \in T_{d} \}$ ($o_{id}$と$e_{id}$ はそれぞれ開始可能期と終了期)
  • $O_{id}$ : 日 $d$ にスタッフ$i$が、$\{s \mid o_{id} \leq s < e_{id}-m+1 , s \in T_{d}\}$ 期に勤務を開始し, $\{t \mid s+m-1 \leq t \leq e_{id} , t \in T_{d}\}$期に勤務を終了するという組み合わせ$(s, t)$を要素とした集合 ($m$ は最低勤務期間数)

パラメータ:

  • $c_{ist}$ : スタッフ$i$が$s$期に勤務を開始し,$t$期に勤務を終了するときの費用
  • $w_{ist}$ : スタッフ$i$が$s$期に勤務を開始し,$t$期に勤務を終了するときの(休憩時間を除いた)稼働期数
  • $LB_{dtj}$ : 日$d$の期$t$に業務$j$で必要なスタッフの人数
  • $h_{dtj}$ : 日$d$の期$t$における業務$j$のスタッフ不足時のペナルティ費用
  • $m$ : 最低勤務期間数.勤務開始から勤務終了まで$m$期以上勤務しなければならないものとする。
  • $B_{i}$ : スタッフ$i$の計画期間中の勤務期数上限
  • $o_{id}$ : スタッフ$i$の日$d$における勤務開始可能期
  • $e_{id}$ : スタッフ$i$の日$d$における勤務終了期限期
  • $\tau_{st}$ : $s$期から$t$期まで勤務したときに必要な休憩期数
  • $\beta$ : 休憩を開始直後から(もしくは終了直前に)とることを禁止した期数
  • $\zeta_{i}$ : スタッフ$i$が勤務業務を変更したときのペナルティ費用

変数:

  • $x_{idst}$ : スタッフ$i$が日$d$期$s$に勤務を開始し,期 $t$ に勤務を終了するとき $1$、それ以外のとき $0$ を表す$0$-$1$変数

  • $y_{idtj}$: スタッフ$i$が日$d$期$t$に業務$j$に就くとき $1$、それ以外のとき $0$ を表す$0$-$1$変数

  • $\xi_{dtj}$ : 日$d$, 期$t$, 業務$j$のスタッフ不足数を表す整数変数

  • $u_{idtj}$ : スタッフ$i$が日$d$期$t$に勤務業務を休憩以外の別の勤務業務から$j$に変更したとき $1$、それ以外のとき $0$ を表す$0$-$1$変数

定式化:

$$ \begin{array}{lll} minimize & \sum_{ i \in I} \sum_{ d \in D} \sum_{(s,t) \in O_{id}}c_{ist} x_{idst} + \sum_{ d \in D} \sum_{ t \in T_{d}} \sum_{j \in J} h_{dtj} \xi_{dtj} + \sum_{i \in I} \sum_{d \in D} \sum_{t \in T_{d}} \sum_{j \in J_{i}} \zeta_{i} u_{idtj} & \\ s.t. & \sum_{j \in J_{i}} y_{idkj} = \sum_{(s,t):s \leq k \leq t , (s,t) \in O_{id}} x_{idst} & \forall i \in I, d \in D, k \in T'_{id} \\ & \sum_{(s,t) \in O_{id}} x_{idst} \leq 1 & \forall i \in I, d \in D \\ & \sum_{k \in T'_{id}} y_{idkr} = \sum_{(s,t) \in O_{id}} \tau_{st} x_{idst} & \forall i \in I, d \in D \\ & \sum_{i|j \in J_{i}} y_{idtj} + \xi_{dtj} \geq LB_{dtj} & \forall d \in D, t \in T_{d}, j \in J \\ & \sum_{d \in D} \sum_{(s,t) \in O_{id}} w_{ist} x_{idst} \leq B_{i} & \forall i \in I \\ & y_{idtj} - y_{id,t-1,j} - y_{id,t-1,r}\leq u_{idtj} & \forall i \in I, d \in D, t \in T_{d}, j \in J \\ & \sum^{t+\beta}_{k'=k} y_{idk'r} \leq \beta\left(1 - \sum_{(s,t):s=k ,(s,t) \in O_{id}} x_{idst}\right) & \forall i \in I, d \in D, k \in T'_{d} \\ & \sum^{k}_{k'=k-\beta} y_{idk'r} \leq \beta\left(1 - \sum_{(s,t):t=k ,(s,t) \in O_{id}} x_{idst}\right) & \forall i \in I, d \in D, k \in T'_{d} \end{array} $$

目的関数は費用最小化である.

  • 第1項は、スタッフに支払う賃金を表す.
  • 第2項は、人員不足時のペナルティ費用を表す.
  • 第3項は、業務変更の費用を表す。

制約:

  • 変数$y_{idtj}$と変数$x_{idst}$の繋がりを表す制約
  • 1計画日中に出勤・退勤は高々1度しかないことを表す制約
  • 勤務期間内において労働時間に応じた休憩を取らなければならないことを表す制約
  • 日$d$期$t$における業務$j$のスタッフの必要人数を満たすことを表す制約
  • スタッフ$i$の労働期数の上限を表す制約
  • 休憩 (添字 $r$) 以外からの業務変更を行うときの変数 $u_{idtj}$ と変数 $y_{idtj}$ の繋ぎ式
  • 勤務開始直後・終了直前における休憩を禁止する制約

データ生成

日データ day_df (ファイル名はday.csv)

列:

  • day : 日付
  • day_of_week : 曜日;holidaysパッケージを用いて日本の祝日の場合には Holidayを入れる。
  • day_type: 人数の必要量データは、この列の要素ごとに定義される。ここでは、平日 (weekday)、日曜 (sunday)と祝日(holiday)の3種類を準備する。
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.to_csv(folder+"day.csv")
day_df
day day_of_week day_type
0 2020-05-01 Fri weekday
1 2020-05-02 Sat weekday
2 2020-05-03 Holiday holiday
3 2020-05-04 Holiday holiday
4 2020-05-05 Holiday holiday
5 2020-05-06 Holiday holiday
6 2020-05-07 Thu weekday
7 2020-05-08 Fri weekday
8 2020-05-09 Sat weekday
9 2020-05-10 Sun sunday
10 2020-05-11 Mon weekday
11 2020-05-12 Tue weekday
12 2020-05-13 Wed weekday
13 2020-05-14 Thu weekday
14 2020-05-15 Fri weekday

期間データ period_df (ファイル名 period.csv)

1日のスケジュールは、基本時間単位の区間(これを期と呼ぶ)に対して決められる。 以下では、1時間を1期として生成するが、30分や15分でも構わない。 従来のシフトスケジューリングでは、6時間などを1期として扱うことが多かったが、本システムではより細かい時間単位を用いて最適化を行う。 これは、昨今の時間給で働く従業員が増えたことを考慮したものである。

列:

  • id : 0から始まる整数
  • description: 時間区分の説明;ここでは期の開始時刻を入れている。例えば、最初の期は9:00から10:00までを表す。
#period.csv
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
id description
0 0 9:00
1 1 10:00
2 2 11:00
3 3 12:00
4 4 13:00
5 5 14:00
6 6 15:00
7 7 16:00
8 8 17:00
9 9 18:00
10 10 19:00
11 11 20:00
12 12 21:00

休憩データ break_df (ファイル名は break.csv)

時間ごとのシフトスケジュールを組む際には、休憩を考慮することも重要になる。 ここでは、就業規則を反映した休憩データを準備するものとする。 これは、1日の稼働時間に対して、何期分の休憩を入れるかを定義したものである。 また、シフトの開始から(もしくは終了前の)何期の間は休憩を入れることができないといった制約も加える。

列:

  • period : 1日のシフトの稼働時間。最初の行に入っている数字が、最低稼働時間になる。
  • break_time : 休憩を行う期の数
# break.csv
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
period break_time
0 3 0
1 4 1
2 5 1
3 6 1
4 7 2
5 8 2
6 9 2
7 10 2
8 11 2
9 12 3

ジョブ(業務)データ job_df (ファイル名は job_csv)

列:

  • id: : 0から始まる整数
  • description : ジョブ(業務、仕事)の名称;最初の行(idは0)には必ず休憩を表す"break"を入れておく。
# job.csv
#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
id description
0 0 break
1 1 レジ打ち
2 2 接客

スタッフ(従業員)データ staff_df (ファイル名は staff.csv)

列:

  • name : スタッフの名前
  • wage_per_period : 1期あたりの賃金
  • max_period : 1日あたりの最大稼働時間
  • max_day : 計画期間内に出勤できる最大日数
  • job_set : スタッフに割り当てることが可能なジョブ(業務)の集合;リスト形式の文字列で入力する。
  • day_off : 出勤できない日のidをリスト形式の文字列で入力する。
# staff.csv
from faker import Factory, Faker

fake = Faker(['en_US', 'ja_JP'])
Faker.seed(1)

n_staff = 20
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(8,break_df.period.max()+1, n_staff),
                          "max_day": np.random.randint(10,15, 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)), 3 )) for s in range(n_staff) ]
                         } )

staff_df.to_csv(folder+"staff.csv")
staff_df
name wage_per_period max_period max_day job_set day_off
0 Ryan Gallagher 1131 9 13 [2] [6, 12, 11]
1 高橋 翼 1214 12 11 [1] [8, 12, 2]
2 三宅 あすか 1144 9 12 [2, 1] [8, 12, 14]
3 Russell Reynolds 1126 12 13 [1, 2] [3, 6, 0]
4 青田 七夏 985 9 10 [1, 2] [7, 13, 5]
5 喜嶋 陽子 869 9 14 [1, 2] [9, 8, 3]
6 Amanda Johnson 1019 10 14 [2, 1] [8, 6, 7]
7 Teresa James 912 9 14 [2] [13, 5, 6]
8 佐藤 晃 1030 11 14 [2] [5, 0, 8]
9 Jeffrey Simpson 1274 12 14 [1, 2] [8, 9, 12]
10 David Robinson 1123 12 12 [1, 2] [9, 5, 7]
11 Dylan Smith 1286 10 10 [1] [9, 0, 12]
12 Kristie May 921 10 12 [2, 1] [3, 10, 2]
13 渡辺 陽一 995 8 13 [2] [8, 9, 2]
14 Gary Griffith 1111 8 10 [2] [13, 1, 12]
15 吉田 直子 1121 9 10 [1, 2] [8, 12, 4]
16 Meagan Turner 997 10 13 [1] [0, 13, 10]
17 Sonya Mathis 1064 11 14 [1] [1, 14, 0]
18 中村 明美 1171 11 12 [2, 1] [7, 0, 12]
19 三宅 拓真 913 9 10 [2, 1] [12, 4, 3]

必要人数データ requirement_df (ファイル名は requirement.csv)

列:

  • day_type : day_dfの day_type列で入力した日の種類;この種類別に必要人数を定義する。
  • job : ジョブid 
  • period : 期id
  • requirement : 必要人数
# requirement
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()
day_type job period requirement
0 weekday 1 0 1
1 weekday 1 1 1
2 weekday 1 2 2
3 weekday 1 3 2
4 weekday 1 4 2

必要人数が妥当かどうかを調べる。

スタッフにランダムにジョブを割り振ったときの稼働可能時間を計算し、それが必要人数以上であることを確認する。

pd.pivot_table(requirement_df, index=["job","day_type"], values="requirement", aggfunc=sum)
requirement
job day_type
1 holiday 20
sunday 23
weekday 27
2 holiday 28
sunday 25
weekday 26
random.seed(3)
total_hours = np.zeros( len(job_df) )
for row in staff_df.itertuples():
    j = random.sample(ast.literal_eval(row.job_set),1)[0] #select a job randomly 
    total_hours[j] += row.max_period * row.max_day
#total_hours = total_hours/30.
total_hours = total_hours /30
total_hours
array([ 0.        , 45.26666667, 36.76666667])

SCOP Model

制約最適化ソルバー SCOP を用いたモデルを記述する。

引数:

  • period_df : 期間データフレーム
  • break_df : 休憩データフレーム
  • day_df : 日データフレーム
  • job_df : ジョブデータフレーム
  • staff_df : スタッフデータフレーム
  • requirement_df : 必要人数データフレーム
  • theta : 開始直後(もしくは終了直前)に休憩を禁止する期間数(既定値は1)
  • lb_penalty : 必要人数を下回った場合のペナルティ(既定値は10000)
  • job_change_penalty : ジョブを切り替えたときのペナルティ(既定値は10)
  • break_penalty : 開始直後・終了直前の休憩を逸脱したときのペナルティ(既定値は10000)
  • max_day_penalty : 最大稼働日数を超過したときのペナルティ(既定値は5000)
  • OutputFlag : 出力フラグ;ソルバーの出力を出す場合にはTrue (既定値はFalse)
  • TimeLimit : 計算時間上限(既定値は10秒)
  • random_seed : ソルバーで用いる擬似乱数の種(既定値は1)

返値:

  • x : 変数 $x$ を入れた辞書
  • y : 変数 $y$ を入れた辞書
  • sol : 解を表す辞書
  • violated : 逸脱した制約を表す辞書
  • day_off : 希望休日を入れた辞書
  • requirement : 必要人数を入れた辞書
  • status : 最適化の状態を表す数字;以下の意味を持つ。
status 意味
0 最適化成功
1 求解中にユーザが Ctrl-C を入力したことによって強制終了した.
2 入力データファイルの読み込みに失敗した.
3 初期解ファイルの読み込みに失敗した.
4 ログファイルの書き込みに失敗した.
5 入力データの書式にエラーがある.
6 メモリの確保に失敗した.
7 実行ファイル scop.exe のよび出しに失敗した.
10 モデルの入力は完了しているが,まだ最適化されていない.
負の値 その他のエラー

shift_scheduling[source]

shift_scheduling(period_df, break_df, day_df, job_df, staff_df, requirement_df, theta=1, lb_penalty=10000, job_change_penalty=10, break_penalty=10000, max_day_penalty=5000, OutputFlag=False, TimeLimit=10, random_seed=1)

シフト最適化

shift_scheduling関数の使用例

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)

x, y, sol, violated, day_off, requirement, status = shift_scheduling(period_df, break_df, day_df, job_df, staff_df, requirement_df, theta=1,
                     lb_penalty =10000, job_change_penalty = 10, break_penalty = 10000, max_day_penalty = 5000, 
                    OutputFlag=False, TimeLimit=10, random_seed = 1)
 ================ Now solving the problem ================ 

可視化

必要人数を描画する関数 make_requirement_graph

引数:

  • day_df : 日データフレーム
  • period_df : 期間データフレーム
  • job_df : ジョブデータフレーム
  • staff_df : スタッフデータフレーム
  • y : 変数 $y$ を入れた辞書
  • day_off : 希望休日を入れた辞書
  • requirement : 必要人数を入れた辞書
  • day : 描画したい日のid

返値:

  • fig : Plotlyのグラフオブジェクト

make_requirement_graph[source]

make_requirement_graph(day_df, period_df, job_df, staff_df, y, day_off, requirement, day=0)

必要人数のグラフを生成する関数

make_requirement_graphの使用例

print("Status",status)
if status ==0: #SCOPが失敗していないときのみ表示
    fig = make_requirement_graph(day_df, period_df, job_df, staff_df, y, day_off, requirement, day=0)
#fig.show()
Image("../figure/requirement_for_shift.png")
Status 0

ガントチャートを描画する関数 make_gannt_for_shift

引数:

  • day_df : 日データフレーム
  • period_df : 期間データフレーム
  • staff_df : スタッフデータフレーム
  • job_df : ジョブデータフレーム
  • y : 変数 $y$ を入れた辞書
  • day_off : 希望休日を入れた辞書
  • day : 描画したい日のid

返値:

  • fig : Plotlyのグラフオブジェクト

make_gannt_for_shift[source]

make_gannt_for_shift(day_df, period_df, staff_df, job_df, y, day_off, day=0)

スタッフごとのガントチャートを生成する関数

make_gannt_for_shiftの使用例

if status ==0: #SCOPが失敗していないときのみ表示
    fig = make_gannt_for_shift(day_df, period_df, staff_df, job_df, y, day_off, day=0 )
#fig.show()
#plotly.offline.plot(fig)
Image("../figure/gannt_for_shift.png")