Design and analysis of online algorithms for mobile server applications

摘要

Numerous real-world problems exhibit behaviors that can be modeled as a group of servers that are required to visit a series of locations under some set of constraints. In many cases, these problems have the property of being online, that is the system has to act on a particular request or set of requests before it receives subsequent requests. Such applications include scheduling I/O requests for a disk drive, scheduling taxicabs and airport shuttle services, parcel post pickup and delivery, routing freight, and dispatching emergency vehicles. With the advent of intelligent, autonomous distributed systems, mobile robots that use online scheduling algorithms can begin to be used for some of the above applications. This thesis examines a series of models that correspond to such applications. We consider models that are extensions to the basic online k-Server Problem, where a set of servers has to respond to a series of calls where each call is a location that has to be visited. These extensions include adding a second location to each call (the Taxicab Problem), having the calls come from a known probabilistic distribution, limiting the servers' available memory, and allowing servers to reject calls. We develop strategies and algorithms to handle these models. For such problems, it is natural to evaluate the efficiency of the scheduling algorithm either with respect to some absolute metric or relative to some optimal solution, either online or offline. In the offline case, not only are we evaluating the performance of the algorithm, but we also provide a measure of the value of advance knowledge. We consider several measures of performance and present results for these models, giving upper and lower bounds on performance.