M/M/s On Demand : Queues with On-Demand and Reserved Servers

In many real-world applications, there is a growing trend to supplement reserved capacity with on-demand capacity; examples include the deployment of customer-service agents by call centers, servers by cloud-computing providers, and health-care professionals by post-acute-care services. We propose and analyze a canonical M/M/s queueing system that employs both "reserved" and "on-demand" servers – the number of reserved servers is decided at the beginning of the (infinite) time horizon while the number of on-demand servers is decided dynamically as needed, in real time. We study two problems. The first is that of minimizing the infinite-horizon expected discounted cost incurred in the hiring of the (reserved and on-demand) servers and in the waiting of the jobs in the queue. The second is that of minimizing the long-run average cost. Our main result is the structure of the optimal policies for these two problems. In particular, we show that, in each of these problems, the optimal on-demand capacity control is a threshold-based bang-bang policy: If the number of jobs in the system is below a threshold, then no on-demand servers are employed. Otherwise, the number of on-demand servers is chosen such that no jobs wait (i.e., the total number of servers in use equals the total number of jobs in the system). For the discounted-cost problem, we provide an ϵ-optimal solution; that is, for any ϵ>0, we prescribe a solution, comprised of a number of reserved servers and a bang-bang threshold, whose expected cost is at most ϵ above the optimal. For the average-cost problem, we obtain a closed-form expression for the cost of any threshold-based bang-bang policy with a given number of reserved servers. We then use this expression to derive an algorithm for obtaining the optimal number of reserved servers and the bang-bang threshold exactly