US6463346B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Workflow-scheduling optimization driven by target completion time
Assignee: Avaya Inc
•
Filing: 1999-10-08
•
Granted: 2002-10-08
•
Expires: 2019-10-08
Abstract
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.
Inventors
- 👤 Andrew D. Flockhart
- 👤 Darryl J. Maxwell
- 👤 Keith Robert McFarlane
- 👤 Paul L. Richman
- 👤 Lucinda M. Sanders
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 14:54
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/06; G06Q10/10; G06F; G06F15/00; G06F8/00; H; H04; H04M; H04M3/00; H04M3/42; H04M3/50; H04M3/51; H04M3/523; H04M3/5238
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
136 words
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.
Claim 2
Independent Claim
136 words
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.
Claim 3
Dependent Claim
61 words
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.
Claim 4
Dependent Claim
14 words
The method of claim 1 wherein: said determining is performed for each said item.
Claim 5
Dependent Claim
40 words
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.
Claim 6
Dependent Claim
47 words
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.
Claim 7
Dependent Claim
117 words
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.
Claim 8
Independent Claim
237 words
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.
Claim 9
Independent Claim
237 words
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.
Claim 10
Dependent Claim
47 words
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.
Claim 11
Independent Claim
175 words
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.
Claim 12
Independent Claim
175 words
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.
Claim 13
Dependent Claim
47 words
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.
Claim 14
Independent Claim
129 words
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.
Claim 15
Independent Claim
129 words
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.
Claim 16
Independent Claim
283 words
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.
Claim 17
Independent Claim
283 words
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.
Claim 18
Independent Claim
271 words
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.
Claim 19
Independent Claim
271 words
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.
Claim 20
Independent Claim
26 words
An apparatus that effects the method of one of the claims 1 - 5 , 6 , 7 - 10 , and 12 - 13 .
Claim 21
Dependent Claim
38 words
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 .
References Cited (Backward Citations)
US5170355A
Cited
US5291397A
Cited
US5446671A
Cited
US5506898A
Cited
US5612886A
Cited
US5890134A
Cited
US5751580A
Cited
US6115640A
Cited
US6130942A
Cited
US6353769B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-10-07 | 2006-04-08 | 2006-10-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-10-07 | 2010-04-08 | 2010-10-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-10-07 | 2014-04-08 | 2014-10-08 | $7700.00 | Window Closed / Lapsed |