METHOD, APPARATUS, AND SYSTEM FOR PROVIDING AND USING A SCHEDULING DELTA QUEUE

A contact center is described along with various methods and mechanisms for administering the same. Work assignment methods are disclosed that place tasks in bins by time intervals and are processed within a delta queue ring buffer. The delta queue ring buffer can assign the tasks by seconds and order tasks by interval for efficient handling, and then loop around to use the same bins. By using fixed intervals and a moving queue pointer, the scheduling delta queue solution allows for fast selection of the queue to insert and fast processing of the queues on timeout. The scheduling delta queue solution allows for the processing of at least, but not limited to one million tasks with only memory as a constraint.

DETAILED DESCRIPTION

FIG. 1shows an illustrative embodiment of a communication system100in accordance with at least some embodiments of the present disclosure. The communication system100may be a distributed system and, in some embodiments, comprises a communication network104connecting one or more communication devices108to a work assignment mechanism116, which may be owned and operated by an enterprise administering a contact center in which a plurality of resources112are distributed to handle incoming work items (in the form of contacts) from the customer communication devices108.

In accordance with at least some embodiments of the present disclosure, the communication network104may comprise any type of known communication medium or collection of communication media and may use any type of protocols to transport messages between endpoints. The communication network104may include wired and/or wireless communication technologies. The Internet is an example of the communication network104that constitutes an Internet Protocol (IP) network consisting of many computers, computing networks, and other communication devices located all over the world, which are connected through many telephone systems and other means. Other examples of the communication network104include, without limitation, a standard Plain Old Telephone System (POTS), an Integrated Services Digital Network (ISDN), the Public Switched Telephone Network (PSTN), a Local Area Network (LAN), a Wide Area Network (WAN), a Session Initiation Protocol (SIP) network, a Voice over IP (VoIP) network, a cellular network, and any other type of packet-switched or circuit-switched network known in the art. In addition, it can be appreciated that the communication network104need not be limited to any one network type, and instead may be comprised of a number of different networks and/or network types. As one example, embodiments of the present disclosure may be utilized to increase the efficiency of a grid-based contact center. Examples of a grid-based contact center are more fully described in U.S. Patent Publication No. 2010/0296417 to Steiner, the entire contents of which are hereby incorporated herein by reference. Moreover, the communication network104may comprise a number of different communication media such as coaxial cable, copper cable/wire, fiber-optic cable, antennas for transmitting/receiving wireless messages, and combinations thereof.

The communication devices108may correspond to customer communication devices. In accordance with at least some embodiments of the present disclosure, a customer may utilize their communication device108to initiate a work item, which is generally a request for a processing resource112. Exemplary work items include, but are not limited to, a contact directed toward and received at a contact center, a web page request directed toward and received at a server farm (e.g., collection of servers), a media request, an application request (e.g., a request for application resources location on a remote application server, such as a SIP application server), and the like. The work item may be in the form of a message or collection of messages transmitted over the communication network104. For example, the work item may be transmitted as a telephone call, a packet or collection of packets (e.g., IP packets transmitted over an IP network), an email message, an Instant Message, an SMS message, a fax, and combinations thereof.

In some embodiments, the communication may not necessarily be directed at the work assignment mechanism116, but rather may be on some other server in the communication network104where it is harvested by the work assignment mechanism116, which generates a work item for the harvested communication. An example of such a harvested communication includes a social media communication that is harvested by the work assignment mechanism116from a social media network or server. Exemplary architectures for harvesting social media communications and generating tasks based thereon are described in U.S. Patent Publication Nos. 2010/0235218, 2011/0125826, and 2011/0125793, to Erhart et al, filed Mar. 20, 1010, Feb. 17, 2010, and Feb. 17, 2010, respectively, the entire contents of each are hereby incorporated herein by reference in their entirety.

The format of the work item may depend upon the capabilities of the communication device108and the format of the communication.

In some embodiments, work items and tasks are logical representations within a contact center of work to be performed in connection with servicing a communication received at the contact center (and more specifically the work assignment mechanism116). With respect to the traditional type of work item, the communication associated with a work item may be received and maintained at the work assignment mechanism116, a switch or server connected to the work assignment mechanism116, or the like until a resource112is assigned to the work item representing that communication at which point the work assignment mechanism116passes the work item to a routing engine128to connect the communication device108which initiated the communication with the assigned resource112.

Although the routing engine128is depicted as being separate from the work assignment mechanism116, the routing engine128may be incorporated into the work assignment mechanism116or its functionality may be executed by the work assignment engine120.

In accordance with at least some embodiments of the present disclosure, the communication devices108may comprise any type of known communication equipment or collection of communication equipment. Examples of a suitable communication device108include, but are not limited to, a personal computer, laptop, Personal Digital Assistant (PDA), cellular phone, smart phone, telephone, or combinations thereof. In general each communication device108may be adapted to support video, audio, text, and/or data communications with other communication devices108as well as the processing resources112. The type of medium used by the communication device108to communicate with other communication devices108or processing resources112may depend upon the communication applications available on the communication device108.

In accordance with at least some embodiments of the present disclosure, the work item is sent toward a collection of processing resources112via the combined efforts of the work assignment mechanism116and routing engine128. The resources112can either be completely automated resources (e.g., Interactive Voice Response (IVR) units, processors, servers, or the like), human resources utilizing communication devices (e.g., human agents utilizing a computer, telephone, laptop, etc.), or any other resource known to be used in contact centers.

As discussed above, the work assignment mechanism116and resources112may be owned and operated by a common entity in a contact center format. In some embodiments, the work assignment mechanism116may be administered by multiple enterprises, each of which has their own dedicated resources112connected to the work assignment mechanism116.

In some embodiments, the work assignment mechanism116comprises a work assignment engine120which enables the work assignment mechanism116to make intelligent routing decisions for work items. In some embodiments, the work assignment engine120is configured to administer and make work assignment decisions in a queueless contact center, as is described in U.S. Patent Application Serial No. 2011/0255683 filed Sep. 15, 2010, the entire contents of which are hereby incorporated herein by reference.

More specifically, the work assignment engine120can generate bitmaps/tables124and determine, based on an analysis of the bitmaps/tables124, which of the plurality of processing resources112is eligible and/or qualified to receive a work item and further determine which of the plurality of processing resources112is best suited to handle the processing needs of the work item. In situations of work item surplus, the work assignment engine120can also make the opposite determination (i.e., determine optimal assignment of a work item to a resource). In some embodiments, the work assignment engine120is configured to achieve true one-to-one matching by utilizing the bitmaps/tables124and any other similar type of data structure.

The work assignment engine120may reside in the work assignment mechanism116or in a number of different servers or processing devices. In some embodiments, cloud-based computing architectures can be employed whereby one or more components of the work assignment mechanism116are made available in a cloud or network such that they can be shared resources among a plurality of different users.

FIG. 2depicts exemplary data structures200which may be incorporated in or used to generate the bitmaps/tables124used by the work assignment engine120. The exemplary data structures200include one or more pools of related items. In some embodiments, three pools of items are provided, including an enterprise work pool204, an enterprise resource pool212, and an enterprise qualifier set pool220. The pools are generally an unordered collection of like items existing within the contact center. Thus, the enterprise work pool204comprises a data entry or data instance for each work item within the contact center at any given time.

In some embodiments, the population of the work pool204may be limited to work items waiting for service by or assignment to a resource112, but such a limitation does not necessarily need to be imposed. Rather, the work pool204may contain data instances for all work items in the contact center regardless of whether such work items are currently assigned and being serviced by a resource112or not. The differentiation between whether a work item is being serviced (i.e., is assigned to a resource112) may simply be accounted for by altering a bit value in that work item's data instance. Alteration of such a bit value may result in the work item being disqualified for further assignment to another resource112unless and until that particular bit value is changed back to a value representing the fact that the work item is not assigned to a resource112, thereby making that resource112eligible to receive another work item.

Similar to the work pool204, the resource pool212comprises a data entry or data instance for each resource112within the contact center. Thus, resources112may be accounted for in the resource pool212even if the resource112is ineligible due to its unavailability because it is assigned to a work item or because a human agent is not logged-in. The ineligibility of a resource112may be reflected in one or more bit values.

The qualifier set pool220comprises a data entry or data instance for each qualifier set within the contact center. In some embodiments, the qualifier sets within the contact center are determined based upon the attributes or attribute combinations of the work items in the work pool204. Qualifier sets generally represent a specific combination of attributes for a work item. In particular, qualifier sets can represent the processing criteria for a work item and the specific combination of those criteria. Each qualifier set may have a corresponding qualifier set identified “qualifier set ID” which is used for mapping purposes. As an example, one work item may have attributes of language=French and intent=Service and this combination of attributes may be assigned a qualifier set ID of “12” whereas an attribute combination of language=English and intent=Sales has a qualifier set ID of “13.” The qualifier set IDs and the corresponding attribute combinations for all qualifier sets in the contact center may be stored as data structures or data instances in the qualifier set pool220.

In some embodiments, one, some, or all of the pools may have a corresponding bitmap. Thus, a contact center may have at any instance of time a work bitmap208, a resource bitmap216, and a qualifier set bitmap224. In particular, these bitmaps may correspond to qualification bitmaps which have one bit for each entry. Thus, each work item228,232in the work pool204would have a corresponding bit in the work bitmap208, each resource112in the resource pool212would have a corresponding bit in the resource bitmap216, and each qualifier set in the qualifier set pool220may have a corresponding bit in the qualifier set bitmap224.

In some embodiments, the bitmaps are utilized to speed up complex scans of the pools and help the work assignment engine120make an optimal work item/resource assignment decision based on the current state of each pool. Accordingly, the values in the bitmaps208,216,224may be recalculated each time the state of a pool changes (e.g., when a work item surplus is detected, when a resource surplus is detected, etc.).

FIG. 3is a diagram depicting an instantiation of a scheduling delta queue300with a ring buffer which may be used by a work assignment mechanism116or a resource112to efficiently process tasks.

In some embodiments, a delta queue is configured to schedule contact center tasks, as described at least in part in U.S. Pat. No. 7,500,241, issued Mar. 3, 2009, to Flockhart et al, and U.S. Pat. No. 8,094,804, issued Jan. 10, 2012, to Flockhart et al, the entire contents of each are hereby incorporated herein by reference in their entirety.

A work assignment mechanism116may have certain tasks pending execution. These tasks typically need to be executed based on certain parameters, such as time and in a certain order. To facilitate the most efficient execution of tasks, a special type of scheduling delta queue300may be used.

The scheduling delta queue300may break time into equal segments or bins. In a preferred embodiment, the segments may be one second segments which are uniform and each segment may be a delta queue. The scheduling delta queue300may comprise a set of segments/bins304,308,312,316,320,324,328,332where the set may be more or fewer than depicted, and where each bin represents a one second segment. The bins304,308,312,316,320,324,328,332may contain one or more work items or tasks. For example, bin308may contain work items or tasks308-1,308-2,308-3,308-4,308-5,308-6and bin316may contain one task316-1. Each segment/bin may have more or fewer tasks than depicted.

A task324-1that is scheduled for completion may be inserted, for example, in bin324based on the time period in which it is scheduled to be executed. The time period in which a task324-1is scheduled to be executed may correspond to an absolute time or a time period relative to current time336. Rather than sending subsequent tasks to a secondary scheduler queue comprising a scheduling array, a second insertion point may be available for a task324-2within bin324, a third insertion point may be available for a task324-3within bin324, and a fourth insertion point may be available for a task324-4within bin324, and so on.

In some embodiments, the scheduling delta queue may only consider the current bin/segment312and process tasks within that bin/segment312. For instance, the work assignment engine120may begin by executing task312-1. The work assignment engine then processes the next task312-2, rather than having to assess bin316,320,324and so on before executing task312-2. Significant efficiencies may be achieved by removing the requirement to check every subsequent segment every time. Instead, all tasks may be executed within a bin and then the process increments to the next bin. In other words, the time-consuming process of incrementing can be delayed until all tasks within a bin have been executed.

FIG. 4is a histogram depicting the frequency of task execution in accordance with embodiments of the present disclosure. The vertical axis may represent the number of tasks, and the horizontal axis may represent the time relative to now. In this example, the execution of tasks is graphed showing a large number of seconds to show the relative change in efficiency as time elapses, and thus the bin number, gets larger. The scheduling delta queue300increases efficiency at early intervals, but may be less effective as time increases and frequency decreases. Most of the tasks will be completed in an early interval, and by the late bins the tasks may have already been completed, expired, or rescheduled. By adding a delta queue ring buffer340, the use of one-second bins in a delta queue to minimize processor resources may be further enhanced to automatically wrap around to the beginning, to the first bin of the delta queue. This may allow the ring buffer to be used without the limitation or requirement of a fixed queue size and may allow maximum efficiency based on the frequency of tasks in early bins.

FIG. 5is a first flow diagram depicting the placement of tasks into a delta queue bin in accordance with an embodiment of the present disclosure. While a general order for the steps of the method500are shown inFIG. 5, the method500can include more or fewer steps or the order of the steps can be arranged differently than those shown inFIG. 5. The method500can be executed as a set of computer-executable instructions executed by a computer system and encoded or stored on a non-transitory computer readable medium.

Generally, the method begins with a work item or task that comes into the work assignment engine120within the work assignment mechanism116. The task processing begins, in step504. The work assignment engine120may determine when the task should be executed. In step508, based on the information delivered with the task, the work assignment engine120can calculate the required queue position for the task. In some embodiments, the bins in a scheduling delta queue are set in intervals of one second each. The work assignment engine120can determine in which bin the task should be placed, in step512. Once the work assignment engine120has determined in which bin to place the task, the work assignment120engine may insert the task into the required queue position in that bin, in step516.

FIG. 6is a second flow diagram depicting a bin sequencing method in a ring delta queue buffer in accordance with an embodiment of the present disclosure. While a general order for the steps of the method600are shown inFIG. 6, the method600can include more or fewer steps or the order of the steps can be arranged differently than those shown inFIG. 6. The method600can be executed as a set of computer-executable instructions executed by a computer system and encoded or stored on a non-transitory computer readable medium.

Generally, the method begins with a work item or task that comes into the work assignment engine120within the work assignment mechanism116. As discussed in conjunction withFIG. 5, tasks may be placed into one or more bins based on the time or segment information provided by the tasks. In step604, task processing begins with bin0.

The work assignment engine120is operable to process all of the tasks in bin0, in step608, in time order. If there is time left after the tasks have been executed, the work assignment engine120may optionally wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin1which is the next bin in the scheduling delta queue. The work assignment engine120then determines if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin1, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin2which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin2, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin3which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin3, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin4which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin4, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin5which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin5, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin6which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin6, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin7which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin7, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin8which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin8, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin9which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin9, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin10(where N=10) which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

If the bin number is not greater than N, the work assignment engine120may begin processing all the tasks in bin10, in step608. If there is time left after the tasks have been executed, the work assignment engine120may wait for the remainder of the one second interval to expire, in step612. In step616, the count may increment to bin11=N+1 (where Bin>N) which is the next bin in the scheduling delta queue. The work assignment engine120asks if the bin number is greater than N, in step620.

When the answer is yes, the work assignment engine120loops back around to bin0and the process begins again, in step604. The combination of task insertion and bin sequencing provide efficient use of the scheduling delta queue within and through the segments.

It should be appreciated that while embodiments of the present disclosure have been described in connection with a queueless contact center architecture, embodiments of the present disclosure are not so limited. In particular, those skilled in the contact center arts will appreciate that some or all of the concepts described herein may be utilized in a queue-based contact center or any other traditional contact center architecture.