Batch scheduling

• US 9,250,952 B2
• Filed: 11/11/2013
• Issued: 02/02/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:
  US14/077,108
• Publication Number:
  US 20140075442A1
• Time in Patent Office: 813 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 method to schedule execution of a plurality of batch jobs by a computer system, the method comprising:

reading one or more constraints that constrain the execution of the plurality of batch jobs by the computer system, including constraints from a service level agreement specifying irregular run frequencies for the plurality of batch jobs, 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 of the operations 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;

computing an average number of operations per time period generated by the at least one batch job in the first run frequency on the computer system during an average duration of the at least one batch job based on a total number of operations generated by the at least one batch job;

computing a worst-case number of operations per time period generated by the at least one batch job in the first run frequency on the computer system by multiplying the at least one batch job'"'"'s average number of operations per time period by a factor that transforms the average number of operations per time period into a greatest number of operations per time period experienced during an execution of the at least one batch job; and

determining an optimized start time that meets the one or more constraints, for the at least one batch job in the first run frequency, based on adding the at least one batch job'"'"'s worst-case number of operations per time period to the expected number of operations per time period on the computer system at a proposed start time and comparing this value to a maximum number of operation per time period of the computer system.

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

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

4. The method of claim 3, 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.

5. The method of claim 4, further comprising:

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

computing an average number of operations per time period generated by the at least one batch job in the second run frequency on the computer system during average duration of the at least one batch job based on a total number of operations generated by the at least one batch job;

computing a worst-case number of operations per time period generated by the at least one batch job in the second run frequency on the computer system by multiplying the at least one batch job'"'"'s average number of operations per time period by a factor that transforms the average number of operations per time period in the second run frequency into a greatest number of operations per time period experienced during an execution of the at least one batch job; and

determining an optimized start time that meets the one or more constraints, for the at least one batch job in the second run frequency, based on adding the at least one batch job'"'"'s worst-case number of operations per time period to the updated expected number of operations per time period on the computer system at a proposed start time and comparing this value to a maximum number of operation per time period of the computer system.

6. A system to schedule execution of a plurality of batch jobs by a third party computer system, the system comprising:

at least one processor for implementing;

an input module adapted to read one or more constraints that constrain the execution of the plurality of batch jobs by the third party computer system, including constraints from a service level agreement, specifying irregular run frequencies for the plurality of batch jobs, and an expected number of operations per time period on the third party computer system;

a frequency regularization module adapted to define, for each batch job of the plurality of batch jobs, multiple batch jobs with regular run frequencies that together perform all of the operations of the batch job, to 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 to set the at least one run frequency to a first run frequency;

a load initialization module adapted to compute an average number of operations per time period generated by the at least one batch job in the first run frequency on the third party computer system during an average duration of the at least one batch job based on a total number of operations generated by the at least one batch job; and

compute a worst-case number of operations per time period generated by the at least one batch job in the first run frequency on the third party computer system by multiplying the at least one batch job'"'"'s average number of operations per time period by a factor that transforms the average number of operations per time period into a greatest number of operations per time period experienced during an execution of the at least one batch job; and

a start time determination module adapted to determine an optimized start time that meets the one or more constraints, for the at least one batch job in the first run frequency, based on adding the at least one batch job'"'"'s worst-case number of operations per time period to the expected number of operations per time period on the third party computer system at a proposed start time and comparing this value to a maximum number of operation per time period of the third party computer system.

7. The system of claim 6, further comprising a time initialization module for initializing each batch job'"'"'s proposed start time to a preset value.

8. The system of claim 6, further comprising a schedule generation module adapted to generate a batch job schedule for the first run frequency.

9. The system of claim 8, further comprising a load update module adapted to update the expected number of operations per time period on the third party computer system during the first run frequency based on the batch job schedule for the first run frequency.

10. The system of claim 9, wherein:

the frequency regularization module is further adapted to set the at east one run frequency to a second run frequency;

the load initialization module is further adapted to;

compute an average number of operations per time period generated by the at least one batch job in the second run frequency on the third party computer system during average duration of the at least one batch job based on a total number of operations generated by the at least one batch job; and

compute a worst-case number of operations per time period generated by the at least one batch job in the second run frequency on the third party computer system by multiplying the at least one batch job'"'"'s average number of operations per time period by a factor that transforms the average number of operations per time period in the second run frequency into a greatest number of operations per time period experienced during an execution of the at least one batch job; and

the start time determination module is further adapted to determine an optimized start time that meets the one or more constraints, for the at least one batch job in the second run frequency, based on adding the at least one batch job'"'"'s worst-case number of operations per time period to the updated expected number of operations per time period on the third party computer system at a proposed start time and comparing this value to a maximum number of operation per time period of the third party computer system.

11. A non-transitory machine-readable storage medium including a set of instructions to schedule execution of a plurality of batch jobs by a computer system, the instructions, when executed by a processor cause the machine to:

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

define, for each batch job of the plurality of batch jobs, multiple batch jobs with regular run frequencies that together perform all of the operations 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;

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

compute an average number of operations per time period generated by the at least one batch job in the first run frequency on the computer system during an average duration of the at least one batch job based on a total number of operations generated by the at least one batch job;

compute a worst-case number of operations per time period generated by the at least one batch job in the first run frequency on the computer system by multiplying the at least one batch job'"'"'s average number of operations per time period by a factor that transforms the average number of operations per time period into a greatest number of operations per time period experienced during an execution of the at least one batch job; and

determine an optimized start time that meets the one or more constraints, for the at least one batch job in the first run frequency, based on adding the at least one batch job'"'"'s worst-case number of operations per time period to the expected number of operations per time period on the computer system at a proposed start time and comparing this value to a maximum number of operation per time period of the computer system.

12. The machine-readable storage medium of claim 11, wherein the instructions cause the machine to initialize each batch job'"'"'s proposed start time to a preset value.

13. The machine-readable storage medium of claim 11, wherein the instructions cause the machine to generate a batch job schedule for the first run frequency.

14. The machine-readable storage medium of claim 13, wherein the instructions cause the machine 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.

15. The machine-readable storage medium of claim 14, wherein the instructions use the machine to:

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

compute an average number of operations per time period generated by the at least one batch job in the second run frequency on the computer system during average duration of the at least one batch job based on a total number of operations generated by the at least one batch job;

compute a worst-case number of operations per time period generated by the at least one batch job in the second run frequency on the computer system by multiplying the at least one batch job'"'"'s average number of operations per time period by a factor that transforms the average number of operations per time period in the second run frequency into a greatest number of operations per time period experienced during an execution of the at least one batch job; and

determine an optimized start time that meets the one or more constraints, for the at least one batch job in the second run frequency, based on adding the at least one batch job'"'"'s worst-case number of operations per time period to the updated expected number of operations per time period on the computer system at a proposed start time and comparing this value to a maximum number of operation per time period of the computer system.