public class SchedulingCP extends Object
SchedulingCPParams
.
This scheduling method is an iterative algorithm that solves a linear problem (using the solver Cplex) at each iteration, and adds new linear cuts based on the violated performance measure constraints. The algorithm starts with an infeasible solution (where constraints are violated), and adds new linear cuts to eliminate infeasible solution regions. It iterates until it finds a feasible solution that satisfies all the constraints. There are four levels of aggregation of the performance measure constraints:
Note that the user can choose to solve the linear problem by integer programming or to relax the integer variables and solve the continuous linear problem instead. Relaxing the integer variables requires an extra rounding procedure to obtain an integer scheduling solution. We use a simple threshold rounding procedure, such that a variable is rounded to its ceiling value if its fractional value is higher than this threshold, otherwise it is rounded down to its floor value.
To find the initial scheduling solution, the algorithm only considers the flow covering equations. These equations require the workload (service rates times the number of agents) to cover a certain (parameter specified by the user) proportion of the arrival rates. Note there are no subgradient-based cuts in the initialization step.
At the end of the algorithm, a local search SchedLocalSearch
is executed to improve the solution.
The local search is usually executed with longer (and more precise) simulations.
The local search is composed of 3 moves:
When the user chooses to relax the problem as a linear continuous problem, a rounding procedure is used to generate an integer solution. The best procedure found is to round each continuous variable based on a fractional threshold parameter. The cutting-plane algorithm stops at the first iteration where the rounded staffing requirement or the rounded and skill-transfered scheduling is feasible (by satisfying all constraints).
We have also tried a more sophisticated rounding procedure that involves iteratively fixing variables to their ceiling values and re-optimizing the LP. This approach is slower (due to multiple LP to optimize) and the cost is often greater than with the fractional threshold approach.
The simulator is required to estimate these two performance measures:
PerformanceMeasureType.SERVICELEVEL
and
PerformanceMeasureType.ABANDONMENTRATIO
.
This scheduling algorithm allows the user to set both minimum service level targets
and maximum abandonment ratio thresholds.
The service level targets are set in the call center parameters, as usual, and they
are retrieved by calling CallCenter.getServiceLevelParams(int)
.
To set the abandonment ration thresholds, the user needs to set a DoubleArray
named abandonThreshold
, which will be converted and place in the field SchedulingCPParams.abandonThresholdArray
.
Because the local search SchedLocalSearch
does not consider abandonment constraint,
we do not recommend the user to execute the local search at the end of the cutting-plane optimization,
if there are abandonment ratios constraints.
Modifier and Type | Class and Description |
---|---|
static class |
SchedulingCP.SimEvalResults
Contains the simulation results returned by the method
simEvalStaffing(int[][]) . |
Constructor and Description |
---|
SchedulingCP(CallCenterParams ccp,
SchedulingCPParams cp,
CallCenterSim sim,
String folder,
RepSimParams repsp,
RandomStream rand)
Constructs a new instance of the optimization algorithm.
|
Modifier and Type | Method and Description |
---|---|
void |
createChart(int[][] scheduling,
String fileName)
Creates an Excel file containing the results.
|
void |
createChartForSL(DoubleMatrix2D sl)
Creates an Excel file that report the given service levels.
|
double |
getBestObjective()
Returns the objective value of the best scheduling vector found.
|
int[][] |
getBestScheduling()
Returns the best scheduling solution found.
|
double |
getCost(int[][] scheduling)
Computes the cost of the scheduling solution.
|
double |
getCplexTimeSec()
Returns the total time taken by Cplex, in seconds.
|
int[][][] |
getEffectiveSkillTransfers(int[][] scheduling)
Returns the effective skill transfered agents.
|
int |
getNumSimCall()
Returns the number of simulation calls.
|
static int[] |
getShiftLengths(CallCenter cc,
boolean verbose)
Returns the shift length (number of paid periods) for each shift.
|
double |
getSimTimeSec()
Returns the total time taken by simulations in seconds.
|
int[][] |
getStaffing(int[][] scheduling)
From the scheduling (group, shifts) matrix, get the corresponding staffing
(group, periods) matrix.
|
int[][] |
getStaffing(int[][] scheduling,
boolean applySkillTransfer)
From the scheduling (group, shifts) solution, returns the corresponding staffing
(group, periods) solution.
|
double |
getTotalTimeSec()
Returns the total execution time, including the local search time, in seconds.
|
boolean |
isFeasible(DoubleMatrix2D sl,
DoubleMatrix2D aban)
Checks if the given service levels and abandonment ratios satisfy
all the targets.
|
static void |
main(String[] args)
Executes the scheduling algorithm based on the cutting-plane method.
|
void |
optimize()
Executes the cutting-plane algorithm, followed by a local search.
|
protected void |
printAbandonmentRatios(DoubleMatrix2D aban)
Prints the abandonment ratios with their targets in the output file.
|
void |
printSchedule()
Prints the current schedule solution.
|
protected void |
printServiceLevels(DoubleMatrix2D sl)
Prints the service levels with their targets in the output file.
|
void |
printSolution()
Prints both the current scheduling and the staffing solution (with skill transfers
applied if transfer mechanism is used).
|
void |
printSolution(boolean printSchedule,
boolean printStaffing)
Prints the solution in the
OUTPUT.txt file created in the folder passed to the
SchedulingCP(umontreal.iro.lecuyer.contactcenters.msk.params.CallCenterParams, umontreal.iro.lecuyer.ccoptim.scheduling.SchedulingCPParams, umontreal.iro.lecuyer.contactcenters.msk.CallCenterSim, java.lang.String, umontreal.iro.lecuyer.contactcenters.app.params.RepSimParams, umontreal.iro.lecuyer.rng.RandomStream) constructor. |
void |
printStaffing()
Prints the current staffing (with skill transfers applied, if skill transfer
mechanism is used).
|
protected void |
printViolatedAbanConstraints(DoubleMatrix2D aban)
Prints, in the output file, the violated abandonment ratio constraints.
|
protected void |
printViolatedSLConstraints(DoubleMatrix2D sl)
Prints, in the output file, the violated service level constraints.
|
SchedulingCP.SimEvalResults |
simEvalStaffing(int[][] y)
Simulates a staffing solution using a transient simulation.
|
public SchedulingCP(CallCenterParams ccp, SchedulingCPParams cp, CallCenterSim sim, String folder, RepSimParams repsp, RandomStream rand)
ccp
- the call center parameterscp
- the cutting-plane scheduling parameterssim
- the call center simulatorfolder
- the folder where to put the resultsrepsp
- the parameters of the simulator. The number of replications might be increased
during the local search.rand
- the random stream to be used by the optimization (mainly for local search)
If null
, a default random stream is used.public double getTotalTimeSec()
public double getSimTimeSec()
public double getCplexTimeSec()
public static int[] getShiftLengths(CallCenter cc, boolean verbose)
integerList
property named shiftLengths
inside
the element properties
.
However, the user should declare the shiftLengths
property if the shift lengths
do not correspond exactly to the sum of covered periods defined in the shiftMatrix
element.
For example, the user should declare shiftLengths
manually if, for some shifts, there are non-working periods
that are paid (like breaks or lunch time).cc
- the call center modelverbose
- if true
, then it prints the length (number of paid periods) of each shift.public int getNumSimCall()
public void optimize() throws ilog.concert.IloException
ilog.concert.IloException
public double getBestObjective()
public SchedulingCP.SimEvalResults simEvalStaffing(int[][] y)
y
- the staffing matrix (y[s][p] = number of agents of type s in the period p).public void printSolution()
boolean)
with arguments true, true
.public void printSchedule()
boolean)
with arguments true, false
.public void printStaffing()
boolean)
with arguments false, true
.public void printSolution(boolean printSchedule, boolean printStaffing)
OUTPUT.txt
file created in the folder passed to the
SchedulingCP(umontreal.iro.lecuyer.contactcenters.msk.params.CallCenterParams, umontreal.iro.lecuyer.ccoptim.scheduling.SchedulingCPParams, umontreal.iro.lecuyer.contactcenters.msk.CallCenterSim, java.lang.String, umontreal.iro.lecuyer.contactcenters.app.params.RepSimParams, umontreal.iro.lecuyer.rng.RandomStream)
constructor.printSchedule
- choose to print the current scheduleprintStaffing
- choose to print the current staffingilog.concert.IloException
protected void printViolatedSLConstraints(DoubleMatrix2D sl)
sl
- the service level matrixprotected void printServiceLevels(DoubleMatrix2D sl)
sl
- the service level matrixprotected void printViolatedAbanConstraints(DoubleMatrix2D aban)
SchedulingCPParams.checkAbandon
is set to false
,
then this method will do nothing, since there are no abandonment constraints.aban
- the abandonment ratio matrixprotected void printAbandonmentRatios(DoubleMatrix2D aban)
SchedulingCPParams.checkAbandon
is set to false
, then
the printed target will be 0.aban
- the abandonment ratio matrixpublic void createChart(int[][] scheduling, String fileName)
SchedulingCP(umontreal.iro.lecuyer.contactcenters.msk.params.CallCenterParams, umontreal.iro.lecuyer.ccoptim.scheduling.SchedulingCPParams, umontreal.iro.lecuyer.contactcenters.msk.CallCenterSim, java.lang.String, umontreal.iro.lecuyer.contactcenters.app.params.RepSimParams, umontreal.iro.lecuyer.rng.RandomStream)
constructor.
It contains a sheet with the total load and the total staffing for each period. The total load and the total staffing are obtained by summing the load and the staffing respectively of each call type and each agent group.
scheduling
- the scheduling solutionfileName
- the file name of the Excel filepublic void createChartForSL(DoubleMatrix2D sl)
SchedulingCP(umontreal.iro.lecuyer.contactcenters.msk.params.CallCenterParams, umontreal.iro.lecuyer.ccoptim.scheduling.SchedulingCPParams, umontreal.iro.lecuyer.contactcenters.msk.CallCenterSim, java.lang.String, umontreal.iro.lecuyer.contactcenters.app.params.RepSimParams, umontreal.iro.lecuyer.rng.RandomStream)
constructor.sl
- the service level matrixpublic double getCost(int[][] scheduling)
scheduling
- the scheduling solutionpublic boolean isFeasible(DoubleMatrix2D sl, DoubleMatrix2D aban)
sl
- the service levelsaban
- the abandonment ratiospublic int[][] getStaffing(int[][] scheduling)
scheduling
- the scheduling matrix.public int[][] getStaffing(int[][] scheduling, boolean applySkillTransfer)
scheduling
- the scheduling solutionapplySkillTransfer
- to apply the skill transfers or notpublic int[][][] getEffectiveSkillTransfers(int[][] scheduling)
null
if skill transfers are not allowed by the user.scheduling
- the scheduling solution to calculate the effective number of skill transfers.null
if skill transfers are not allowed.public int[][] getBestScheduling()
public static void main(String[] args) throws Exception
RepSimParams
: simulation parameters,
SchedulingCPParams
: the parameters for the cutting-plane algorithm,
args
- see the description of this methodCallCenterCreationException
Exception