Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies

DOI10.1016/J.EJOR.2012.02.033arXiv2207.12109MaRDI QIDQ6405944FDOQ6405944

Publication date: 25 July 2022

Abstract: This paper considers a Markovian model for the optimal dynamic routing of homogeneous traffic to parallel heterogeneous queues, each having its own finite input buffer and server pool, where buffer and server-pool sizes, as well as service rates, may differ across queues. The main goal is to identify a heuristic index-based routing policy with low complexity that consistently attains a nearly minimum average loss rate (or, equivalently, maximum throughput rate). A second goal is to compare alternative policies, with respect to computational demands and empirical performance. A novel routing policy that can be efficiently computed is developed based on a second-order extension to Whittle's restless bandit (RB) index, since the latter is constant for this model. New results are also given for the more computationally demanding index policy obtained via policy improvement (PI), including that it reduces to shortest queue routing under symmetric buffer and server-pool sizes. A numerical study shows that the proposed RB index policy is nearly optimal across the instances considered, and substantially outperforms several previously proposed index policies.

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Markov and semi-Markov decision processes (90C40)

This page was built for publication: Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405944)