COST-MINIMIZING TASK SCHEDULER

• US 20140229221A1
• Filed: 02/11/2013
• Published: 08/14/2014
• Est. Priority Date: 02/11/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: SHIH, KATHRYN MARIE, CHRISTOFFERSON, CARL LOUIS, COLE, RICHARD JEFFREY, SIROTA, PETER, AGGARWAL, VAIBHAV
• Granted Patent: US 10,552,774 B2
• Time in Patent Office: Days
• US Class Current: 705/7.23
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/06313 Resource planning in a project environment
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis

Abstract

Methods and systems for cost-minimizing job scheduling are disclosed. A definition of a task is received. The definition comprises a need-by time. The need-by time comprises a deadline for completion of execution of the task. An estimated duration to complete the execution of the task is determined for each of a plurality of computing resources. One or more of the computing resources are selected based on an estimated cost of completing the execution using the computing resources. The execution of the task is initiated at a scheduled time using the selected one or more computing resources. The scheduled time is earlier than the need-by time by at least the estimated duration.

Claims

1. A system, comprising:

a plurality of computing devices configured to implement a plurality of resources of a provider network, wherein the resources are organized into a plurality of resource pools, wherein each resource pool has an associated usage cost; and

one or more computing devices configured to implement a resource manager, wherein the resource manager is operable to;

receive a task specification comprising a need-by time for a task, wherein the need-by time comprises a deadline for completion of execution of the task;

determine a respective estimated duration to complete the execution of the task for each of a plurality of resource configurations of the plurality of resource pools;

select one or more resource configurations having a lowest usage cost from the ones of the plurality of resource configurations having a respective estimated duration allowing completion of the execution of the task prior to the need-by time;

determine a scheduled time for initiation of the execution of the task on one or more of the resource pools having the selected one or more resource configurations, wherein the scheduled time is earlier than the need-by time by at least the estimated duration; and

ensure the completion of the execution of the task on the one or more resource pools having the selected one or more resource configurations prior to the need-by time.

2. The system as recited in claim 1, wherein the task corresponds to a first node in a graph comprising a plurality of additional nodes, wherein each of the plurality of additional nodes corresponds to a respective additional task, and wherein the one or more resource configurations are selected to minimize a global cost of executing the task and one or more of the additional tasks.

3. The system as recited in claim 1, wherein the resource manager is operable to:

determine a customer price for the execution of the task, wherein the customer price comprises a discount based on the need-by time.

4. The system as recited in claim 1, wherein an execution window for the task begins at a first point in time and ends at a second point in time, wherein the first point in time comprises a point in time at which the definition of the task is received, wherein the second point in time is based on the need-by time, and wherein the discount varies based on a size of the execution window.

5. A computer-implemented method, comprising:

receiving a definition of a task, wherein the definition comprises a need-by time, wherein the need-by time comprises a user-specified deadline for completion of execution of the task;

determining an estimated duration to complete the execution of the task for each of a plurality of computing resources;

selecting one or more of the computing resources based on an estimated cost of completing the execution of the task for each of the plurality of computing resources; and

initiating the execution of the task at a scheduled time using the selected one or more computing resources, wherein the scheduled time is earlier than the need-by time by at least the estimated duration.

6. The method as recited in claim 5, further comprising:

selecting a configuration for the one or more computing resources for the execution of the task, wherein the configuration is selected to minimize a cost of the execution of the task within an execution window, wherein an endpoint of the execution window is based on the need-by time.

7. The method as recited in claim 5, wherein the plurality of computing resources vary in usage cost, and wherein selecting one or more of the computing resources comprises:

selecting the one or more computing resources having the lowest usage cost from the ones of the plurality of computing resources having a respective estimated duration allowing completion of the execution of the task prior to the need-by time;

wherein the execution of the task is initiated at the scheduled time using the selected one or more computing resources.

8. The method as recited in claim 5, wherein the estimated duration to complete the execution of the task is determined based on one or more prior executions of the task.

9. The method as recited in claim 5, wherein the estimated duration to complete the execution of the task is determined based on a prior execution of one or more other tasks.

10. The method as recited in claim 5, wherein the one or more computing resources are selected to minimize a global cost of executing the task and one or more additional tasks.

11. The method as recited in claim 5, further comprising:

assessing a customer price for the execution of the task, wherein the customer price comprises a discount based on the need-by time.

12. The method as recited in claim 11, wherein an execution window for the task begins at a first point in time and ends at a second point in time, wherein the first point in time comprises a point in time at which the definition of the task is received, wherein the second point in time is based on the need-by time, and wherein the discount varies based on a size of the execution window.

13. A system, comprising:

at least one processor;

a memory coupled to the at least one processor, wherein the memory stores program instructions, wherein the program instructions are executable by the at least one processor to;

receive a need-by time for a task, wherein the need-by time comprises a deadline for completion of execution of the task;

determine an estimated duration to complete the execution of the task for each of a plurality of resource configurations, wherein each of the plurality of resource configurations has a respective usage cost;

selecting one or more of the resource configurations to minimize a cost of the execution of the task within an execution window, wherein an endpoint of the execution window is based on the need-by time; and

determine a scheduled time for the execution of the task on one or more compute instances having the selected one or more resource configurations, wherein the scheduled time is earlier than the need-by time by at least the estimated duration.

14. The system as recited in claim 13, wherein the one or more resource configurations are selected to minimize a global cost of execution of the task and one or more additional tasks.

15. The system as recited in claim 13, wherein, in selecting one or more of the resource configurations, the program instructions are further executable by the at least one processor to:

select the one or more resource configurations having the lowest usage cost from the ones of the plurality of resource configurations having a respective estimated duration allowing completion of the execution of the task prior to the need-by time.

16. The system as recited in claim 13, wherein the estimated duration to complete the execution of the task is determined based on one or more prior executions of the task.

17. The system as recited in claim 13, wherein the program instructions are further executable by the at least one processor to:

determine a customer price for the execution of the task, wherein the customer price comprises a discount based on the need-by time.

18. The system as recited in claim 17, wherein an execution window for the task begins at a first point in time and ends at a second point in time, wherein the first point in time comprises a point in time at which the definition of the task is received, wherein the second point in time is based on the need-by time, and wherein the discount varies based on a size of the execution window.

19. A computer-readable storage medium storing program instructions computer-executable to perform:

receiving a definition of a task, wherein the definition comprises a deadline for completion of execution of the task;

selecting one or more resource configurations for the execution of the task, wherein the one or more resource configurations are selected to minimize a cost of the execution of the task; and

scheduling the task for execution using the selected one or more resource configurations at a scheduled time, wherein the scheduled time is earlier than the deadline by at least an estimated duration to complete the execution of the task.

20. The computer-readable storage medium as recited in claim 19, wherein the one or more resource configurations are selected to minimize a global cost of execution of the task and one or more additional tasks.

21. The computer-readable storage medium as recited in claim 19, wherein the plurality of resource configurations vary in usage cost, and wherein selecting the one or more resource configurations further comprises:

selecting the one or more resource configurations having the lowest usage cost from the ones of the plurality of resource configurations able to complete the execution of the task prior to the deadline;

wherein the execution of the task is initiated at the scheduled time using the selected one or more resource configurations.

22. The computer-readable storage medium as recited in claim 19, wherein the estimated duration to complete the execution of the task is determined based on one or more prior executions of the task.

23. The computer-readable storage medium as recited in claim 19, wherein the program instructions are further computer-executable to perform:

assessing a customer price for the execution of the task, wherein the customer price comprises a discount based on the deadline.

24. The computer-readable storage medium as recited in claim 23, wherein an execution window for the task begins at a first point in time and ends at a second point in time, wherein the first point in time comprises a point in time at which the definition of the task is received, wherein the second point in time is based on the deadline, and wherein the discount varies based on a size of the execution window.