Scheduling als longest-path

Moderator: Algorithmische Modellierung

Siggi
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 15. Okt 2006 12:46

Scheduling als longest-path

Beitrag von Siggi » 7. Mai 2010 09:06

Ich verstehe nicht ganz, wieso das Problem des Scheduling als longest-path Problem definiert werden kann.
Die Erzeugung des Graphen ist klar; genauso die topologische Sortierung.

Aber löst die topologische Sortierung immer ein longest-path Problem?
Wie der Name schon sagt, ist die topologische Sortierung eine Sortierung, d. h. alle Objekte (jobs) bleiben erhalten und werden nur anders angeordnet. Bei einem längsten oder kürzesten Wegeproblem gibt es ja keine Einschränkung, dass alle Knoten (jobs) erhalten bleiben.

Angenommen es gibt zwei Jobs: i und j. Die frühste Startzeit von i ist 1; Dauer von i ist 2 (Zeit zwischen i und j ist 0). Job i muss vor j ausgeführt werden. Die frühste Startzeit von j ist 5. Der längste Weg wäre jetzt aber direkt von Knoten r zum Job j, da 5 < (1 + 2 +0) = 3. Damit würde Job i ignoriert werden.

[Edit]
So, jetzt hab ich es verstanden. Ich habe übersehen, dass von r aus der längste Pfad zu jedem Knoten berechnet wird. Damit ist ja dann auch klar, dass jeder Job eine Startzeit erhält.

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Scheduling als longest-path

Beitrag von MisterD123 » 7. Mai 2010 23:32

topologische sortierung löst jedes pfad-problem relativ einfach weil in nem topologisch sortierten graphen nur endlich viele pfade existieren, es gibt keine zyklen..

Antworten

Zurück zu „Algorithmische Modellierung“