Contact center scheduling using integer programming

• US 7,725,339 B1
• Filed: 07/07/2003
• Issued: 05/25/2010
• Est. Priority Date: 07/07/2003
• Status: Active Grant

• Current Assignee: inContact Incorporated (Nice Ltd)
• Original Assignee: AC2 Solutions, Inc. (Nice Ltd)
• Inventors: Aykin, Turgut
• Primary Examiner(s): Jeanty; Romain
• Assistant Examiner(s): FEENEY, BRETT A
• Application Number:
  US10/614,483
• Time in Patent Office: 2,514 Days
• Field of Search: None
• US Class Current: 705/7.14
• CPC Class Codes: G06Q 10/063112 Skill-based matching of a person or a group to a task
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

The present invention relates to a method for workforce scheduling in which workload and workload types vary during scheduling period. The method acquires agent and skill requirements for all periods and contact types; acquires the contact center information including agent skill groups, agent work groups, tour and shift scheduling rules, agent availability, objective criterion to be optimized and its parameters; develops a Mixed Integer Linear Programming (MILP) model for the scheduling environment; applied an optimization algorithm that uses the Branch and Bound algorithm with a Rounding Algorithm to improve performance; and locates a globally optimal or near optimal workforce schedule in total cost or paid time or agent satisfaction. Detailed schedules may be developed by assigning daily shifts to work patterns, and breaks scheduled to daily shifts.

Claims

1. A computer implemented system for developing an optimized workforce schedule for a plurality of agents, each with a combination of defined skills and belonging to a skill group with agents having the same skills, to serve one or more contact types such as telephone calls, email, and other interaction media, a plurality of tour types with defined scheduling rules, located at one or more contact centers each with its own operating hours and time zones, comprising the steps of:

(a) acquiring agent requirements, b^r_h, for each contact type, and for each period and day to be scheduled by a computer;

(b) acquiring tour, shift, days-off, and break scheduling rules, agent skill groups, agent availability, and objective criterion to be optimized and its parameters by a computer;

(c) formulating the constraints and objective function of a Mixed Integer Programming (MILP) model with the tour types and associated scheduling rules including consistent and non-consistent daily start time requirements, a plurality of relief and lunch breaks each with a duration of one or more planning periods and a break window during which the break must be started and completed, agent requirements for a plurality of contact types and for each period to be scheduled, a plurality of agent skills and skill groups, agent availability, and agent costs by a computer;

wherein formulating the constraints and objective function of the MILP model comprises;

Minimize

Σ

<sub>jε

J</sub>Σ

<sub>1ε

QLk</sub>Σ

<sub>k∈

QKj</sub>C^j_k1Q^j_k1+Σ

<sub>jε

J</sub>Σ

<sub>k∈

QKj</sub>Σ

<sub>nε

Fk</sub>Σ

_hΣ

<sub>iε

QIk</sub>c^j_knhiQX^j_knhi+Σ

<sub>rε

R</sub>Σ

<sub>t∈

Th</sub>Σ

_hP^r_htS^r_ht 

 

(c1)

Subject to

Σ

<sub>jε

Mr</sub>e^jrG^jr_ht+S^r_ht−

O^r_ht=b^r_ht, rε

R, tε

T_h, h=1, . . . , 7, 

 

(c2)

f^j_ht(QX, QU, QW, QV)−

Σ

<sub>r∈

Nj</sub>G^jr_ht=0, jε

J, tε

T_h, h=1, . . . , 7, 

 

(c3)

QX^j_knhi=Σ

<sub>t∈

QB1knih</sub>QU^j_kniht, jε

J, nε

Fk, iε

QI_k, k∈

QK_j, h=1, . . . , 7, 

 

(c4)

QX^j_knhi=Σ

<sub>t∈

QB2knih</sub>QW^j_kniht, jε

J, nε

Fk, iε

QI_k, k∈

QK_j, h=1, . . . , 7, 

 

(c5)

QX^j_knhi=Σ

<sub>t∈

QB3knih</sub>QV^j_kniht, jε

J, nε

Fk, iε

QI_k, k∈

QK_j, h=1, . . . , 7, 

 

(c6)

Σ

<sub>1ε

QLk</sub>A_k1hQ^j_k1=Σ

<sub>nε

Fk</sub>Σ

<sub>iε

QIk</sub>QX^j_knhi, jε

J, k∈

QK_j, h=1, . . . , 7, 

 

(c7)

Σ

<sub>1ε

QLk</sub>Q^j_k1<

QD^j_k^max, jε

J, k∈

QK_j, 

 

(c8)

QX^j_knhi, Q^j_k1, QU^j_kniht, QW^j_kniht, and QV^j_kniht>

0 and integer for all j, k, n, i, h, t, and G^jr_ht, S^r_ht, and O^r_ht>

0 for all j, r, h, and t, 

 

(c9)

where, in constraint (c3),

f^j_ht(QX, QU, QW, QV)=Σ

<sub>k∈

QKj</sub>Σ

<sub>nε

Fk</sub>Σ

<sub>iε

QIk</sub>a_knihtQX^j_knhi−

Σ

<sub>k∈

QKj</sub>Σ

<sub>nε

Fk</sub>Σ

<sub>iε

QT1knht</sub>QU^j_kniht−

Σ

<sub>k∈

QKj</sub>Σ

<sub>nε

Fk</sub>Σ

<sub>iε

QT2knht</sub>(QW^j_kniht+QW^j<sub>knih(t−

1)</sub>)−

Σ

<sub>k∈

QKj</sub>Σ

<sub>nε

Fk</sub>Σ

<sub>iε

QT3knht</sub>QV^j_kniht, jε

J, tε

T_h, h=1, . . . , 7, 

 

(c10)

where

F_k is the set of shift lengths specified for tour k;

J is the set of all skill groups;

R is the set of all contact groups;

T_h is the set of all planning periods in day h;

OI_k is the set of daily start times for tour k;

QK_j is the set of all possible tours including both requiring and not requiring consistent daily start times for scheduling agents in skill group j;

when a tour requires consistent daily start times, a pseudo tour is defined for each start time of the tour with the same tour, shift, break, and work and non-work rules, and included in QI_k and QK_j;

QL_k is the set of all allowed work day patterns for the agents assigned to tour k;

only the work patterns satisfying the work and non-work day rules specified for tour k are included in QL_k;

QB1_knih is the set of planning periods on day h during which an agent assigned to tour k and shift length n with a daily start time of i may start his/her first relief break and complete within the time window specified for this tour group, shift length, start time, and day;

QB2_knih is the set of planning periods on day h during which an agent assigned to tour k and shift length n with a daily start time of i may start his/her lunch break and complete within the time window specified for this tour group, shift length, start time, and day;

QB3_knih is the set of planning periods on day h during which an agent assigned to tour k and shift length n with a daily start time of i may start his/her second relief break and complete within the time window specified for this tour group, shift length, start time, and day;

QT1_knht is the set of daily start times for shift length n for tour k for which period t on day h is a first relief break start period;

QT2_knht is the set of daily start times for shift length n for tour k for which period t on day h is a lunch break start period;

QT3_knht is the set of daily start times for shift length n for tour k for which period t on day h is a second relief break start period;

M^r is the set of skill groups that can serve contact type r;

Nj is the set of contact types that skill group j is qualified to provide service;

a_kniht is equal to one when period t on day h is in the shift span (that is, a work or a break period) of agents assigned to tour k who have a daily start time of i and shift length n on day h, and zero otherwise;

A_k1h is equal to one when day h is a work day for agents assigned to tour k and work pattern 1, and zero otherwise;

C^j_k1 is the weekly cost of assigning an agent in skill group j to tour k with work pattern of 1;

c^j_knhi is the daily wage paid in addition to the weekly cost of C^j_k1 to agents in skill group j assigned to tour type k with a daily shift length of n and start time of i on day h;

b^r_ht is the number of agents with the highest skill proficiency to serve contact type rε

R required in period t on day h;

P^r_ht is the per-unit penalty cost for allocating fewer than the number of agents with skill to serve contact type rε

R required b^r_ht, in period t on day h;

e^jr is the relative efficiency of an agent from skill group j in serving contact type r with respect to an agent with the highest skill proficiency (100% efficiency level) for contact type r, e^jrε

[0, 1];

QD^j_k^max is the maximum number of agents available in skill group j to assign to tour k;

where decision variables whose values are determined by a solution to the MILP model are defined as;

shift variables;

QX^j_knhi is the number of agents in skill group j assigned to tour k and shift length n with a daily starting time of i on day h;

break variables;

QU^j_kniht is the number of agents in skill group j assigned to tour k and shift length n with a daily start time of i and starting their first relief breaks in period t on day h;

QW^j_kniht is the number of agents in skill group j assigned to tour k and shift length n with a daily start time of i and starting their lunch breaks in period t on day h;

when a tour has more than one lunch break to be scheduled during a shift, then a set of break variables and constraints are defined for each lunch break type in the same manner with QW^j_kniht variables and constraints (c5), and included in constraint (c3);

a lunch break variable may be two or more periods long;

a lunch break variable will appear in all periods on the left hand side of (c3) with a negative sign during which the agents assigned to the associate break start time will be on break;

QV^j_kniht is the number of agents in skill group j assigned to tour k and shift length n with a daily start time of i and starting their second relief breaks in period t on day h;

when a tour has more than two relief breaks to be scheduled during a shift, then a set of break variables and constraints are defined for each break type in the same manner with QU^j_kniht and QV^j_kniht variables and constraints (c4) and (c6), and included in constraint (c3) A relief break variable may be one or more periods long;

a relief break variable will appear in all periods on the left hand side of (c3) with a negative sign during which the agents assigned to that break start time will be on break;

work pattern variables;

Q^j_k1 is the number of agents in skill group j assigned to tour k with a work pattern of 1;

allocation variables;

G^jr_ht is the number of agents from skill group j scheduled and not on a break in planning period t on day h, and allocated to contact type r;

shortage variables;

S^r_ht is the total agent shortages on the left hand side of constraint (c2) in meeting the required number of agents, b^r_ht, with skill to serve contact type rε

R in planning period t on day h;

excess variables;

O^r_ht is the total overstaffing on the left hand side of constraint (c2) in excess of the required number of agents, b^r_ht, with skill to serve contact type rε

R in planning period t on day h;

variable sets

QX={QX^j_knhi;

j∈

J, n∈

F_k, k∈

QK_j, i∈

I_k, h=1, . . . , 7} is the set of shift variables QX^j_knhi;

QU, QW, and QV are defined similar to the set QX to include, respectively, the first relief break, lunch, and second relief break variables (e.g. the set QU includes QU^j_kniht, QW includes QW^j_kniht) for skill groups in J, nε

F_k, k∈

QK_j, i∈

I_k, h=1, . . . , 7, and t∈

QB1_knih for QU, t∈

QB2_knih for QW, and t∈

QB3_knih for QV;

to facilitate the presentation of function (c10), planning period index (t−

1) is used;

if (t−

1) is in one day and planning period t in the next day, planning period and day indexes are adjusted accordingly;

for example, if a planning period is 15 minutes long and period 96 is starting period for a lunch break variable on day h, then the second planning period for this variable is not period 97, which is in the next day, but period 1 of day (h+1);

likewise if (h+1) is beyond the end of the scheduling period, schedules “

wrap around” and

agent availabilities appear in the first of the scheduling period;

if some tours have four or more break types to be scheduled, one set for each break type is defined in the same manner with QU, QW, and QV;

the function f^j_ht(QX, QU, QW, QV) includes the decision variables for skill group j in QX, and the sets of break variables (e.g. QU, QW, QV) only,

and

G={G^jr_ht;

j∈

J, r∈

R, t∈

T_h, h=1, . . . , 7} is the set of variables G^jr_ht;

(d) obtaining the Linear Programming (LP) relaxation of the MILP model in the Branch and Cut (B&

C) algorithm by relaxing all integrality constraints on the decision variables, solving the LP relaxation, and stopping the B&

C algorithm with an optimal solution to the MILP model when the optimal solution of the LP relaxation satisfies all integrality constraints by a computer;

(e) calling the Rounding Algorithm (RA) consisting of the following steps by a computer when the solution to the LP relaxation of the MILP model violating some integrality constraints is found by the B&

C algorithm;

i. Obtaining the values of the decision variables in the optimal solution found for the LP relaxation of the MILP model;

ii. Rounding the fractional values of decision variables in QX, QU, QW, QV, and G down, and weekly tour variables QX, and work pattern variables Q^j_k1 down when their fractional part is less than or equal to 0.50, and up if greater than 0.50, provided the agent availability constraints on the maximum number of agents available are not violated;

iii. Scheduling additional shifts by increasing the values of decision variable in QX if additional shifts are needed to satisfy the number of work days required by tour scheduling rules for each agent, and to have a shift scheduled for every agent who will be working on a given day based on the work patterns Q^j_k1 scheduled;

iv. Scheduling additional daily breaks when the number of breaks of each type is not sufficient to satisfy break scheduling rules for a tour for each day, daily shift length and start time, and unscheduling breaks when there are more breaks scheduled than required by a tour for a day, shift length and start time, due to rounding;

v. Computing the left side of constraint (c2) using the values determined in steps (1-iv) for the decision variables, subtracting the right side from the left side of constraint (c2, and determining agent shortages S^r_ht, when the difference is negative, and excesses O^r_ht, when the difference is positive, for each contact type and planning period;

vi. Computing scheduled agent availability for all skill groups and planning periods in (c10), comparing them with the agent allocations to different contact types by the rounded values of allocation variables G, and adjusting the values of the associated allocation, G, shortage, S^r_ht, and excess, O^r_ht, variables to make agent allocations equal to scheduled agent availability in (c10) and satisfy (c2);

vii. Checking the solution constructed in steps (i) through (vi) to determine if all agent requirements are met in every planning period and, when all requirements are met, eliminating all redundant agent tour schedules that do not create agent shortages in any period when removed by lowering the values of related shift, break, and work pattern variables and stopping with the integer feasible solution found;

viii. Continuing to step (xii) with an integer feasible solution with agent shortages when agent requirements for some contact types are not met in all periods and all available agents in constraint (c8) who can serve these contact types are scheduled;

ix. Continuing to step (x) when there are agents available to schedule when left hand side of (c8) is less than its right hand side for one or more skill groups and there shortages in some periods for some contact types served by these skill groups;

x. finding all periods in which some contact types have shortages, finding an agent with skills needed, from a skill group for which the left side of (c8) is less than its right side, together with a complete tour schedule with work and non-work days, daily shift start times and shift lengths, daily break times to reduce the agent shortages for one or more contact types, and adding them to the solution by increasing the values of the corresponding decision variables by one to include the newly added agent tour schedule, and continuing to step (xii) when all agent requirements are met;

xi. repeating steps (viii), (ix), and (x) until all agent requirements are met, or agent requirements for some contact types are not met in all periods and all available agents in constraint (c8) who can serve these contact types are scheduled;

xii. Examining the tours scheduled in the integer feasible solution found and eliminating redundant tours that do not create new agent shortages in any period when removed by lowering the values of related shift, break, and work pattern variables;

(f) applying the RA algorithm to the solution found for the LP relaxation of the MILP model (current node) by the B&

C algorithm when it violates one or more integrality conditions and, when a solution better than the best integer solution known is found by the RA algorithm, passing it to the B&

C algorithm by a computer.

2. The method of claim 1 further comprising of repeating steps (e) and (f) for every node the B&

C algorithm solves by the computer and finds a solution whose values for decision variables violate one or more integrality constraints, until a terminal solution that is either an optimal integer solution or the best integer solution for the MILP model is reached.

3. The method of claim 1 further comprising of processing the terminal solution found by the computer to assign daily shifts with start times and shift lengths to work patterns, and daily breaks to specific shifts with start times and shift lengths to develop detailed weekly agent schedules.

4. The method of claim 1 further comprising of assigning agents to detailed weekly agent schedules by the computer.

5. The method of claim 1, in which a terminal solution to the MILP model is found when the objective function value for an integer feasible solution differs no more than a pre-specified percentage from the lowest objective function value found for the LP relaxations of all nodes created in the B&

C algorithm to which the RA algorithm has not been applied when the integer feasible solution is found.

6. The method of claim 1, in which a terminal solution to the MILP model formulated is found when an integer feasible solution is found and a pre-specified period of time is passed in searching for a better integer feasible solution by the B&

C algorithm.

7. The method of claim 1, in which a terminal solution to the MILP model formulated is found when an integer feasible solution is found and a pre-specified number of nodes are solved in the B&

C algorithm and evaluated using the RA algorithm.