Workflow-scheduling optimization driven by target completion time

• US 6,463,346 B1
• Filed: 10/08/1999
• Issued: 10/08/2002
• Est. Priority Date: 10/08/1999
• Status: Expired due to Term

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: McFarlane, Keith Robert, Flockhart, Andrew D., Richman, Paul L., Maxwell, Darryl J., Sanders, Lucinda M.
• Primary Examiner(s): Picard, Leo
• Assistant Examiner(s): RODRIGUEZ, PAUL L
• Application Number:
  US09/415,577
• Time in Patent Office: 1,096 Days
• Field of Search: 379/266.01, 379/266.02, 379/266.03, 379/266.04, 379/266.06, 379/266.05, 700/28, 700/32, 700/33, 700/341, 700/242, 700/100, 700/101, 700/102, 706/19, 705/8, 705/9
• US Class Current: 700/102
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04M 3/523 with call distribution or queueing
• CPC Class Codes: H04M 3/5238 with waiting time or load prediction arrangements

Abstract

The flow of work items (40) through a workflow process (50) is optimized by repeatedly reordering (FIG. 3) work items enqueued in inbox queues (21) of workflow process tasks (500) to maximize results according to a given business strategy expressed through target times. Each enqueued work item has an associated in-queue rating (IQR 28) that represents the number of queue positions (23) that the work item can be retarded or needs to be advanced to meet its target time. When a work item enters a queue and whenever a work item changes its queue position, its IQR is computed. An optimization function is then performed (404) on the queue to determine an order of the enqueued work items that optimizes a metric of those work items that may fail to meet their target times. The work items in the queue are then reordered (406) accordingly.

Claims

1. A method of optimizing workflow:

in a queue having a sequence of a plurality of positions for work items and an ordered plurality of the work items waiting to be worked and each work item having at least one target time including a target start time or a target completion time, determining, from an amount of the target time of an item that has already expired and an amount of additional time that is likely to expire before the item is worked, a number of the positions that the item either may be retarded or needs to be advanced in the queue relative to other said items in the queue to meet its target time; and

reordering the items in the queue to optimize a metric of items that may fail to meet their target time.

2. The method of claim 1 wherein:

the amount of the target time of an item that has already expired comprises

a time that the item has already spent in the queue; and

the amount of additional time that is likely to expire before the item is worked comprises

an additional time that the item is likely to remain in the queue.

3. The method of claim 1 wherein:

said determining is performed for each said item.

4. The method of claim 3 wherein:

optimizing a metric comprises

minimizing either (a) a number of the items that will fail to meet their target times, or an amount of time by which the items will exceed their target times.

5. The method of claim 3 wherein:

reordering comprises

performing an optimization function on the queue to determine an order of the items in the queue that optimizes the metric of items that may fail to meet their target time; and

ordering the items in the determined order.

6. The method of claim 1 wherein:

the sequence of a plurality of positions terminates at a head end;

each item further has a rate of advance between positions in the sequence;

the amount of the target time of an item that has already expired comprises a time that the item has already spent in the queue;

the amount of additional time that is likely to expire before the item is worked involves the rate of advance, and a present position of the item from the head end; and

the additional number comprises a number of the positions that the item either may be retarded or needs to be advanced in the sequence to meet its target time.

14. An apparatus that effects the method of one of the claims 1-5, 6, 7-10, and 12-13.

15. A computer-readable medium containing instructions which, when executed in a processor, cause the processor to perform the method of one of the claims 1-5, 6, 7-10, and 12-13.

7. A method of optimizing workflow in a queue having an ordered plurality of positions, each for a different one of a plurality of work items waiting to be worked, that terminates at a head end, comprising:

determining a rate of advance of the work items between the positions,

in response to an item that has an associated target time including a target start time or a target completion time entering the queue, determining a number of positions that the item either may be retarded or needs to be advanced in the queue as one of (a) the target completion time less a sum of an estimated wait time of the item in the queue and an average handling time of the work item, divided by the rate of advance and rounded down, and (b) the target start time less the estimated wait time of the item in the queue, divided by the rate of advance and rounded down;

in response to an item changing its position in the queue, redetermining the number of the positions that the item either may be retarded or needs to be advanced;

performing an optimization function on the queue to determine an order of the items in the queue that optimizes a metric of those items that need to be advanced in the queue in order to meet the target time; and

reordering the items in the queue in the determined order.

8. The method of claim 7 wherein:

the order minimizes either (a) a number of the items that need to be advanced in the queue in order to meet their target times, or (b) a total amount of time by which the items will exceed their target times.

9. A method of optimizing a workflow comprising a sequence of a plurality of tasks each having a corresponding queue including a sequence of a plurality of positions for an ordered plurality of work items waiting for the task, comprising:

in each said queue, assigning to each work item at least one target time including a target start time or a target completion time for the corresponding task;

for each work item in each said queue, determining, from an amount of the target time of the item for the corresponding task that has already expired and an amount of additional time that is likely to expire before the item undergoes the corresponding task, a number of the positions that the item either may be retarded or needs to be advanced in the queue relative to other said items in the queue to meet its target time for the corresponding task; and

in each said queue, reordering the items to optimize a metric of items that may fail to meet their target time for the corresponding task.

10. The method of claim 9 wherein:

said determining is performed for each item when the item enters any queue and when the item changes its position in any queue; and

said reordering is performed for each queue whenever determining is performed for any item in that queue.

11. An apparatus comprising:

a queue having a sequence of a plurality of positions for work items for storing a plurality of the work items waiting to be worked and each work item having at least one target time including a target start time or a target completion time;

means for determining, from an amount of the target time of an item that has already expired and an amount of additional time that is likely to expire before the item is worked, a number of the positions that the item either may be retarded or needs to be advanced in the queue to meet its target time; and

means for reordering the items in the queue to optimize a metric of items that may fail to meet their target times.

12. A method of optimizing workflow:

in a queue having an ordered plurality of work items waiting to be worked and each having at least a target start time, the queue further having a sequence of a plurality of positions for the work items that terminates at a head end and wherein each item further has a rate of advance between positions in the sequence, determining, from an amount of the target time of an item that has already expired and an amount of additional time that is likely to expire before the item is worked, whether the item either may be retarded or needs to be advanced in the queue relative to other said items in the queue to meet its target time, including

in response to an item entering the queue, determining, from a time that the item has already spent in the queue, the rate of advance, and a present position of the item from the head end, a number of the positions that the item either may be retarded or needs to be advanced in the sequence to meet its target time as;

the target completion time less a sum of an estimated wait time of the item in the queue and an average handling time of a work item, divided by the rate of advance and rounded down,

in response to an item changing its position in the queue, redetermining the number of the positions that the item either may be retarded or needs to be advanced, and

reordering the items in the queue to optimize a metric of items that have a negative said determined number of the positions and thus may fail to meet their target time.

13. A method of optimizing workflow:

in a queue having an ordered plurality of work items waiting to be worked and each having at least a target completion time, the queue further having a sequence of a plurality of positions for the work items that terminates at a head end and wherein each item further has a rate of advance between positions in the sequence, determining, from an amount of the target time of an item that has already expired and an amount of additional time that is likely to expire before the item is worked, whether the item either may be retarded or needs to be advanced in the queue relative to other said items in the queue to meet its target time, including

in response to an item entering the queue, determining, from a time that the item has already spent in the queue, the rate of advance, and a present position of the item from the head end, a number of the positions that the item either may be retarded or needs to be advanced in the sequence to meet its target time as;

the target start time less an estimated wait time of the item in the queue, divided by the rate of advance and rounded down,

in response to an item changing its position in the queue, redetermining the number of the positions that the item either may be retarded or needs to be advanced, and

reordering the items in the queue to optimize a metric of items that have a negative said determined number of the positions and thus may fail to meet their target time.