- search hit 1 of 1
The Online Transportation Problem: Competitive Scheduling of Elevators
Please always quote using this URN: urn:nbn:de:0297-zib-3779
- In this paper we consider the following online transportation problem (\textsc{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 \textsc{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 \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{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, \textsf{REPLAN} and \textsf{IGNORE}, are $5/2$-competitive. We also present a somewhat less natural strategy \textsf{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 \textsf{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.
Author: | Norbert Ascheuer, Sven Krumke, Jörg Rambau |
---|---|
Document Type: | ZIB-Report |
Tag: | competitive analysis; elevator; online optimization |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
CCS-Classification: | F. Theory of Computation / F.1 COMPUTATION BY ABSTRACT DEVICES / F.1.2 Modes of Computation |
Date of first Publication: | 1998/12/08 |
Series (Serial Number): | ZIB-Report (SC-98-34) |
ZIB-Reportnumber: | SC-98-34 |
Published in: | Appeared as: Online Dial-a-Ride Problems: in: Minimizing the Completion Time. Proceeding of the 17th International Symposium on Theoretical Aspects of Computer Science, Vol 1770 of Lecture Notes in Computer Science, Springer 2000, 639-650 |