TY - GEN A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Wo bleibt der Aufzug? N2 - Dieser Artikel gibt eine allgemeinverständliche Einführung in die spezielle Problematik kombinatorischer Online-Problem am Beispiel der Fahrstuhlsteuerung. T3 - ZIB-Report - SC-99-29 KW - Aufzugsteuerung KW - Online-Optimierung KW - Echtzeit-Optimierung KW - kompetitive Analyse Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4175 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Online Optimierung N2 - Wie soll man einen Aufzug steuern, wenn man keine Informationen über zukünftige Fahraufträge besitzt? Soll man eine Bahncard kaufen, wenn die nächsten Bahnreisen noch unbekannt sind? In der klassischen kombinatorischen Optimierung geht man davon aus, daß die Daten jeder Probleminstanz vollständig gegeben sind. In vielen Fällen modelliert diese \emph{Offline-Optimierung} jedoch die Situationen aus Anwendungen nur ungenügend. Zahlreiche Problemstellungen in der Praxis sind in natürlicher Weise \emph{online}: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zukünftiger Ereignisse getroffen werden müssen. Als ein Standardmittel zur Beurteilung von Online-Algorithmen hat sich die \emph{kompetitive Analyse} durchgesetzt. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten Lösung mit dem Wert einer optimalen Offline-Lösung. Mit Hilfe der kompetitiven Analyse werden im Skript Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schwächen der kompetitiven Analyse werden aufgezeigt und alternative Analysekonzepte vorgestellt. Neben der theoretischen Seite werden auch die Anwendungen der Online-Optimierung in der Praxis, vor allem bei Problemen der innerbetrieblichen Logistik, beleuchtet. Bei der Steuerung automatischer Transportsysteme tritt eine Fülle von Online-Problemen auf. Hierbei werden an die Algorithmen oftmals weitere Anforderungen gestellt. So müssen Entscheidungen unter strikten Zeitbeschränkungen gefällt werden (Echtzeit-Anforderungen). Dieses Skript ist aus dem Online-Teil der Vorlesung -Ausgewählte Kapitel aus der ganzzahligen Optimierung- (Wintersemester~1999/2000) und der Vorlesung -Online Optimierung- (Sommersemester~2000) an der Technischen Universität Berlin entstanden. T3 - ZIB-Report - 00-55 KW - Kompetitive Analyse KW - Online Optimierung KW - Online Algorithmen Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6238 ER - TY - GEN A1 - Rambau, Jörg T1 - Triangulierungen von Punktmengen und Polyedern N2 - Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung über Triangulierungen von Punktmengen und Polyedern als Skriptum verwendet. Nach einem motivierenden Kapitel werden grundlegende Begriffe und Konstruktionen in der Theorie der Triangulierungen von Punktmengen und Polyedern vorgestellt. Danach werden als weiterführende Themen reguläre Triangulierungen, Sekundärpolytope, bistellare Operationen, höhere Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel über Enumeration und Optimierung beschließt die Zusammenstellung. T3 - ZIB-Report - 00-46 KW - point configuration KW - triangulation KW - polytope KW - polyhedron KW - Gale diagram KW - secondary polytope KW - cyclic polytope KW - graph of all triangulations KW - conn Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6145 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Probieren geht über Studieren? Entscheidungshilfen für kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik N2 - Die Automatisierung von innerbetrieblicher Logistik erfordert -- über die physikalische Steuerung von Geräten hinaus -- auch eine effiziente Organisation der Transporte: ein Aufgabenfeld der kombinatorischen Optimierung. Dieser Artikel illustriert anhand von konkreten Aufgabenstellungen die Online-Problematik (unvollständiges Wissen) sowie die Echtzeit-Problematik (beschränkte Rechenzeit), auf die man in der innerbetrieblichen Logistik trifft. Der Text gibt einen Überblick über allgemeine Konstruktionsprinzipien für Online-Algorithmen und Bewertungsmethoden, die bei der Entscheidung helfen, welche Algorithmen für eine vorliegende Problemstellung geeignet sind. T3 - ZIB-Report - 02-05 KW - Logistik KW - Hochregallagerbediengeräte KW - Kommissioniermobile KW - Aufzüge KW - Online-Optimierung KW - Echtzeit-Optimierung KW - Simulation KW - kompetitive Analyse Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6723 ER -