Patent ID: 7725339
Filing Date: 2010-05-25
Classification: G06Q

Abstract:
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 (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 Subject to where, in constraint (c3), where F J is the set of all skill groups; R is the set of all contact groups; T OI QK QL QB1 QB2 QB3 QT1 QT2 QT3 M Nj is the set of contact types that skill group j is qualified to provide service; a A C c b P e QD where decision variables whose values are determined by a solution to the MILP model are defined as: shift variables: QX break variables: QU QW QV work pattern variables: Q allocation variables: G shortage variables: S excess variables: O variable sets QX={QX 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 and G={G (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: (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.