Job scheduling system and method
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
39 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
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. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
-
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.
-
Specification