Dozent: Mark Proksch
Termine
Die erste Vorlesung findet wegen der Einführungsveranstaltung erst am 23.10.2000 statt.| VL | Montag | 13:00 - 15:00 | (RUD 25, 4.110) |
|---|
Zuordnung
- Hauptstudium, 1. Teil eines Halbkurses
- Theoretische Informatik
Inhalte und Lernziele
Man betrachte sich folgende Probleme:- Ein Reisender will eine bestimmte Menge von Städten besuchen und sucht nach einer möglichst kurzen (oder auch möglichst billigen) Route, mit der er jeden Ort genau einmal besucht. (Traveling Salesman Problem)
- Eine Betrieb stellt eine Menge von Produkten mit Hilfe einer Menge verschiedener Maschinen her. Jedes Produkt erfordert zu seiner Herstellung die Benutzung bestimmter Maschinen in einer bestimmten Reihenfolge und jeweiliger Bearbeitungszeit. Anhand von Auftragslage und Lieferterminen ist nun ein Fertigungsplan zu erstellen, der alle Termine und Stückzahlen einhält und sowohl die Standzeiten der Maschinen (freie Kapazität für weitere Aufträge) als auch die Durchlaufzeiten der Produkte (Lagerhaltungskosten) minimiert. (Maschinenbelegungsproblem)
- Ein Verkehrsbetrieb will einen Fahrplan erstellen. Die Taktzeiten jeder Linie sind vorgegeben. Die genauen Abfahrtzeiten sind so zu wählen, daß an Wendestellen genügend Wartezeit für Pausen und Verspätungspuffer zur Verfügung stehen und die Anschlüsse optimiert (durchschnittliche Wartezeiten der Kunden minimiert) werden.
- Eine Fluggesellschaft möchte den monatlichen Einsatzplan seines fliegenden Personals erstellen. Dieser Plan muß zunächst den gesetzlichen und tarifvertraglichen Vorschriften (Ruhezeiten, maximale Flugzeiten) genügen und alle anfallenden Dienste mit Hilfe des vorhandenen Personals abdecken. Darüber hinaus möchte die Fluggesellschaft Wartezeiten des Personals minimieren, Hotel- und zusätzliche Transportkosten senken und die Robustheit des Einsatzplans gegenüber Verspätungen erhöhen. (Crew Scheduling Problem)
Diesen Problemen ist gemein, daß die Generierung einer beliebigen, zulässigen Lösung vergleichsweise einfach, aber das Auffinden einer kostengünstigen bzw. effizienten Lösung sehr schwer ist. In Bereichen wie Logistik, Transport und Produktion finden sich eine Vielzahl ähnlicher Problemstellungen, deren Lösung zu einem ökonomischen Einsatz von Ressourcen, erhöhter Effizienz von Prozessen oder einer Verbesserung der Produktqualität beiträgt.
Die Vorlesung widmet sich verschiedenen Lösungsverfahren solcher kombinatorischer Optimierungsprobleme. Sie besteht aus zwei Teilen, in denen die zwei bedeutendsten Algorithmenfamilien behandelt werden.
Im ersten Teil sollen verschiedene lokale Suchverfahren wie z.B. Simulated Annealing und Tabu-Search vorgestellt und untersucht werden. Anhand verschiedener Projekte unseres Lehrstuhles können die Umsetzung der Algorithmen in die Praxis demonstriert und die dabei auftretenden Probleme erläutert werden.
Der im Sommersemester folgende zweite Teil befaßt sich mit linearer und ganzzahliger Programmierung. Es werden gängige Verfahren wie die Primal-Dual-Methode, der Simplexalgorithmus und die Ellipsoidmethode erarbeitet und analysiert.
Beide Teile bilden zusammen einen Halbkurs und werden im Sommer gemeinsam geprüft.
