M/M/1 Queueing Decision Processes with Monotone Hysteretic Optimal Policies

This paper studies an M/M/1 queueing decision process in which the arrival and service rates are chosen from a finite set whenever the queue length changes. Each choice has a switching cost depending on the chosen rates and those currently in use, and a usage cost depending on the chosen rates and the queue length; these switching and usage cost functions are submodular and satisfy additional technical conditions. The system objective is to find a policy for dynamically choosing the rates, based on the current rates and queue length, that minimizes the expected total discounted cost or average cost over an infinite horizon. We prove that there is a monotone hysteretic optimal policy in which the arrival and service rates are decreasing and increasing, respectively, in the queue length; there is a hysteresis (retardation) in the changing of the actions due to the switching costs. We establish this result by showing that such optimal policies exist for an equivalent discrete-time random walk decision process. Our results confirm a decade-old conjecture that the M/M/1 queue has a monotone hysteretic optimal control policy.