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

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

勤務時間帯を均等に

スッタフの勤務時間帯を均等にするには、勤務時間帯単位で上限を決めて、それ以下になるように制約条件を追加します。

param target_frequency{t in TimeSlot} := card({(d,t) in BusinessHour})/card(Staff); # 時間帯別の目標出勤回数
param limit_frequency{t in TimeSlot} := ceil(target_frequency[t]); # 切り上げた整数

s.t. limit_freq{t in TimeSlot, s in Staff}: sum{(d,t) in BusinessHour}assignShiftSchedule[d,t,s]<=limit_frequency[t];

例では朝、昼が3回、夜が2.5回を目標回数として、それを切り上げた値を上限として制限を加えています。

この方法は簡単なのですが、休みや出勤の指定が増えてくると条件を満たせない可能性が高くなってきます。s.t.で指定した制約条件全てを満たす必要があります。条件を満たせない時には
LP HAS NO PRIMAL FEASIBLE SOLUTION
と言うメッセージを出力して終了します。
条件を緩めるしかないのですが

次に違ったやり方を紹介します。
目標回数からの誤差の絶対値を最小化する方法です。追加分だけを示します。全体版は後に載せておきます。

param target_frequency{t in TimeSlot} := card({(d,t) in BusinessHour})/card(Staff); # 時間帯別の目標出勤回数

var absoluteValueOfDeviation{t in TimeSlot, s in Staff}>=0; # 目標出勤回数からの誤差の絶対値

# 目標出勤回数からの誤差の絶対値を計算して最小になるように最適化
s.t. abs_dev1{t in TimeSlot, s in Staff}: sum{(d,t) in BusinessHour}assignShiftSchedule[d,t,s]-target_frequency[t]<=absoluteValueOfDeviation[t,s];
s.t. abs_dev2{t in TimeSlot, s in Staff}: sum{(d,t) in BusinessHour}assignShiftSchedule[d,t,s]-target_frequency[t]>=-absoluteValueOfDeviation[t,s];
minimize sumOfAbsoluteValueOfDeviation: sum{t in TimeSlot, s in Staff}absoluteValueOfDeviation[t,s];

ゼロ以上に制限した変数absoluteValueOfDeviationを宣言して、2つのs.t.文とminimize文で絶対値の合計の最小値を求めることができます。よく読むと分かると思いますが、

「整数計画法」「定式化」で検索すると色々と出てきます。
少し高度になりますが
整数計画法による定式化入門
も参考になりそうです。

このシリーズは一旦ここで終了します。
質問や要望がありましたらコメント欄に書き込んでください。

改良版

shift4.model

# version 0.14
# シフト表作成
param firstDate; # 期間の最初の日付
param endDate;   # 最後の日付
set Date := firstDate..endDate; # 期間内の日付
set TimeSlot := {"朝", "夕", "夜"}; # シフト時間枠
set Staff; # スタッフ名
param maxWorkingDays{Staff}; # 各スタッフの最大勤務日数
set BusinessHour dimen 2; # 営業時間帯
set FixOnDuty dimen 3;    # 勤務時間帯
set FixOffDuty dimen 3;   # 非番時間帯

param target_frequency{t in TimeSlot} := card({(d,t) in BusinessHour})/card(Staff); # 時間帯別の目標出勤回数

# 日付,シフト時間枠,スタッフの配列を確保、出勤の割り当てで1が入る
var assignShiftSchedule{(d,t) in BusinessHour, s in Staff} binary, >= if (d,t,s) in FixOnDuty then 1 else 0, <= if (d,t,s) in FixOffDuty then 0 else 1;
var absoluteValueOfDeviation{t in TimeSlot, s in Staff}>=0; # 目標出勤回数からの誤差の絶対値

# シフト時間枠に必ず1人従事
s.t. keepStaffInTimeSlot{(d,t) in BusinessHour}: sum{s in Staff}assignShiftSchedule[d,t,s]==1;
# 出勤は1日1回以下
s.t. avoidShiftPatten1{s in Staff, d in Date}: sum{(d,t) in BusinessHour}
    assignShiftSchedule[d,t,s]<=1;
# 各スタッフの最大勤務日数で制限
s.t. restrictMaxWorkDays{s in Staff}: sum{(d,t) in BusinessHour}
    assignShiftSchedule[d,t,s]<=maxWorkingDays[s];
# 連続勤務は3日以下
s.t. keepOffDay{s in Staff, d in firstDate..endDate-3}: sum{t in TimeSlot, d4 in d..d+3 : (d4,t) in BusinessHour}
    assignShiftSchedule[d4,t,s]<=3;
# 翌日の勤務時間帯を制限
s.t. avoidShiftPatten2{s in Staff, d in firstDate..endDate-1}: sum{(d1, t) in {(d, "夕"), (d, "夜"), (d+1, "朝")} :(d1,t) in BusinessHour}
    assignShiftSchedule[d1,t,s]<=1;
s.t. avoidShiftPatten3{s in Staff, d in firstDate..endDate-1}: sum{(d1, t) in {(d, "夜"), (d+1, "朝"), (d+1, "夕")} :(d1,t) in BusinessHour}assignShiftSchedule[d1,t,s]<=1;
# 目標出勤回数からの誤差の絶対値を計算して最小になるように最適化
s.t. abs_dev1{t in TimeSlot, s in Staff}: sum{(d,t) in BusinessHour}assignShiftSchedule[d,t,s]-target_frequency[t]<=absoluteValueOfDeviation[t,s];
s.t. abs_dev2{t in TimeSlot, s in Staff}: sum{(d,t) in BusinessHour}assignShiftSchedule[d,t,s]-target_frequency[t]>=-absoluteValueOfDeviation[t,s];
minimize sumOfAbsoluteValueOfDeviation: sum{t in TimeSlot, s in Staff}absoluteValueOfDeviation[t,s];

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

data;
# 期間の最初の日付と最後の日付
param firstDate:=1; 
param endDate  :=13;
# スタッフ名と最大勤務日数
param : Staff : maxWorkingDays :=
"A"  9
"B"  9
"C"  9
"D"  9
;
# 営業時間帯
set BusinessHour :=
(1, *) "朝" "夕" "夜"
(2, *) "朝" "夕" "夜"
(3, *) "朝" "夕" "夜"
(4, *) "朝" "夕" "夜"
(5, *) "朝" "夕" "夜"
(6, *) "朝" "夕"
# 7日は休業
(8, *) "朝" "夕" "夜"
(9, *) "朝" "夕" "夜"
(10, *) "朝" "夕" "夜"
(11, *) "朝" "夕" "夜"
(12, *) "朝" "夕" "夜"
(13, *) "朝" "夕"
;
# スタッフが従事する時間帯を指定
set FixOnDuty :=
(1, "朝", "A")
(1, "夕", "B")
(1, "夜", "C")
;
# スタッフが出勤できない時間帯を指定
set FixOffDuty :=
(2, *, "A") "朝" "夕" "夜"
(3, *, "B") "朝" "夕" "夜"
;