Batch scheduling

• US 9,477,513 B2
• Filed: 02/01/2016
• Issued: 10/25/2016
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: eBay Inc.
• Original Assignee: eBay Inc.
• Inventors: Ferrandiz, Josep M.
• Primary Examiner(s): PATEL, HIREN P
• Application Number:
  US15/012,580
• Publication Number:
  US 20160147562A1
• Time in Patent Office: 267 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• 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

Abstract

There is provided a method to schedule execution of a plurality of batch jobs by a computer system. The method includes: reading one or more constraints that constrain the execution of the plurality of batch jobs by the computer system and a current load on the computer system; grouping the plurality of batch jobs into at least one run frequency that includes at least one batch job; setting the at least one run frequency to a first run frequency; computing a load generated by each batch job in the first run frequency on the computer system based on each batch job'"'"'s start time; and determining an optimized start time for each batch job in the first run frequency that meets the one or more constraints and that distributes each batch job'"'"'s load on the computer system using each batch job'"'"'s computed load and the current load.

Claims

1. A system comprising:

an input module comprising one or more processors and configured to access;

one or more constraints that constrain the execution of a plurality of batch jobs by a computer system, including constraints from a service level agreement specifying irregular run frequencies for the plurality of batch jobs;

a maximum number of operation per time period of the computer system; and

an expected number of operations per time period on the computer system;

a frequency regularization module comprising one or more processors and configured to;

define, for each batch job of the plurality of batch jobs, multiple batch jobs with regular run frequencies that together perform all irregular runs of the batch job;

group the batch jobs with regular run frequencies into at least one run frequency that includes at least one batch job with a regular run frequency; and

set the at least one run frequency to a first run frequency;

a size determination module comprising one or more processors and configured to;

determine a size of an input file of the at least one batch job in the first run frequency; and

determine a maximum size of the input file for the at least one batch job in the first run frequency at a start time that meets the one or more constraints based on subtracting the expected number of operations per time period on the computer system from the maximum number of operation per time period of the computer system for each time period from the start time up to an average duration of the at least one batch job and summing all results of the subtractions; and

a start time determination module comprising one or more processors and configured to begin the at least one batch job in the first run frequency at the start time based on the size of the input file of the at least one batch job in the first run frequency being less than the maximum size of the input file for the at least one batch job in the first run frequency.

2. The system of claim 1, wherein the size of the input file of the at least one batch job is based on a total number of lines in the input file.

3. The system of claim 1, further comprising a time initialization module comprising one or more processors and configured to initialize each batch job'"'"'s start time to a preset value.

4. The system of claim 1, further comprising a schedule generation module comprising one or more processors and configured to generate a batch job schedule for the first run frequency.

5. The system of claim 4, further comprising a load update module comprising one or more processors and configured to update the expected number of operations per time period on the computer system during the first run frequency based on the batch job schedule for the first run frequency.

6. The system of claim 5, wherein:

the frequency regularization module is further configured to set the at least one run frequency to a second run frequency;

the size determination module is further configured to;

determine a size of an input file of the at least one batch job in the second run frequency; and

determine a maximum size of the input file for the at least one batch job in the second run frequency at a second start time that meets the one or more constraints based on subtracting the updated expected number of operations per time period on the computer system from the maximum number of operation per time period of the computer system for each time period from the second start time up to an average duration of the at least one batch job and summing all results of the subtractions; and

the start time determination module is further configured to begin the at least one batch job in the second run frequency at the second start time based on the size of the input file of the at least one batch job in the second run frequency being less than the maximum size of the input file for the at least one batch job in the second run frequency.

7. The system of claim 6, wherein:

the schedule generation module is further configured to generate a batch job schedule for the second run frequency; and

the load update module is further configured to update the expected number of operations per time period on the computer system during the second run frequency based on the batch job schedule for the second run frequency.

8. A method comprising:

accessing one or more constraints that constrain the execution of a plurality of batch jobs by a computer system including constraints from a service level agreement specifying irregular run frequencies for the plurality of batch jobs, a maximum number of operation per time period of the computer system, and an expected number of operations per time period on the computer system;

defining, for each batch job of the plurality of batch jobs, multiple batch jobs with regular run frequencies that together perform all irregular runs of the batch job;

grouping the batch jobs with regular run frequencies into at least one run frequency that includes at least one batch job with a regular run frequency;

setting the at least one run frequency to a first run frequency;

determining a size of an input file of the at least one batch job in the first run frequency; and

determining a maximum size of the input file for the at least one batch job in the first run frequency at a start time that meets the one or more constraints based on subtracting the expected number of operations per time period on the computer system from the maximum number of operation per time period of the computer system for each time period from the start time up to an average duration of the at least one batch job and summing all results of the subtractions; and

beginning the at least one batch job in the first run frequency at the start time based on the size of the input file of the at least one batch job in the first run frequency being less than the maximum size of the input file for the at least one batch job in the first run frequency.

9. The method of claim 8, wherein the size of the input file of the at least one batch job is based on a total number of lines in the input file.

10. The method of claim 8, further comprising initializing each batch job'"'"'s start time to a preset value.

11. The method of claim 8, further comprising generating a batch job schedule for the first run frequency.

12. The system of claim 11, further comprising updating the expected number of operations per time period on the computer system during the first run frequency based on the batch job schedule for the first run frequency.

13. The method of claim 12, further comprising:

setting the at least one run frequency to a second run frequency;

computing a size of an input file of the at least one batch job in the second run frequency; and

determining a maximum size of the input file for the at least one batch job in the second run frequency at a second start time that meets the one or more constraints based on subtracting the updated expected number of operations per time period on the computer system from the maximum number of operation per time period of the computer system for each time period from the second start time up to an average duration of the at least one batch job and summing all results of the subtractions; and

beginning the at least one batch job in the second run frequency at the second start time based on the size of the input file of the at least one batch job in the second run frequency being less than the maximum size of the input file for the at least one batch job in the second run frequency.

14. The method of claim 13, further comprising:

generating a batch job schedule for the second run frequency; and

updating the expected number of operations per time period on the computer system during the second run frequency based on the batch job schedule for the second run frequency.

15. A machine-readable hardware storage device containing instructions that, when executed by a processor of a machine, cause the machine to perform operations comprising:

accessing one or more constraints that constrain the execution of a plurality of batch jobs by a computer system including constraints from a service level agreement specifying irregular run frequencies for the plurality of batch jobs, a maximum number of operation per time period of the computer system, and an expected number of operations per time period on the computer system;

defining, for each batch job of the plurality of batch jobs, multiple batch jobs with regular run frequencies that together perform all irregular runs of the batch job;

grouping the batch jobs with regular run frequencies into at least one run frequency that includes at least one batch job with a regular run frequency;

setting the at least one run frequency to a first run frequency;

determining a size of an input file of the at least one batch job in the first run frequency; and

determining a maximum size of the input file for the at least one batch job in the first run frequency at a start time that meets the one or more constraints based on subtracting the expected number of operations per time period on the computer system from the maximum number of operation per time period of the computer for each time period from the start time up to an average duration of the at least one batch job and summing all results of the subtractions; and

beginning the at least one batch job in the first run frequency at the start time based on the size of the input file of the at least one batch job in the first run frequency being less than the maximum size of the input file for the at least one batch job in the first run frequency.

16. The machine-readable hardware storage device of claim 15, wherein the size of the input file of the at least one batch job is based on a total number of lines in the input file.

17. The machine-readable hardware storage device of claim 15, the operations further comprising initializing each batch job'"'"'s start time to a preset value.

18. The machine-readable hardware storage device of claim 15, the operations further comprising generating a batch job schedule for the first run frequency.

19. The machine-readable hardware storage device of claim 18, the operations further comprising updating the expected number of operations per time period on the computer system during the first run frequency based on the batch job schedule for the first run frequency.

20. The machine-readable hardware storage device of claim 19, the operations further comprising:

setting the at least one run frequency to a second run frequency;

computing a size of an input file of the at least one batch job in the second run frequency; and

determining a maximum size of the input file for the at least one batch job in the second run frequency at a second start time that meets the one or more constraints based on subtracting the updated expected number of operations per time period on the computer system from the maximum number of operation per time period of the computer for each time period from the second start time up to an average duration of the at least one batch job and summing all results of the subtractions; and

beginning the at least one batch job in the second run frequency at the second start time based on the size of the input file of the at least one batch job in the second run frequency being less than the maximum size of the input file for the at least one batch job in the second run frequency.