UniBanner

Möhring

Projektplanung bei zufälligen Vorgangsdauern und unvollständiger Information.

Vortrag von Prof. Dr. Rolf H. Möhring
(TU Berlin)

 

Der Vortrag behandelt das Problem, in einem Projektnetzplan (= partielle Ordnung) N, dessen Vorgänge (= Elemente der Ordnung) zufällige, möglicherweise abhängige Bearbeitungszeiten haben, Informationen über die (ebenfalls zufällige) kürzeste Projektdauer (= längster Kette von N) zu bekommen. Die in der Praxis übliche deterministische Rechnung auf der Basis mittlerer Vorgangsdauern unterschätzt die erwartete Projektdauer in der Regel erheblich.

Die Berechnung stochastischer Information ist allerdings sehr aufwendig. Bereits die Berechnung von nur einem Wert der Verteilungsfunktion der Projektdauer ist schwierig (im technischen Sinne #P-vollständig). Dies motiviert - neben dem Einsatz von Simulationsmethoden - die Konstruktion von unteren und oberen Schranken für die Verteilungsfunktion der Projektdauer.

Wir diskutieren existierende Ansätze und berichten über die Verbindung zu Problemen der Ordnungstheorie und der Kombinatorischen Optimierung (Modifikation einer Ordnung in serien-parallele Ordnungen, Zeit-Kosten-Optimierung, Ermittlung k-längster Ketten). Ein neues Ergebnis (gemeinsam mit R. Müller, Berlin) zeigt, daß eine neue Minorenkonstruktion für partielle Ordnungen und ihre Wegesysteme verschiedene bekannte Schranken für unabhängige Vorgangsdauern (Kleindorfer 71, Spelde 76, Dodin 85) zusammenfaßt und verallgemeinert. Wir berichten über algorithmische Erfahrungen mit diesen Schranken, und zeigen, daß diese selbst bei unvollständiger Information über die Vorgangsdauerverteilungen ein ausgezeichnetes Planungsinstument darstellen.