Managing Queues with Different Resource Requirements

Queueing models that are used to capture various service settings typically assume that customers require a single unit of resource (server) to be processed. However, there are many service settings where such an assumption may fail to capture the heterogeneity in resource requirements of different customers. We propose a multiserver queueing model with multiple customer classes in which customers from different classes may require different amounts of resources to be served. We study the optimal scheduling policy for such systems. To balance holding costs, service rates, resource requirement, and priority-induced idleness, we develop an index-based policy that we refer to as the idle-avoid $c\mu /m$ rule. For a two-class two-server model, where policy-induced idleness can have a big impact on system performance, we characterize cases where the idle-avoid $c\mu /m$ rule is optimal. In other cases, we establish a uniform performance bound on the amount of suboptimality incurred by the idle-avoid $c\mu /m$ rule. For general multiclass multiserver queues, we establish the asymptotic optimality of the idle-avoid $c\mu /m$ rule in the many-server regime. For long-time horizons, we show that the idle-avoid $c\mu /m$ is throughput optimal. Our theoretical results, along with numerical experiments, provide support for the good and robust performance of the proposed policy.

Funding: J. Dong was supported in part by the National Science Foundation [Grant CMMI-1762544]. N. Zychlinski was supported in part by the Eric and Wendy Schmidt Postdoctoral Award for Women in Mathematical and Computing Sciences and the Israeli Council for Higher Education.