Method and system for traversing in reverse chronological order along a critical path of a plurality of jobs, and reducing time gaps between jobs until an estimated end time of the last job is less than or equal to a target end time

• US 8,473,951 B2
• Filed: 12/30/2009
• Issued: 06/25/2013
• Est. Priority Date: 12/30/2009
• Status: Active Grant

• Current Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Original Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Inventors: Sharon, Eyal, Tourgeman, Yoel, Tchenak, Yakov, Admon, Tamar, Amram, Hana, Chenkin, Ohad
• Primary Examiner(s): Lee, Thomas
• Assistant Examiner(s): Chen, Xuxing
• Application Number:
  US12/649,925
• Publication Number:
  US 20110161959A1
• Time in Patent Office: 1,273 Days
• Field of Search: 718/101, 718/102
• US Class Current: 718/101
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

Systems and methods for improved batch flow management are described. At least some embodiments include a computer system for managing a job flow including a memory storing a plurality of batch queue jobs grouped into Services each including a job and a predecessor job. A time difference is the difference between a scheduled job start time and an estimated predecessor job end time. Jobs with a preceding time gap include jobs immediately preceded only by non-zero time differences. The job start depends upon the predecessor job completion. The computer system further includes a processing unit that identifies jobs preceded by a time gap, selects one of the Services, and traverses in reverse chronological order a critical path of dependent jobs within the Service until a latest job with a preceding time gap is identified or at least those jobs along the critical path preceded by another job are traversed.

Claims

1. A computer system for managing a flow of batch jobs, comprising:

a memory comprising a plurality of jobs within a batch queue grouped together into one or more services that each comprises a job and a predecessor job, wherein a time difference comprises the difference between a scheduled start time of the job and an estimated end time of the predecessor job,

wherein jobs with a preceding time gap comprise jobs immediately preceded only by non-zero time differences, and

wherein the job start depends upon the predecessor job completion; and

a processing unit, coupled to the memory, that identifies those jobs of the plurality of jobs preceded by a time gap, selects a service of the one or more services, traverses in reverse chronological order a critical path of dependent jobs within the selected service until a latest job with a preceding time gap is identified or until at least those jobs along the critical path preceded by another job are traversed,

reduces the time difference between the latest job with a preceding time gap and a nearest predecessor job, and

repeats the traversing and reducing until no jobs with time gaps remain along the critical path or until an estimated end time of the selected service is less than or equal to a target end time,

wherein the processing unit traverses the critical path by selecting, for each job preceded by another job along the critical path, a nearest predecessor job with an estimated end time that is closest to, but not greater than, a scheduled start time of a currently selected job.

2. The computer system of claim 1, further comprising a display device, wherein the latest job with a preceding time gap, if identified, is indicated on the display device.

3. The computer system of claim 1, wherein the processing unit further adds new jobs to a service.

4. The computer system of claim 3, wherein the processing unit further runs a simulation to estimate an execution end time for the service.

5. The computer system of claim 1, wherein the processing unit further repeats the service selection for each of the one or more services.

6. The computer system of claim 1, wherein the processing unit simulates the execution of all scheduled jobs within the batch queue to estimate the end time of each of the plurality of jobs.

7. A method for managing a flow of batch jobs within a computer system, comprising:

grouping, by the computer system, a plurality of jobs within a batch queue into one or more services that each comprises a job and a predecessor job;

determining, by the computer system, a time difference comprising the difference between a scheduled start time of the job and an estimated end time of the predecessor job, the job start depending upon the predecessor job completion;

identifying, by the computer system, those jobs of the plurality of jobs preceded by a time gap, which comprise jobs immediately preceded only by non-zero time differences;

selecting, by the computer system, a service of the one or more services;

traversing, by the computer system, in reverse chronological order a critical path of dependent jobs within the selected service until a latest job with a preceding time gap is identified or until at least those jobs along the critical path preceded by another job are traversed;

reducing, by the computer system, the time difference between the latest job with a preceding time gap and a nearest predecessor job; and

repeating the traversing and reducing until no jobs with time gaps remain along the critical path or until an estimated end time of the selected service is less than or equal to a target end time,

wherein traversing the critical path comprises selecting, for each job preceded by another job along the critical path, a nearest predecessor job with an estimated end time that is closest to, but not greater than, a scheduled start time of a currently selected job.

8. The method of claim 7, further comprising displaying, if identified, the latest job with a preceding time gap by the computer system.

9. The method of claim 7, further comprising adding, by the computer system, new jobs to a service.

10. The method of claim 9, further comprising running a simulation to estimate an execution end time for the service.

11. The method of claim 7, further comprising repeating the selecting for each of the one or more services.

12. The method of claim 7, further comprising estimating, by the computer system, the end time of each of the plurality of jobs by performing a simulation of the execution of all scheduled jobs within the batch queue.

13. A non-transitory computer-readable storage medium comprising software that can be executed on a processor to cause the processor to perform a method for managing a flow of batch jobs within a computer system, comprising:

grouping, by the computer system, a plurality of jobs within a batch queue into one or more services that each comprises a job and a predecessor job;

determining, by the computer system, a time difference comprising the difference between a scheduled start time of the job and an estimated end time of the predecessor job, the job start depending upon the predecessor job completion;

identifying, by the computer system, those jobs of the plurality of jobs preceded by a time gap, which comprise jobs immediately preceded only by non-zero time differences;

selecting, by the computer system, a service of the one or more services;

traversing, by the computer system, in reverse chronological order a critical path of dependent jobs within the selected service until a latest job with a preceding time gap is identified or until at least those jobs along the critical path preceded by another job are traversed;

reducing, by the computer system, the time difference between the latest job with a preceding time gap and a nearest predecessor job; and

repeating the traversing and reducing until no jobs with time gaps remain along the critical path or until an estimated end time of the selected service is less than or equal to a target end time,

wherein traversing the critical path comprising selecting, for each job preceded by another job along the critical path, a nearest predecessor job with an estimated end time that is closest to, but not greater than, a scheduled start time of a currently selected job.

14. A networked computer system, comprising:

a communication network; and

a plurality of computer systems each coupled to the communication network, at least one computer system of the plurality of computer systems comprising;

a memory comprising a plurality of jobs within a batch queue grouped together into one or more services that each comprises a job and a predecessor job,

wherein a time difference comprises the difference between a scheduled start time of the job and an estimated end time of the predecessor job,

wherein jobs with a preceding time gap comprise jobs immediately preceded only by non-zero time differences, and wherein the job start depends upon the predecessor job completion; and

a processing unit, coupled to the memory, that identifies those jobs of the plurality of jobs preceded by a time gap, selects a service of the one or more services, and traverses in reverse chronological order a critical path of dependent jobs within the selected service until a latest job with a preceding time gap is identified or until at least those jobs along the critical path preceded by another job are traversed,

reduces the time difference between the latest job with a preceding time gap and a nearest predecessor job, and

repeats the traversing and reducing until no jobs with time gaps remain along the critical path or until an estimated end time of the selected service is less than or equal to a target end time,

wherein the processing unit traverses the critical path by selecting, for each job preceded by another job along the critical path, a nearest predecessor job with an estimated end time that is closest to, but not greater than, a scheduled start time of a currently selected job.

15. The networked computer system of claim 14, wherein the at least one computer system further comprises a display device, and wherein the latest job with a preceding time gap, if identified, is indicated on the display device.

16. The networked computer system of claim 14, where the processing unit further adds new jobs to a service.

17. The computer system of claim 16, wherein the processing unit further runs a simulation to estimate an execution end time for the service.

18. The networked computer system of claim 14, wherein the processing unit further repeats the service selection for each of the one or more services.

19. The networked computer system of claim 14, wherein the processing unit simulates the execution of all scheduled jobs within the batch queue to estimate the end time of each of the plurality of jobs.