Gegeben sei eine Menge an Jobs, jeder mit einer Verarbeitungsdauer und einer Deadline. Die Jobs sind nacheinander auf einer Maschine auszuführen, es kann nur ein Job gleichzeitig ausgeführt werden. Wir möchten einen Plan entwickeln, d.h. eine Reihenfolge der Jobs, so dass jeder Job vor seiner Deadline fertig wird. Einen solchen Plan nennen wir "ausführbar".
Implementieren Sie in der Methode scheduleGreedy() ein Greedy-Verfahren, das - gegeben eine Menge von Jobs (als Array) - einen Plan zurückliefert. Dieser Plan soll ebenfalls ein Array von Jobs sein, wobei der vorderste Job zuerst ausgeführt wird, dann der nächste, usw. Fügen Sie in jeder Iteration ihrem Plan einen möglichst geeigneten nächsten Job hinzu. Beachten Sie:
- Ihre Methode sollte das originale Jobs-Array nicht verändern.
- Sie können annehmen, dass Dauer und Deadline eines Jobs jeweils nicht negativ sind. Der Beginn der Ausführung ihres Plans liegt bei $t=0$.
- Sollte kein ausführbarer Plan gefunden werden, soll ihre Methode eine ScheduleException werfen.
Ist Ihr Verfahren "optimal", d.h. findet es auch immer einen ausführbaren Plan wenn ein solcher Plan existiert? Falls nicht, geben Sie ein Gegenbeispiel. Fall ja, geben Sie eine informelle, aber schlüssige Begründung.
package de.hsrm.ads;
public class Scheduler {
static class Job {
double duration;
double deadline;
public Job(double duration, double deadline) {
this.duration = duration;
this.deadline = deadline;
}
};
static class ScheduleException extends RuntimeException {
public ScheduleException(String msg) {
super(msg);
}
};
public static Job[] scheduleGreedy(Job[] jobs) throws ScheduleException {
// FIXME
}
public static void main(String[] args) {
// a small test
Job[] jobs = new Job[] {
new Job(10,15),
new Job(5,7),
new Job(2,21)
};
Job[] schedule = scheduleGreedy(jobs);
for (Job j : schedule) {
System.out.println(j.deadline + " " + j.duration);
}
}
}
Subato
