SC 98-34 Norbert Ascheuer, Sven O. Krumke, Jörg Rambau: The Online Transportation Problem: Competitive Scheduling of
Elevators
Abstract: In this paper we consider the following online transportation
problem (OLTP): Objects are to be transported between the vertices
of a given graph. Transportation requests arrive online, specifying
the objects to be transported and the corresponding source and
target vertex. These requests are to be handled by a server which
commences its work at a designated origin vertex and which picks up
and drops objects at their starts and destinations. After the end
of its service the server returns to its start. The goal of OLTP
is to come up with a transportation schedule for the server which
finishes as early as possible.
We first show a lower bound of 5/3 for the competitive ratio of
any deterministic algorithm. We then analyze two simple and natural
strategies which we call
REPLAN and IGNORE.
REPLAN completely discards its schedule and
recomputes a new one when a new request arrives.
IGNORE always
runs a (locally optimal) schedule for a set of known requests and
ignores all new requests until this schedule is completed.
We show that both strategies, REPLAN and IGNORE, are
5/2-competitive. We also present a somewhat less natural strategy
SLEEP, which in contrast to the other two strategies may leave the
server idle from time to time although unserved requests are known.
We also establish a competitive ratio of 5/2 for the algorithm
SLEEP.
Our results are extended to the case of ``open
schedules where the server is not required to return to its start
position at the end of its service.
Keywords: online optimization,
competitive analysis,
elevator
MSC: 90C27, 90B06
CR: F.1.2