Tutorial : Java-Applet
Topsort und CPM
Es gibt heute viele Softwarewerkzeuge mit deren Hilfe die vergleichsweise hohe Rechenleistung von Datenverarbeitungsmaschinen rasch und in sehr guter Qualität verfügbar gemacht werden kann. Sehen Sie hier ein kleines Beispiel mit Nutzeffekt.
Um Informationen für die Terminplanung zu gewinnen oder um Engpässe leichter zu erkennen, können Herstellprozesse, Projekte, oder allgemein, Vorgänge mit vielen voneinander abhängigen Teilvorgängen oder Komponenten methodisch und computergestützt hinsichtlich beteiligter Ressourcen untersucht werden.
warm-up. Zwei gedankliche Schritte zum Einstieg
(1) eine Liste aller Teilvorgänge aufstellen und zu jedem (Teil-)Vorgang die Dauer des Vorgangs und die Liste der vorhergehenden Vorgänge angegeben.
Welche Teilvorgänge gibt es im Projekt?
Wie lange dauert jeder Teilvorgang?
Welche Teilvorgänge müssen abgeschlossen sein, damit ein Vorgang beginnen kann?
(2) aus der Vorgangsliste ein Vorgangspfeilnetz erstellen, dabei alle Vorgänge als Pfeile und die Startereignisse Xi und Endeereignisse Xj jedes Vorgangs Vij als Punkte wiedergegeben.
Abhängigkeiten zwischen Vorgängen werden graphisch einfach dadurch ausgedrückt, indem der Punkt für das Startereignis eines Vorgangs und die Punkte der Endeereignisse der unmittelbar vorausgesetzten Vorgänge zusammenfallen.
Um gegebene Verhältnisse eindeutige wiederzugeben und um Regeln durchzusetzen, die erfüllt sein müssen, damit eine computergestützte Auswertung möglich ist, können Scheinvorgänge (Vorgänge mit Dauer 0) eingesetzt werden.
Ergebnis dieses Schritts sollte ein zyklenfreier gerichteter Graph, ohne parallele und ohne überlappende Vorgänge, sein.
In der bisher skizzierten Implementierung sind parallele Vorgänge und Selbstbezüge bereits ausgeschlossen.
Die Vorgangsdauer als Eigenschaft der Pfeil-Klasse „E2i”
Indem in der bisher vorgestellten Implementierung des gerichteten Graphen die Pfeil-Klasse „E2i” um die Vorgangsdauer als öffentliche Klasseneigenschaft erweitert wird, kann anhand der Vorgangsliste bereits ein Vorgangspfeilnetz aufgebaut werden.
Topologisch Sortieren
Die topologische Sortierung der Punkte (Knoten, Ereignisse) macht die Punkt-Eingabe einfacher und liefert zudem einen Nachweis über die Zyklenfreiheit des Vorgangspfeilnetzes.
Da die Punktobjekte in Eingabereihenfolge als verkettete Objekte einfach am Ende der Punktliste eingefügt werden, liegen diese über kurz oder lang wild verstreut im Speicher. Zur computergestützten Anwendung der critical path method (CPM) müssen jedoch die Punkte, topologisch sortiert, das heißt, so "nummeriert", also in Reihenfolge gebracht werden, dass bei jedem Punkt alle Vorereignisse eine niedrigere Nummer und alle Nachereignisse eine höhere Nummer haben.
Das entspricht einer Linearisierung des Vorgangspfeilnetzes, wodurch dann tatsächlich der erste Punkt der Punktliste den Projektbeginn und der letzte Punkt das Projektende markiert. Ausserdem markiert dann das Endeereignis jedes Vorgangs einen Punkt an dem alle Vorgänge abgeschlossen sein müssen, ehe der nächste Vorgang beginnen darf.
Zur Sortierung werden der Eingangsgrad „ind” und die Ordnungsnummer „ord” für jeden Punkt berechnet.
Die Punkt-Klasse „V2i” ist also zunächst um diese beiden Klasseneigenschaften zu erweitern.
Wenn ein Graph keine Zyklen hat, dann existiert darin mindestens ein Punkt Xi bei dem keine Pfeile eintreffen, bei denen also der Eingangsgrad 0 ist. - Diese Punkte machen den Anfang der Nummerierung. - Entfernt man all diese Punkte mit Eingangsgrad 0 aus dem Graph, so bleibt ein Graph übrig, bei dem wieder mindestens ein Punkt Xj existiert bei dem keine Pfeile eintreffen, diese Punkte erhalten die nächst höheren Nummerierungen. - Das Ganze wird fortgesetzt bis keine Punkte mehr übrig sind - oder - bis kein Punkt mehr gefunden wird bei dem keine Pfeile eintreffen. - Im ersten Fall ist der Gaph zyklenfrei und alle Punkte sind wie oben beschrieben nummeriert. Im zweiten Fall hat der Graph mindestens einen Zyklus und die Punkte konnten nicht alle nummeriert werden.
Die Klasse „Dcal” wird daher um eine öffentliche Methode „topsort()” erweitert.
Java
public boolean topsort()
{
boolean hasNoLoops;
int n; int nmax;
DcalNode node; DcalArc pfeil;
Stack<DcalNode> zerodeg;
Stack<DcalNode> topsr;
// Eingangsgrad berechnen und kritischen Pfad rücksetzen
nmax = 0;
for (node = this.root; node != null; node = node.next)
{
nmax++;
node.info.ind = 0;
node.info.ord = 0;
}
for (node = this.root; node != null; node = node.next)
{
if (node.arclist != null)
{
for (pfeil = node.arclist; pfeil != null; pfeil = pfeil.next)
{
pfeil.endnode.info.ind++;
pfeil.info.nonCritical();
}
}
}
// Punkte mit Eingangsgrad 0 sammeln
zerodeg = new Stack<DcalNode>();
for (node = this.root; node != null; node = node.next)
{
if (node.info.ind == 0) { zerodeg.push(node); }
}
// topologische Sortierung ermitteln
n = 0;
topsr = new Stack<DcalNode>();
while (!zerodeg.empty())
{
node = zerodeg.pop();
n++;
node.info.ord = n;
topsr.push(node);
if (node.arclist != null)
{
for (pfeil = node.arclist; pfeil != null; pfeil = pfeil.next)
{
pfeil.endnode.info.ind--;
if (pfeil.endnode.info.ind == 0) { zerodeg.push(pfeil.endnode); }
}
}
}
// DCAL sortieren
hasNoLoops = (n == nmax);
if (hasNoLoops)
{
if (!topsr.empty())
{
DcalNode next = null;
node = topsr.pop();
node.next = next;
node.prev = null;
while (!topsr.empty())
{
next = node;
node.prev = topsr.pop();
node = node.prev;
node.next = next;
node.prev = null;
}
this.root = node;
}
}
return hasNoLoops;
}
Kritischer Pfad
Vom Projektbeginn zum Projektende existiert mindestens ein Pfad auf dem die Pufferzeiten aller Teilvorgänge 0 sind. Dauert ein Teilvorgang auf diesem Pfad länger als geplant, so wird das Projektende erst später als geplant statt finden können.
Im sortierten Vorgangspfeilnetz wird erst in einer Vorwärtrechnung vom Projektstart zu jedem Punkt bis hin zum Projektende der längste Weg und dann in einer Rückwärtsrechnung vom Projektende zu jedem Punkt bis schließlich zum Projektbeginn ebenfalls der längste Weg ermittelt. Wegmaß ist die Vorgangsdauer und begonnen wird bei 0.
Ergebnisse beider Rechenschritte sind für jeden Punkt der frühest mögliche Starttermin „t1” und der spätest erlaubte Starttermin „t2”; beides Zeitpunkte relativ zum Projektbeginn.
Die Punkt-Klasse „V2i” wird um diese beiden öffentlichen Klasseneigenschaften erweitert und ist damit komplett.
Anhand des frühest möglichen Starttermins „t1”, des spätest erlaubten Starttermins „t2” und der Vorgangsdauer werden für alle Teilvorgänge die gesamte Pufferzeit „GP”, die freie Pufferzeit „FP” und die unabhängige Pufferzeit „UP” berechnet.
pfeil.info.GP = pfeil.endnode.info.t2 - next.info.t1 - pfeil.info.Dauer;
pfeil.info.FP = pfeil.endnode.info.t1 - next.info.t1 - pfeil.info.Dauer;
pfeil.info.UP = Math.max(0, pfeil.endnode.info.t1 - next.info.t2 - pfeil.info.Dauer);
Die Pfeil-Klasse „E2i” wird um diese drei öffentlichen Klasseneigenschaften erweitert und ist damit ebenfalls komplett.
Die Klasse „Dcal” wird um eine öffentliche Klassenmethode „cpm()” erweitert.
Java
public void cpm()
{
DcalNode prev;
DcalNode next;
DcalArc pfeil;
if (this.root != null)
{
// frühest möglicher Start (Vorwärtsrechnung)
for (next = this.root; next != null; next = next.next)
{
next.info.t1 = 0;
}
prev = null;
for (next = this.root; next != null; next = next.next)
{
if (next.arclist != null)
{
for (pfeil = next.arclist; pfeil != null; pfeil = pfeil.next)
{
if ((next.info.t1+pfeil.info.Dauer) > pfeil.endnode.info.t1)
{
pfeil.endnode.info.t1 = (next.info.t1+pfeil.info.Dauer);
}
}
}
prev = next;
}
if (prev != null)
{
// spätest erlaubter Start (Rückwärtsrechnung)
int t2 = prev.info.t1;
for (next = prev; next != null; next = next.prev)
{
if (next.arclist == null) {t2 = next.info.t1;}
next.info.t2 = t2;
}
for (next = prev.prev; next != null; next = next.prev)
{
if (next.arclist != null)
{
for (pfeil = next.arclist; pfeil != null; pfeil = pfeil.next)
{
if ((pfeil.endnode.info.t2-pfeil.info.Dauer) < next.info.t2)
{
next.info.t2 = (pfeil.endnode.info.t2-pfeil.info.Dauer);
}
}
}
}
// Pufferzeiten GP, FP, UP
for (next = this.root; next != null; next = next.next)
{
if (next.arclist != null)
{
for (pfeil = next.arclist; pfeil != null; pfeil = pfeil.next)
{
pfeil.info.GP = pfeil.endnode.info.t2 - next.info.t1 - pfeil.info.Dauer;
pfeil.info.FP = pfeil.endnode.info.t1 - next.info.t1 - pfeil.info.Dauer;
pfeil.info.UP = Math.max(0, pfeil.endnode.info.t1 - next.info.t2 - pfeil.info.Dauer);
}
}
prev = next;
}
}
}
}
Die Methoden „topsort()” und „cpm()” sehen Sie im Java-Applet auf der ersten Seite dieses Tutorials im Einsatz.