Dynamic critical-path recalculation facility

• US 8,612,991 B2
• Filed: 11/24/2008
• Issued: 12/17/2013
• Est. Priority Date: 12/18/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Perticara', Valeria
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): KIM, SISLEY NAHYUN
• Application Number:
  US12/276,909
• Publication Number:
  US 20090158294A1
• Time in Patent Office: 1,849 Days
• Field of Search: None
• US Class Current: 718/106
• 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

Abstract

A method for dynamically recalculating a critical path in a job scheduling system is disclosed. In selected embodiments, the method may include determining when a first job associated with a critical path is substantially complete. The method may further include identifying a successor job of the first job and identifying multiple predecessor jobs of the successor job. The method may then determine whether there is at least one predecessor job that has not completed. In the event there is at least one predecessor job that has not completed, the method may recalculate the critical path. A corresponding apparatus and computer program product for implementing the above-stated method are also disclosed.

Claims

1. A method for dynamically recalculating a critical path in a job scheduling system, the method comprising:

determining that a first job in the critical path has completed;

identifying a successor job of the first job, wherein an initiation of the successor job is dependent on the completion of the first job;

identifying a predecessor job of the successor job, wherein the predecessor job is not the first job, and the initiation of the successor job is dependent on the completion of the predecessor job;

in the event the predecessor job has not completed, dynamically recalculating the critical path such that the recalculated critical path does not include the first job, wherein dynamically recalculating the critical path comprises ensuring a correct order of prioritization for jobs in the recalculated critical path; and

leaving the critical path unchanged in the event the predecessor job, as well as any other predecessor jobs of the successor job, have completed.

2. The method of claim 1, wherein recalculating the critical path comprises

employing a conventional critical path determination algorithm.

3. The method of claim 2, wherein employing the conventional critical path determination algorithm comprises

employing the conventional critical path determination algorithm starting from an earliest non-completed predecessor job.

4. A computer program product for dynamically recalculating a critical path in a job scheduling system, the computer program product comprising a non-transitory computer-readable storage medium having computer-usable program code embodied therein, the computer-usable program code comprising:

computer-usable program code for determining that a first job in the critical path has completed;

computer-usable program code for identifying a successor job of the first job, wherein an initiation of the successor job is dependent on the completion of the first job;

computer-usable program code for identifying a predecessor job of the successor job, wherein the predecessor job is not the first job, and the initiation of the successor job is dependent on the completion of the predecessor job;

computer-usable program code for, in the event the predecessor job has not completed, dynamically recalculating the critical path such that the recalculated critical path does not include the first job, wherein dynamically recalculating the critical path comprises ensuring a correct order of prioritization for jobs in the recalculated critical path; and

computer-usable program code for leaving the critical path unchanged in the event the predecessor job, as well as any other predecessor jobs of the successor job, have completed.

5. The computer program product of claim 4, further comprising computer-usable program code for recalculating the critical path by employing a conventional critical path determination algorithm.

6. The computer program product of claim 5, further comprising computer-usable program code for employing the conventional critical path determination algorithm starting at an earliest non-completed predecessor job.

7. An apparatus for dynamically recalculating a critical path in a job scheduling system, the apparatus comprising:

at least one processor;

at least one memory device coupled to the at least one processor and storing modules for execution on the at least one processor, the modules comprising;

a determination module to determine that a first job in the critical path has completed;

an identification module to identify a successor job of the first job, wherein an initiation of the successor job is dependent on the completion of the first job;

an identification module to identify a predecessor job of the successor job, wherein the predecessor job is not the first job, and the initiation of the successor job is dependent on the completion of the predecessor job; and

a recalculation module to, in the event the predecessor job has not completed, dynamically recalculate the critical path such that the recalculated critical path does not include the first job, wherein dynamically recalculating the critical path comprises ensuring a correct order of prioritization for jobs in the recalculated critical path, and leave the critical path unchanged in the event the predecessor job, as well as any other predecessor jobs of the successor job, have completed.

8. The apparatus of claim 7, wherein the recalculation module is further configured to employ a conventional critical path determination algorithm to recalculate the critical path.

9. The apparatus of claim 8, wherein the recalculation module is further configured to employ the conventional critical path determination algorithm starting at an earliest non-completed predecessor job.