UC Berkeley

We focus on systems with task arrivals in time and space. A good model for the single-customer case is the Dynamic Traveling Repairman Problem (DTRP) [1]. The DTRP literature has focused on optimizing the expected value of system time, defined as the elapsed time between the arrival and the completion of each task. We focus on the stability and distribution of system time, including its variance. This dissertation establishes a partially policy independent necessary and sufficient condition for stability in the DTRP. The policy class includes some of the policies proven to be optimal for system time expectation under light and heavy loads in the literature. We propose a new policy named PART-n-TSP and compute a good approximation for its system time distribution. PART-n-TSP has lower system time variance than PART-TSP [2] and Nearest Neighbor [1] when the load is neither too small or too large. We prove that PART-n-TSP is also optimal for system time expectation under light and heavy loads.

In the multi-customer case, the scheduling policies of the DTRP and other vehicle routing problems do not create performance isolation [3] between customers. We explore performance isolation between customers by borrowing the virtual machine abstraction from cloud computing. Since our servers are moving vehicles, we propose a new equivalent of the virtual machine called the virtual vehicle enabling what we call cloud computing in space. The customer operates virtual vehicles that are in reality hosted by fewer, shared provider-operated real vehicles. We show that cloud computing in space can do better than conventional cloud computing in the sense of realizing high performance isolation (e.g. 98%) while requiring significantly fewer real vehicles (e.g. approximately 1-for-5).