Dynamic Assignment Control of a Closed Queueing Network under Complete Resource Pooling

Abstract

We study the design of state dependent control for a closed queueing network model, inspired by shared transportation systems such as ridesharing. In particular, we focus on the design of assignment policies, wherein the platform can choose which supply unit to dispatch to meet an incoming customer request. The supply unit subsequently becomes available at the destination after dropping the customer. We consider the proportion of dropped demand in steady state as the performance measure. We propose a family of simple and explicit state dependent policies called Scaled MaxWeight (SMW) policies and prove that under the complete resource pooling (CRP) condition (analogous to a strict version of Hall’s condition for bipartite matchings), any SMW policy induces an exponential decay of demand-dropping probability as the number of supply units scales to infinity. Furthermore, we show that there is an SMW policy that achieves the optimal exponent among all assignment policies, and analytically specify this policy in terms of the matrix of customer-request arrival rates. The optimal SMW policy protects structurally under-supplied locations.

Publication
Preprint arXiv_id:1803.04959

Earlier conference version: Banerjee et al. (2018)

Siddhartha Banerjee
Siddhartha Banerjee
Associate Professor

Sid Banerjee is an associate professor in the School of Operations Research at Cornell, working on topics at the intersection of data-driven decision-making and stochastic control, economics and computation, and large-scale network algorithms.