勤務シフト表の作成3【GLPK】(多店舗の勤務シフト表)

<--目次へ

某質問掲示板の質問をもとに多店舗で使える勤務シフト表の作成プログラムを作ってみました。

シフトの条件

• 複数の店舗で従業員のやりくりをする（ただし同時には2店舗以上はダメ）
• 優先配属店舗を設定（店舗ごとペナルティを設定）
• 各従業員の勤務コマ数の下限と上限を設定
• 従業員ごとに出勤と休みを設定。出勤可能は休み設定しない事で実現
• 連続勤務の日数を制限できる(4日を上限としているが従業員ごとに設定可能)
• 同じ日に複数店舗を掛け持ちすることを抑制(掛け持ちのペナルティ)
• 職階で最低必要な人数を設定(ここでは店舗に社員が1人以上)
• 1週間程度の期間を想定しているが特に制限はありません。出勤、休暇などの日付は日番号(1からの整数)にしてますが、日付か曜日の方が良いのかな？？　曜日だと1週間を超えると表現しにくいし。リクエストがあれば変更方法を追記します。

まだ大事なものが抜けているよな

##使い方
プログラムとデータを分けてあります。
慣れない方は、プログラムの後にデータを結合して1つのファイルにして、GLPKで実行してみてください。

GLPKの使い方などは上の「目次」を辿ってみてください。

データ変更だけで広範囲に対応できるはずです。
コメントに従って設定してみてください。
「データセクションの書き方」も参考に。またGLPKに同梱されているgmpl.pdfの「5 Model data」に詳しく書かれています.

もし答えが返ってこない場合は、「結果が得られないときには」を参考に。そこにも書いていますが、収束しない場合は--tmlimオプションを追加する必要あるかもしれません。

(2018.7.5追記)
「タブ区切り出力」はその部分を画面上でコピーし、エクセルの表部分にペーストできます。
「FixWorkScheduleWithShopNameの設定用」は、データ部分の
set FixWorkScheduleWithShopName :=
の下にコピペすることで、その部分のスケジュールを固定できます。

感想

ある程度機能を詰め込めば汎用的なシフト作成プログラムになるのかなと思って作ってみましたが、意外と複雑なので個別に作るしかないような気がしてきました。

ここのソフトはご自由にお使いください。改変もご自由に。
ツッコミや質問は大いに歓迎いたします。

###プログラム

(2018.7.5変更) version 0.1 -> 0.2

• 104行目 s.t. workingShop2〜をコメントに
• 107,108行目 s.t. workingMultiShop2〜をコメントに
  or演算を103,104行目で、合計が2以上の判断を　105〜108行目で行なっております。それぞれ制約式のペアになっていますが、minimizeの影響で片方の制約式は不要ですので削除しました。この変更により10.7秒->2.5秒に高速化しました。（もう1式くらいは削除できるかも）
  上の目次からたっどて「整数計画法での定式化」で若干触れています。
• ミススペルの修正 Calender -> Calendar に変更 (khskさんご指摘ありがとございます)
  データ部分にも変更がありますのでそちらも注意してください。

shift31.mod

# version 0.2
# シフト表作成 複数店舗
set DayOfWeek; # 曜日を読み込む
set TimeSlot;  # シフトの時間帯を読み込む
set Shop;  # 店舗名を読み込む
param requireNStaffsByDayOfWeek{DayOfWeek, TimeSlot, Shop} default 0; # 店舗の必要従業員数を読み込む
set Staff dimen 2;    # 従業員名と職階を読み込み
set StaffName :=  setof{(n,e) in Staff}(n); # 従業員名を取り出す
set JobClass := setof{(n,e) in Staff}(e); # 職階を取り出す

set Calendar dimen 3; # カレンダーを読み込む
param shopPenalty{StaffName, Shop} default 0 ; # 店舗へ配属のペナルティを読み込む
param mutilShopPenalty{StaffName}; # 同じ日に2店舗へ配属される場合のペナルティを読み込む
param continuousWorkDaysBeforeFirstDay{StaffName} default 0; # シフト初日までの連続勤務日数を読み込む
set FixWorkSchedule dimen 3;  # 従業員が従事する時間帯を読み込む(店舗は指定しない)
set FixWorkScheduleWithShopName dimen 4;  # 従業員が従事する時間帯を読み込む(店舗指定あり)
set FixOffDuty dimen 3; # 従業員が休暇申請する時間帯を読み込む
param upperLimitOfContnuosWork{StaffName}; # 連続勤務日数の上限
param largeNumber := 10000; # 勤務時間上限の制限を受けない大きな数
param upperLimitOfWorkingSlot{StaffName} integer, default largeNumber; # 従業員別の勤務時間帯数の上限を読み込む
param lowerLimitOfWorkingSlot{StaffName} integer, default 0; # 従業員別の勤務時間帯数の下限を読み込む
set WorkSlot := {(i,d,w) in Calendar, t in TimeSlot, s in Shop : requireNStaffsByDayOfWeek[w,t,s]>0}; # 各店舗別の営業時間帯
set OpenDayEachShop:=setof{(i,d,w,t,s) in WorkSlot}(i,d,w,s); # 店舗ごとの営業日
set TimeSlotOfAnyShopOpen := setof{(i,d,w,t,s) in WorkSlot}(i,d,w,t); # どこかの店舗が営業している時間帯

param requireNStaffs{(i,d,w,t,s) in WorkSlot} := requireNStaffsByDayOfWeek[w,t,s]; # 店舗の営業に必要な従業員数を読み込む
param minRequireNJobClass{JobClass} integer, >=0, default 0; # 店舗あたりの職級別のデフォルトの必要人数を読み込む

param minRequireNJobClassInShop{(i,d,w,t,s) in WorkSlot, e in JobClass} integer,  >=0, default minRequireNJobClass[e]; # 店舗ごとの職級別必要人数
set EffectiveDuty := setof{(n,i,t,s) in FixWorkScheduleWithShopName}(n,i,t) union FixWorkSchedule; # 従業員の有効な出勤時間帯を求める
set EffectiveOffDuty := FixOffDuty diff EffectiveDuty; # 従業員の有効な休暇時間帯を求める

printf "入力された設定値を出力\n";
printf "店舗ごとの必要従業員数\n";
for{s in Shop}{
  printf "%s\n", s;
  for{(i,d,w) in Calendar}{
    printf "%s %s %s ", i, d, w;
    printf{t in TimeSlot}"\t%s" & (if requireNStaffsByDayOfWeek[w,t,s]>0 then " %d人" else " -"),t, requireNStaffsByDayOfWeek[w,t,s];
    printf "\n";
  }
}
printf "合計\n";
for{(i,d,w) in Calendar}{
  printf "%s %s %s ", i, d, w;
  printf{t in TimeSlot}"\t%s" & (if sum{s in Shop}requireNStaffsByDayOfWeek[w,t,s]>0 then " %d人" else " -"),t, sum{s in Shop}requireNStaffsByDayOfWeek[w,t,s];
  printf "\n";
}

printf "\n従業員の勤務・休暇申請状況\n";
printf "           カッコ内はシフト初日までの連続勤務日数\n";
for{(n,e) in Staff}{
  printf "%s  %s" & (if continuousWorkDaysBeforeFirstDay[n]!=0 then "  (%d日)\n" else "\n"), n,e,continuousWorkDaysBeforeFirstDay[n];
  for{(i,d,w,t) in TimeSlotOfAnyShopOpen}{
    printf{(n,i,t,s) in FixWorkScheduleWithShopName} "  %s %s(%s) %s %s\n", i, d, w, t, s;
    printf (if (n,i,t) in FixWorkSchedule then "  %s %s(%s) %s 出\n" else ""), i, d, w, t;
    printf (if (n,i,t) in EffectiveOffDuty then "  %s %s(%s) %s 休\n" else ""), i, d, w, t;
  }
  printf"\n";
}

printf "\n日別の出勤申請状況\n";
for{(i,d,w) in Calendar,t in TimeSlot : sum{s in Shop}requireNStaffsByDayOfWeek[w,t,s]>0}{
  printf "%s  %s  %s  %s   ", i, d, w, t;
  printf "%d / %d\n", card({n in StaffName : (n,i,t) in EffectiveDuty}), sum{s in Shop}requireNStaffsByDayOfWeek[w,t,s];
  printf{n in StaffName : (n,i,t) in EffectiveDuty} "  %s",n;
  printf "\n";
}
# ここまで設定値を出力

# シフトを割り振る変数出勤の割り当ては>=1が入る
# 休暇申請があれば<=0に
var assignShiftSchedule{(i,d,w,t,s) in WorkSlot, (n,e) in Staff} binary, 
        <= if (n,i,t) in EffectiveOffDuty then 0 else 1,
        >= if (n,i,t,s) in FixWorkScheduleWithShopName then 1 else 0;
# 勤務した日を示す変数 完全休みは0, 出勤は1
var dutyDay{Calendar, Staff} binary;
# その日に仕事をした店
var workingShopInTheDay{(i,d,w,s) in OpenDayEachShop, (n,e) in Staff} binary;
var workingMultiShopInTheDay{Calendar, (n,e) in Staff} binary;

# 同時に1店舗しか従事できない
s.t. oneShop{(i,d,w,t) in TimeSlotOfAnyShopOpen, (n,e) in Staff}: sum{(i,d,w,t,s) in WorkSlot}assignShiftSchedule[i,d,w,t,s,n,e]<=1;
# 職級別に最低必要人数を確保
s.t. regularEmployee{(i,d,w,t,s) in WorkSlot, e in JobClass : minRequireNJobClassInShop[i,d,w,t,s,e]>0}: sum{(n,e) in Staff}assignShiftSchedule[i,d,w,t,s,n,e]>=minRequireNJobClassInShop[i,d,w,t,s,e];
# 店舗の人数を確保
s.t. requireStaff{(i,d,w,t,s) in WorkSlot}: sum{(n,e) in Staff}assignShiftSchedule[i,d,w,t,s,n,e]==requireNStaffs[i,d,w,t,s];
# 出勤は設定した範囲内に
s.t. maxWorkSlot{(n,e) in Staff : upperLimitOfWorkingSlot[n]<largeNumber}:
  sum{(i,d,w,t,s) in WorkSlot}assignShiftSchedule[i,d,w,t,s,n,e]<=upperLimitOfWorkingSlot[n];
s.t. minWorkSlot{(n,e) in Staff : lowerLimitOfWorkingSlot[n]>0}:
  sum{(i,d,w,t,s) in WorkSlot}assignShiftSchedule[i,d,w,t,s,n,e]>=lowerLimitOfWorkingSlot[n];
# 出勤希望日を反映する
s.t. fix1{(n,i,t) in FixWorkSchedule, (n,e) in Staff}: sum{(i,d,w,t,s) in WorkSlot}assignShiftSchedule[i,d,w,t,s,n,e]==1;
# 勤務した日単位で調べる
s.t. dutyDate1{(n,e) in Staff, (i,d,w,t,s) in WorkSlot}: assignShiftSchedule[i,d,w,t,s,n,e]<=dutyDay[i,d,w,n,e];
s.t. dutyDate2{(n,e) in Staff, (i,d,w) in Calendar}: sum{(i,d,w,t,s) in WorkSlot}assignShiftSchedule[i,d,w,t,s,n,e]>=dutyDay[i,d,w,n,e];
# 最大連続勤務 upperLimitOfContnuosWork日以下に
s.t. maxContinuousWork1{(n,e) in Staff , j in 1..(card(Calendar)-upperLimitOfContnuosWork[n])}: sum{i1 in j..(j+upperLimitOfContnuosWork[n]), (i1,d1,w1) in Calendar}dutyDay[i1,d1,w1,n,e]<=upperLimitOfContnuosWork[n]; 
# シフト開始日までの連続勤務を処理
s.t. maxContinuousWork2{(n,e) in Staff, j in 1..continuousWorkDaysBeforeFirstDay[n]}: sum{i1 in 1..(upperLimitOfContnuosWork[n]-j+1), (i1,d1,w1) in Calendar}dutyDay[i1,d1,w1,n,e]<=upperLimitOfContnuosWork[n]-j;

s.t. workingShop1{(i,d,w,t,s) in WorkSlot, (n,e) in Staff}: assignShiftSchedule[i,d,w,t,s,n,e]<=workingShopInTheDay[i,d,w,s,n,e];
# s.t. workingShop2{(i,d,w,s) in OpenDayEachShop, (n,e) in Staff}: sum{t in TimeSlot:(i,d,w,t,s) in WorkSlot}assignShiftSchedule[i,d,w,t,s,n,e]>=workingShopInTheDay[i,d,w,s,n,e];
s.t. workingMultiShop1{(i,d,w) in Calendar, (n,e) in Staff}:
  sum{s in Shop : (i,d,w,s) in OpenDayEachShop}workingShopInTheDay[i,d,w,s,n,e]-1<=card(Shop)*workingMultiShopInTheDay[i,d,w,n,e];
# s.t. workingMultiShop2{(i,d,w) in Calendar, (n,e) in Staff}:
#  sum{s in Shop : (i,d,w,s) in OpenDayEachShop}workingShopInTheDay[i,d,w,s,n,e]>=2*workingMultiShopInTheDay[i,d,w,n,e];

minimize petanly: sum{(n,e) in Staff, (i,d,w,t,s) in WorkSlot : shopPenalty[n,s]!=0}assignShiftSchedule[i,d,w,t,s,n,e]*shopPenalty[n,s]+
    sum{(i,d,w) in Calendar, (n,e) in Staff : mutilShopPenalty[n]>0}workingMultiShopInTheDay[i,d,w,n,e]*mutilShopPenalty[n];

solve;
# 出力
printf "\n日別の勤務シフト\n";
for{(i,d,w) in Calendar}{
  printf "%s  %s(%s)\n", i,d,w;
  for{s in Shop, (i,d,w,t,s) in WorkSlot}{
    printf "  %s  %s  ", s, t;
    printf{(n,e) in Staff : assignShiftSchedule[i,d,w,t,s,n,e]==1} " %s", n;
    printf "\n";
  }
}
printf "\n従業員別のシフト\n";
for{(n,e) in Staff}{
  printf "%s (%d)\n", n, sum{(i,d,w,t,s) in WorkSlot}assignShiftSchedule[i,d,w,t,s,n,e];
  for{(i,d,w) in Calendar}{
    printf "%s   %s(%s)", i, d, w;
    printf{t in TimeSlot, s in Shop : (i,d,w,t,s) in WorkSlot and assignShiftSchedule[i,d,w,t,s,n,e]==1} "\t%s %s", t, s;
    printf (if dutyDay[i,d,w,n,e]==0 then "\t休\n" else "\n");
  }
}

printf "タブ区切り出力(エクセルへの取り込み用)\n";
printf{(i,d,w) in Calendar, t in TimeSlot}"\t%s%s",d,t;
printf "\n";
for{(n,e) in Staff}{
  printf "%s", n;
  for{(i,d,w) in Calendar, t in TimeSlot}{
    printf{s in Shop : (i,d,w,t,s) in WorkSlot and assignShiftSchedule[i,d,w,t,s,n,e]==1} "\t%s",s;
    printf (if sum{s in Shop:(i,d,w,t,s) in WorkSlot}assignShiftSchedule[i,d,w,t,s,n,e]==0 then "\t-" else "");
  }
  printf "\n";
}

printf "\nFixWorkScheduleWithShopNameの設定用\n";
for{(i,d,w) in Calendar, t in TimeSlot}{
  printf{(n,e) in Staff, (i,d,w,t,s) in WorkSlot : assignShiftSchedule[i,d,w,t,s,n,e]==1} "('%s', %s, '%s', '%s')\n", n, i, t, s;
}

####データ
(2018.7.5変更)

• 81行目 ミススペルの修正 Calender -> Calendar に変更

data31

data;
set DayOfWeek := "日" "月" "火" "水" "木" "金" "土" "祝"; # 曜日
set TimeSlot := AM PM; # シフトの時間帯
set Shop := "A店" "B店" "C店"; # 店舗名

# 曜日別の必要な従業数 0人の場合は休業
param requireNStaffsByDayOfWeek:=
[*,*,"A店"](tr):
      "日" "月" "火" "水" "木" "金" "土" "祝" :=
  AM    0    5    5    5    0    5    5    5
  PM    0    4    4    4    0    4    0    0
[*,*,"B店"](tr):
      "日" "月" "火" "水" "木" "金" "土" "祝" :=
  AM    4    5    5    5    5    0    5    0
  PM    0    4    3    3    4    0    3    0
[*,*,"C店"](tr):
      "日" "月" "火" "水" "木" "金" "土" "祝" :=
  AM    4    5    5    5    5    5    4    4
  PM    0    4    4    4    4    4    4    4
;
# 従業員名と職階
set Staff :=
(*, "社員") "Aさん" "Bさん" "Cさん" "Dさん" "Eさん" "Fさん"
(*, "パート")  "Gさん" "Hさん" "Iさん" "Jさん" "Kさん" "Lさん"
(*, "パート")  "Mさん" "Nさん" "Oさん" "Pさん" "Qさん" "Rさん"
(*, "アルバイト")  "Sさん" "Tさん" "Uさん"
;
# 店舗に最低限必要な職階の人数 defaultは0人
param minRequireNJobClass["社員"]:=1; # 社員は1人以上

# 店舗へ配属のペナルティ 値が大きいほど避ける 整数
# 0以外は同じ数値が並ぶのではなく、バラバラの方が早く収束する傾向がある
param shopPenalty :=
 [*,*] :  "A店"   "B店"   "C店" :=
"Aさん"     0      10       5
"Bさん"     0      10       5
"Cさん"    10       0       5
"Dさん"    10       0       5
"Eさん"    10      10       0
"Fさん"    10      10       0
"Gさん"     0      25      21
"Hさん"     0      25      22
"Iさん"     0      25      21
"Jさん"     0      25      22
"Kさん"    25      21       0
"Lさん"    25      21       0
"Mさん"    25      21       0
"Nさん"    25       0      21
"Oさん"    25       0      22
"Pさん"    25       0      20
"Qさん"     0      25      24
"Rさん"    25      25       0
;
# 同じ日に2店舗以上に勤務した時のペナルティ
param mutilShopPenalty default 30 :=
"Aさん" 0 "Bさん" 0 "Cさん" 0 "Dさん" 0 "Eさん" 0 "Fさん" 0 # 社員は0
;

# 連続勤務日数の上限
param upperLimitOfContnuosWork default 4 :=
"Gさん" 7 "Hさん" 7 "Iさん" 7 "Jさん" 7 "Kさん" 7 "Lさん" 7
"Mさん" 7 "Nさん" 7 "Oさん" 7 "Pさん" 7 "Qさん" 7 "Rさん" 7
;

# 期間中の勤務コマ数の下限と上限
# defaultでは上限下限なし
param  : lowerLimitOfWorkingSlot  upperLimitOfWorkingSlot :=
"Aさん"    8    8
"Bさん"   10   10
"Cさん"   10   10
"Dさん"   10   10
"Eさん"   10   10
"Fさん"   10   10
"Sさん"    0    8
"Tさん"    0    8
"Uさん"    0    8
;
# カレンダー
# 日番号、日付、曜日 最初のカラムの日番号は1からの連続した数値
# 曜日は上の店舗ごとの人数設定を反映
set Calendar:=
1  7-29 "日"
2  7-30 "月"
3  7-31 "火"
4  8-1  "水"
5  8-2  "木"
6  8-3  "金"
7  8-4  "土"
;
# 従業員のシフト初日以前の連続勤務日数
param continuousWorkDaysBeforeFirstDay :=
"Aさん"   2
"Bさん"   3
"Cさん"   0
"Dさん"   4
"Eさん"   1
"Fさん"   3
"Sさん"   1
"Tさん"   2
"Uさん"   3
;
# 従業員の出勤申請 出勤が割り当てられる
# 氏名、日番号、時間帯
set FixWorkSchedule :=
("Gさん", *, *) 2 AM 3 AM 4 AM 6 AM
# 次の様な書き方もできます
#                      日 月 火 水 木 金 土
("Hさん", *, *) (tr)  : 1  2  3  4  5  6  7 :=
                    AM  -  +  +  +  -  +  +
                    PM  -  +  -  +  -  +  -
("Iさん", *, *) (tr)  : 1  2  3  4  5  6  7 :=
                    AM  -  +  -  +  -  +  +
                    PM  -  -  -  -  -  -  -
("Jさん", *, *) 2 PM 3 PM 4 PM 5 PM 6 PM # 5連続になっている
("Kさん", *, *) 2 AM 3 AM 4 AM 5 AM 6 AM # 5連続になっている
("Lさん", *, *) 2 AM 2 PM 3 AM 5 AM

("Mさん", *, *) 3 AM 3 PM 4 PM 5 PM 6 AM
#                      日 月 火 水 木 金 土
("Nさん", *, *) (tr)  : 1  2  3  4  5  6  7 :=
                    AM  -  +  +  +  -  -  +
                    PM  -  +  +  +  -  -  +
("Oさん", *, *) (tr)  : 1  2  3  4  5  6  7 :=
                    AM  +  +  -  +  +  -  +
                    PM  -  +  -  +  +  -  -
("Pさん", *, *) 1 AM 2 PM 4 AM 5 AM 5 PM 7 PM
("Qさん", *, *) 4 AM 5 AM
("Rさん", *, *) (tr)  : 1  2  3  4  5  6  7 :=
                    AM  +  +  +  -  +  -  -
                    PM  -  -  -  -  -  +  -
;
# 店舗を指定した出勤時間帯
# 氏名、日番号、時間帯、店舗名
# 上のFixWorkScheduleと重なっていても問題ありません
set FixWorkScheduleWithShopName :=
;
# 従業員の休暇申請
# ここに指定されていない時間帯は割り当てられる可能性がある
# 氏名、日番号、時間帯
# 上の出勤(FixWorkScheduleまたはFixWorkScheduleWithShopName)指定されると休暇は無視されます
# 従って全期間を休暇とすると出勤以外の勤務を割り当てられません
set FixOffDuty :=
("Hさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Iさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Jさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Kさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Lさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Mさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Nさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Oさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Pさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Qさん", *, *) 1 AM 1 PM 2 AM 2 PM 3 AM 3 PM 4 AM 4 PM 5 AM 5 PM 6 AM 6 PM 7 AM 7 PM
("Rさん", *, *) (tr)  : 1  2  3  4  5  6  7 :=
                    AM  +  +  +  +  +  +  +
                    PM  +  +  +  +  +  +  +
("Aさん", *, *) 2 AM 2 PM # 年休
;