Dynamic critical path update facility

• US 8,266,622 B2
• Filed: 12/08/2008
• Issued: 09/11/2012
• Est. Priority Date: 12/18/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cardelli, Marco
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US12/329,809
• Publication Number:
  US 20090158287A1
• Time in Patent Office: 1,373 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 11/0715 in a system implementing multitasking multitasking per se G06F9/46
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/0766 Error or fault reporting or storing
• CPC Class Codes: G06F 11/3414 Workload generation, e.g. scripts, playback
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• 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 is presented for dynamically selecting and updating a critical execution path. The method may include receiving a network of jobs for execution. One or more critical jobs may be included in the network of jobs. A job causing a delay in the execution of the network of jobs may be detected, where the job precedes the critical job. A critical path in the network of jobs may then be determined as a function of the job causing a delay. Determination of the critical path may be further based on a slack time associated with jobs in the network that have planned execution times preceding a planned execution time for the critical job.

Claims

1. A method for dynamically selecting a critical execution path in a network of jobs, the method comprising:

receiving a network of jobs for execution, the network of jobs comprising a critical job having a completion deadline and a plurality of predecessor jobs that need to be completed prior to completing the critical job;

determining a workload plan for executing the network of jobs to enable the critical job to complete by the completion deadline;

including, in the workload plan, a planned start time and a latest start time for each predecessor job of the plurality of predecessor jobs;

determining a critical path through the network of jobs by finding a path through the predecessor jobs with a lowest slack time;

detecting, by at least one processor during execution of the network of jobs, whether a predecessor job did not start in time to meet its latest start time specified in the workload plan; and

recalculating the critical path in the event the predecessor job did not start in time to meet its latest start time.

2. The method of claim 1, further comprising including, in the workload plan, an estimated duration time for each predecessor job of the plurality of predecessor jobs.

3. The method of claim 2, further comprising determining, during execution of the network of jobs, whether a predecessor job of the plurality of predecessor jobs took longer than its estimated duration time to complete.

4. The method of claim 1, further comprising recalculating the critical path in the event a predecessor job from the plurality of predecessor jobs took longer than its estimated duration time to complete.

5. The method of claim 1, further comprising determining whether execution of a predecessor job from the plurality of predecessor jobs resulted in error.

6. The method of claim 5, further comprising recalculating the critical path in the event execution of a predecessor job from the plurality of predecessor jobs resulted in error.

7. An apparatus for dynamically selecting a critical execution path, the apparatus comprising:

at least one processor;

at least One memory device coupled to the at least one processor and storing computer instructions for execution on the at least one processor, the computer instructions enabling the at least one processor to;

receive a network of jobs for execution, the network of jobs comprising a critical job having a completion deadline and a plurality of predecessor jobs that need to be completed prior to completing the critical job;

determine a workload plan for executing the network of jobs to enable the critical job to complete by the completion deadline;

include, in the workload plan, a planned start time and a latest start time for each predecessor job of the plurality of predecessor jobs;

determine a critical path through the network of jobs by finding a path through the predecessor jobs with a lowest slack time;

detect, during execution of the network of jobs, whether a predecessor job did not start in time to meet its latest start time specified in the workload plan; and

recalculate the critical path in the event the predecessor job did not start in time to meet its latest start time.

8. The apparatus of claim 7, wherein the computer instructions further enable the at least one processor to include, in the workload plan, an estimated duration time for each predecessor job of the plurality of predecessor jobs.

9. The apparatus of claim 8, wherein the computer instructions further enable the at least one processor to determine, during execution of the network of jobs, whether a predecessor job of the plurality of predecessor jobs took longer than its estimated duration time to complete.

10. The apparatus of claim 9, wherein the computer instructions further enable the at least one processor to recalculate the critical path in the event a predecessor job from the plurality of predecessor jobs took longer than its estimated duration time to complete.

11. The apparatus of claim 7, wherein the computer instructions further enable the at least one processor to determine whether execution of a predecessor job from the plurality of predecessor jobs resulted in error.

12. The apparatus of claim 11, wherein the computer instructions further enable the at least one processor to recalculate the critical path in the event execution of a predecessor job from the plurality of predecessor jobs resulted in error.

13. The apparatus of claim 7, wherein the computer instructions further enable the at least one processor to receive a workload model and determine the critical path based on the workload model.

14. A computer program product for dynamically selecting a critical execution path, the computer program product comprising a non-transitory computer-readable storage medium having computer-usable program code stored therein the computer-usable program code comprising:

computer-usable program code to receive a network of jobs for execution, the network of jobs comprising a critical job having a completion deadline and a plurality of predecessor jobs that need to be completed prior to completing the critical job;

computer-usable program code to determine a workload plan for executing the network of jobs to enable the critical job to complete by the completion deadline;

computer-usable program code to include, in the workload plan, a planned start time and a latest start time for each predecessor job of the plurality of predecessor jobs;

computer-usable program code to determine a critical path through the network of jobs by finding a path through the predecessor jobs with a lowest slack time;

computer-usable program code to detect, during execution of the network of jobs, whether a predecessor job did not start in time to meet its latest start time specified in the workload plan; and

computer-usable program code to recalculate the critical path in the event the predecessor job did not start in time to meet its latest start time.

15. The computer program product of claim 14, further comprising computer-usable program code to include, in the workload plan, an estimated duration time for each predecessor job of the plurality of predecessor jobs.

16. The computer program product of claim 15, further comprising computer-usable program code to determine, during execution of the network of jobs, whether a predecessor job of the plurality of predecessor jobs took longer than its estimated duration time to complete.

17. The computer program product of claim 16, further comprising computer-usable program code to recalculate the critical path in the event a predecessor job from the plurality of predecessor jobs took longer than its estimated duration time to complete.

18. The computer program product of claim 14, further comprising computer-usable program code to determine whether execution of a predecessor job from the plurality of predecessor jobs resulted in error.

19. The computer program product of claim 18, further comprising computer-usable program code to recalculate the critical path in the event execution of a predecessor job from the plurality of predecessor jobs resulted in error.