- LocalSolverホーム
- LocalSolver製品概要
- LocalSolver例題集
- Nurse Rostering（看護師スケジューリング）
Nurse Rostering（看護師スケジューリング）
看護師スケジューリング（PATAT' 10コンペ）B. Dessort, C. Groix, C. Jaulin , Ecole des Mines de Nantes（フランス）提供
看護師のスケジューリング問題は、いくつかの制約を考慮した看護師のシフト勤務の割り当問題が内在します。
ここでの唯一の制約は、各看護婦が1日につき、正確に1つのシフトに割り当てられ、一日単位を対象とする制約もまたその日ごとに満たされている必要があります。目的関数は規則をスケジューリングする一定数の充足に関連した違反の線形結合です。
：出勤日数の最小/最大、連続出勤日数の最小/最大、週末の同一シフト、望んでいないシフト・パターン数の最小/最大など。
この例題は、PATAT2010 Nurse Rostering コンペで取り上げられた問題です。詳細情報は http://www.kuleuven-kulak.be/nrpcom...からご覧いただけます。このコンペの最終段階のテキストデータファイルは例題集/フォルダーでご利用いただけます。このコンペのWEBサイトで数多くの例題をダウンロードすることが可能です。この問題は下記のコマンドで開始します。
このモデルをLocalSolverは10秒間で解くことができます。出力ファイルは、xml形式で作成されており、コンペの公式な評価で確認することが可能です。
いくつかの理由から、この評価者がXML入力ファイルを必要としたため、これらのXML入力は評価者フォルダーで提供されています。下記のコマンドは上記を計算し、そのコストを計算することで、解の有効性を確認します。
java -jar evaluator/evaluator.jar evaluator/sprint_hidden01.xml solution01.xml
モデリング観点から説明すると、このモデルは古典的に、X[e,d,s]意思決定変数をベースとしています。従業員eが日ｄのシフトｓに割り当てられた場合、1と同等となります。LocalSolverは条件付き演算子を含め、多くの非線形演算子を利用することが可能です。例えば、連続出勤日における違反は従業員eのスケジュールで前日の日ｄ（出勤していた、または休日）と同一の日数と等しい中間変数nbSlidingConsecutive[e][d]でモデル化されます。それぞれのnbSlidingConsecutive[e][d]意思決定変数は中間演算子によりnbSlidingConsecutive[e][d]変数から再帰的に定義されます。最終的に、極端な長期間にわたる連続出勤または極端な短期間の連続出勤を簡単に発見することが可能です。
詳細は http://www.kuleuven-kulak.be/nrpcom...をご覧ください。
LSP ソースファイル
/********** nurse_rostering.lsp **********/
/** Reads input data. */
function input() {
usage = "\nUsage: localsolver nurse_rostering.lsp inFileName=model.txt solFileName=solution.xml\n";
if (inFileName == nil || solFileName == nil) error(usage);
inFile = openRead(inFileName);
dowIndex["Monday"]=0;
dowIndex["Tuesday"]=1;
dowIndex["Wednesday"]=2;
dowIndex["Thursday"]=3;
dowIndex["Friday"]=4;
dowIndex["Saturday"]=5;
dowIndex["Sunday"]=6;
readSchedulingPeriod();
readSkills();
readShifts();
readContracts();
readPatterns();
readEmployees();
readCoverage();
readDateSpecificCover();
dayoffrequests = readDayRequests();
dayonrequests = readDayRequests();
shiftoffrequests = readDayRequests();
shiftonrequests = readDayRequests();
}
/** Reads the scheduling period.
* Note that all instances starting on the same day hence no calendar function is needed. */
function readSchedulingPeriod() {
scheduling_period = getLinesAfterTitle()[0];
sss = split(scheduling_period,",");
planningName = sss[0];
startDate = trim(sss[1]);
startDay = nrpDate(startDate);
endDate = trim(sss[2]);
endDay = nrpDate(endDate);
nbDays = endDay-startDay+1;
if (startDate == "2010-01-01") startDayOfWeek = 4; // Friday
else if (startDate== "2010-06-01") startDayOfWeek = 1; // Tuesday
else if (startDayOfWeek == nil) error("Unknown start Day Of Week:"+startDate);
if (nbDays % 7 != 0) error("Number of days should be a multiple of 7");
nbWeeks = nbDays / 7;
}
function readSkills() {
skills = getLinesAfterTitle();
}
/** Read shifts. They are given index starting at 1, 0 coding for Day Off. */
function readShifts() {
lines = getLinesAfterTitle();
nbShifts = count(lines);
local sxIndex = 1;
for[l in lines] {
trimmed = splitAndTrim(l);
shiftIndexMap[trimmed[0]]=sxIndex;
shiftNames[sxIndex]=trimmed[0];
shiftSkills[sxIndex] = split(trimmed[5]," ");
sxIndex = sxIndex+1;
}
}
/** Read constracts. Most constraints take the form (on|weight|value). */
function readContracts() {
lines = getLinesAfterTitle();
nbContracts = count(lines);
ON = 0; WEIGHT = 1; VALUE = 2;
for[l in lines] {
trimmed = splitAndTrim(l);
local id = toInt(trimmed[0]);
contractName[id] = trimmed[1];
//onWeightValue(trimmed[2]);
maxAssignment[id] = onWeightValue(trimmed[3]);
minAssignment[id] = onWeightValue(trimmed[4]);
maxConsecutiveWorkingDays[id] = onWeightValue(trimmed[5]);
minConsecutiveWorkingDays[id] = onWeightValue(trimmed[6]);
maxConsecutiveFreeDays[id] = onWeightValue(trimmed[7]);
minConsecutiveFreeDays[id] = onWeightValue(trimmed[8]);
maxConsecutiveWorkingWeekends[id] = onWeightValue(trimmed[9]);
minConsecutiveWorkingWeekends[id] = onWeightValue(trimmed[10]);
maxWorkingWeekendsInFourWeeks[id] = onWeightValue(trimmed[11]);
if (trimmed[12] != "SaturdaySunday") error("Non standard week-ends");
completeWeekEnds[id] = onWeightValue(trimmed[13]);
identicalShiftsDuringWeekEnd[id] = onWeightValue(trimmed[14]);
noNightShiftBeforeFreeWeekend[id] = onWeightValue(trimmed[15]);
twoFreeDaysAfterNightShifts[id] = onWeightValue(trimmed[16]);
alternativeSkillCategory[id] = onWeightValue(trimmed[17]);
nbUnwantedPatterns[id] = toInt(trimmed[18]);
splittedPatterns = split(trimmed[19]," ");
if (count(splittedPatterns) != nbUnwantedPatterns[id]) error("Wrong number of unwanted patterns");
unwantedPatterns[id] = map();
for[s in splittedPatterns] add(unwantedPatterns[id],toInt(s));
}
}
/** Utility function for reading contract constraints of the form (on|weight|value) or (on|weight). */
function onWeightValue(str) {
local n = length(str);
substr = substring(str,1,n-2);
splitted = split(substr,"|");
result = map();
for[s in splitted] add(result,toInt(s));
return result;
}
/** Read patterns. A pattern is a unwanted sequence of shifts. */
function readPatterns() {
lines = getLinesAfterTitle();
for [l in lines] {
trimmed = splitAndTrim(l);
local id = toInt(trimmed[0]);
patternWeight[id] = toInt(trimmed[1]);
local str = split(trimmed[2]," ");
patternLength[id] = toInt(str[0]);
patternShifts[id] = map();
for[k in 1..patternLength[id]] {
local sx = replace(str[k],"(","");
sx = replace(sx,")","");
add(patternShifts[id],split(sx,"|"));
}
}
}
/** Read all employees. Note that usually they are not defined in the order of their Ids. */
function readEmployees() {
lines = getLinesAfterTitle();
nbEmployees = count(lines);
for[e in 0 ..nbEmployees-1] {
splitted = splitAndTrim(lines[e]);
employeeId[e] = toInt(splitted[0]);
employeeIndexFromId[employeeId[e]] = e;
employeeContract[e] = toInt(splitted[2]);
employeeSkills[e] = map();
for[k in 4..count(splitted)-1] add(employeeSkills[e],splitted[k]);
}
}
/** Returns true if this employee has all the required skills for this shift.*/
function hasSkillForShift(employee,shift) {
return and[sks in shiftSkills[shift]](or[esk in employeeSkills[employee]](sk == esk));
}
/** Read coverage requirements. They are given by day of week.*/
function readCoverage() {
lines = getLinesAfterTitle();
coverage[d in 0..6][s in 1..nbShifts] = 0;
for[l in lines] {
splitted = splitAndTrim(l);
dayofweek = dowIndex[splitted[0]];
shiftIndex = shiftIndexMap[splitted[1]];
cover = toInt(splitted[2]);
coverage[dayofweek][shiftIndex] = cover;
}
//infer the "requirement" for days off
for[d in 0..6] coverage[d][0] = nbEmployees - sum[s in 1..nbShifts](coverage[d][s]);
}
/** No date specific coverage requirement are specified in instances of the PATAT competition. */
function readDateSpecificCover() {
datespecificcover = getLinesAfterTitle();
if (count(datespecificcover) > 0) error("This example does not handle date-specific coverage constraints.");
}
/** A day request is either [employee, date, weight] or [employee, date, shift, weight]. */
function readDayRequests() {
lines = getLinesAfterTitle();
local result = map();
for[l in lines] {
local splitted = splitAndTrim(l);
if (count(splitted) == 3) add(result, {toInt(splitted[0]),nrpDate(splitted[1]),toInt(splitted[2])});
else add(result, {toInt(splitted[0]),nrpDate(splitted[1]),splitted[2],toInt(splitted[3])});
}
// the official PATAT 2012 checker counts no day penalty as soon as one has a weight of 0
if (count(result) > 0 && min[req in result](req[count(req)-1]) == 0) return map();
return result;
}
/** Get the requirement for a given day. */
function getCover(d,s) {
return coverage[(startDayOfWeek + d) % 7][s];
}
/** Utility function splitting a strng around "," and trimming each component. */
function splitAndTrim(line) {
words = split(line,",");
trimmed=map();
for[w in words] add(trimmed,trim(w));
return trimmed;
}
/** Skip blank lines + a serie of 3 title lines,
* return the following consecutive non empty lines (with ";" chars removed). */
function getLinesAfterTitle() {
local lines = map();
local stop = 0;
while (stop == 0) {
line = readln(inFile);
if (line != "") stop = 1;
}
if (!startsWith(line,"//")) error("expecting title line starting with //");
for[i in 1..2] readln(inFile);
stop = 0;
while (stop == 0) {
line = readln(inFile);
if (line != "") add(lines,replace(line,";",""));
else stop = 1;
}
return lines;
}
/** Get a day index from a date in format YYYY-MM-DD. */
function nrpDate(str) {
local snrpDate=split(str,"-");
return toInt(snrpDate[2]) - 1; // index days starting from 0
}
/**
* Models the problem with 0-1 decisions. The only hard constraints are the assignment of a single shift
* per day per employee and the satisfaction of coverage requirements.
* All other requirements are preferences. The objective function is a weighted sum of penalties.
*
* Notations:
* shift[e][d][s] = 1 if employee e is assigned to shift s on day d (remember that shift 0 codes for days off)
* work[e][d] = 1 if employee e works on day d
**/
function model() {
shift[0..nbEmployees-1][0..nbDays-1][0..nbShifts] <- bool(); // 0 codes for no_shift
// exactly one shift (possibly the "0-shift") for each employee and each day
for[e in 0..nbEmployees-1][d in 0..nbDays-1]
constraint sum[s in 0..nbShifts](shift[e][d][s]) == 1;
// exact coverage of requirements
for[d in 0..nbDays-1][s in 0..nbShifts] {
constraint sum[e in 0..nbEmployees-1](shift[e][d][s]) == getCover(d,s);
}
// intermediate variable work[e][d] = 1 iff e is assigned a working shift on day d
work[e in 0..nbEmployees-1][d in 0..nbDays-1] <- !shift[e][d][0];
// intermediate variable workedWeekEnd[e][w] == 1 if the week-end of week w is worked
for[e in 0..nbEmployees-1][w in 0 ..nbWeeks-1] {
local saturday = w * 7 + (5 - startDayOfWeek) % 7;
local sunday = w * 7 + (6 - startDayOfWeek) % 7;
if (saturday < 0) workedWeekEnd[e][w] <- work[e][sunday];
else if (sunday < nbDays) workedWeekEnd[e][w] <- work[e][saturday] || work[e][sunday];
else if (saturday < nbDays) workedWeekEnd[e][w] <- work[e][saturday];
}
// total number of worked days
nbDaysWorked[e in 0..nbEmployees-1] <- sum[d in 0..nbDays-1](work[e][d]);
// intermediate variables for constraints on consecutive days in, days off and week-ends
nbSlidingConsecutive[e in 0..nbEmployees-1][0] <- 1;
nbSlidingConsecutive[e in 0..nbEmployees-1][d in 1..nbDays-1] <-
work[e][d] == work[e][d-1] ? nbSlidingConsecutive[e][d-1]+1:1;
nbConsecutive[e in 0..nbEmployees-1][d in 0..nbDays-2] <-
nbSlidingConsecutive[e][d] >= nbSlidingConsecutive[e][d+1] ? nbSlidingConsecutive[e][d] : 0;
nbConsecutive[e in 0..nbEmployees-1][nbDays-1] <-
nbSlidingConsecutive[e][nbDays-1];
nbSlidingConsecutiveWE[e in 0..nbEmployees-1][0] <- 1;
nbSlidingConsecutiveWE[e in 0..nbEmployees-1][w in 1..nbWeeks-1] <-
workedWeekEnd[e][w] == workedWeekEnd[e][w-1] ? nbSlidingConsecutiveWE[e][w-1]+1:1;
nbConsecutiveWE[e in 0..nbEmployees-1][w in 0..nbWeeks-2] <-
nbSlidingConsecutiveWE[e][w] >= nbSlidingConsecutiveWE[e][w+1] ? nbSlidingConsecutiveWE[e][w] : 0;
nbConsecutiveWE[e in 0..nbEmployees-1][nbWeeks-1] <-
nbSlidingConsecutiveWE[e][nbWeeks-1];
// Contract constraints for each employee
for [e in 0..nbEmployees-1] {
local c = employeeContract[e];
local minAssign = minAssignment[c];
local maxAssign = maxAssignment[c];
local minConsWorking = minConsecutiveWorkingDays[c];
local minConsFree = minConsecutiveFreeDays[c];
local maxConsWorking = maxConsecutiveWorkingDays[c];
local maxConsFree = maxConsecutiveFreeDays[c];
local minConsWorkingWE = minConsecutiveWorkingWeekends[c];
local maxConsWorkingWE = maxConsecutiveWorkingWeekends[c];
penaltyMinAssign[e] <- minAssign[WEIGHT] * max(0,minAssign[VALUE]-nbDaysWorked[e]);
penaltyMaxAssign[e] <- maxAssign[WEIGHT] * max(0,nbDaysWorked[e]-maxAssign[VALUE]);
penaltyMinConsWorking[e] <- minConsWorking[ON]==0 ? 0 : minConsWorking[WEIGHT] *
sum[d in 0..nbDays-1]((nbConsecutive[e][d] != 0 && work[e][d]) ?
max(0,minConsWorking[VALUE] - nbConsecutive[e][d]) : 0);
penaltyMaxConsWorking[e] <- maxConsWorking[ON]==0 ? 0 :maxConsWorking[WEIGHT] *
sum[d in 0..nbDays-1](nbConsecutive[e][d] != 0 && work[e][d] ?
max(0,nbConsecutive[e][d]-maxConsWorking[VALUE]) : 0);
penaltyMinConsFree[e] <- minConsFree[ON]==0 ? 0 :minConsFree[WEIGHT] *
sum[d in 0..nbDays-1](nbConsecutive[e][d] != 0 && !work[e][d] ?
max(0,minConsFree[VALUE]-nbConsecutive[e][d]) : 0);
penaltyMaxConsFree[e] <- maxConsFree[ON]==0 ? 0 :maxConsFree[WEIGHT] *
sum[d in 0..nbDays-1](nbConsecutive[e][d] != 0 && !work[e][d] ?
max(0,nbConsecutive[e][d]-maxConsFree[VALUE]) : 0);
penaltyMinConsWorkingWE[e] <- minConsWorkingWE[ON]==0 ? 0 :minConsWorkingWE[WEIGHT] *
sum[w in 0..nbWeeks-1](nbConsecutiveWE[e][w] != 0 && workedWeekEnd[e][w] ?
max(0,minConsWorkingWE[VALUE]-nbConsecutiveWE[e][w]) : 0);
penaltyMaxConsWorkingWE[e] <- maxConsWorkingWE[ON]==0 ? 0 :maxConsWorkingWE[WEIGHT] *
sum[w in 0..nbWeeks-1](nbConsecutiveWE[e][w] != 0 && workedWeekEnd[e][w] ?
max(0,nbConsecutiveWE[e][w]-maxConsWorkingWE[VALUE]) : 0);
// unwanted patterns
PATTSHIFT = 0;
PATTDAY = 1;
if (nbUnwantedPatterns[c]>0) {
for[k in 0..nbUnwantedPatterns[c]-1] {
local pId = unwantedPatterns[c][k];
lp = patternLength[pId];
lsx = patternShifts[pId];
for[d in 0..nbDays-lp] {
if (lsx[0][PATTDAY] == "Any" || (d + startDayOfWeek) % 7 == dowIndex[lsx[0][PATTDAY]]) {
if (lsx[0][PATTSHIFT] == "None") { //special case
patternFound[e][k][d] <- matchingTerm(e,lsx[0][PATTSHIFT],d) &&
or[a in 1..lp-1](matchingTerm(e,lsx[a][PATTSHIFT],d+a));
} else {
patternFound[e][k][d] <- and[a in 0..lp-1](matchingTerm(e,lsx[a][PATTSHIFT],d+a));
}
} else {
patternFound[e][k][d] <- 0;
}
}
unwantedPenalty[e][k] <- patternWeight[pId] * sum[d in 0..nbDays-lp](patternFound[e][k][d]);
}
totalUnwantedPenalty[e] <- sum[k in 0..nbUnwantedPatterns[c]-1](unwantedPenalty[e][k]);
} else {
totalUnwantedPenalty[e] <- 0;
}
// alternate skills
if (alternativeSkillCategory[c][ON] == 0) penaltyAlternateSkill[e] <- 0;
else penaltyAlternateSkill[e] <- alternativeSkillCategory[c][WEIGHT] *
sum[s in 1..nbShifts:!hasSkillForShift(e,s)][d in 0..nbDays-1](shift[e][d][s]);
// complete week-ends
local saturday = dowIndex["Saturday"];
if (completeWeekEnds[c][ON] == 0) penaltyCompleteWeekEnd[e] <- 0;
else penaltyCompleteWeekEnd[e] <- completeWeekEnds[c][WEIGHT] *
sum[d in 0..nbDays-2 : (d + startDayOfWeek) % 7 == saturday](work[e][d] != work[e][d+1]);
// indentical week-ends
if (identicalShiftsDuringWeekEnd[c][ON] == 0) penaltyIdenticalWeekEnd[e] <- 0;
else penaltyIdenticalWeekEnd[e] <- identicalShiftsDuringWeekEnd[c][WEIGHT] *
sum[d in 0..nbDays-2 : (d + startDayOfWeek) % 7 == saturday]
[s in 1..nbShifts](shift[e][d][s] != shift[e][d+1][s]);
}
// day off requests
if (count(dayoffrequests) == 0) dayoffPenalty <- 0;
else dayoffPenalty <- sum[r in dayoffrequests](work[employeeIndexFromId[r[0]]][r[1]] * r[2]);
// day on requests
if (count(dayonrequests) == 0) dayonPenalty <- 0;
else dayonPenalty <- sum[r in dayonrequests](shift[employeeIndexFromId[r[0]]][r[1]][0] * r[2]);
// shift off requests
if (count(shiftoffrequests) == 0) shiftoffPenalty <- 0;
else shiftoffPenalty <-
sum[r in shiftoffrequests](shift[employeeIndexFromId[r[0]]][r[1]][shiftIndexMap[r[2]]] * r[3]);
// shift on requests
if (count(shiftonrequests) == 0) shiftonPenalty <- 0;
else shiftonPenalty <-
sum[r in shiftonrequests](!shift[employeeIndexFromId[r[0]]][r[1]][shiftIndexMap[r[2]]] *r[3]);
// objective function
obj <- sum[e in 0..nbEmployees-1](penaltyMinAssign[e]+penaltyMaxAssign[e] +
penaltyMinConsWorking[e] + penaltyMaxConsWorking[e] +
penaltyMinConsFree[e] + penaltyMaxConsFree[e] +
penaltyMaxConsWorkingWE[e] + penaltyMinConsWorkingWE[e] +
totalUnwantedPenalty[e] + penaltyAlternateSkill[e] +
penaltyCompleteWeekEnd[e] + penaltyIdenticalWeekEnd[e])
+ dayoffPenalty + dayonPenalty + shiftoffPenalty + shiftonPenalty;
minimize obj;
}
/** Return the boolean variable representing the matching by employee e on day d
* of the given shift string (as expressed in pattern).*/
function matchingTerm(employee,shiftStr,day) {
if (shiftStr=="Any") return work[employee][day];
if (shiftStr=="None") return shift[employee][day][0];
local s = shiftIndexMap[shiftStr];
if (s == nil) error("No shift with Id "+shiftStr);
if (shift[employee] == nil) error("No shift for employee #"+employee);
if (shift[employee][day] == nil) error("No shift for employee #"+employee+" on day "+day);
return shift[employee][day][s];
}
/** Writes the solution as an XML file compatible with the evaluator of the PATAT'10 competition. */
function output() {
solFile = openWrite(solFileName);
println(solFile,"");
println(solFile,""+planningName+" ");
println(solFile,""+LocalSolver+" ");
println(solFile,""+getValue(obj)+" ");
for[d in 0..nbDays-1][e in 0..nbEmployees-1][s in 1..nbShifts] {
if (getValue(shift[e][d][s]) == 1) {
println(solFile,"");
println(solFile,""+dayName(d)+" ");
println(solFile,""+employeeId[e]+" ");
println(solFile,""+shiftNames[s]+" ");
println(solFile," ");
}
}
println(solFile," ");
}
/** Utility function writing a day in format YYYY-MM-DD. */
function dayName(dayIndex) {
local dayPrefix = "";
if (startDate == "2010-01-01") dayPrefix = "2010-01-";
else if (startDate == "2010-06-01") dayPrefix = "2010-06-";
else error("Unexcepted start date for NRP instance");
daystring = ((dayIndex+1) <= 9 ? "0" : "")+(dayIndex+1);
return dayPrefix+daystring;
}
例題コンテンツ
- nurse_rostering/
- nurse_rostering/evaluator/
- nurse_rostering/evaluator/evaluator.jar
- nurse_rostering/evaluator/sprint_hidden01.xml
- nurse_rostering/evaluator/sprint_hidden02.xml
- nurse_rostering/evaluator/sprint_hidden03.xml
- nurse_rostering/evaluator/sprint_hidden04.xml
- nurse_rostering/evaluator/sprint_hidden05.xml
- nurse_rostering/evaluator/sprint_hidden06.xml
- nurse_rostering/evaluator/sprint_hidden07.xml
- nurse_rostering/evaluator/sprint_hidden08.xml
- nurse_rostering/evaluator/sprint_hidden09.xml
- nurse_rostering/evaluator/sprint_hidden10.xml
- nurse_rostering/instances/
- nurse_rostering/instances/sprint_hidden01.txt
- nurse_rostering/instances/sprint_hidden02.txt
- nurse_rostering/instances/sprint_hidden03.txt
- nurse_rostering/instances/sprint_hidden04.txt
- nurse_rostering/instances/sprint_hidden05.txt
- nurse_rostering/instances/sprint_hidden06.txt
- (+ 7 other files)
