METHOD AND APPARATUS FOR SCHEDULING MEDIA PROCESSING JOBS ON MULTIPLE PROCESSORS TO MAXIMIZE PROCESSOR UTILIZATION

• US 20150006226A1
• Filed: 06/28/2013
• Published: 01/01/2015
• Est. Priority Date: 06/28/2013
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: SMITH, Donald E., ALLEN, John David
• Granted Patent: US 9,547,836 B2
• Time in Patent Office: Days
• US Class Current: 705/7.23
• CPC Class Codes: G06Q 10/06313 Resource planning in a project environment

Abstract

An approach is provided for scheduling work order tasks based on an optimization of available resources and an assessment of cost penalty functions for missing work order deadlines, including determining an estimated work order completion time for processing a plurality of tasks associated with a work order on one or more resources, scheduling the plurality of tasks in a processing queue based on the estimated work order completion time, and determining a value of a penalty function for violating a work order deadline.

Claims

1. A method comprising:

determining an estimated work order completion time for processing a plurality of tasks associated with a work order on one or more resources;

scheduling the plurality of tasks in a processing queue based on the estimated work order completion time; and

determining a value of a penalty function for violating a work order deadline.

2. The method according to claim 1, wherein the penalty function specifies a financial cost for an actual work order completion time violating the work order deadline.

3. The method according to claim 1, wherein the estimated work order completion time is based on an earliest availability of the one or more resources.

4. The method according to claim 1, further comprising:

determining a duration estimate of each of the plurality of tasks; and

determining any precedence relationships between the plurality of tasks,

wherein the estimated work order completion time is further based on the duration and any precedence relationships.

5. The method according to claim 4, further comprising:

generating one or more sequences for processing the plurality of tasks based on the precedence relationships to evaluate a resulting estimated work order completion time,

wherein the schedule of the plurality of tasks is further based on the sequence that minimizes the estimated work order completion time.

6. The method according to claim 1, further comprising:

determining an availability of the one or more resources,

wherein the estimated work order completion time is further based on the availability.

7. The method according to claim 1, further comprising:

processing at least one other work order to determine whether scheduling of the other work order will increase the value of the penalty function.

8. The method according to claim 7, wherein the scheduling of the other work order increases the penalty function, the method further comprising:

initiating a rescheduling of the plurality of tasks in the processing queue based on minimizing the value of the penalty function,

wherein the rescheduling of the plurality of tasks is an iterative process.

9. The method according to claim 1, wherein the at least one work order includes one or more media files, one or more output formats, the work order deadline, or a combination thereof.

10. The method according to claim 1, wherein the at least one work, the plurality of tasks, or a combination thereof are not related to media files.

20. The method according to claim 1, wherein the at least one work, the plurality of tasks, or a combination thereof are not related to media files.

11. An apparatus comprising:

a processor; and

a memory including computer program code for one or more programs,

the memory and the computer program code configured to, with the processor, causing to perform at least the following,

determine an estimated work order completion time for processing a plurality of tasks associated with a work order on one or more resources;

schedule the plurality of tasks in a processing queue based on the estimated work order completion time; and

determine a value of a penalty function for violating a work order deadline.

12. An apparatus according to claim 11, wherein the penalty function specifies a financial cost for an actual work order completion time violating the work order deadline

13. An apparatus according to claim 11, wherein the estimated work order completion time is based on an earliest availability of the one or more resources

14. An apparatus according to claim 11, wherein the apparatus is further configured to:

determine a duration estimate of each of the plurality of tasks; and

determine any precedence relationships between the plurality of tasks,

wherein the estimated work order completion time is further based on the duration and any precedence relationships.

15. An apparatus according to claim 14, wherein the apparatus is further configured to:

generate one or more sequences for processing the plurality of tasks based on the precedence relationships to evaluate a resulting estimated work order completion time,

wherein the schedule of the plurality of tasks is further based on the sequence that minimizes the estimated work order completion time.

16. An apparatus according to claim 11, wherein the apparatus is further configured to:

determine an availability of the one or more resources,

wherein the estimated work order completion time is further based on the availability.

17. An apparatus according to claim 11, wherein the apparatus is further configured to:

process at least one other work order to determine whether scheduling of the other work order will increase the value of the penalty function.

18. An apparatus according to claim 17, wherein the scheduling of the other work order increases the penalty function, the method further comprising, the apparatus is further configured to:

initiate a rescheduling of the plurality of tasks in the processing queue based on minimizing the value of the penalty function,

wherein the rescheduling of the plurality of tasks is an iterative process.

19. The method according to claim 11, wherein the at least one work order includes one or more media files, one or more output formats, the work order deadline, or a combination thereof.