public class RandomizedSearch extends Object
removeAgents(int[])
and switchAgents(int[])
, or
a hybrid remove-switch method removeSwitch(int[])
.
SimCorrector
that uses simulation.
When the user give the optimization parameters with RandomizedSearchParams
,
she can simply call multiOpt()
to execute the optimization,
which returns the best staffing solution found (with the lowest cost).
To reduce the execution time, the main search algorithm uses the approximation
LossDelayApprox
to evaluate the performance of the call center.
It is important to note that this approximation can have substantial errors.
At the end of the randomized search,
this program will execute a correction by simulation using SimCorrector
.
Modifier and Type | Class and Description |
---|---|
static class |
RandomizedSearch.SearchMode
Defines the available search moves for the randomized search.
|
Constructor and Description |
---|
RandomizedSearch(CallCenter cc,
RandomizedSearchParams rsp,
LossDelayApprox lda,
ContactCenterSim sim,
RandomStream rand)
Constructs a new randomized search instance that is ready to optimize
by calling
multiOpt() . |
Modifier and Type | Method and Description |
---|---|
double[] |
getAgentCost()
Returns a vector that contains the cost per agent per group.
|
int[] |
getFeasible()
Finds an initial staffing vector for the neighborhood search that is feasible
according to approximation
LossDelayApprox . |
int[] |
getFeasible(double beta,
double initSLTarget,
int maxCPUsec)
Finds an initial staffing vector for the randomized search that is feasible
according to the approximation
LossDelayApprox . |
int[] |
getFeasible(int[] staffing,
int maxCPUsec)
Finds an initial staffing vector, starting from the given staffing vector,
that is feasible (according to the approximation
LossDelayApprox ). |
RandomStream |
getRandomStream()
Returns the
RandomStream used by the randomized search. |
double |
getTimeGetLDFeasible()
Returns the total time spent in milliseconds in the procedure
getFeasible() . |
double |
getTimeLD()
Returns the total time spent in milliseconds by the
Loss-delay approximator.
|
double |
getTimeLDRemove()
Returns the total time spent in milliseconds in the procedure
removeAgents(int[]) . |
double |
getTimeLDRemoveSwitch()
Returns the total time spent in milliseconds in the procedure
removeSwitch(int[]) . |
double |
getTimeLDSwitch()
Returns the total time spent in milliseconds in the procedure
switchAgents(int[]) . |
double |
getTimeSim()
Returns the total time spent in milliseconds in simulation calls.
|
protected static int |
getTotalAgents(int[] staffing)
Counts the total number of agents in the given staffing vector.
|
double |
getTotalCost(int[] staffing)
Computes the total cost of the given staffing vector.
|
long |
getTotalNumLD()
Returns the number of executions by the approximator
LossDelayApprox . |
long |
getTotalNumSim()
Returns the number of calls to the simulator.
|
static void |
main(String[] args)
Executes the randomized search with the parameters
RandomizedSearchParams . |
int[] |
multiOpt()
Search the optimal solution with multiple start points.
|
int[] |
optimize()
Optimizes the call center and returns the best staffing vector found.
|
int[] |
optimize(RandomizedSearch.SearchMode mode,
boolean findInitialStaffing,
double cr,
double initSLTarget,
int maxCPUsec)
Optimizes the call center and returns the best staffing vector found.
|
int[] |
optimize(RandomizedSearch.SearchMode mode,
boolean findInitialStaffing,
int[] initStaffing,
double cr,
double initSLTarget,
int maxCPUsec)
Executes a single run of the randomized search and returns the best staffing vector found.
|
protected static void |
printStaffing(int[] staffing)
Prints the number of agents in the given staffing vector.
|
int[] |
removeAgents(int[] staffing)
Starting from the given initial staffing vector, this method reduces the staffing until
it cannot remove any more agent while keeping the feasibility of the solution.
|
int[] |
removeAgents(int[] staffing,
int maxCPUsec)
Similar to the method
removeAgents(int[]) but with the given
CPU time limit. |
int[] |
removeAgents(int maxCand,
double delta,
int[] staffing,
int maxCPUsec)
Starting from the given initial staffing vector, this method reduces the staffing until
it cannot remove any more agent while keeping the feasibility of the solution.
|
int[] |
removeSwitch(int[] staffing)
Performs a mix of
removeAgents(int[]) and switchAgents(int[]) on the given staffing vector. |
int[] |
removeSwitch(int[] staffing,
int maxCPUsec)
Similar to
removeSwitch(int[]) , but the given CPU time limit is used. |
int[] |
removeSwitch(int maxCand,
double delta,
int[] staffing,
int maxCPUSec)
Performs a mix of
removeAgents(int[]) and switchAgents(int[]) on the given staffing vector. |
int[] |
simCorrection(int[] staffing)
Applies the correction by simulation procedures on the given staffing vector
and returns the corrected vector.
|
int[] |
switchAgents(int[] staffing)
Switches agents from most expensive groups to less expensive groups, while
satisfying the service level targets.
|
int[] |
switchAgents(int[] staffing,
int maxCPUsec)
Similar to
switchAgents(int[]) but with the given CPU time limit. |
int[] |
switchAgents(int maxCand,
double delta,
int[] staffing,
int maxCPUsec)
Switches agents from most expensive groups to less expensive groups, while
satisfying the service level targets.
|
public RandomizedSearch(CallCenter cc, RandomizedSearchParams rsp, LossDelayApprox lda, ContactCenterSim sim, RandomStream rand)
multiOpt()
.
In order to limit the CPU time, the randomized search uses the approximation LossDelayApprox
to
evaluate the performance measures of the solutions.
Simulation is used to correct the final solution, using SimCorrector
.
The period to optimize is specified by the parameter RandomizedSearchParams.currentPeriod
.
The evaluation period for lda
and
sim
are modified in consequence
by calling ContactCenterEval.setEvalOption(umontreal.iro.lecuyer.contactcenters.app.EvalOptionType, java.lang.Object)
.
cc
- the parameters of the call centerrsp
- the parameters for the randomized searchlda
- the approximation LossDelayApprox
used for the randomized searchsim
- the simulator that will be used to correct the final solutionrand
- the random stream that will be used when the optimizer needs
to generate random numbers. If null
, then it will use
the random generator MRG32k3a
by default.public int[] multiOpt()
RandomizedSearchParams.initSLTarget
times the
number of RandomizedSearchParams.lowestCostRatio
.
For each run, it will execute optimize()
.
At the last step, this method will execute a correction by simulation using SimCorrector
.public int[] optimize()
boolean, int[], double, double, int)
with the parameters given by RandomizedSearchParams
, with the first
value of the vector RandomizedSearchParams.lowestCostRatio
and
RandomizedSearchParams.initSLTarget
.
The randomized search uses the approximation LossDelayApprox
to evaluate the performance measures.
This method does not call SimCorrector
to correct the solution by simulation.
public int[] optimize(RandomizedSearch.SearchMode mode, boolean findInitialStaffing, double cr, double initSLTarget, int maxCPUsec)
boolean, int[], double, double, int)
with a null
argument for the initial staffing vector.mode
- choose to use remove and switch moves simultaneously or
sequentiallyfindInitialStaffing
- if true
, the optimizer will
compute an initial staffing vector, else the staffing vector
defined in the call center parameters will be used as the
initial staffingcr
- cost ratio used if findInitialStaffing
is true
initSLTarget
- the target service level used if if findInitialStaffing
is true
maxCPUsec
- the maximum CPU time limit is second allow for this function
(including the sub functions)public int[] optimize(RandomizedSearch.SearchMode mode, boolean findInitialStaffing, int[] initStaffing, double cr, double initSLTarget, int maxCPUsec)
multiOpt()
will execute multiple runs with different
starting solutions, and will correct the solution by simulation using SimCorrector
.
The randomized search uses the approximation LossDelayApprox
to evaluate the performance measures.
The user should correct the returned staffing solution with SimCorrector
.mode
- chooses to use removeAgents-switch move simultaneously or
sequentiallyfindInitialStaffing
- if true
, the optimizer will
compute an initial staffing vector, else the staffing vector
defined in the call center parameters will be used as the
initial staffinginitStaffing
- if findInitialStaffing
is false
, then
it will set this vector as the initial staffing, unless it is null
.
In the last case (staffing vector is null
and findInitialStaffing
is false
,
the staffing vector defined in the call center model is used.
Deep copy is used, so the input staffing vector will remain unchanged.cr
- cost ratio used if findInitialStaffing
is true
initSLTarget
- the target service level used if findInitialStaffing
is true
maxCPUsec
- the maximum CPU time limit (in seconds) allocated for this methodpublic int[] simCorrection(int[] staffing)
RandomizedSearchParams.simFeasiblePriority
,
RandomizedSearchParams.useSimRemove
and RandomizedSearchParams.useSimSwitch
.
The returned staffing vector should be feasible according to simulation.staffing
- the staffing vector to correct. Deep copy done;
this input parameter remains unchanged.public int[] getFeasible()
LossDelayApprox
.
This method will execute double, int)
with the
first parameters of RandomizedSearchParams.lowestCostRatio
and
RandomizedSearchParams.initSLTarget
, and the CPU limit time
RandomizedSearchParams.maxRSCPUsec
.public int[] getFeasible(int[] staffing, int maxCPUsec)
LossDelayApprox
).
If the given staffing is not feasible, it is incremented
until feasibility is reached (both for the global service level and per call
type service level).staffing
- the staffing vector to become feasible. Deep copy is
performed; so this parameter remains unchanged.maxCPUsec
- the maximum CPU time allocated to this methodpublic int[] getFeasible(double beta, double initSLTarget, int maxCPUsec)
LossDelayApprox
.beta
- the ratio of agents to be allocated to the cheapest skill group
of each call type. This would correspond to the parameter
RandomizedSearchParams.lowestCostRatio
.
For each call type, if there are multiple groups have the lowest per agent cost,
then this method will select the smallest-index group.initSLTarget
- the service level target used by the root-finding procedure
to initialize the staffing vector. This value should be set around the real
service level target of the call center. However, the user
may give a different target in order to adjust for approximation errors.maxCPUsec
- the CPU time limit allocated to this methodLossDelayApprox
.
However, the staffing may be infeasible if the time limit has expired.public int[] removeAgents(int[] staffing)
LossDelayApprox
to
evaluate the performance measures and the feasibility of the solutions.
This method calls the procedure double, int[], int)
with the parameters defined in RandomizedSearchParams
.staffing
- the initial staffing vector to be reduced; it should be feasible
according to approximationpublic int[] removeAgents(int[] staffing, int maxCPUsec)
removeAgents(int[])
but with the given
CPU time limit.staffing
- the initial staffing vector to be reduced; it should be feasible
according to approximationmaxCPUsec
- the maximum CPU time that can be spent inside this methodpublic int[] removeAgents(int maxCand, double delta, int[] staffing, int maxCPUsec)
LossDelayApprox
to
evaluate the performance measures and the feasibility of the solutions.maxCand
- the maximum solution candidates to test at each iteration (set
lower number to reduce optimization time). Minimum is 1.delta
- ratio of the number of possible reduction over maxCand
is added to the test. If the ratio is 1, then it will test
every possible case.staffing
- the initial staffing vector to be reduced. Deep copy done;
so the input vector remains unchanged. This staffing vector should be feasible
according to approximationmaxCPUsec
- the CPU time limit allocated for this methodpublic int[] switchAgents(int[] staffing)
LossDelayApprox
.
The returned staffing remains feasible according to the approximation.
This method calls double, int[], int)
with
the parameters defined in RandomizedSearchParams
.staffing
- the initial staffing vector to be switched; it should be feasible
according to approximationpublic int[] switchAgents(int[] staffing, int maxCPUsec)
switchAgents(int[])
but with the given CPU time limit.staffing
- the initial staffing vector to be switched; it should be feasible
according to approximationmaxCPUsec
- the CPU time limit, in seconds, allocated for this methodpublic int[] switchAgents(int maxCand, double delta, int[] staffing, int maxCPUsec)
LossDelayApprox
.
The returned staffing remains feasible according to the approximation.maxCand
- the maximum number of solution candidates to test at each iteration
(set lower number to reduce CPU time). Minimum is 1.delta
- ratio of the number of possible reduction over maxCand
is added to the test. If the ratio is 1, then it will test
every possible case. This value must be between 0 and 1, inclusively.staffing
- the initial staffing vector to be switched; it should be feasible
according to approximationmaxCPUsec
- the CPU time limit, in seconds, allocated for this methodpublic int[] removeSwitch(int[] staffing)
removeAgents(int[])
and switchAgents(int[])
on the given staffing vector.
For a random number q, if it cannot remove q agents from any groups,
then it will try to apply the switch method.
It evaluates the staffing solution by approximation LossDelayApprox
.
This method calls double, int[], int)
with the parameters given by RandomizedSearchParams
.
The return staffing vector remains feasible according to approximation.staffing
- the initial staffing vector; it must be feasible according to approximationpublic int[] removeSwitch(int[] staffing, int maxCPUsec)
removeSwitch(int[])
, but the given CPU time limit is used.staffing
- the initial staffing vector; it must be feasible according
to approximationmaxCPUsec
- the CPU time limit, in seconds, allocated for this methodpublic int[] removeSwitch(int maxCand, double delta, int[] staffing, int maxCPUSec)
removeAgents(int[])
and switchAgents(int[])
on the given staffing vector.
For a random number q, if it cannot remove q agents from any groups,
then it will try to apply the switch method.
It evaluates the staffing solution by approximation LossDelayApprox
.
The return staffing vector remains feasible according to approximation.maxCand
- the maximum number of solution candidates to test at each iteration
(set lower number to reduce CPU time)delta
- the ratio of the number of possible reductions over maxCand
is added to the test. If the ratio is 1, then it will test
every possible case.staffing
- the starting staffing vector; it must be feasible according to approximationmaxCPUSec
- the maximum CPU time allocated for this methodprotected static void printStaffing(int[] staffing)
staffing
- the staffing vector to printprotected static int getTotalAgents(int[] staffing)
staffing
- the staffing vectorpublic double getTotalCost(int[] staffing)
staffing
- the staffing vectorpublic double[] getAgentCost()
public long getTotalNumLD()
LossDelayApprox
.LossDelayApprox
.public long getTotalNumSim()
public double getTimeLD()
public double getTimeSim()
public double getTimeGetLDFeasible()
getFeasible()
.public double getTimeLDRemove()
removeAgents(int[])
.public double getTimeLDSwitch()
switchAgents(int[])
.public double getTimeLDRemoveSwitch()
removeSwitch(int[])
.public RandomStream getRandomStream()
RandomStream
used by the randomized search.public static void main(String[] args) throws Exception
RandomizedSearchParams
.
This program calls multiOpt()
.
The arguments are:
args
- the parameter filesException