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

F. V. Lu and R. F. Serfozo
Additional contact information
F. V. Lu: St. John's University, Jamaica, New York
R. F. Serfozo: Georgia Institute of Technology, Atlanta, Georgia

Operations Research, 1984, vol. 32, issue 5, 1116-1132

Abstract: 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.

Keywords: 117 random walk and queueing Markov decision processes; 696 control of arrival and service rates in M/M/1 queues (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.5.1116 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:32:y:1984:i:5:p:1116-1132

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().