Dozenten: Dr. Stefan Hougardy und Mark Proksch
Termine
| VL | Dienstag | 11:00 - 13:00 | (RUD 25, 4.101) M. Proksch |
|---|---|---|---|
| Donnerstag | 13:00 - 15:00 | (RUD 25, 4.111) Dr. S. Hougardy |
Zuordnung
- Hauptstudium, Halbkurs
- 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 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.
Programmierpraktikum
Parallel zur Vorlesung besteht für besonders Interessierte die Möglichkeit, das erarbeitete Wissen in die Praxis umzusetzen. Dies kann anhand eines einfachen Beispielproblems oder auch innerhalb eines unserer Projekte erfolgen.
Die Teilnahme am Praktikum ist freiwillig und somit KEINE Prüfungsvoraussetzung.
English