@misc{KrumkeRambau, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Probieren geht {\"u}ber Studieren? Entscheidungshilfen f{\"u}r kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6723}, number = {02-05}, abstract = {Die Automatisierung von innerbetrieblicher Logistik erfordert -- {\"u}ber die physikalische Steuerung von Ger{\"a}ten hinaus -- auch eine effiziente Organisation der Transporte: ein Aufgabenfeld der kombinatorischen Optimierung. Dieser Artikel illustriert anhand von konkreten Aufgabenstellungen die Online-Problematik (unvollst{\"a}ndiges Wissen) sowie die Echtzeit-Problematik (beschr{\"a}nkte Rechenzeit), auf die man in der innerbetrieblichen Logistik trifft. Der Text gibt einen {\"U}berblick {\"u}ber allgemeine Konstruktionsprinzipien f{\"u}r Online-Algorithmen und Bewertungsmethoden, die bei der Entscheidung helfen, welche Algorithmen f{\"u}r eine vorliegende Problemstellung geeignet sind.}, language = {de} } @misc{Rambau, author = {Rambau, J{\"o}rg}, title = {Triangulierungen von Punktmengen und Polyedern}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6145}, number = {00-46}, abstract = {Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung {\"u}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{\"u}hrende Themen regul{\"a}re Triangulierungen, Sekund{\"a}rpolytope, bistellare Operationen, h{\"o}here Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel {\"u}ber Enumeration und Optimierung beschließt die Zusammenstellung.}, language = {de} } @misc{KrumkeRambau, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6238}, number = {00-55}, abstract = {Wie soll man einen Aufzug steuern, wenn man keine Informationen {\"u}ber zuk{\"u}nftige Fahrauftr{\"a}ge besitzt? Soll man eine Bahncard kaufen, wenn die n{\"a}chsten Bahnreisen noch unbekannt sind? In der klassischen kombinatorischen Optimierung geht man davon aus, daß die Daten jeder Probleminstanz vollst{\"a}ndig gegeben sind. In vielen F{\"a}llen modelliert diese \emph{Offline-Optimierung} jedoch die Situationen aus Anwendungen nur ungen{\"u}gend. Zahlreiche Problemstellungen in der Praxis sind in nat{\"u}rlicher Weise \emph{online}: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zuk{\"u}nftiger Ereignisse getroffen werden m{\"u}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{\"o}sung mit dem Wert einer optimalen Offline-L{\"o}sung. Mit Hilfe der kompetitiven Analyse werden im Skript Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schw{\"a}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{\"u}lle von Online-Problemen auf. Hierbei werden an die Algorithmen oftmals weitere Anforderungen gestellt. So m{\"u}ssen Entscheidungen unter strikten Zeitbeschr{\"a}nkungen gef{\"a}llt werden (Echtzeit-Anforderungen). Dieses Skript ist aus dem Online-Teil der Vorlesung -Ausgew{\"a}hlte Kapitel aus der ganzzahligen Optimierung- (Wintersemester~1999/2000) und der Vorlesung -Online Optimierung- (Sommersemester~2000) an der Technischen Universit{\"a}t Berlin entstanden.}, language = {de} } @misc{GroetschelKrumkeRambau, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Wo bleibt der Aufzug?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4175}, number = {SC-99-29}, abstract = {Dieser Artikel gibt eine allgemeinverst{\"a}ndliche Einf{\"u}hrung in die spezielle Problematik kombinatorischer Online-Problem am Beispiel der Fahrstuhlsteuerung.}, language = {de} }