- LocalSolverホーム
- LocalSolver製品概要
- LocalSolver例題集
- Workforce Planning (人員配置計画)
Workforce Planning (人員配置計画)
人員配置計画 MSI提供(http://www.msi-jp.com/)
ここに掲載している人員配置計画は、MSIの顧客が、与えられた要求を満たすために、在籍する従業員のシフト表を作成する際に取り組んだ問題です。
毎日、一時間毎のスケジュールを作成し、需要は、業務毎の人員配置（従業員数）目標としてモデル化されます。従業員については、各自実践可能な業務（従業員スキル）に条件があります。毎日のシフトは、始業、終業および継続時間で制約され、労働日数は考慮された日数で制限されます。日毎の各従業員については、解は始業時間、終業時間及び時間ステップ毎（一時間毎）、1つの業務で定義されます。目標は目標人員配置まで、隔たりの合計を最小化することです。
モデリングの重要ポイントは、シフト（始業、終業）を休暇中の従業員に割当てるのか、このシフト外の時間に割当てられた活動は無関係なのか、事前に定義された値を取るためにこれら変数を制約しないことが重要です。これは各従業員が出勤しているか否かに関わらず、毎日の毎時間、割当てられた業務を行っていることを意味します。目標人員配置までの隔たりを計算するとき、勤務表内の時間ステップのみ考慮されます。この手法は、探索空間の高密度を保障します。：休暇の切り替えは1つの変数を変更することを意味します。
そして、従業員の業務時間枠を拡張するとき、一連の有効な業務は、追加された時間ステップを満たすことが可能です。データファイルは、従業員数、日数、時間ステップ数、アクティビティの数から始め、その後、各従業員に対し、従業員が従事できる業務に一連の整数（0か1）が与えられます。そして各従業員と毎日の最も早い始業時間と最も遅い終業時間（2*nbDays一人あたりの数）を振り分けます。最終的に、各日の各時間ステップに、各業務に従事するのに目標となるスタッフの配置を与えます。
LSPソースファイル
/********** workforce.lsp **********/
/* Reads instance data. */
function input()
{
usage = "\nUsage: localsolver cast.lsp "
+ "inFileName=inputFile [lsTimeLimit=timeLimit]\n";
if (inFileName == nil) error(usage);
inFile = openRead(inFileName);
nEmployees = readInt(inFile);
nDate = readInt(inFile);
nTime = readInt(inFile);
nAct = readInt(inFile);
for [e in 0..nEmployees-1]
for [p in 0..nAct-1]
hasSkill[e][p] = readInt(inFile);
for [e in 0..nEmployees-1]
for [d in 0..nDate-1]
{
earliestStart[e][d] = readInt(inFile);
latestEnd[e][d] = readInt(inFile);
}
for [d in 0..nDate-1]
for [t in 0..nTime-1]
for [p in 0..nAct-1]
nbRequired[d][t][p] = readInt(inFile);
maxWorkingDurationPerDay = readInt(inFile);
minWorkingDurationPerDay = readInt(inFile);
maxNumberOfWorkedDays = readInt(inFile);
costCoef = readInt(inFile);
// identify single-skill employees
for [e in 0..nEmployees-1]
for [p in 0..nAct-1 : hasSkill[e][p] == 1] {
if (singleSkill != nil && singleSkill[e] != nil) singleSkill[e] = -1;
else singleSkill[e] = p;
}
}
/* Declares the optimization model. */
function model()
{
// 0-1 decision variables:
// X[e][d][t][duration] == 1 when the shift chosen for employee e on day d
// starts at t and lasts duration timesteps
// From these decision variables we compute isWorkDay[e][d] (equal to 1 if a shift is assigned to this day)
for [e in 0..nEmployees-1][d in 0..nDate-1]
{
for[t in 0..nTime-1]
{
for[duration in minWorkingDurationPerDay..maxWorkingDurationPerDay]
{
if (latestEnd[e][d] ==0 || // interval [0,0] codes for "forced day off"
t < earliestStart[e][d] ||
t+duration>latestEnd[e][d] ||
t+duration>=nTime)
X[e][d][t][duration] <- 0;
else X[e][d][t][duration] <- bool();
}
startsAtTime[e][d][t] <- sum[l in minWorkingDurationPerDay..maxWorkingDurationPerDay](X[e][d][t][l]);
}
isWorkDay[e][d] <- sum[t in 0..nTime-1](startsAtTime[e][d][t]);
constraint isWorkDay[e][d] <= 1;
}
// Y[e][d][t][p] = 1 when the activity assigned to employee e on day d at timestep t is p
// From these decision variables we compute activeY[e][d][t][p] (equal to 1
// if employee e actually work on activity p at timestep t of day d)
for [e in 0..nEmployees-1][d in 0..nDate-1][t in 0..nTime-1]
{
local canBePresent = false;
for [p in 0..nAct-1]
{
if (hasSkill[e][p]==0 || latestEnd[e][d] ==0 || // interval [0,0] codes for "forced day off"
earliestStart[e][d] > t ||
latestEnd[e][d] < t) Y[e][d][t][p] <- 0;
else {
if (singleSkill[e] == p) Y[e][d][t][p] <- 1;
else Y[e][d][t][p] <- bool();
canBePresent = true;
}
}
if (canBePresent) {
presence[e][d][t] <-
sum[start in 0..t][duration in t-start+1..maxWorkingDurationPerDay](X[e][d][start][duration]);
if (singleSkill[e] == -1) constraint sum[l in 0..nAct-1](Y[e][d][t][l]) == 1;
activeY[e][d][t][l in 0..nAct-1] <- presence[e][d][t] >0 && Y[e][d][t][l];
} else {
activeY[e][d][t][l in 0..nAct-1] <- 0;
}
}
// for each employee the number of worked days is limited
for [e in 0..nEmployees-1]
constraint sum[d in 0..nDate-1](isWorkDay[e][d]) <= maxNumberOfWorkedDays;
// for each time step and activity we compute the distance to target
for [d in 0..nDate-1][t in 0..nTime-1][p in 0..nAct-1]
distanceToRequired[d][t][p] <-abs(sum[e in 0..nEmployees-1](activeY[e][d][t][p])-nbRequired[d][t][p]);
// objective function: minimize the sum of distances to target staffing
totalDistanceToRequired <- sum[d in 0..nDate-1][t in 0..nTime-1][p in 0..nAct-1](distanceToRequired[d][t][p]);
minimize totalDistanceToRequired * costCoef;
}
function param()
{
if (lsTimeLimit == nil) lsTimeLimit = 100;
if (lsNbThreads == nil) lsNbThreads = 8;
}
/* Writes a digest of the planning with "." for worked days and and "O" for days off. */
function display()
{
println("Objective function = " + getValue(totalDistanceToRequired));
for [d in 0..nDate-1]
{
print("Day "+d+": ");
for [e in 0..nEmployees-1]{
if (getValue(isWorkDay[e][d])) print(".");
else print ("O");
}
println();
}
println();
}
/* Writes the detailed planning to a file. */
function output()
{
println("Write solution into file 'solution.txt'");
solFile = openWrite("solution.txt");
for [e in 0..nEmployees-1]
{
println(solFile, "Employee "+e);
for [d in 0..nDate-1]
{
if (getValue(isWorkDay[e][d])) print(solFile,"W:");
else print (solFile,"O:");
for [k in 0..nTime-1]
{
nOut = 0;
for [l in 0..nAct-1] {
// since some activeY were left undefined we must check equality to nil before retrieving value
if (activeY[e] != nil &&
activeY[e][d] != nil &&
activeY[e][d][k] != nil &&
activeY[e][d][k][l] != nil &&
getValue(activeY[e][d][k][l])==1)
{
print(solFile, l+1);
nOut = 1;
}
}
if (nOut==0)
print(solFile, "-");
}
print(solFile," ");
for [t in 0..nTime-1][l in minWorkingDurationPerDay..maxWorkingDurationPerDay]
if (getValue(X[e][d][t][l]) == 1) print(solFile,"["+t+","+(t+l-1)+"]");
println(solFile);
}
println(solFile);
}
}
例題コンテンツ
- workforce_planning/
- workforce_planning/instances/
- workforce_planning/instances/large.in
- workforce_planning/instances/medium.in
- workforce_planning/instances/small.in
- workforce_planning/README.txt
- workforce_planning/workforce.lsp
