Transportation Polytope and its Applications in Parallel Server Systems

Parallel server system is a stochastic processing network widely studied in the context of manufacturing, supply chain, ride-hailing, call centers, etc. Heterogeneous customers arrive into the system and only a subset of servers can serve any given customer type depending on the flexibility graph. As the flexibility can be overlapping, scheduling decisions must be made to minimize the delay experienced by the customers. Exact analysis of delay is not possible and so, we consider the heavy traffic asymptotic regime, wherein the arrival rate is loaded up to approach the service rate. We consider the general case when the so called complete resource pooling (CRP) is not satisfied. Recent work established that when the MaxWeight scheduling algorithm is used, the state space collapses (SSC) into a lower dimensional sub-space. Building upon this result, the goal of our paper is to design, analyze and improve the flexibility graph such that the dimension of SSC is minimized. First, we characterize the SSC and thus, the mean delay performance in terms of a given flexibility graph. Using this result, we next study the problem of designing the sparsest flexibility graph that leads to a target SSC dimension. We establish a necessary and sufficient condition on the number of edges required, and provide an algorithm to construct such a graph. Finally, we consider the question of how to improve a given flexibility graph if one is allowed to add a single additional edge. The above results are obtained by identifying a connection to the transportation polytope, and adding to a long line of literature, we develop new theoretical results for it. These results are therefore of independent interest. In particular, we obtain new results on the extreme points and the so-called support graphs of the transportation polytope.