Glossar · approach
Precedence Constraint
Teilordnungs-Bedingung, die festlegt, dass eine Aufgabe (oder Aktivität) abgeschlossen sein muss, bevor eine andere beginnt; grundlegende Bedingungsfamilie in Scheduling- und Montage-OR-Problemen.
VorrangbedingungVorrangrelationTeilordnungAufgaben-Vorrang
Eine Vorrangbedingung (Precedence Constraint) drückt eine Teilordnungs-Relation zwischen zwei Aufgaben oder Aktivitäten aus: Aufgabe i muss abgeschlossen sein, bevor Aufgabe j beginnt. Sie ist die grundlegende Bedingungsfamilie in vielen OR-Scheduling- und Zuordnungsproblemen. In der Linienaustaktung (Salveson 1955; Boysen, Fliedner und Scholl 2007) muss der Stationsindex, der Aufgabe i enthält, kleiner oder gleich dem Stationsindex sein, der Aufgabe j enthält; im Resource-Constrained Project Scheduling Problem (RCPSP) wirkt sich die Bedingung auf die Startzeiten aus; im Job-Shop-Scheduling bestimmt sie die Operationsreihenfolge eines Teils. Vorrang wird typisch als gerichteter azyklischer Graph (DAG) dargestellt; die transitive Hülle dient kompakten Formulierungen. Erweiterungen: Vorrang mit Zeit-Lag (j darf t Minuten nach Ende von i starten), Synchronisierung (start-start, finish-finish) und verallgemeinerter Vorrang zwischen gebündelten Aktivitäten. In MIP-Modellen wird sie üblicherweise als lineare Ungleichung zwischen Binärvariablen kodiert.
Örnek
Auf einer Automobilmontage muss die Aufgabe 'Innenverkleidung einlegen' vor 'Türverkleidung montieren' liegen; im SALBP-MIP wird das als lineare Ungleichung zwischen den Stationsindizes der beiden Aufgaben kodiert.