Textprobe: Kapitel 2.2, Anwendungen des LSPs: Das vorliegende Optimierungsproblem tritt nicht nur bei Schleusen auf. Wir geben nun eine Übersicht über mögliche Anwendungen des LSPs. Bei dieser Gelegenheit wiederholen wir noch einmal einige wichtige Voraussetzungen für die Anwendbarkeit auf die Planung von Schleusungsvorgängen. Schiffsschleusen: Das LSPs kann nur dann auf die Ablaufplanung von Schleusungen bei einer Schleuse angewandt werden, wenn folgenden Bedingungen erfüllt sind: - Die Schleusenkammern sind parallel angeordnet. - Die Schleusenkammern sind parallel angeordnet. ist die Verhinderung von Kollisionen nach Bemerkung 1.6. - Die Füllzeit ist nur von der Schleusenkammer und nicht etwa von den Gezeiten abhängig. - Die Schiffe können eigenständig fahren und werden nicht in mehrere physische Teile aufgeteilt. - Die Daten aller Schiffe sind im Voraus bekannt. Interaktionen der Schleusungsvorgänge an verschiedenen Schleusen-Standorten müssen von einem übergeordneten Algorithmus behandelt werden. Beim NOK geschieht dies, wie in der Einleitung beschrieben, durch aufeinanderfolgende überlappende Zeithorizonte. Gütertransport z.B. bei Autofähren: Ein Anwendungsbeispiel, das überraschenderweise ebenfalls mit Schifffahrt zu tun hat, liegt bei Autofähren vor: Voneinander unabhängige Fähren, die den Schleusenkammern entsprechen, transportieren Fahrzeuge verschiedener Größen zwischen zwei Ufern hin und her. Die Fahrzeuge kommen an den Ufern wie die Schiffe an den beiden Seiten einer Schleuse zu zufälligen Zeitpunkten an und sollen jeweils mit möglichst kurzer Wartezeit überführt werden. Ähnliche Anwendungen findet man bei Güterzügen und Lastenaufzügen, sofern sie ebenfalls Güter zwischen zwei Stationen hin- und hertransportieren. Verladestationen: Auch auf Verladestationen wäre das Problem anwendbar, wenn z.B. Container von Kränen zwischen zwei Terminals umgeladen werden. Auf die Verwandtschaft des LSPs mit dem Truck-Scheduling-Problem (TrSP), das bei Verladehäfen angewandt wird, werden wir in Kapitel 3.3 näher eingehen. Man muss allerdings stets voraussetzen, dass die Güter nach der Umladung sofort verarbeitet oder weitertransportiert werden. Denn andernfalls wäre es sinnlos, die Wartezeiten der Güter nur während des Umladens zu minimieren. 2.3, Komplexitätsanalyse: Das zum LSP gehörige Entscheidungsproblem (dLSP) lautet: Gegeben eine Instanz I des LSPs und eine reelle Zahl g, existiert für I eine Lösung, die 1) zulässig ist und 2) deren Kosten nicht größer als g sind? Viele bekannte Entscheidungsprobleme sind (falls P _= NP) nicht effizient lösbar, d.h. die Entscheidung kann oft nicht innerhalb einer Laufzeit getroffen werden, die höchstens polynomiell von der Problemgröße abhängt. Wir weisen nach, dass das dLSP zu diesen stark NP-schweren Problemen gehört. Zudem zeigen wir, dass es Element der Komplexitätsklasse NP ist, woraus schließlich seine starke NP-Vollständigkeit folgt. Satz 2.4. dLSP ? NP. Beweis. Gegeben sei eine Instanz des dLSPs mit der Antwort 'ja', d.h. für eine Instanz I des LSPs und ein g ?R existiert eine zulässige Lösung S mit cost(S)?g. Wir nehmen S als Zertifikat. Zu zeigen ist, dass beide geforderten Eigenschaften von S mit polynomiellem Zeitaufwand verifiziert werden können. Zulässigkeit: Die in Kapitel 2.1.4 aufgeführten Bedingungen für die Zulässigkeit von LSP-Lösungen können jeweils in polynomieller Zeit verifiziert werden. Denn wegen Bedingung 2.11 ist die Anzahl der Schleusungen einer zulässigen Lösung linear beschränkt. Einhalten der Kostenschranke: Die Summe der Extrazeiten einer Lösung kann nach Kapitel 2.1.5 in linearer Zeit berechnet werden. Der Wert dieser Summe muss mit g verglichen werden.