コロナ禍で重要になる最適化モデル（１）シフト最適化

シフト最適化

コロナ禍においては，人的資源（スタッフ）の適切な配置が重要性を増すと考えられます．たとえば，スーパーのレジに適切な人数を適切な時間に配置しないと，お客さんがたくさん並んでしまい，コロナへの感染危険度が増します．そのようなスーパーには，お客さんは足を運ぶことを躊躇するでしょう．

このような問題を解決するための最適化モデルが，シフトスケジューリングモデルです．このモデルでは，「シフト」の概念が中心的な役割を果たします．

シフトとは，各日にスタッフが何時に出勤して何時に退勤するかで決まります．単純に，時間帯を区切って，それをシフトと呼ぶ場合もあります．たとえば，看護婦のシフトスケジューリングにおいては，朝，昼，夜の3つのシフトを考えたります．しかし，我々が考えているシフトは，もっと柔軟なものです．たとえば，８時に出勤して１５時に帰る人もいれば，９時に出勤して１８時まで働く人もいたりします．このように，出勤時刻と退勤時刻の可能な対をすべてシフトと定義するわけです．

シフトには，休みというシフトも入ります．このようなシフトの集合から1つのものを選択して，それを（たとえば）１ヶ月分決めるものとしましょうい．この際には，以下のような制約を考慮する必要があります．

• １ヶ月の出勤時間の合計が各スタッフの希望時間の範囲内
• 適当な期間（たとえば１週間）に休みが適当な回数入っている．
• あるシフト（たとえば夜勤）の次に入れられないシフト（たとえば朝勤）がある．
• 同じシフトに特定のスタッフが同時に勤務することを禁止する．

スタッフごとにできる仕事が限定されている場合もあります．これを業務と呼びます．たとえば，レジ打ちとか接客とか休憩が業務に相当します．1日の勤務時間帯にどの業務をするかも同時に最適化します．この際，以下のような制約を考慮する必要があります．

• 特定の業務（たとえば休憩）は，特定の時間帯（たとえば出勤直後や退勤直前）にはできない．
• ある業務（たとえば品出し）は，特定の業務（たとえばトイレ掃除）の後には（もしくは前には）できない．
• できるだけ時間帯ごとに定められた各業務に必要な人数を満たす．

スタッフの時給が既知のときに，総費用を最小化し，制約をなるべく満たすようなスケジュールを決める問題は，制約最適化問題になります．

大規模な制約最適化問題は，通常は解くことが難しい問題ですが，弊社ではメタヒューリスティクスに基づく最適化を用いることによって，スタッフ数100程度の大規模な問題例でも数分で良好な解を算出することに成功しています．

詳細については，OptShiftの製品ページをご参照下さい．