ContactCenters
V. 0.9.9.

umontreal.iro.lecuyer.contactcenters.router
Class OverflowAndPriorityRouter

java.lang.Object
  extended by umontreal.iro.lecuyer.contactcenters.router.Router
      extended by umontreal.iro.lecuyer.contactcenters.router.OverflowAndPriorityRouter
All Implemented Interfaces:
NewContactListener

public class OverflowAndPriorityRouter
extends Router

Represents a routing policy allowing contacts to overflow from one set of agents to another, and agents to pick out queued contacts based on priorities that can change at predefined moments during the waiting time. This routing policy also supports some forms of conditional routing. However, the router using this policy might be slow, because of the more complex management of queues. Therefore, if conditional routing is not needed, or if priorities do not change with time, it might be faster to use a simpler policy such as AgentsPrefRouter or AgentsPrefRouterWithDelays. The latter policy also supports some forms of priorities changing with time.

We now describe the policy in details. The agent selection of any new contact C of type k using this policy is based on a sequence of stages. Each stage is defined by a triplet (wk, j, fk, j(X, C), gk, j(X, C)) where wk, j is a minimal waiting time, fk, j(X, C) is a function returning a vector of ranks for agent selection, and gk, j(X, C) is another function returning a vector of ranks for queueing. For any call type k = 0,…, K - 1, we have 0≤wk, 0 < wk, 1 < ... . Often, we have fk, j = gk, j. The vectors returned by these functions can depend on the contact but also on the state X of the system, which allows the implementation of some forms of conditional routing.

More specifically, when a contact of type k arrives, the router checks the first triplet (wk, 0, fk, 0, gk, 0). If wk, 0 > 0, the contact waits for wk, 0 time units in an extra waiting queue no agent has access to; this can be used to model a positive routing delay. Then, the function fk, 0(X, C) is evaluated on the new contact C to get a vector of ranks (r0,…, rI-1). These ranks determine which agent groups can be selected for the new contact, and the priority for each group. The smaller is ri, the higher is the priority for the agent group i. If ri = ∞, the contact cannot be sent to agent group i at this stage of routing.

The router selects the agent group with the smallest value ri among the groups containing at least one free agent. If a single group with this minimal rank exists, the contact is sent to a free agent in it, and routing is done. Otherwise, a score Si is associated with each group with minimal rank, and the group with the highest score is selected. Usually, the score corresponds to the longest idle time of agents in the group.

If no agent group can be assigned to the new contact, the contact is put into one or more waiting queues. There is one priority queue per agent group, and an extra queue storing contacts not queued to any agent group. To select the waiting queues, the router applies the function gk, 0(X, C) on the new contact to get a vector (q0,…, qI-1) of ranks. The rank qi determines the priority of the contact in queue i. The smaller is the rank, the higher is the priority. An infinite rank qi prevents the contact to be put in queue i. Often, the priority is the same for every waiting queue allowed for the contact, but priorities may differ in general. If all ranks qi are infinite, the contact goes into the extra queue.

When an agent becomes free, it looks for a contact in the queue associated with its group only. The contacts in this queue are sorted in increasing order of rank. Contacts sharing the same rank are sorted in decreasing order of score. The default function for the score is the time spent in queue. When a contact is removed from a queue, it is also removed from every other queue managed by the router.

If the contact waits for w1 time units in queue without abandoning or being served, a new agent selection happens. The selection is similar to the first one, except that a new function, fk, 1(X, C), is used to generate the vector of ranks. The ranks can thus evolve with time. If no agent group is available for the contact at this second stage of routing, a waiting queue update occurs. For this, a vector of ranks is generated using gk, 1(X, C), and used to determine the new priority of the contact, for each queue. If the priority qi goes from an infinite to a finite value, the contact joins queue i. If the priority goes from a finite to an infinite value, the contact leaves queue i. If the priority changes from a finite value to another finite value, the position of the contact in queue is updated. The priority of a contact can thus evolve with time. This process is repeated at waiting time w2, w3, and so on, for all stages of routing.

A contact leaving all waiting queues linked to agent groups at a given stage is put into the extra waiting queue. It can still abandon, but it cannot be served until a subsequent stage of routing puts it back into a waiting queue linked to an agent group. On the other hand, if a contact enters a queue linked to an agent group at a given stage of routing, it leaves the extra queue. Moreover, even if the contact changes queue, it keeps the same residual patience time; changing waiting queue does not reset the maximal queue time.

For example, suppose that a contact of type k can be served by two agent groups, 0 and 1. A newly arrived contact has access to group 0 only, and is queued with priority 1 if it cannot be served immediately. However, after s seconds of wait, the contact gains access to group 1. It is queued to this new group with priority 1, but the priority with original group 0 changes to 2 (a lower priority). The parameters for such a routing would be (0,(1,∞),(1,∞)), (s,(1, 1),(2, 1)). For an example with conditional routing, suppose that at waiting time s, the priorities depend on the service level observed in the last m minutes.


Nested Class Summary
static class OverflowAndPriorityRouter.RoutingInfo
          Represents information about the routing for a particular contact.
 
Field Summary
 
Fields inherited from class umontreal.iro.lecuyer.contactcenters.router.Router
BLOCKTYPE_CANTQUEUE, BLOCKTYPE_NOLINE, BLOCKTYPE_QUEUEFULL, DEQUEUETYPE_BEGINSERVICE, DEQUEUETYPE_FANTOM, DEQUEUETYPE_NOAGENT, DEQUEUETYPE_TRANSFER, dqTypeRet
 
Constructor Summary
OverflowAndPriorityRouter(int numGroups, RoutingStageInfo[][] stages)
          Constructs a new overflow and priority router with numGroups agent groups, and stages for information about routing stages.
 
Method Summary
 boolean canServe(int i, int k)
          Returns true if and only if some agents in group i are authorized to serve contacts of type k by this router.
protected  void checkWaitingQueues(AgentGroup group)
          This method is called when the agent group group contains no more online agents, i.e., AgentGroup.getNumAgents() returns 0.
protected  void dequeued(DequeueEvent ev)
          This method is called when a contact leaves a waiting queue, ev representing the corresponding dequeue event.
 AgentSelectionScore getAgentSelectionScore()
          Returns the current mode of computation for the agent selection score.
 ContactSelectionScore getContactSelectionScore()
          Returns the current mode of computation for the contact selection score.
 Comparator<? super DequeueEvent> getNeededWaitingQueueComparator(int q)
          Determines how contacts in queue should be compared with each other for waiting queue q.
 WaitingQueueStructure getNeededWaitingQueueStructure(int q)
          Returns the needed data structure for waiting queue with index q.
protected  double getReroutingDelay(DequeueEvent dqEv, int numReroutingsDone)
          Returns the delay, in simulation time units, after which a queued contact should be rerouted.
protected  double getScoreForAgentSelection(Contact ct, AgentGroup testGroup, Agent testAgent)
          Returns the score for contact ct associated with agent group testGroup and agent testAgent.
protected  double getScoreForContactSelection(DequeueEvent ev)
          Returns the score for the queued contact represented by ev.
 WaitingQueueType getWaitingQueueType()
          Returns an indicator describing how the implemented routing policies organizes waiting queues.
 double[][] getWeightsGT()
          Returns the matrix of weights defining $ \wGT$(i, k) for each contact type and agent group.
 double[][] getWeightsTG()
          Returns the matrix of weights defining $ \wTG$(k, i) for each contact type and agent group.
 boolean needsDetailedAgentGroup(int i)
          Determines if the agent group i should consider individual agents.
protected  EndServiceEvent selectAgent(Contact contact)
          Begins the service of the contact contact by trying to assign it a free agent.
protected  EndServiceEvent selectAgent(Contact contact, OverflowAndPriorityRouter.RoutingInfo info)
           
protected  EndServiceEvent selectAgent(DequeueEvent dqEv, int numReroutingsDone)
          Selects an agent for serving a queued contact in the context of rerouting.
protected  DequeueEvent selectContact(AgentGroup group, Agent agent)
          Returns a dequeue event representing a queued contact to be served by the agent agent in agent group group.
protected  DequeueEvent selectWaitingQueue(Contact contact)
          Selects a waiting queue and puts the contact contact into it.
protected  DequeueEvent selectWaitingQueue(Contact contact, OverflowAndPriorityRouter.RoutingInfo info)
           
protected  DequeueEvent selectWaitingQueue(DequeueEvent dqEv, int numReroutingsDone)
          Selects a waiting queue for a queued contact in the context of rerouting.
 void setAgentSelectionScore(AgentSelectionScore agentSelectionScore)
          Sets the way scores for agent selection are computed to agentSelectionScore.
 void setContactSelectionScore(ContactSelectionScore contactSelectionScore)
          Sets the way scores for contact selection are computed to contactSelectionScore.
 void setWeightsGT(double[][] weightsGT)
          Sets the matrix of weights defining $ \wGT$(i, k) for each k and i to weightsGT.
 void setWeightsTG(double[][] weightsTG)
          Sets the matrix of weights defining $ \wTG$(k, i) for each k and i to weightsTG.
 
Methods inherited from class umontreal.iro.lecuyer.contactcenters.router.Router
addExitedContactListener, agentReroutingEventsIterator, beginService, checkFreeAgents, clearExitedContactListeners, contactReroutingEventsIterator, endContact, endService, enqueued, exitBlocked, exitDequeued, exitServed, formatAgentGroups, formatWaitingQueues, getAgentGroup, getAgentGroupListener, getAgentGroups, getAgentReroutingEvents, getContactFactory, getContactReroutingEvents, getCurrentQueueSize, getDescription, getDialers, getExitedContactListeners, getNumAgentGroups, getNumContactTypes, getNumWaitingQueues, getReroutingDelay, getTotalQueueCapacity, getWaitingQueue, getWaitingQueueListener, getWaitingQueues, init, isKeepingReroutingEvents, mustClearWaitingQueue, newContact, notifyBlocked, notifyDequeued, notifyServed, removeExitedContactListener, restore, save, selectContact, setAgentGroup, setClearWaitingQueue, setClearWaitingQueues, setContactFactory, setKeepingReroutingEvents, setTotalQueueCapacity, setWaitingQueue, startDialers, toLongString, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

OverflowAndPriorityRouter

public OverflowAndPriorityRouter(int numGroups,
                                 RoutingStageInfo[][] stages)
Constructs a new overflow and priority router with numGroups agent groups, and stages for information about routing stages. The 2D array stages must contain K rows, each row giving a routing script for a specific contact type.

Parameters:
numGroups - the number of agent groups.
stages - the information about routing stages.
Throws:
NullPointerException - if stages is null.
IllegalArgumentException - if numGroups is negative or a list of stages are not ordered with respect to waiting time, for at least one contact type.
Method Detail

getWeightsTG

public double[][] getWeightsTG()
Returns the matrix of weights defining $ \wTG$(k, i) for each contact type and agent group. These weights are used by getScoreForAgentSelection(Contact,AgentGroup,Agent) to compute scores for agent groups, and default to 1 if they are not set by setWeightsTG(double[][]).

Returns:
the matrix of weights defining $ \wTG$(k, i).

setWeightsTG

public void setWeightsTG(double[][] weightsTG)
Sets the matrix of weights defining $ \wTG$(k, i) for each k and i to weightsTG.

Parameters:
weightsTG - the new matrix of weights defining $ \wTG$(k, i).
Throws:
NullPointerException - if weightsTG is null.
IllegalArgumentException - if weightsTG is not rectangular or has wrong dimensions.

getWeightsGT

public double[][] getWeightsGT()
Returns the matrix of weights defining $ \wGT$(i, k) for each contact type and agent group. These weights are used by getScoreForContactSelection(DequeueEvent) to give scores to waiting queues, and default to 1 if they are not set by setWeightsGT(double[][]).

Returns:
the matrix of weights defining $ \wGT$(i, k).

setWeightsGT

public void setWeightsGT(double[][] weightsGT)
Sets the matrix of weights defining $ \wGT$(i, k) for each k and i to weightsGT.

Parameters:
weightsGT - the new matrix of weights defining $ \wGT$(i, k).
Throws:
NullPointerException - if weightsGT is null.
IllegalArgumentException - if weightsGT is not rectangular or has wrong dimensions.

getAgentSelectionScore

public AgentSelectionScore getAgentSelectionScore()
Returns the current mode of computation for the agent selection score. The default value is AgentSelectionScore.LONGESTIDLETIME.

Returns:
the way the score is computed for agent selection.

setAgentSelectionScore

public void setAgentSelectionScore(AgentSelectionScore agentSelectionScore)
Sets the way scores for agent selection are computed to agentSelectionScore.

Parameters:
agentSelectionScore - the way scores for agent selection are computed.
Throws:
NullPointerException - if agentSelectionScore is null.

getContactSelectionScore

public ContactSelectionScore getContactSelectionScore()
Returns the current mode of computation for the contact selection score. The default value is ContactSelectionScore.LONGESTWAITINGTIME.

Returns:
the way the score is computed for contact selection.

setContactSelectionScore

public void setContactSelectionScore(ContactSelectionScore contactSelectionScore)
Sets the way scores for contact selection are computed to contactSelectionScore.

Parameters:
contactSelectionScore - the way scores for contact selection are computed.
Throws:
NullPointerException - if contactSelectionScore is null.

canServe

public boolean canServe(int i,
                        int k)
Description copied from class: Router
Returns true if and only if some agents in group i are authorized to serve contacts of type k by this router.

Specified by:
canServe in class Router
Parameters:
i - the agent group index.
k - the contact type index.
Returns:
determines if contacts can be served.

checkWaitingQueues

protected void checkWaitingQueues(AgentGroup group)
Description copied from class: Router
This method is called when the agent group group contains no more online agents, i.e., AgentGroup.getNumAgents() returns 0. It must check each waiting queue accessible for agents in this group to determine if they need to be cleared. A queue is cleared if no agent, whether free or busy, is available to serve any contact in it.

Specified by:
checkWaitingQueues in class Router
Parameters:
group - the agent group with no more agents.

selectAgent

protected EndServiceEvent selectAgent(Contact contact)
Description copied from class: Router
Begins the service of the contact contact by trying to assign it a free agent. The method must select an agent group with a free agent (or a specific free agent), start the service, and return the end-service event if the service was started, or null otherwise.

Specified by:
selectAgent in class Router
Parameters:
contact - the contact being routed to an agent.
Returns:
the end-service event representing the started service, or null if the contact could not be served immediately.

selectAgent

protected EndServiceEvent selectAgent(Contact contact,
                                      OverflowAndPriorityRouter.RoutingInfo info)

selectWaitingQueue

protected DequeueEvent selectWaitingQueue(Contact contact)
Description copied from class: Router
Selects a waiting queue and puts the contact contact into it. Returns the dequeue event if the contact could be queued, or null otherwise.

Specified by:
selectWaitingQueue in class Router
Parameters:
contact - the contact being queued.
Returns:
the dequeue event representing the queued contact, or null if the contact could not be queued.

selectWaitingQueue

protected DequeueEvent selectWaitingQueue(Contact contact,
                                          OverflowAndPriorityRouter.RoutingInfo info)

getNeededWaitingQueueComparator

public Comparator<? super DequeueEvent> getNeededWaitingQueueComparator(int q)
Description copied from class: Router
Determines how contacts in queue should be compared with each other for waiting queue q. This comparator is used by a simulator to construct a waiting queue if Router.getNeededWaitingQueueStructure(int) returns WaitingQueueStructure.SORTEDSET or WaitingQueueStructure.PRIORITY. By default, this returns null.

Overrides:
getNeededWaitingQueueComparator in class Router
Parameters:
q - the index of the waiting queue.
Returns:
the waiting queue comparator.

getNeededWaitingQueueStructure

public WaitingQueueStructure getNeededWaitingQueueStructure(int q)
Description copied from class: Router
Returns the needed data structure for waiting queue with index q. This method is used by the simulator to get clues on how to construct the waiting queue; it does not affect directly the implementation of the waiting queue returned by Router.getWaitingQueue(int). By default, this returns WaitingQueueStructure.LIST.

Overrides:
getNeededWaitingQueueStructure in class Router
Parameters:
q - the index of the waiting queue.
Returns:
the structure indicator.

getWaitingQueueType

public WaitingQueueType getWaitingQueueType()
Description copied from class: Router
Returns an indicator describing how the implemented routing policies organizes waiting queues. The supported modes of organization cover the most common cases only: waiting queues corresponding to contact types or agent groups. For any other modes, the WaitingQueueType.GENERAL must be used.

By default, this method returns WaitingQueueType.GENERAL.

Overrides:
getWaitingQueueType in class Router
Returns:
the organization mode of waiting queues.

needsDetailedAgentGroup

public boolean needsDetailedAgentGroup(int i)
Description copied from class: Router
Determines if the agent group i should consider individual agents. This does not determine directly how the agent group returned by Router.getAgentGroup(int) is implemented. This method only gives clues to a simulator on how to construct the concerned agent group.

Overrides:
needsDetailedAgentGroup in class Router
Parameters:
i - the index of the agent group.
Returns:
the detailed status of the agent group.

getReroutingDelay

protected double getReroutingDelay(DequeueEvent dqEv,
                                   int numReroutingsDone)
Description copied from class: Router
Returns the delay, in simulation time units, after which a queued contact should be rerouted. The value of numReroutingsDone gives the number of preceding reroutings, and dqEv is the dequeue event. If this delay is negative, infinite, or NaN, no rerouting happens for the contact. numReroutings will be -1 when this method is called at the time the contact is queued. By default, this method returns Double.POSITIVE_INFINITY.

Overrides:
getReroutingDelay in class Router
Parameters:
dqEv - the dequeue event representing the queued contact.
numReroutingsDone - the number of reroutings so far.
Returns:
the rerouting delay.

selectAgent

protected EndServiceEvent selectAgent(DequeueEvent dqEv,
                                      int numReroutingsDone)
Description copied from class: Router
Selects an agent for serving a queued contact in the context of rerouting. The event dqEv is used to represent the dequeued contact, while numReroutingsDone indicates the number of reroutings that has happened so far. The method should return the end-service event corresponding to the contact's new service by an agent, or null for the contact to stay in queue.

Overrides:
selectAgent in class Router
Parameters:
dqEv - the dequeue event representing the queued contact.
numReroutingsDone - the number of preceding reroutings.
Returns:
the end-service event, or null.

selectWaitingQueue

protected DequeueEvent selectWaitingQueue(DequeueEvent dqEv,
                                          int numReroutingsDone)
Description copied from class: Router
Selects a waiting queue for a queued contact in the context of rerouting. The event dqEv is used to represent the queued contact, while numReroutingsDone indicates the number of reroutings that has happened so far. The method should return the dequeue event corresponding to the contact's new queue, or null if the contact is required to leave the system. If no transfer of queue is required, this method should return dqEv. If a transfer occurs, one can use the Router.dqTypeRet field to store the dequeue type of the contact leaving the queue.

Overrides:
selectWaitingQueue in class Router
Parameters:
dqEv - the dequeue event representing the queued contact.
numReroutingsDone - the number of preceding reroutings.
Returns:
the dequeue event, or null.

selectContact

protected DequeueEvent selectContact(AgentGroup group,
                                     Agent agent)
Description copied from class: Router
Returns a dequeue event representing a queued contact to be served by the agent agent in agent group group. If agent is null, the method must return a contact that can be served by any agent in the group. If no contact is available, this method returns null. The selected contacts come from waiting queues attached to the router. Before the selected contact is returned, it must be removed from its queue with dequeue type Router.DEQUEUETYPE_BEGINSERVICE, e.g., by using queue.removeFirst (DEQUEUETYPE_BEGINSERVICE), or queue.remove (ev, DEQUEUETYPE_BEGINSERVICE), etc.

Generally, it is sufficient to override this method instead of Router.checkFreeAgents(AgentGroup,Agent). One can override Router.checkFreeAgents(AgentGroup,Agent) to improve efficiency when looking for contacts in the same waiting queue. This method is not abstract and returns null by default in order to allow Router.checkFreeAgents(AgentGroup,Agent) to be overridden without implementing this method.

Overrides:
selectContact in class Router
Parameters:
group - the affected agent group.
agent - the agent having ended its service.
Returns:
the dequeue event representing the contact being selected.

dequeued

protected void dequeued(DequeueEvent ev)
Description copied from class: Router
This method is called when a contact leaves a waiting queue, ev representing the corresponding dequeue event. By default, for any effective dequeue type other than 0, this calls Router.exitDequeued(DequeueEvent). This method should not notify an exiting contact for a 0 dequeue type since it is reserved for queued and served contacts.

Overrides:
dequeued in class Router
Parameters:
ev - the dequeue event.

getScoreForAgentSelection

protected double getScoreForAgentSelection(Contact ct,
                                           AgentGroup testGroup,
                                           Agent testAgent)
Returns the score for contact ct associated with agent group testGroup and agent testAgent. When selecting an agent for contact ct, if there are several agent groups with the same minimal rank, the agent group with the greatest score is selected. Returning a negative infinite score prevents an agent group from being selected.

By default, this returns a score depending on the return value of getAgentSelectionScore(). This can return the longest weighted idle time (the default), the weighted number of free agents, or the weight only. See AgentSelectionScore for more information.

Parameters:
ct - the contact being assigned an agent.
testGroup - the tested agent group.
testAgent - the tested agent, can be null.
Returns:
the score given to the association between the contact and the agent.

getScoreForContactSelection

protected double getScoreForContactSelection(DequeueEvent ev)
Returns the score for the queued contact represented by ev.

By default, this returns a score depending on the return value of getContactSelectionScore(). This can return the weighted waiting time (the default), the weighted number of queued agents, or the weight only. See ContactSelectionScore for more information.

Parameters:
ev - the dequeue event.
Returns:
the assigned score.

ContactCenters
V. 0.9.9.

To submit a bug or ask questions, send an e-mail to Richard Simard.