Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@ki073

勤務シフト表の作成2【GLPK】

Last updated at Posted at 2017-12-20

<--目次へ

(2017.12.30追記)シフトの条件が抜けていましたので追記しました

2日連続して勤務する場合の勤務シフト

24時間勤務などで2日連続する勤務の場合のシフトを作成してみました。

###シフトの条件
*シフト作成期間は28日間
*従業員は3人
*2日連続勤務 初日は「泊」、次の日は「明」
*希望休日、希望勤務シフトを設定できる
*避けたい勤務シフトを設定できる(希望勤務シフトが複数のうち1つの場合に使う)
*5日を超える連続勤務はない
*休日数が偏らないように上限と下限を設定できる
*休日数は個人単位でも設定できる
*毎日「泊」が1人、「明」が1人
*「泊」「明」の人数を日単位でも設定できる

次のように、必ず「泊」の翌日が「明」になる条件を設定しています。
s.t. restrictShiftPatten1{s in Staff, d in firstDate..endDate-1}: assignSchedule[d,s,"泊"]==assignSchedule[d+1,s,"明"];
このような制約式で"泊"の翌日は"明"になります。また逆に"明"の前日は"泊"になります。

書き方などはGLPKによる勤務シフト表の作成1から順番に説明部分を読まれると参考になると思います。特にデータセクションの効率的な書き方がありますので。

shift5.model
# version 0.21
# シフト表作成
param firstDate; # 期間の最初の日付を読み込む
param endDate;   # 最後の日付を読み込む
set Date := firstDate..endDate; # 期間内の日付
set TimeSlot := {"泊", "明", "休"}; # シフト枠
set Staff; # スタッフ名を読み込む
set FixSchedule, dimen 3; # 希望する勤務シフトを読み込む
set AvoidSchedule, dimen 3; # 避ける勤務シフトを読み込む
param defaultMinOffDays; # スタッフの標準的な最低休日数を読み込む
param defaultMaxOffDays; # スタッフの標準的な最高休日数を読み込む
param defaultNStaffsOfAllDay; # 標準的な泊の人数を読み込む
param minOffDays{Staff} integer, default defaultMinOffDays; # 各スタッフの最低休日数
param maxOffDays{Staff} integer, default defaultMaxOffDays; # 各スタッフの最高休日数
param nStaffsOfAllDayStart{Date} integer, default defaultNStaffsOfAllDay; # 各日の泊の人数
param nStaffsOfAllDayEnd{Date} integer, default defaultNStaffsOfAllDay;   # 各日の明の人数

# 希望するシフト、避けるシフトを出力
printf "シフトの希望\n";
for{d in Date}{
    printf "%s  ", d;
    printf{s in Staff, t in TimeSlot : (d,s,t) in FixSchedule} "%s:%s ", s, t;
    printf{s in Staff, t in TimeSlot : (d,s,t) in AvoidSchedule} "%sx%s ", s, t;
    printf "\n";
}

# シフトを割り当てるための変数
var assignSchedule{d in Date, s in Staff, t in TimeSlot} binary,
   >= if (d,s,t) in FixSchedule then 1 else 0, # シフトを固定する場合には>=1に
   <= if (d,s,t) in AvoidSchedule then 0 else 1; # 避ける場合には<=0に制限

# 勤務形態を1つ設定
s.t. uniqueTimeSlot{d in Date, s in Staff}: sum{t in TimeSlot}assignSchedule[d,s,t]==1;
s.t. obteinStaff1{d in Date}: sum{s in Staff}assignSchedule[d,s,"泊"]==nStaffsOfAllDayStart[d]; # 泊の人数
s.t. obteinStaff2{d in Date}: sum{s in Staff}assignSchedule[d,s,"明"]==nStaffsOfAllDayEnd[d]; # 明の人数
# 各スタッフの休日数を範囲内に
s.t. restrictOffDuty1{s in Staff}: sum{d in Date}assignSchedule[d,s,"休"]>=minOffDays[s];
s.t. restrictOffDuty2{s in Staff}: sum{d in Date}assignSchedule[d,s,"休"]<=maxOffDays[s];
# 連続勤務は5日以下(連続した6日間で休が1つ以上)
s.t. keepOffDay{s in Staff, d in firstDate..endDate-5}: sum{d6 in d..d+5}assignSchedule[d6,s,"休"]>=1;
# 翌日のシフトの制限 泊の翌日は必ず明, 逆に明の前日は泊
s.t. restrictShiftPatten1{s in Staff, d in firstDate..endDate-1}: assignSchedule[d,s,"泊"]==assignSchedule[d+1,s,"明"];

solve;

# 結果を出力
printf "\nシフト表\n";
for{s in Staff}{
    printf "%s  ", s;
    printf{d in Date, t in TimeSlot : assignSchedule[d,s,t]==1} "%s ", t;
    printf "\n";
}
# 各人のシフト集計
printf "\n集計\n";
for{s in Staff}{
    printf "%-10s ", s;
    printf{t in TimeSlot} "  %s %d", t, sum{d in Date}assignSchedule[d,s,t];
    printf "\n";
}
# 画面からのExcelへのコピペ用
printf "\n\nTab区切り出力\n";
for{s in Staff}{
    printf "%s ", s;
    printf{d in Date, t in TimeSlot : assignSchedule[d,s,t]==1} "\t%s", t;
    printf "\n";
}

今回はデータを分けています。使い方が慣れないうちは1つのファイルに合体した方が良いかも知れません。

shift5.data
data;
# 期間の最初の日付と最後の日付
param firstDate:=1; 
param endDate  :=28;
# 標準的な最低休日数,標準的な最高休日数,標準的な泊の人数
param defaultMinOffDays := 8;
param defaultMaxOffDays := 12;
param defaultNStaffsOfAllDay := 1;
# スタッフ名
set Staff := "01さん" "02さん" "03さん"
;
# スタッフの希望
set FixSchedule :=
(*,"02さん","明") 9
(*,"02さん","休") 1 10
(*,"03さん","休") 5
;
# 避けたいシフト
set AvoidSchedule :=
;
end;

標準的な設定をデータセクションでしています。例えば3日の泊の人数と翌日(4日)の明の人数を0にした時には
param nStaffsOfAllDayStart[3]:=0;
param nStaffsOfAllDayEnd[4]:=0;
をデータセクションに追加することで、標準以外の値に設定できます。

避けたいシフトの設定は
set AvoidSchedule :=
と
;
の間に
(*,"03さん","休") 2
のように避けたいシフトを追加できます。

実際に動かしてみて
「PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION」
と表示が出て止まってしまった場合には、全ての条件を満たすことができないことを示しています。「スタッフの希望」などを少し削ってみたり、条件を緩めてみてください。

日勤を追加

###追加条件
*日勤が毎日1人で、その翌日は必ず休み
*従業員数や「泊」「明」の日々の人数は増やしています

ここでは日勤の翌日は必ず休みになるように制約条件を追加します（しかし休みの前日は日勤とは限りません）。泊と明の関係のように==でダメで、
s.t. setPatten2{s in Staff, d in firstDate..endDate-1}: assignSchedule[d,s,"日"]<=assignSchedule[d+1,s,"休"];
のように不等号になっています。"日"の翌日は必ず"休"になりますが、"休"の前日は"日"とは限らない制約条件になっています。

また、"日"の前日は必ず"明"であるが、"明"の翌日は"日"とは限らなので、同じよに不等号を使った制約式になっています。

shift6.model
# version 0.22
# シフト表作成
param firstDate; # 期間の最初の日付を読み込む
param endDate;   # 最後の日付を読み込む
set Date := firstDate..endDate; # 期間内の日付
set TimeSlot := {"泊", "明", "日", "休"}; # シフト枠　日を追加
set Staff; # スタッフ名を読み込む
set FixSchedule, dimen 3; # 希望する勤務シフトを読み込む
set AvoidSchedule, dimen 3; # 避ける勤務シフトを読み込む
param defaultMinOffDays; # スタッフの標準的な最低休日数を読み込む
param defaultMaxOffDays; # スタッフの標準的な最高休日数を読み込む
param defaultNStaffsOfAllDay; # 標準的な泊の人数を読み込む
param minOffDays{Staff} integer, default defaultMinOffDays; # 各スタッフの最低休日数
param maxOffDays{Staff} integer, default defaultMaxOffDays; # 各スタッフの最高休日数
param nStaffsOfAllDayStart{Date} integer, default defaultNStaffsOfAllDay; # 各日の泊の人数
param nStaffsOfAllDayEnd{Date} integer, default defaultNStaffsOfAllDay;   # 各日の明の人数
# 追加
param defaultMinDayShift; # 標準的なスタッフの最低日勤数を読み込む
param defaultMaxDayShift; # 標準的なスタッフの最高日勤数を読み込む
param defaultNStaffsOfDayShift; # 標準的な日勤人数を読み込む
param minDayShift{Staff} integer, default defaultMinDayShift; # 各スタッフの最低日勤数
param maxDayShift{Staff} integer, default defaultMaxDayShift; # 各スタッフの最高日勤数
param nStaffsOfDayShift{Date} integer, default 1; # 日勤の人数
#
# 希望するシフト、避けるシフトを出力
printf "シフトの希望\n";
for{d in Date}{
    printf "%s  ", d;
    printf{s in Staff, t in TimeSlot : (d,s,t) in FixSchedule} "%s:%s ", s, t;
    printf{s in Staff, t in TimeSlot : (d,s,t) in AvoidSchedule} "%sx%s ", s, t;
    printf "\n";
}

# シフトを割り当てるための変数
var assignSchedule{d in Date, s in Staff, t in TimeSlot} binary,
   >= if (d,s,t) in FixSchedule then 1 else 0, # シフトを固定する場合には>=1に
   <= if (d,s,t) in AvoidSchedule then 0 else 1; # 避ける場合には<=0に制限

# 勤務形態を1つ設定
s.t. uniqueTimeSlot{d in Date, s in Staff}: sum{t in TimeSlot}assignSchedule[d,s,t]==1;
s.t. obteinStaff1{d in Date}: sum{s in Staff}assignSchedule[d,s,"泊"]==nStaffsOfAllDayStart[d]; # 泊の人数
s.t. obteinStaff2{d in Date}: sum{s in Staff}assignSchedule[d,s,"明"]==nStaffsOfAllDayEnd[d]; # 明の人数
# 各スタッフの休日数を範囲内に
s.t. restrictOffDuty1{s in Staff}: sum{d in Date}assignSchedule[d,s,"休"]>=minOffDays[s];
s.t. restrictOffDuty2{s in Staff}: sum{d in Date}assignSchedule[d,s,"休"]<=maxOffDays[s];
# 連続勤務は5日以下(連続した6日間で休が1つ以上)
s.t. keepOffDay{s in Staff, d in firstDate..endDate-5}: sum{d6 in d..d+5}assignSchedule[d6,s,"休"]>=1;
# 翌日のシフトの制限 泊の翌日は必ず明, 逆に明の前日は泊
s.t. restrictShiftPatten1{s in Staff, d in firstDate..endDate-1}: assignSchedule[d,s,"泊"]==assignSchedule[d+1,s,"明"];

# 追加
s.t. obteinStaff3{d in Date}: sum{s in Staff}assignSchedule[d,s,"日"]==nStaffsOfDayShift[d]; # 日の人数
# 各スタッフの日勤数を範囲内に
s.t. restricDayShift1{s in Staff}: sum{d in Date}assignSchedule[d,s,"日"]>=minDayShift[s];
s.t. restricDayShift2{s in Staff}: sum{d in Date}assignSchedule[d,s,"日"]<=maxDayShift[s];
# 日の翌日は必ず休
s.t. setPatten2{s in Staff, d in firstDate..endDate-1}: assignSchedule[d,s,"日"]<=assignSchedule[d+1,s,"休"];
# 日の前日は必ず明
s.t. setPatten3{s in Staff, d in firstDate..endDate-1}: assignSchedule[d,s,"明"]>=assignSchedule[d+1,s,"日"];
#
solve;

# 結果を出力
printf "\nシフト表\n";
for{s in Staff}{
    printf "%s  ", s;
    printf{d in Date, t in TimeSlot : assignSchedule[d,s,t]==1} "%s ", t;
    printf "\n";
}
# 各人のシフト集計
printf "\n集計\n";
for{s in Staff}{
    printf "%-10s ", s;
    printf{t in TimeSlot} "  %s %d", t, sum{d in Date}assignSchedule[d,s,t];
    printf "\n";
}
# 画面からのExcelへのコピペ用
printf "\n\nTab区切り出力\n";
for{s in Staff}{
    printf "%s ", s;
    printf{d in Date, t in TimeSlot : assignSchedule[d,s,t]==1} "\t%s", t;
    printf "\n";
}
shift6.data
data;
# 期間の最初の日付と最後の日付
param firstDate:=1; 
param endDate  :=28;
# 標準的な最低休日数,標準的な最高休日数,標準的な泊の人数
param defaultMinOffDays := 8;
param defaultMaxOffDays := 12;
param defaultNStaffsOfAllDay := 2;
# 追加
# 標準的な最低日勤数,標準的な最高日勤数,標準的な日勤数
param defaultMinDayShift := 3;
param defaultMaxDayShift := 4;
param defaultNStaffsOfDayShift := 1;
#
# スタッフ名
set Staff := "あ" "い" "う" "え" "お" "か" "き" "く"
;
# スタッフの希望を入力
set FixSchedule :=
(*,"あ","明") 16
(*,"あ","休") 24 25 26
(*,"い","明") 10 12
(*,"い","休") 13 14 15 16 17
(*,"う","明") 
(*,"う","休") 2 28
(*,"え","明") 2
(*,"え","休") 18 19 20 28
(*,"か","休") 1 10 19 20
(*,"き","明") 2
(*,"き","休") 3 7 8 9 10
(*,"く","明") 18 23
;
# 避けたいシフト
set AvoidSchedule :=
;
end;

実際に動かしていると休みの偏っているのが気になります。次にこれを軽減してみます。

長い休みを減らしたい

これまで書いたshft5.modelとshft6.modelは3連休以上の長い休みがたくさんできてしまいます。2連休くらいまでにしてそれ以上を減らす方法を考えてみます。
制約条件では長い希望休がある場合にはそれを回避しないとうまくいきません。

休みの連続を検出

隣り合う休日を示すバイナリ変数x1とx2が両方とも1の場合に連休となります。論理積x1x2で検出できますが、整数計画法では変数の積を取ることができません。加算か減算だけです。
この場合には、バイナリ変数yを用意して、x1+x2-1<=yとx1+x2>=2yの両式が成り立つときにはyが論理積になります。実際には連休検出は次のようになります。

shift7a.model
var twoConsecutive{firstDate..endDate-1, Staff} binary;
s.t. two_consecutive1{s in Staff, d in firstDate..endDate-1}:+1:
    sum{d1 in d..d+1}assignSchedule[d1,s,"休"]-1<=twoConsecutive[d,s];
s.t. two_consecutive2{s in Staff, d in firstDate..endDate-1}:
    sum{d1 in d..d+1}assignSchedule[d1,s,"休"]>=2*twoConsecutive[d,s];

休みが3連続の場合は

shift7b.model
var threeConsecutive{firstDate..endDate-2, Staff} binary;
s.t. three_consecutive1{s in Staff, d in firstDate..endDate-2}:
    sum{d1 in d..d+2}assignSchedule[d1,s,"休"]-2<=threeConsecutive[d,s];
s.t. three_consecutive2{s in Staff, d in firstDate..endDate-2}:
    sum{d1 in d..d+2}assignSchedule[d1,s,"休"]>=3*threeConsecutive[d,s];

となります。隣り合う2連休や3連休の検出ですので、それよりも長い休みも同時に検出してしまいます。

三連休以上を減らすには

shift7b.modelのthreeConsecutiveは隣り合う3連休で1になりますので、threeConsecutiveの合計をminimizeする目的関数を追加することで達成できます。shft5.modelやshft6.modelのsolve;より前に以下を追加してみてください。

shift7c.model
var threeConsecutive{firstDate..endDate-2, Staff} binary;
s.t. three_consecutive1{s in Staff, d in firstDate..endDate-2}:
    sum{d1 in d..d+2}assignSchedule[d1,s,"休"]-2<=threeConsecutive[d,s];
minimize consecutive: sum{s in Staff, d in firstDate..endDate-2}threeConsecutive[d,s];

s.t. three_consecutive2〜がありませんが、minimizeで使う場合には省略できます。(理由は考えてみてください)

1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?