Ordnung und Abhängigkeit erklärt
Ein Umschlag- oder Bauvorhaben besteht aus Aufgaben, von denen manche vor anderen fertig sein müssen. Diese Abhängigkeiten bilden einen gerichteten Graphen, und dieselbe Frage nimmt diese Linie neunmal in die Hand: Ist der Plan überhaupt einhaltbar, und wenn nicht, welche Kreise gibt es und welche wenigen Beziehungen streicht man? Wie lange dauert das Vorhaben, welche Wege, Teams und Reihenfolgen erlaubt es, und was ändert sich, wenn der Plan wächst oder für die ganze Erreichbarkeitstabelle zu groß wird?
Die Stücke bauen aufeinander auf: erst Kreise erkennen, zählen und auflösen, dann auf dem kreisfreien Plan rechnen (kritischer Pfad, Wege und Hülle, Ketten, Reihenfolgen), am Ende wachsende und große Pläne. Gerechnet wird auf erzeugten Plänen mit einer verdeckten Wunschreihenfolge, in der ein einstellbarer Teil der Beziehungen umgedreht wird; echte Bau- oder Umschlagpläne gehören nicht dazu.
In short: Interactive demos on task dependency graphs: detecting, counting and breaking cycles, the critical path under uncertain durations, shortest paths and transitive closure in DAGs, chains and antichains, linear extensions, incremental topological order and reachability indexes.
Hintergrund zum Thema: Netzwerkdesign.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Der kritische Pfad verständlich erklärt
Warum nur die längste Kette von Aufgaben das Projektende bestimmt, alle anderen Puffer haben und der kritische Pfad bei unsicheren Dauern wandern kann: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die neun Stücke im Überblick
Die Linie hat eine Wurzel und drei Stränge. Der erste kümmert sich um Widersprüche: einen Kreis erkennen und belegen (die Wurzel), alle Kreise zählen, wenige Beziehungen streichen. Der zweite rechnet auf dem kreisfreien Plan: der kritische Pfad, dann Wege und Hülle, dann Ketten und die Zahl der Reihenfolgen. Der dritte fragt, was bei wachsenden und großen Plänen passiert: die Ordnung Kante für Kante nachführen und der Erreichbarkeitsindex, der die Hülle ersetzt, wenn sie zu groß wird.
Drei Stücke sind Zusammenflüsse: Das Auflösen der Kreise führt Erkennen und Zählen zusammen, die wachsende Ordnung greift auf die Kreis-Erkennung und die Erreichbarkeit zurück, und der Index steht zwischen der Hülle und dem wachsenden Plan: Er ersetzt die Hülle, wenn sie zu groß wird, muss aber bei neuen Beziehungen neu gebaut werden.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Gestrichelte Doppelpfeile sind Kontraste (wachsend gegen statisch), gepunktete Pfeile übernehmen nur eine Idee, graue gestrichelte Knoten sind Bausteine aus anderen Linien. Die Stücke lassen sich in beliebiger Reihenfolge lesen, ein Pfeil ist keine vorgeschriebene Reihenfolge.
Verwandt in anderen Linien
- Graphen und Netzwerke — Kreise liegen nur innerhalb starker Zusammenhangskomponenten: Die Demo zu starken Zusammenhangskomponenten zerlegt einen Graphen so und kondensiert ihn zu einem kreisfreien Graphen. Die Di-Kreis-Demo dieser Linie behandelt den Kreis selbst als Beleg, und das Auflösen der Kreise zerlegt den Plan zuerst in solche Komponenten und löst jede für sich.
- Kürzeste Wege — Allgemeine Graphen mit Kreisen gehören in diese Linie (Bellman-Ford); im kreisfreien Plan genügt ein Durchlauf in topologischer Reihenfolge, und das Standard-Dijkstra rechnet dort mit negativen Kosten falsch, wie die Wege-und-Hülle-Demo misst. Dieselbe Idee der Nabenmarken wie bei der Erreichbarkeit auf großen Plänen zeigt das Hub Labeling für Distanzen.
- Matching-Algorithmen — Die kleinste Zahl von Teams ist ein Matching auf der Hülle des Plans: Die Demo zu Ketten und Antiketten rechnet Ketten gleich n minus Matching, mit Kuhn und Hopcroft–Karp als Werkzeugen; die Verfahren selbst zeigt die Matching-Linie.
- Klassische Scheduling-Theorie — Der kritische Pfad kennt nur Abhängigkeiten: Teilen sich Aufgaben ein Team oder eine Maschine, ist er nicht mehr nur ein Pfad der Abhängigkeiten, und die ressourcenbeschränkte Projektplanung der Scheduling-Linie übernimmt, was die Kritischer-Pfad-Demo bewusst weglässt.
- Planarität und Zeichnen — Die Sugiyama-Demo der Linie Planarität und Zeichnen zeichnet Abhängigkeitspläne so, dass jede Beziehung nach unten zeigt; enthält der Plan einen Kreis, bricht sie ihn zuerst, wofür das Auflösen der Kreise hier die wenigsten Beziehungen sucht.
Di-Kreis erkennen und belegen
Verfolgen Sie, wie man einen Kreis in den Abhängigkeiten eines Vorhabens nicht nur erkennt, sondern belegt: Die Tiefensuche liefert den Kreis nebenbei, das Abbauverfahren nach Kahn nur einen Rest. Ein Regler für die Zahl der Widersprüche zeigt beide live. Der Haken: Der Rest ist kein Beleg. Bei 300 Aufgaben und 0,5 % Widersprüchen liegen 108 im Rest, aber nur 7 auf einem Kreis.
Demo starten →Alle Kreise: aufzählen und zählen
Sehen Sie, wie schnell die Zahl der Kreise in einem widersprüchlichen Plan wächst und wie man sie zählt, ohne sich in Sackgassen zu verlaufen: Das Verfahren von Johnson sperrt Aufgaben, aus denen kein Weg zurückführt. Ein Regler für die Widersprüche zeigt live Kreiszahl und meistbelegte Beziehung. Der Haken: Bei 40 Aufgaben und 24 Widersprüchen überschreiten 17 von 30 Plänen das Kreisbudget, die Zahl ist dann nur eine untere Schranke.
Demo starten →Kreise auflösen: wie wenig muss man streichen
Verfolgen Sie, wie wenig man streichen muss, damit ein widersprüchlicher Plan aufgeht: Der exakte Löser lädt nur die Kreise nach, die er braucht, und findet das Optimum, das meist weit unter der Zahl der Widersprüche liegt. Ein Vergleich zeigt live die Faustregeln. Der Haken: Bei 40 Aufgaben und 16 Widersprüchen trifft die Heuristik von Eades, Lin und Smyth das Optimum in keinem von 30 Plänen.
Demo starten →Kritischer Pfad, Puffer und Unsicherheit
Sehen Sie, wie lange ein Vorhaben dauert, welche Aufgaben kritisch sind und wie viel Puffer die übrigen haben, und was das bei unsicheren Dauern bedeutet: Dort laufen Pfade zusammen, und der Plan der Erwartungswerte kippt. Ein Zufallsversuch zeigt live, wie oft der Plan hält. Der Haken: Bei stark rechtsschiefen Dauern und 40 Aufgaben hält er in nur 34 % der Läufe.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Wege und Erreichbarkeit im DAG
Verfolgen Sie, wie ein einziger Durchlauf in der richtigen Reihenfolge kürzeste Wege auch bei negativen Kosten liefert, wo das Standard-Dijkstra falsch rechnet, und wie viele Abhängigkeiten sich aus anderen ergeben. Ein Vergleich zeigt live die Rechenschritte. Der Haken: Streicht man die überflüssigen Abhängigkeiten, bleibt die Projektdauer gleich, die kürzesten Wege aber bei 40 Aufgaben in keinem von 30 Plänen.
Demo starten →Ketten und Antiketten
Sehen Sie, wie viele Teams ein Vorhaben mindestens braucht, damit jede Aufgabe nach ihren Vorgängern drankommt, und wie die größte Menge voneinander unabhängiger Aufgaben beweist, dass es nicht weniger geht. Die Zahl kommt aus einem Matching auf der Hülle. Der Haken: Das ist der ungünstigste Fall; im frühesten Zeitplan liegt die Spitze in 213 von 240 Plänen darunter.
Demo starten →Zulässige Reihenfolgen
Verfolgen Sie, wie viele Reihenfolgen ein Plan erlaubt, das ist der Spielraum der Planung, und wie man eine davon fair zufällig zieht: Der naheliegende Zufall verzerrt, die Zähltabelle über die abgeschlossenen Teilmengen des Plans nicht. Der Haken: Zählen ist im Allgemeinen nicht effizient möglich; bei 40 Aufgaben und dünnem Plan (Ausgangsgrad 1) liegen 8 von 8 über dem Budget, dann bleibt nur ein Schätzer.
Demo starten →Wachsende Abhängigkeiten
Sehen Sie, was passiert, wenn Abhängigkeiten Kante für Kante dazukommen: Die nachgeführte Ordnung arbeitet nur, wenn die neue Beziehung sie verletzt, und meldet einen Kreis mit Beleg. Ein Vergleich zeigt live den Aufwand gegen die naive Suche und die Neuberechnung. Der Haken: Ein rückwärts gebauter Pfad kostet bei 200 Aufgaben 39 800 Besuche und damit mehr als die naive Suche mit 39 601.
Demo starten →Erreichbarkeitsanfragen auf großen DAGs
Verfolgen Sie, wie man Erreichbarkeitsfragen beantwortet, wenn die ganze Hülle zu groß wird: Intervallmarken aus Zufallsdurchläufen sagen oft sofort Nein, Nabenmarken vergleichen zwei kurze Listen. Ein Plan-Regler zeigt live Platz, Aufbau und Anfragekosten. Der Haken: Bei 20 000 Aufgaben braucht die Hülle erst 47,7 MiB, und ein Durchlauf entscheidet in dichten Plänen nur 62 % der Neins sofort.
Demo starten →Welches Stück passt zu meiner Aufgabe?
Ein Entscheidungsbaum über alle neun Stücke, entlang der Frage, was am Abhängigkeitsplan gesucht wird: ein Kreis, alle Kreise, eine Reparatur, die Dauer, Wege, Teams, Reihenfolgen oder ein wachsender Plan, und wie groß der Plan ist.
Welches Stück passt zu meiner Aufgabe?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: Die Antworten gelten für die erzeugten Pläne der Demos mit höchstens 400 Aufgaben (der Index bis 20 000) und die dort gemessenen Größen, nicht für jeden Plan. Das Auflösen der Kreise kann bei dichten Plänen an die Zeitgrenze des Lösers stoßen (Stück 3), und das Zählen der Reihenfolgen gibt bei dünnen Plänen ab etwa 30 Aufgaben auf (Stück 7).
Weitere Linien in diesem Bereich
Kürzeste Wege
Wie findet man die beste Route? Zwölf Verfahren von der Breitensuche bis zur Fahrplanauskunft, jedes mit seiner gemessenen Grenze.
Spannbäume
Wie verbindet man alle Standorte mit möglichst wenig Leitung? Elf Stücke vom billigsten Baum über Richtung, Kapazität und Zwischenknoten bis zum Zufallsbaum.
Netzwerkfluss
Wie viel geht durch ein Netz, was kostet es, und was ändert sich, wenn Güter sich Kanten teilen, der Ausbau selbst Entscheidung ist oder die Zeit mitzählt? Neunzehn Stücke von Edmonds-Karp bis zum Fluss über die Zeit.
Schnitte und Zusammenhang
Wie robust hängt ein Netz zusammen, und wie teilt man es in Teile? Acht Stücke über Engstellen, kleinste Schnitte, getrennte Terminals, fehlende Leitungen, ausgewogene Hälften und zusammenhängende Gebiete.
Matching-Algorithmen
Wer wird womit gepaart? 13 Verfahren von der billigsten Kante zuerst bis zum Nierentausch unter medizinischen Zwängen, jedes mit seiner gemessenen Grenze.
Graphen und Netzwerke
Wie durchmustert man ein Netz, welche Kante ist kritisch, wie wichtig ist ein Knoten, und wie verwundbar ist das Ganze? Dreizehn Stücke von BFS/DFS über die interne Verlinkung einer echten Website bis zur eigenen Forschung über Bandbreite.
Härte und Struktur
Welche Sendungen dürfen zusammen fahren? Acht Stücke über Cliquen, Überdeckungen und Baumweite: was Struktur auf einem Konfliktgraphen leicht macht und wo sie nicht reicht.
Planarität und Zeichnen
Lässt sich ein Netz ohne Überkreuzung zeichnen, und was folgt daraus? Neun Stücke über Färben, Trennen, Zeichnen, Flüsse als kürzeste Wege, Näherung, Zählen und fast planare Netze.
Netzwerkanalyse
Was verrät die Struktur eines Netzes, wie breitet sich etwas darauf aus, und wie gleichen sich seine Betriebe an? Dreizehn Stücke über Kernzahl, Gemeinschaften, Einfluss, Eindämmung, Meinungen, Standorte und Kontaktfolgen.
Netzmodelle
Welches Zufallsmodell erzeugt welche Eigenschaft eines Netzes, wie prüft man ein Netz gegen ein Modell, und was geschieht, wenn keines passt? Neun Stücke vom Zufallsgraphen bis zur Modellwahl.