Job scheduling system and method

• US 7,958,507 B2
• Filed: 06/16/2005
• Issued: 06/07/2011
• Est. Priority Date: 06/16/2005
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Santos, Cipriano A., Beyer, Dirk
• Primary Examiner(s): An; Meng A
• Assistant Examiner(s): LEE, TAMMY EUNHYE
• Application Number:
  US11/154,305
• Publication Number:
  US 20060288346A1
• Time in Patent Office: 2,182 Days
• Field of Search: 718/102, 718/103, 718/104
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/506 Constraint
• 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

In at least some embodiments, a method comprises computing an initial schedule of jobs to be run on a computing system using a mathematical program and monitoring the computing system. The method also comprises, based on the monitoring, determining, using the mathematical program used to compute the initial schedule, whether the initial schedule should be re-computed.

Claims

1. A method, comprising:

computing an initial schedule of jobs to be run on a computing system using a mathematical program that maximizes a total reward associated with jobs that are timely completed while satisfying precedence constraints among tasks that comprise the jobs;

monitoring said computing system; and

based on the monitoring, determining, using the mathematical program used to compute the initial schedule, whether the initial schedule should be re-computed;

wherein computing the initial schedule includes the mathematical program determining a state for job selection decision variables that dictate which jobs are selected to be part of the initial schedule, and wherein determining whether the initial schedule should be re-computed comprises forcing the job selection decision variables to said state that was computed while computing the initial schedule.

2. The method of claim 1 wherein computing the initial schedule includes providing an input value to the mathematical program and determining whether the initial schedule should be re-computed comprises changing said input value.

3. The method of claim 2 wherein the input value comprises an amount of time that can be used to run the scheduled jobs.

4. The method of claim 1 wherein determining whether the initial schedule should be re-computed comprises leaving unconstrained the job selection decision variable for any job that was not selected.

5. The method of claim 1 wherein determining whether the initial schedule should be re-computed comprises forcing the job selection decision variables to select only those jobs that have been completed and leaving unconstrained the job selection decision variable for all other jobs.

6. The method of claim 1 wherein the computing system comprises a plurality of processors and wherein computing the initial schedule includes the mathematical program computing placement decision variables to identify which processors are to be assigned to which of the initially scheduled jobs, and further wherein determining whether the initial schedule should be re-computed comprises forcing the placement decision variables to be as was computed by the mathematical program while computing the initial schedule.

7. The method of claim 1 wherein the computing system comprises a plurality of processors and wherein computing the initial schedule includes the mathematical program computing placement decision variables to identify which processors are to be assigned to which of the initially scheduled jobs, and further wherein determining whether the initial schedule should be re-computed comprises leaving unconstrained the placement decision variables.

8. The method of claim 1 wherein monitoring said computing system comprises determining a completion time of a task within a job.

9. The method of claim 8 wherein computing the initial schedule comprises using an estimate of task completion time and wherein determining whether the initial schedule should be re-computed comprises using an update of said estimate task completion time from said monitoring.

10. The method of claim 1 further comprising re-computing said schedule if the initial schedule cannot be fully completed by a deadline.

11. The method of claim 1 further comprising re-computing said schedule if the initial schedule is estimated to take more than a threshold amount of time past a deadline to complete.

12. The method of claim 1 further comprising re-computing said schedule if the initial schedule will be completed more than a threshold amount of time prior to a deadline.

13. The method of claim 1 wherein monitoring said computing system comprises determining a probability distribution of completion times of a plurality of tasks comprising a job and determining whether the initial schedule should be re-computed based on said probability distribution.

14. A computer readable medium containing software that, when executed by a processor, causes the processor to perform a method for assessing whether an initial schedule of jobs should be re-computed after said initial schedule has been computed and begun to run, said method comprising:

computing the initial schedule of jobs to be run on a computing system using a mathematical program that maximizes a total reward associated with jobs that are timely completed while satisfying precedence constraints among tasks that comprise the jobs;

monitoring said computing system; and

based on the monitoring, determining, using the mathematical program used to compute the initial schedule, whether the initial schedule should be re-computed;

wherein computing the initial schedule includes the mathematical program computing a state for job selection decision variables that dictate which jobs are selected to be part of the initial schedule, and wherein determining whether the initial schedule should be re-computed comprises forcing the job selection decision variables to said state that was computed while computing the initial schedule.

15. The computer readable medium of claim 14 wherein computing the initial schedule includes providing a deadline to the mathematical program and determining whether the initial schedule should be re-computed comprises changing deadline based on how much time has expired since the initial schedule began to run.

16. The computer readable medium of claim 14 wherein determining whether the initial schedule should be re-computed comprises leaving unconstrained the job selection decision variable for any job that was not selected.

17. The computer readable medium of claim 14 wherein determining whether the initial schedule should be re-computed comprises forcing the job selection decision variables to select only those jobs that have been completed and leaving unconstrained the job selection decision variable for all other jobs.

18. The computer readable medium of claim 14 wherein the computing system comprises a plurality of processors and wherein computing the initial schedule includes the mathematical program computing placement decision variables to identify which processors are to be assigned to which of the initially scheduled jobs, and further wherein determining whether the initial schedule should be re-computed comprises forcing the placement decision variables to be as was computed by the mathematical program while computing the initial schedule.

19. The computer readable medium of claim 14 wherein the computing system comprises a plurality of processors and wherein computing the initial schedule includes the mathematical program computing placement decision variables to identify which processors are to be assigned to which of the initially scheduled jobs, and further wherein determining whether the initial schedule should be re-computed comprises leaving unconstrained the placement decision variables.

20. The computer readable medium of claim 14 wherein monitoring said computing system comprises determining a completion time of a task within a job.

21. The computer readable medium of claim 20 wherein computing the initial schedule comprises using an estimate of task completion time and wherein determining whether the initial schedule should be re-computed comprises using an update of said estimate task completion time from said monitoring.

22. The computer readable medium of claim 14 further comprising re-computing said schedule if the initial schedule cannot be fully completed by a deadline.

23. The computer readable medium of claim 14 further comprising re-computing said schedule if the initial schedule is estimated to take more than a threshold amount of time past a deadline to complete.

24. The computer readable medium of claim 14 further comprising re-computing said schedule if the initial schedule will completed more than a threshold amount of time prior to a deadline.

25. A system, comprising:

a processor; and

storage coupled to said processor, said storage comprising an executable planner, monitor, and controller;

said planner computes an initial schedule of jobs to run on a computing system, said planner computes said initial schedule using a mathematical program that maximizes a total reward associated with jobs that are timely completed while satisfying precedence constraints among tasks that comprise the jobs;

said monitor monitors the computing system; and

said controller, while said initial schedule runs on the computing system, determines whether said initial schedule should be re-calculated based, at least in part, on information from said monitor regarding said computing system;

wherein said planner uses the mathematical program to compute the initial schedule by determining a state for job selection decision variables that dictate which jobs are selected to be part of the initial schedule, and wherein the controller determines whether the initial schedule should be re-computed by forcing the job selection decision variables to said state that was computed while computing the initial schedule.

26. The system of claim 25 wherein each job comprises one or more jobs and said information comprises an amount of time it takes for individual tasks within a job to complete.

27. The system of claim 26 wherein the planner estimates an amount of time required to complete each task and said controller re-estimates the amount of time based, at least in part, on said information.

28. The system of claim 25 wherein said planner computes the initial schedule by providing a deadline to the mathematical program and said controller determines whether the initial schedule should be re-computed by changing the deadline based on how much time has expired since the initial schedule began to run.

29. The system of claim 25 wherein when said planner computes the initial schedule, said planner computes job selection decision variables that dictate which jobs are selected to be part of the initial schedule, and wherein said controller determines whether the initial schedule should be re-computed by forcing the job selection decision variables to select only those jobs that were selected by said planner initially and by leaving unconstrained the job selection decision variable for any job that was not selected by the planner initially.

30. The system of claim 25 wherein when said planner computes the initial schedule, said planner computes job selection decision variables that dictate which jobs are selected to be part of the initial schedule, and wherein said controller determines whether the initial schedule should be re-computed by forcing the job selection decision variables to select only those jobs that have been completed and by leaving unconstrained the job selection decision variable for all other jobs.

31. The system of claim 25 wherein the computing system comprises a plurality of processors and wherein said planner computes the initial schedule by computing placement decision variables to identify which processors are to be assigned to which of the initially scheduled jobs, and wherein said controller determines whether the initial schedule should be re-computed by forcing the placement decision variables to be as was computed by said planner initially.

32. The system of claim 25 wherein the computing system comprises a plurality of processors and wherein said planner computes the initial schedule by computing placement decision variables to identify which processors are to be assigned to which of the initially scheduled jobs, and wherein said controller determines whether the initial schedule should be re-computed by leaving unconstrained the placement decision variables.

33. The system of claim 25 wherein said controller causes said schedule to be re-computed if the initial schedule cannot be fully completed by a deadline.

34. The system of claim 25 wherein said controller causes said schedule to be re-computed if the initial schedule is estimated to take more than a threshold amount of time past a deadline to complete.

35. The system of claim 25 wherein said controller causes said schedule to be re-computed if the controller estimates that the initial schedule will be completed more than a threshold amount of time prior to a deadline.

36. The system of claim 25 wherein said information from said monitor that is used by said controller to determine whether to re-calculate the initial schedule comprises a change in an objective function that is used by the planner to compute the initial schedule.

37. The system of claim 25 wherein said information from said monitor that is used by said controller to determine whether to re-calculate the initial schedule comprises a violation of an affinity or fair-share resource constraint.

38. A system, comprising:

means for using a scheduling algorithm to schedule jobs to run on a computing system, said means for using computes schedules the jobs using a mathematical program that maximizes a total reward associated with jobs that are timely completed while satisfying precedence constraints among tasks that comprise the jobs;

means for monitoring said computing system; and

means for determining whether the schedule should be re-computed using said scheduling algorithm while said scheduled jobs are running on said computing system;

wherein said means for using computes the initial schedule by using the mathematical program to compute a state for job selection decision variables that dictate which jobs are selected to be part of the initial schedule, and wherein determining the means for determining determines whether the initial schedule should be re-computed by forcing the job selection decision variables to said state that was computed while computing the initial schedule.

39. A method, comprising:

using a mathematical program to select jobs to form an initial schedule to run on a computing system, each job comprising one or more tasks, at least one job not being selected to form the initial schedule, said mathematical program selects the jobs to form the initial schedule by maximizing a total reward associated with jobs that are timely completed while satisfying precedence constraints among tasks that comprise the jobs;

monitoring said computing system while said initially scheduled jobs are running on said computing system; and

based at least in part on the monitoring, determining, using the mathematical program used to compute the initial schedule, whether the initial schedule should be re-computed;

wherein a deadline used to form the initial schedule is varied when determining whether the initial schedule should be re-computed; and

wherein job selection variables are computed to form the initial schedule, the job selection variables dictate which jobs are selected and which are not selected for the initial schedule, and wherein when determining whether the initial schedule should be re-computed, the method comprising forcing at least some of the job selection variables to a predetermined state.