Design and Analysis of Flexible Server Systems

We consider problems related to design and analysis of flexible server systems. On the analysis side, we study the stability properties of the X-model under parameter agnostic policies. The X-model is a special case of flexible server systems that carries insights into larger flexible server systems. It consists of two servers and two queues where both servers are capable of serving either queue. It is the smallest flexible server system that contains a cycle, for which the stability question has not been fully answered. We consider this model under parameter agnostic policies, which dictate what queue an idle server will serve. These policies are appealing in real-world scenarios as they solely rely on queue size information, and eliminate the need for knowledge about system parameters. We show that, despite being desirable, such policies can result in instability. Our analysis focuses on parameter agnostic switching curve policies, wherein each server's service decision is determined by a non-decreasing function of queue sizes. We demonstrate that even at relatively low system loads, these policies can lead to instability. We explore various classes of parameter agnostic policies and characterize sufficient conditions for instability.We then focus on the design problem on flexible server systems, where the goal is to construct a sparse server-buffer compatibility graph without compromising performance. Researchers have proposed various flexibility structures to tackle the design problem, and validated the proposed designs by theoretical justifications. However, these structures typically rely on a restrictive flow conservation assumption, where exactly one unit of processing capacity is required for one unit of a job. We, on the other hand, relax the flow conservation assumption and allow that arbitrary processing capacities may be required to process one unit of a job. We show that in systems with general processing rates, there exists a sparse flexibility structure with O(m+n) arcs that can achieve good performance in heavy traffic, where m is the number of servers and n is the number of buffers; and we introduce an algorithm that constructs the said flexibility structure. We justify the performance of our proposed design via numerical experiments. We highlight the critical differences in the analysis of such systems compared to systems where flow conservation assumption holds, and we discuss the connection between the flexibility structure design problem and the transportation problems.