ShiftSolver for GLPK

ShiftSolver for GLPK

• glpsol による医師拘束割り付けを作ってみました
  • ほとんど https://qiita.com/ki073/items/a8b26883e931e4bf6584 の丸写しです
  • data セクションのparamのみ30日分にしているが、他はcsvから読み込むように変更
• fixon.csv : 当直のように、絶対その日は拘束になる日を指定

Day,Doctor
1,"Doctor D"

• fixoff.csv : 各Doctorが休みたい日を指定

Day,Doctor
2,"Doctor A"
5,"Doctor A"
1,"Doctor C"

• doctor.csv : 各Doctorの名前を羅列

Name
"Doctor A"
"Doctor B"
"Doctor C"
"Doctor D"

• shiftsolver.mod

# 参考：https://qiita.com/ki073/items/a8b26883e931e4bf6584

param firstDate; # 期間の最初の日付
param endDate;   # 最後の日付
set Date := firstDate..endDate; # 期間内の日付
set Staff; # スタッフ名

table data IN "CSV" "doctor.csv" : Staff<-[Name];

set FixOnDuty dimen 2;    # 当直勤務表 = 絶対勤務
set FixOffDuty dimen 2;   # 休み希望表

table data IN "CSV" "fixon.csv" : FixOnDuty<-[Day,Doctor];     # 当直勤務表
table data IN "CSV" "fixoff.csv" : FixOffDuty<-[Day,Doctor];    # 休み希望表
param target_frequency := card({d in Date})/card(Staff);

# 連続拘束はできるだけ避ける
# 当直勤務日の翌日は避けた方がよい（連続拘束は避けるから自動的に満たされるが）

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

# 出勤は1日1回以下
s.t. keepStaffInDate{d in Date}: sum{s in Staff}assignShiftSchedule[d,s]==1;

# 連続勤務は1日以下=しない
s.t. keepOffDay{s in Staff, d in firstDate..endDate-1}: sum{d4 in d..d+1 : d4 in Date}
    assignShiftSchedule[d4,s]<=1;

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

solve;

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

data;
# 期間の最初の日付と最後の日付
param firstDate:=1; 
param endDate  :=30;
end;

• 使い方

  • glpsol -m shiftsolver.mod --tmlim 10
  • time limit 10secをつけないと、延々おわらないから

• 実行例

GLPSOL--GLPK LP/MIP Solver 5.0
Parameter(s) specified in the command line:
 -m shiftsolver.mod --tmlim 10
...中略
Time used:   10.0 secs
Memory used: 31.2 Mb (32666027 bytes)
 1  Doctor D
 2  Doctor C
 3  Doctor B
 4  Doctor A
 5  Doctor B
 6  Doctor A
...中略
Model has been successfully processed