Allocation of flows in closed bipartite queueing networks

• A method for approximating optimal routing probabilities in closed bipartite networks.
• A method for partitioning the agents circulating in the network into deterministic routes.
• Closed-form optimality conditions for routing in closed bipartite queuing networks.

This paper describes a novel method for allocating agents to routes in a closed bipartite queueing network to maximize system throughput using three open network approximations. Results are presented which compare this method with known prior work and optimal solutions to provide an empirical optimality gap. Average empirical optimality gaps of 1.29 percent, 1.13 percent and 1.29 percent are observed for the three approximations considered. Further, because many systems are under the control of rational agents, conditions are derived in order to determine properties of the market context that induce optimal behavior. It is shown that uniform rewards do not yield an efficient rational equilibrium in general. However, for systems with homogeneous servers and travel times or those with travel times that are much larger than queue waiting times, uniform rewarding is optimal.