public class TwoStep extends Object
TwoStepParams
.
There are 2 steps:
The staffing problems in Step 1 are solved using the
RandomizedSearch
method Avramidis et al. (2009).
Step 1 uses the randomized search, instead of CuttingPlaneOptimizer
, because the solutions from
the randomized search are usually much closer and this facilitates the optimization of Step 2.
As Step 1 solves the staffing period by period, it requires a BatchSimParams
simulator.
In Step 2, the scheduling is simulated for all the periods and needs another simulator that
uses RepSimParams
.
Step 2 optimizes the shift scheduling as an integer problem (IP) using Cplex. Since Step 2 needs to optimize the IP only once, the budget time for Cplex can be large and the best incumbent integer solution found returned at the end. Solving partially the IP may be preferable than to solve the relaxed LP version, because of subsequent rounding difficulties. For small problems, solving the IP is relatively quick. For large problems, rounding the LP solution is far from trivial and it may generate a worse solution.
The cost per agent is controlled by TwoStepParams
.
If TwoStepParams.useBusyCost
is set to true
, then the optimization will
use the busy cost per agent specified in the call center parameters.
Else, the user would specify the skill premium for each additional skill above 1
with TwoStepParams.skillPremiumCost
. And the cost for the first skill is 1.
Finally, the cost of an agent is multiplied by its shift length.
Note the parameters in TwoStepParams
will override the same parameters
found in RandomizedSearchParams
.
Modifier and Type | Field and Description |
---|---|
protected ilog.cplex.IloCplex |
cplex
The Cplex object that contains the LP.
|
protected double |
objValue
Represents the most recent objective value found by Cplex solver.
|
protected ilog.concert.IloIntVar[][] |
varX
Represents the shift scheduling variables of the IP.
|
protected HashMap<String,ilog.concert.IloNumVar> |
varZ
A
HashMap to contain the skill transfer variables. |
Constructor and Description |
---|
TwoStep(CallCenterParams ccParams,
TwoStepParams tsParams,
LossDelayParams ldParams,
RandomizedSearchParams rsParams,
CallCenterSim rsSim,
BatchSimParams batchParams,
CallCenterSim schedSim,
String folder,
RandomStream rsRand)
Constructs and initializes the Two-step optimizer.
|
Modifier and Type | Method and Description |
---|---|
double[][] |
computeLoad()
Computes and returns the load matrix of the call center.
|
void |
createChart(int[][] scheduling,
String fileName,
String excelFileName)
Creates an Excel file containing the results.
|
void |
createChartForSL(DoubleMatrix2D sl)
Creates an Excel file and some
.eps images to report the service levels. |
void |
createProblem()
Creates the MIP problem of Step 2.
|
double |
getBestSolutionCost()
Returns the cost of the best integer solution found.
|
double |
getCost(int[][] scheduling)
Computes and returns the cost of the given scheduling solution.
|
protected int[][][] |
getEffectiveSkillTransfers(int[][] scheduling)
Returns the matrix containing the
effective skill transfered agents only (this is not the scheduling nor the staffing matrix).
|
double |
getMIPGap()
Returns the relative MIP gap from Cplex after solving the integer problem.
|
protected int[] |
getShiftLengths()
Computes the shift lengths of all shifts.
|
int[][] |
getStaffing(int[][] scheduling)
From the scheduling (group, shifts) matrix, returns the corresponding staffing
(group, periods) matrix.
|
int[][] |
getStaffing(int[][] scheduling,
boolean applySkillTransfer)
Same as
getStaffing(int[][]) , but the user can choose to apply
skill transfers or not. |
double |
getTotalTimeSec()
Returns the total time taken by the Two-step algorithm (Steps 1 and 2) in seconds.
|
boolean |
isFeasible(DoubleMatrix2D sl)
Checks if all the service levels satisfy their targets: (1) globally for
all call types and periods, (2) per call type for all periods, (3) per periods
for all types, and (4) per types and per period.
|
static void |
main(String[] args)
Executes the Two-step algorithm.
|
void |
printSolution()
Prints the solution to screen.
|
void |
printTransfers()
Prints the values of the skill transfer variables to screen.
|
DoubleMatrix2D |
simEvalScheduling(int[][] x)
Simulates the call center with the given scheduling matrix.
|
boolean |
solve()
Optimizes the scheduling problem using the Two-step method.
|
void |
solveStaffingProblems()
Step 1 of the algorithm:
solve the staffing problem for each period.
|
protected ilog.cplex.IloCplex cplex
protected ilog.concert.IloIntVar[][] varX
protected HashMap<String,ilog.concert.IloNumVar> varZ
HashMap
to contain the skill transfer variables.protected double objValue
public TwoStep(CallCenterParams ccParams, TwoStepParams tsParams, LossDelayParams ldParams, RandomizedSearchParams rsParams, CallCenterSim rsSim, BatchSimParams batchParams, CallCenterSim schedSim, String folder, RandomStream rsRand)
ccParams
- the call center parameterstsParams
- the parameters for the Two-step algorithmldParams
- the parameters for the Loss-delay approximationrsParams
- the parameters for RandomizedSearch
used in the first phase to solve the staffing problemsrsSim
- the simulator to use to solve the staffing problems with RandomizedSearch
batchParams
- the parameters of the simulator used by RandomizedSearch
. It is needed to change the simulation period.schedSim
- the multi-period simulator to be used in the second phasefolder
- the directory where to create the output filesrsRand
- the random stream to be used by RandomizedSearch
protected int[] getShiftLengths()
IntegerListProperty
element
named "shiftLengths" inside the call center properties
element, and accessible with
CallCenterParams.getProperties()
.
A user should declare the shiftLengths
property in the XML file if the shift lengths
don't correspond exactly to the number of the covered periods. For example, the user
should declare shiftLengths
manually if, for some shifts, there are non-working periods
that are paid (e.g.: breaks, lunch time).
This method will first check if the call center property shiftLengths
exists in the XML parameters of CallCenterParams
.
If such element exists, then it will return the vector of integers specified by the user.
Otherwise (if the user does not declare shiftLengths
parameter), then
it returns the number of periods covered by each shift. This matrix is obtained by
calling CallCenterParams.getShiftMatrix()
.
public DoubleMatrix2D simEvalScheduling(int[][] x)
x
- the scheduling matrix, where element x[i][j] is the number of agents of group i
assigned to shift jpublic void createProblem() throws ilog.concert.IloException
solveStaffingProblems()
.ilog.concert.IloException
public void solveStaffingProblems()
RandomizedSearch.multiOpt()
from the randomized search.
The staffing solutions are used to build the MIP problem of Step 2.public boolean solve() throws ilog.concert.IloException
solveStaffingProblems()
method to find the staffing vector for
each period, then it invokes the createProblem()
method to create the MIP problem
and solves it using Cplex.true
if the MIP problem has a solution, false
otherwiseilog.concert.IloException
public void printSolution()
public void printTransfers()
public double getCost(int[][] scheduling)
scheduling
- the scheduling solutionpublic double[][] computeLoad()
public int[][] getStaffing(int[][] scheduling)
TwoStepParams.allowSkillTransfer
.scheduling
- the scheduling matrixpublic int[][] getStaffing(int[][] scheduling, boolean applySkillTransfer)
getStaffing(int[][])
, but the user can choose to apply
skill transfers or not.scheduling
- the scheduling matrixapplySkillTransfer
- to apply the skill transfers or notprotected int[][][] getEffectiveSkillTransfers(int[][] scheduling)
null
if the skill transfer mechanism is not allowed by the user.
Let E the returned matrix, element
e[p][i][j] represents the number of
agents from group i that are transfered to group j at period p.scheduling
- the scheduling matrix to calculate the effective number of skill transfersnull
if skill transfer is not allowed.public boolean isFeasible(DoubleMatrix2D sl)
sl
- the service level to checktrue
if all service level targets has been reached, otherwise false
public void createChart(int[][] scheduling, String fileName, String excelFileName)
TwoStep
constructor.
This file contains some sheets:
.eps
image) of the
information reported in the Excel sheet grouped_staffing_load.scheduling
- the scheduling solutionfileName
- the filename of the image to plotexcelFileName
- the filename of the Excel file to createpublic void createChartForSL(DoubleMatrix2D sl)
.eps
images to report the service levels.
The image files are created in the folder whose name is passed to TwoStep
constructor.sl
- the service level matrix of the current solutionpublic double getBestSolutionCost()
public double getMIPGap()
public double getTotalTimeSec()
public static void main(String[] args) throws Exception
BatchSimParams
: batch means simulation parameters (needed by randomized search),
RepSimParams
: simulation by replication parameters to simulate to whole day,
TwoStepParams
: the parameters for the Two-step algorithm,
args
- see description of this methodException