Batch processing job streams using and/or precedence logic

• US 20030149717A1
• Filed: 01/31/2003
• Published: 08/07/2003
• Est. Priority Date: 02/05/2002
• Status: Abandoned Application

• Current Assignee: Sourcespring Software LLC
• Original Assignee: Sourcespring Software LLC
• Inventors: Heinzman, William
• Application Number:
  US10/355,367
• Publication Number:
  US 20030149717A1
• Time in Patent Office: Days
• US Class Current: 718/101
• 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
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A product and associated methodology provided for scheduling job streams and leveling machine loads automatically without regard to specific knowledge of a job'"'"'s internals or estimates of its machine load and without specific knowledge of a machine'"'"'s resources or its total machine load capability. This involves use of a generalized critical path method algorithm in conjunction with a resource leveling algorithm. The generalized CPM algorithm supports arbitrary precedence logic and precedence types. The invention can therefore provide automatic resource leveling in connection with a broad range of practical applications including managing resources of a computer network.

Claims

1. A method for use in analyzing job streams, comprising the steps of:

receiving input information defining a job stream including arbitrary precedence logic, said job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent on an outcome of one or more of said predecessor jobs, and said arbitrary precedence logic includes at least one AND precedence set such that execution of first successor job is dependent on an outcome of each of two or more of said predecessor jobs and at least one OR precedence set such that execution of a second successor job, that may be the same or different than said first successor job, is dependent on an outcome of less than all of two or more predecessor jobs;

first configuring a first processor to execute a Critical Path Method (CPM) algorithm adapted to handle said arbitrary precedence logic, said CPM algorithm involving the identification of a job path within said job stream wherein each job of said job path has an identical early start and late start time upon proper application of all associated precedences; and

first employing said processor to process said job stream using said CPM algorithm.

2. A method as set forth in claim 1, wherein said job stream is a batch process job stream of a computer network.

3. A method as set forth in claim 1, wherein said step of first employing comprises simulating said job stream using said CPM algorithm.

4. A method as set forth in claim 1, wherein said step of first employing comprises analyzing said job stream using said CPM algorithm.

5. A method as set forth in claim 1, wherein said step of first employing comprises optimizing said job stream using said CPM algorithm.

6. A method as set forth in claim 1, further comprising the steps of:

second configuring a second processor, which may be the same as or different than said first processor, to execute a resource leveling algorithm based at least in part on said CPM algorithm, said resource leveling algorithm being directed to moderating a usage extremum of at least one resource of said defined resource set, said extremum being one of a relative minimum usage level of said resource and a relative maximum usage level of said resource; and

second employing said second processor to process said job stream using said resource leveling algorithm.

7. A method as set forth in claim 6, wherein said step of second employing comprises identifying a non-critical path job and rescheduling said non-critical path job.

8. A method as set forth in claim 1, wherein said step of first configuring comprises executing said algorithm so as to handle arbitrary precedent types, said arbitrary precedence types including at least a first outcome type relating to a first outcome of a first predecessor job and a second outcome type, different than said first outcome type, relating to a second outcome of a second predecessor job.

9. A method as set forth in claim 1, wherein said first processor is further operative for determining a first float of a first job and a second float of a second job related to said first job, said second float including a transferred portion associated with said first float of said first job.

10. A method as set forth in claim 1, wherein said job stream includes a parent object and first and second child objects and said processor is operative to determine a float of one of said first and second child objects that is due at least in part to an inheritance from the parent object.

11. A method as set forth in claim 8, wherein said second float is comprised entirely of said inherited portion associated with said first float of said first predecessor job.

12. A method as set forth in claim 1, wherein said first processor is further operative for graphically depicting, on a graphical user interface, output information including float for at least one job of said predecessor jobs and successor jobs.

13. A method as set forth in claim 12, wherein said first processor is further operative for executing changes to a schedule of said job stream in response to user inputs entered relative to said graphical user interface.

14. A method as set forth in claim 1, wherein said first processor is operative for determining a float for a first job of said predecessor and successor jobs and for making a determination regarding a time for triggering an alarm concerning a delay in completion of said first job, said determination being based at least in part on said float of said first job.

15. A method as set forth in claim 1, wherein said first processor is operative to add a float to said entire job stream and use said float to schedule execution of said job stream.

16. A method as set forth in claim 1, wherein said first processor is further operative for monitoring execution of said job stream and dynamically rescheduling jobs of said job stream based on said monitoring.

17. A method for use in analyzing job streams, comprising the steps of:

receiving input information defining a job stream including arbitrary precedence types, said job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent on an outcome of one or more of said predecessor jobs, and said arbitrary precedence types include at least a first outcome type relating to a first outcome of a first predecessor job and a second outcome type, different than said first outcome type, relating to a second outcome of a second predecessor job;

first configuring a first processor to execute a Critical Path Method (CPM) algorithm adapted to handle said arbitrary precedence types, said CPM algorithm involving the identification of a job path within said job stream wherein each job of said job path has an identical early start and late start time upon proper application of associated precedences; and

first employing said processor to process said job stream using said CPM algorithm.

18. A method as set forth in claim 17, wherein said job stream is a batch process job stream of a computer network.

19. A method as set forth in claim 17, wherein said step of first employing comprises simulating said job stream using said CPM algorithm.

20. A method as set forth in claim 17, wherein said step of first employing comprises analyzing said job stream using said CPM algorithm.

21. A method as set forth in claim 17, wherein said step of first employing comprises optimizing said job stream using said CPM algorithm.

22. A method as set forth in claim 17, further comprising the steps of:

second configuring a second processor, which may be the same as or different than said first processor, to execute a resource leveling algorithm based at least in part on said CPM algorithm, said resource leveling algorithm being directed to moderating a usage extremum of at least one resource of said defined resource set, said extremum being one of a relative minimum usage level of said resource and a relative maximum usage level of said resource; and

second employing said second processor to process said job stream using said resource leveling algorithm.

23. A method as set forth in claim 17, wherein said step of second employing comprises identifying a non-critical path job and rescheduling said non-critical path job.

24. A method as set forth in claim 17, wherein said first processor is further operative for determining a first float of a first job and a second float of a second job related to said first job, said second float including a transferred portion associated with said first float of said first job.

25. A method as set forth in claim 17, wherein said first processor is further operative for graphically depicting, on a graphical user interface, output information including float for at least one job of said predecessor jobs and successor jobs.

26. A method as set forth in claim 25, wherein said first processor is further operative for executing changes to a schedule of said job stream in response to user inputs entered relative to said graphical user interface.

27. A method as set forth in claim 17, wherein said first processor is operative to add a float to said entire job stream and use said float to schedule execution of said job stream.

28. A method as set forth in claim 17, wherein said first processor is further operative for monitoring execution of said job stream and dynamically rescheduling jobs of said job stream based on said monitoring.

29. A method for use in analyzing job streams, comprising the steps of:

receiving input information defining a job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent on a completion of one or more of said predecessor jobs;

first configuring a first processor to execute a resource leveling algorithm directed to moderating a usage extremum of at least one resource of said defined resource set, said extremum being one of a relative minimum usage level of said resource and a relative maximum usage level of said resource; and

first employing said first processor to process said job stream using said resource leveling algorithm.

30. A method as set forth in claim 29, wherein said job stream is a batch process job stream of a computer network.

31. A method as set forth in claim 29, wherein said step of first employing comprises identifying a non-critical path job and rescheduling said non-critical path job.

32. A method as set forth in claim 29, wherein said first processor is operative to execute a critical path method algorithm adapted to handle arbitrary precedence logic, said arbitrary precedence logic including at least one AND precedence set such that execution of a first successor job is dependent on an outcome of each of two or more predecessor jobs and at least one OR precedence set such that execution of a second successor job, that may be the same or different than said first successor job, is dependent on an outcome of less than all of two or more predecessor jobs.

33. A method as set forth in claim 29, wherein said first processor is operative to execute a critical path method algorithm adapted to handle arbitrary precedence types, said arbitrary precedence types including at least a first outcome type relating to a first outcome of a first predecessor job and a second outcome type, different than said first outcome type, relating to a second outcome of a second predecessor job.

34. A method as set forth in claim 29, wherein said first processor is operative for determining a first float of a first job and a second float of a second job related to said first job, said second float including a transferred portion associated with said first float of said first job.

35. A method as set forth in claim 29, wherein said first processor is further operative for graphically depicting, on a graphical user interface, output information including float for at least one job of said predecessor jobs and successor jobs.

36. A method as set forth in claim 35, wherein said first processor is further operative for executing changes to a schedule of said job stream in response to user inputs entered relative to said graphical user interface.

37. A method as set forth in claim 29, wherein said first processor is operative to add a float to said entire job stream and use said float to schedule execution of said job stream.

38. A scheduler, comprising:

input structure configured to receive input information defining a job stream including arbitrary precedence logic, said job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent on an outcome of one or more of said predecessor jobs, and said arbitrary precedence logic includes at least one AND precedence set such that execution of first successor job is dependent on an outcome of each of two or more of said predecessor jobs and at least one OR precedence set such that execution of a second successor job, that may be the same or different than said first successor job, is dependent on an outcome of less than all of two or more predecessor jobs;

processing structure configured to execute a Critical Path Method (CPM) algorithm adapted to handle said arbitrary precedence logic, said CPM algorithm involving the identification of a job path within said job stream wherein each job of said job path has an identical early start and late start time upon proper application of all associated precedences; and

output structure for providing an output based on processing of the job stream by said processing structure using the CPM algorithm.

39. A scheduler as set forth in claim 38, wherein said processing structure is configured to execute said algorithm so as to handle arbitrary precedence types, said arbitrary precedence types including at least a first outcome type relating to a first outcome of a first predecessor job and a second outcome type, different than said first outcome type, relating to a second outcome of a second predecessor job.

40. A scheduler as set forth in claim 38, wherein said input structure is configured to execute a resource leveling algorithm based at least in part on said CPM algorithm, said resource leveling algorithm being directed to moderating a usage extremum of at least one resource of said defined resource set, said extremum being one of a relative minimum usage level of said resource and a relative maximum usage level of said resource.

41. A scheduler, comprising:

input structure configured to receive input information defining a job stream including arbitrary precedence types, said job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, wherein execution of each of said successor jobs is dependent on an outcome of one or more of said predecessor jobs, and said arbitrary precedence types include at least a first outcome type relating to a first outcome of a first predecessor job and a second outcome type, different than said first outcome type, relating to a second outcome of a second predecessor job;

processing structure configured to execute a critical path method algorithm adapted to handle said arbitrary precedence types, said CPM algorithm involving the identification of a job path within said job stream, wherein each job of said job path has an identical Early Start and Late Start time upon proper application of said associated precedences; and

output structure for providing an output based on processing of the job stream by said processing structure using the CPM algorithm.

42. A scheduler as set forth in claim 41, wherein said processing structure is operative to execute a resource leveling algorithm based at least in part on said CPM algorithm, said resource leveling algorithm being directed to moderating a usage extremum of at least one resource of said defined resource set, said extremum being one of a relative minimum usage level of said resource and a relative maximum usage level of said resource.

43. A method for use in analyzing job streams, comprising the steps of:

receiving input information including a definition of a job stream involving a number of jobs to be executed using a defined resource set;

identifying a parent object of said job stream having first and second child objects;

identifying a float associated with the parent object; and

first configuring a first processor to execute logic for determining a second float associated with one of the first and second child objects, said second float defining a temporal flexibility for at least one of a start time and an end time for executing said one of the first and second child objects, said second float including an inherited portion associated with a first float of said first parent object.

44. A method as set forth in claim 43, wherein said job stream is a batch process job stream of a computer network.

45. A method as set forth in claim 43, wherein said first float of said parent object is dependent on a scheduling of a predecessor object.

46. A method as set forth in claim 43, wherein said logic is operative for determining floats for each of first and second child objects based at least in part on said inherited portion of said float.

47. A method as set forth in claim 43, wherein said parent object comprises a substream including multiple jobs and associated dependencies.

48. A method as set forth in claim 43, wherein said inherited float comprises less than the whole of said second float.

54. A method as set forth in claim 46, wherein said computer system is further operative to graphically depict output information including float for at least one job of said job stream.

49. A method for use in analyzing job streams, comprising the steps of:

receiving input information defining a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent on a completion of one or more of said predecessor jobs; and

operating a computer system to determine and graphically depict, on a graphical user interface, output information including float for at least one of said number of jobs, where said float relates to a temporal flexibility of at least one of a start time and an end time for a subject job.

50. A method as set forth in claim 49, wherein said job stream is a batch process job stream of a computer network.

51. A method as set forth in claim 49, wherein said computer system is further operative for executing changes to a schedule of said number of jobs and response to user inputs entered relative to said graphical user interface.

52. A method for use in analyzing job streams, comprising the steps of:

receiving input information defining a job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent on a completion of one or more of said predecessor jobs;

first operating a computer system to graphically depict, on a graphical user interface, a usage graph reflecting a usage level of at least one resource of said resource set over a time period corresponding to execution of at least a portion of said job stream according to a first job stream schedule;

receiving, relative to said graphical user interface, a user input for altering a portion of said usage graph; and

second operating said computer system to alter said first job stream schedule based on said user input.

53. A method as set forth in claim 52, wherein said job stream is a batch process job stream of a computer network.

55. A method for use in analyzing job streams, comprising the steps of:

receiving input information defining a job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent-on a completion of one or more of said predecessor jobs;

first operating a computer system to determine, for a first job of said number of jobs, first information related to an execution time of said first job and second information relating to a float time of said first job; and

second operating said computer system to make a determination regarding a time for triggering an alarm concerning a delay in completion of said first job, said determination being based at least in part on said second information relating to said float time of said first job.

56. A method as set forth in claim 55, wherein said job stream is a batch process job stream of a computer network.

57. A method as set forth in claim 55, wherein said first job has a scheduled end time followed by a float time and said step of second operating comprises identifying said time for triggering said alarm as being later than said scheduled end time but not later than an end of said float time.

58. A method for use in analyzing a job stream, comprising the steps of:

receiving input information defining a job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent on a completion of one or more of said predecessor jobs;

identifying first and second subsets of said job stream, said first subset of said job stream including at least a first job, said first subset being a predecessor within a context of said job stream to said second subset of said job stream, said second subset including at least a second job, wherein said definition of said job stream requires that said first subset is at least partially executed prior to said second subset;

second identifying a critical path relative to said second subset, where each critical path job on said critical path has zero float time such that a delay of any one of said critical path jobs results in a delay in completion of said second subset;

third identifying a first subset float time relating to a temporal flexibility in executing said first subset without delaying completion of said job stream; and

using said first subset float time to establish an execution time of a critical path job of said second subset.

59. A method as set forth in claim 58, wherein said job stream is a batch process job stream of a computer network.

60. A method for use in analyzing a job stream, comprising the steps of:

receiving input information defining a job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent on a completion of one or more of said predecessor jobs;

operating a computer system to identify a back float for a first successor job of said successor jobs, said back float relating to a flexibility to move a scheduled starting time of said first successor job to an earlier time without rescheduling a preceding one of said predecessor jobs; and

using said back float to determine an actual starting time for said first successor job.

61. A method as set forth in claim 60, wherein said job stream is a batch process job stream of a computer network.

62. A method as set forth in claim 60, wherein said step of using said back float comprises executing a resource leveling algorithm directed to moderating a usage extremum of at least one resource of a defined resource set, said extremum being one of a relative minimum usage level of said resource and a relative maximum usage level of said resource.

63. A method for use in analyzing a job stream, comprising the steps of:

receiving input information defining a job stream involving a number of jobs to be executed using a defined resource set, said jobs including multiple predecessor jobs and multiple successor jobs that may be the same or different than the predecessor jobs, where an execution of each of said successor jobs is dependent on a completion of one or more of said predecessor jobs;

first operating a computer system to add a float time to said entire job stream, said float time relating to a temporal flexibility for an execution time of said job stream; and

second operating said computer system to use said input information and said added float time to schedule execution of said job stream.

64. A method as set forth in claim 63, wherein said job stream is a batch process job stream of a computer network.

65. A method as set forth in claim 63, wherein said step of first operating comprises selecting said float time from a predefined menu of float times.

66. A method as set forth in claim 63, wherein said step of second operating comprises executing a resource leveling algorithm directed to moderating a usage extremum of at least one resource of said defined resource set, said extremum being one of a relative minimum usage level of said resource and a relative maximum usage level of said resource.