SC 99-08 Dietrich Hauptmeier, Sven O. Krumke, Jörg Rambau.: The Online Dial-a-Ride Problem under Reasonable Load
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.
Keywords: online optimization,
competitive analysis,
elevator
MSC: 90C27, 90B06
CR: F.1.2