勤務シフト表の作成1(1)【GLPK】

<--目次へ

勤務シフト表の作成1(1) (基礎編) ←ここ (2)　(3)　(4)
勤務シフト表の作成2 (2日連続して勤務する場合の勤務シフト)

マニュアルなど

GLPKに同梱されているマニュアル(gmpl.pdf)に詳しく書かれていますが、いきなり読んでも分かりにくいと思います。
GLPKスーパー簡易マニュアル
GLPKでのペンシルパズル(ナンリンなど)攻略法
などが参考になりそうです。

勤務シフト表作成

まず簡単な例を書いておきます。

shift1.model

# version 0.1
# シフト表作成
param firstDate; # 期間の最初の日付
param endDate;   # 最後の日付
set Date := firstDate..endDate; # 期間内の日付
set TimeSlot := {"朝", "夕", "夜"}; # シフト時間枠
set Staff; # スタッフ名
param maxWorkingDays{Staff}; # 各スタッフの最大勤務日数
# 日付,シフト時間枠,スタッフの配列を確保、出勤の割り当ては1が入る
var assignShiftSchedule{Date, TimeSlot, Staff} binary;

# シフト時間枠に必ず1人従事
s.t. keepStaffInTimeSlot{d in Date, t in TimeSlot}: sum{s in Staff}assignShiftSchedule[d,t,s]==1;
# 出勤は1日1回以下
s.t. avoidShiftPatten1{s in Staff, d in Date}: sum{t in TimeSlot}assignShiftSchedule[d,t,s]<=1;
# 最大勤務日数で制限
s.t. restrictMaxWorkDays{s in Staff}: sum{d in Date, t in TimeSlot}assignShiftSchedule[d,t,s]<=maxWorkingDays[s];

solve;
# 出力
for{d in Date}{
    printf "%2d ", d;
    for{t in TimeSlot}{
        printf{s in Staff : assignShiftSchedule[d,t,s]==1}" %s", s;
    }
    printf "\n";
}

data;
# 期間の最初の日付と最後の日付
param firstDate:=1; 
param endDate  :=12;
# スタッフ名と最大勤務日数
param : Staff : maxWorkingDays :=
"A"  9
"B"  9
"C"  9
"D"  9
;

制約条件の追加

休みを定期的に

上のプログラムでは休みが不規則に入ってします。ちょっと使いたくないですねえ。
それでは定期的に休みが入るようにします。ここでは連続した勤務は3日以内に制限する場合を考えてみます。
GLPKなどの整数計画法のソルバーはvarで指定した変数を足し算や引き算で制限を加えています。
4日連続したどの期間においても3日以下しか勤務しない条件を加えると実現できます。式にすると
s.t. keepOffDay{s in Staff, d in firstDate..endDate-3}: sum{t in TimeSlot}(assignShiftSchedule[d,t,s]+assignShiftSchedule[d+1,t,s]+assignShiftSchedule[d+2,t,s]+assignShiftSchedule[d+3,t,s])<=3;
になります。solveの前に挿入すると制限が追加されます。

翌日の勤務時間帯の制限

次に、"夕"や"夜"勤務の後に翌日の"朝"の勤務にならない条件を加えてみます。
s.t. avoidShiftPatten2{s in Staff, d in firstDate..endDate-1}: assignShiftSchedule[d,"夕",s]+assignShiftSchedule[d,"夜",s]+assignShiftSchedule[d+1,"朝",s]<=1;
さらに"夜"の勤務の後に翌日の"朝"や"夕"の勤務にならない条件も
s.t. avoidShiftPatten3{s in Staff, d in firstDate..endDate-1}: assignShiftSchedule[d,"夜",s]+assignShiftSchedule[d+1,"朝",s]+assignShiftSchedule[d+1,"夕",s]<=1;
これで少しはマシになってきたような。

スタッフの出勤時間帯の指定

例えば1日の朝にAが出勤するように指定するには
s.t. fix01: assignShiftSchedule[1,"朝","A"]=1;
のように強引に制約条件を追加することで実現できます。
逆に出勤できない場合には
s.t. fix11: assignShiftSchedule[2,"朝","A"]=0;
のようにその時間を0にする制約条件を追加すればできるのですが、美しくないですねえ。

GLPKによる勤務シフト表の作成1(2)->