勤務シフト表の作成基礎(2)【GLPK】 #GLPK

2021.10.13 追記あり

勤務シフト表の作成基礎(1)で表計算ソフトのソルバーを使ったプログラムを公開しています。全く同じ機能をGLPKで書いてみましたので、そちらも合わせてご覧ください。
GLPKの使い方などは上の「目次」を辿ってみてください。

最適化の条件1

１週間分の必要出勤人数とスタッフ別の出勤日数から、条件合うようにシフト表を作成します。

shift1.mod

# version 0.0.1
# シフト表作成
set Staff; # スタッフ名を読み込む
param nWorkingDays{Staff}; # 各スタッフの勤務日数を読み込む
param firstDate; # 期間の最初の日付を読み込む
param lastDate;   # 最後の日付を読み込む
set Date := firstDate..lastDate; # 期間内の日付
param necessary_nStaff{Date}; # 日別の必要出勤人数を読み込む

# 日付,スタッフ名が添字の配列を確保、出勤を割り当てる場合は1、休みは0が入る
var assignShiftSchedule{d in Date, s in Staff} binary;

# スタッフごとの出勤日数を合わす
s.t. restrictWorkDays{s in Staff}: sum{d in Date}assignShiftSchedule[d, s]==nWorkingDays[s];
# 日ごとの出勤人数を合わす
s.t. keepStaffInWorkDay{d in Date}: sum{s in Staff}assignShiftSchedule[d, s]==necessary_nStaff[d];

solve;

# 出力
printf "日付\t出勤者\n";
for{d in Date}{
    printf "%2d ", d;
    printf{s in Staff} (if assignShiftSchedule[d,s]==1 then "\t%s" else "\t---"), s;
    printf "\n";
}

data;
# 期間の最初の日付と最後の日付
param firstDate :=  1;
param lastDate := 7;

# 出勤人数 defaultを4とし、それ以外も場合は後で記入
param necessary_nStaff default 4 :=
1  3
2  3
4  3
;

# スタッフ名と勤務日数
param : Staff : nWorkingDays :=
"Aさん"  5
"Bさん"  5
"Cさん"  5
"Dさん"  5
"Eさん"  5
;

最適化の条件2

スタッフの休日希望を反映させるようにします。

s.t. restrictOffDuty{d in Date, s in Staff: (s,d) in FixOffDuty}: assignShiftSchedule[d, s]==0;

のように休日希望日を強制的に0にすること可能です(表計算ソフトのソルバーの例ではそうしています)が、変数の範囲を0以下に制限することで、強制的に0になるようにしています。
var assignShiftSchedule{d in Date, s in Staff} binary, <= if (s,d) in FixOffDuty then 0 else 1;

最適化の条件3 (2021.10.13 追記)

連続勤務日数の制限連続5日を限度とする

期間前の連続勤務日数と、最大連続勤務日数(=5)を追加することで、連続勤務日数の制限ができます。
最大連続勤務日数+1日の範囲の出勤日数を計算し、最大連続勤務日数以下だとその間に休日があることがわかります。
5日目までは期間前の連続勤務日数の影響を受けますので、s.t. limitContinuousWorkDay1でその間を
6日目からはその影響を受けませんので、s.t. limitContinuousWorkDay2で調べています。
下記は、EXCELのソルバーの動作と合わせていますが、shift4.modはより効率的な方法にしています。

s.t. limitContinuousWorkDay1{s in Staff, d in firstDate..firstDate+maxContinuousWorkDay-1}:
    sum{d2 in firstDate..d}assignShiftSchedule[d2, s]+min(daysFromOffDutyBeforeFirstDay[s], maxContinuousWorkDay+firstDate-d)<=maxContinuousWorkDay;
s.t. limitContinuousWorkDay2{s in Staff, d in firstDate+maxContinuousWorkDay..lastDate}:
    sum{d2 in d-maxContinuousWorkDay..d}assignShiftSchedule[d2, s]<=maxContinuousWorkDay;

つまり、休日希望があった時には、その前後の最大連続勤務日数分の間は連続勤務日数を調べなくて良いのでチェックを省略しています。

最適化の条件4 (2021.10.13 プログラム変更)

スタッフの出勤希望を反映させるようにします

次の式で、休日希望の場合には0以下、出勤希望の場合には1以上に制限されます。

var assignShiftSchedule{d in Date, s in Staff} binary, >= if (s,d) in FixOnDuty then 1 else 0, <= if (s,d) in FixOffDuty then 0 else 1;

ここまでの条件を反映したプログラム全体です。

shift4.mod

# version 0.0.4a
# シフト表作成 休日希望、出勤希望の設定あり 連続勤務日の制限あり

set Staff; # スタッフ名を読み込む
param nWorkingDays{Staff}; # 各スタッフの勤務日数を読み込む
param firstDate; # 期間の最初の日付を読み込む
param lastDate;   # 最後の日付を読み込む
set Date := firstDate..lastDate; # 期間内の日付
param necessary_nStaff{Date}; # 日別の必要出勤人数を読み込む
set FixOffDuty dimen 2;   # 休日希望を読み込む
set FixOnDuty  dimen 2;   # 出勤希望を読み込む

param maxContinuousWorkDay; # 最大連続勤務日数を読み込む
param daysFromOffDutyBeforeFirstDay{Staff}; # スタッフの期間前の連続勤務日数

# 日付,スタッフ名が添字の配列を確保、出勤を割り当てる場合は1、休みは0が入る
# 出勤希望の場合は1以上、休日希望の場合は0以下、それぞれ1,0に制限
var assignShiftSchedule{d in Date, s in Staff} binary, >= if (s,d) in FixOnDuty then 1 else 0, <= if (s,d) in FixOffDuty then 0 else 1;

# スタッフごとの出勤日数を合わす
s.t. restrictWorkDays{s in Staff}: sum{d in Date}assignShiftSchedule[d, s]==nWorkingDays[s];
# 日ごとの出勤人数を合わす
s.t. keepStaffInWorkDay{d in Date}: sum{s in Staff}assignShiftSchedule[d, s]==necessary_nStaff[d];
# 連続勤務日数を制限
s.t. limitContinuousWorkDay1{s in Staff, d in firstDate+maxContinuousWorkDay-daysFromOffDutyBeforeFirstDay[s]..firstDate+maxContinuousWorkDay-1 : not exists{d1 in firstDate..d} (s,d1) in FixOffDuty}:
    sum{d2 in firstDate..d}assignShiftSchedule[d2, s]<=d-firstDate;
s.t. limitContinuousWorkDay2{s in Staff, d in firstDate+maxContinuousWorkDay..lastDate : not exists{d1 in d-maxContinuousWorkDay..d} (s,d1) in FixOffDuty}:
    sum{d2 in d-maxContinuousWorkDay..d}assignShiftSchedule[d2, s]<=maxContinuousWorkDay;

solve;

# 出力
printf "日付\t出勤者\n";
for{d in Date}{
    printf "%2d ", d;
    printf{s in Staff} (if assignShiftSchedule[d,s]==1 then "\t%s" else "\t---"), s;
    printf "\n";
}

data;
# 期間の最初の日付と最後の日付
param firstDate :=  1;
param lastDate := 7;

# 出勤人数 defaultを4とし、それ以外も場合は後で記入
param necessary_nStaff default 4 :=
1  3
2  3
4  3
;

# スタッフ名と勤務日数
param : Staff : nWorkingDays :=
"Aさん"  5
"Bさん"  5
"Cさん"  5
"Dさん"  5
"Eさん"  5
;

# 休日希望
set FixOffDuty :=
("Aさん", *) 4
("Cさん", *) 5
("Dさん", *) 3 4
;

# 出勤希望 上の休日希望と同じ形式で追加すると反映されます
set FixOnDuty :=
;

# 最大連続勤務日数
param maxContinuousWorkDay := 5;

# 期間前の連続勤務日数
param daysFromOffDutyBeforeFirstDay :=
"Aさん"  0
"Bさん"  1
"Cさん"  2
"Dさん"  3
"Eさん"  4
;

おまけ (2021.10.13 追記)

休日希望を出勤可能日に変更する方法

set FixOffDuty dimen 2;   # 休日希望を読み込む

を次のように

set WorkableDay dimen 2;   # 出勤可能日を読み込む
set FixOffDuty :=

データセクションの

# 休日希望
set FixOffDuty :=
("Aさん", *) 4
("Cさん", *) 5
("Dさん", *) 3 4
;

を

# 出勤可能日
set WorkableDay :=
("Aさん", *) 1 2 3 5 6 7
("Bさん", *) 1 2 3 4 5 6 7
("Cさん", *) 1 2 3 4 6 7
("Dさん", *) 1 2 5 6 7
("Eさん", *) 1 2 3 4 5 6 7
;

に変更することで可能です。

勤務シフト表の作成 基礎(2)【GLPK】

最適化の条件1

最適化の条件2

最適化の条件3 (2021.10.13 追記)

最適化の条件4 (2021.10.13 プログラム変更)

おまけ (2021.10.13 追記)

勤務シフト表の作成基礎(2)【GLPK】