@misc{HauptmeierKrumkeRambau1999, author = {Hauptmeier, Dietrich and Krumke, Sven and Rambau, J{\"o}rg}, title = {The Online Dial-a-Ride Problem under Reasonable Load}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3961}, number = {SC-99-08}, year = {1999}, abstract = {In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp.\ average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis.}, language = {en} } @misc{GroetschelHauptmeierKrumkeetal.1999, author = {Gr{\"o}tschel, Martin and Hauptmeier, Dietrich and Krumke, Sven and Rambau, J{\"o}rg}, title = {Simulation Studies for the Online-Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3976}, number = {SC-99-09}, year = {1999}, abstract = {In a large distribution center of Herlitz AG, Berlin, we invesigated the elevator subsystem of the fully automated pallet transportation system. Each elevator may carry one pallet and has to serve eight levels. The goal is to minimize the average resp.\ the maximum flow time. The variants of this elevator control problem have been subject of recent theoretical research and are known as online-dial-a-ride problems. In this paper we investigate several online algorithms for several versions of online-dial-a-ride problems by means of a simulation program, developed on the basis of the simulation library AMSEL. We draw statistics from samples of randomly generated data providing for different load situations. Moreover, we provide preliminary studies with real production data for a system of five elevators connected by a conveyor circuit, as can be found at the Herlitz plant. We show which algorithms are best under certain load situations and which lead to break downs under particular circumstances.}, language = {en} } @phdthesis{Krumke2002, author = {Krumke, Sven}, title = {Online Optimization: Competitive Analysis and Beyond}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6925}, number = {02-25}, year = {2002}, abstract = {Traditional optimization techniques assume, in general, knowledge of all data of a problem instance. There are many cases in practice, however, where decisions have to be made before complete information about the data is available. In fact, it may be necessary to produce a part of the problem solution as soon as a new piece of information becomes known. This is called an \emph{online situation}, and an algorithm is termed \emph{online}, if it makes a decision (computes a partial solution) whenever a new piece of data requests an action. \emph{Competitive analysis} has become a standard yardstick to measure the quality of online algorithms. One compares the solution produced by an online algorithm to that of an optimal (clairvoyant) offline algorithm. An online algorithm is called \$c\$-competitive if on every input the solution it produces has cost'' at most \$c\$~times that of the optimal offline algorithm. This situation can be imagined as a game between an online player and a malicious adversary. Although competitive analysis is a worst-case analysis and henceforth pessimistic, it often allows important insights into the problem structure. One can obtain an idea about what kind of strategies are promising for real-world systems and why. On the other hand there are also cases where the offline adversary is simply too powerful and allows only trivial competitiveness results. This phenomenon is called hitting the triviality barrier''. We investigate several online problems by means of competitive analysis. We also introduce new concepts to overcome the weaknesses of the standard approach and to go beyond the triviality barrier.}, language = {en} }