Method and apparatus for scheduling media processing jobs on multiple processors to maximize processor utilization

• US 9,547,836 B2
• Filed: 06/28/2013
• Issued: 01/17/2017
• 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: Allen, John David, Smith, Donald E.
• Primary Examiner(s): SHECHTMAN, SEAN P
• Application Number:
  US13/931,023
• Publication Number:
  US 20150006226A1
• Time in Patent Office: 1,299 Days
• Field of Search: 700/100
• US Class Current: 1/1
• 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 for determining an estimated work order completion time for processing a plurality of tasks associated with a work order for processing one or more video input files on one or more resources, the method comprising:

receiving the work order including information about conversion and/or transcoding, one or more output formats of the video input files and a deadline by which the work order is to be completed;

determining, utilizing at least one processor, a plurality of time duration estimates, each time duration estimate in the plurality of time duration estimates associated with a respective task in the plurality of tasks,

wherein one or more of the respective tasks involve conversion and/or transcoding of one or more of the one or more video input files;

determining one or more precedence relationships between at least two tasks in the plurality of tasks;

determining an availability of the one or more resources;

generating two or more sequences for processing the plurality of tasks based on the one or more precedence relationships to evaluate one or more estimated work order completion times associated with respective sequences in the two or more sequences;

selecting a selected estimated work order completion time from the one or more estimated work order completion times based on one or more criteria;

scheduling the plurality of tasks in a processing queue based on the selected resulting estimated work order completion time and a sequence of the two or more sequences;

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

wherein the value of the penalty function is based on the deadline and/or the selected estimated work order completion time; and

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

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 further based on an earliest availability of the one or more resources.

4. The method according to claim 1,

wherein the selected estimated work order completion time minimizes the estimated work order completion time.

5. The method according to claim 1, 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.

6. 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.

7. The method according to claim 1, wherein the at least one work, the plurality of tasks, or a combination thereof are related to raw film footage.

8. An apparatus for determining an estimated work order completion time for processing a plurality of tasks associated with a work order for processing one or more video input files on one or more resources, the 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,

receive the work order including information about conversion and/or transcoding, one or more output formats of the video input files and a deadline by which the work order is to be completed,

determine a plurality of time duration estimates, each time duration estimate in the plurality of time duration estimates associated with a respective task in the plurality of tasks,

wherein one or more of the respective tasks involve conversion and/or transcoding of one or more of the one or more video input files,

determine one or more precedence relationships between at least two tasks in the plurality of tasks,

determine an availability of the one or more resources,

generate two or more sequences for processing the plurality of tasks based on the one or more precedence relationships to evaluate one or more estimated work order completion times associated with respective sequences in the two or more sequences,

wherein the one or more estimated work order completion times are based on the plurality of time duration estimates, the one or more precedence relationships and the availability of the one or more resources,

select a selected resulting estimated work order completion time from the two or more resulting estimated work order completion times based on one or more criteria,

schedule the plurality of tasks in a processing queue based on the selected resulting estimated work order completion time and a sequence of the two or more sequences,

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

wherein the value of the penalty function is based on the deadline and/or the selected estimated work order completion time, and

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

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

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

11. An apparatus according to claim 8,

wherein the selected estimated work order completion time minimizes the estimated work order completion time.

12. An apparatus according to claim 8, 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.

13. The apparatus according to claim 8, 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.

14. The apparatus according to claim 8, wherein the at least one work order, the plurality of tasks, or a combination thereof are related to raw film footage.