 |
Arbeitsgruppe: Lernen mit Neuronalen Methoden auf Strukturierten Daten |
|
Arbeitsgruppe: Lernen mit Neuronalen Methoden auf Strukturierten Daten |
In the first part of the talk, we consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Our main contribution is to provide algorithms that do not use linear programming, are simple and faster to implement, and have either the same or better quality of approximation as compared to the previous best algorithms in the literature.
In the second part of the talk, we derive bounds on performance guarantees of online algorithms for real-time preemptive scheduling of jobs with deadlines on multiple machines when jobs are characterized in terms of their minimum stretch factor a (or, equivalently, their maximum execution rate r=1/a). We consider two well known preemptive models that are of interest from practical applications: the hard real-time scheduling model and the firm real-time scheduling model. In both models, the objective is to maximize the sum of execution times of the jobs that were executed to completion and preemption is allowed.