Optimal routeing in two-queue polling systems. (16th November 2018)

• Record Type: Journal Article
• Authors: Adan, I. J. B. F.; Kulkarni, V. G.; Lee, N.; Lefeber, E.
• Is Part Of: Journal of applied probability. Volume 55:Number 3(2018)
• Page Start: 944
• Page End: 967
• Publication Date: 2018-11-16
• Subjects: Customer routeing, -- dynamic programming, -- fluid queue, -- linear quadratic regulator, -- Nash equilibrium, -- polling system, -- Ricatti equation, -- individual optimum, social optimum; Primary 60K25, -- Secondary 90B22; 519.2
• DOI: 10.1017/jpr.2018.59
• Languages: English
• ISSNs: 0021-9002

Abstract

Abstract: We consider a polling system with two queues, exhaustive service, no switchover times, and exponential service times with rate µ in each queue. The waiting cost depends on the position of the queue relative to the server: it costs a customer c per time unit to wait in the busy queue (where the server is) and d per time unit in the idle queue (where there is no server). Customers arrive according to a Poisson process with rate λ. We study the control problem of how arrivals should be routed to the two queues in order to minimize the expected waiting costs and characterize individually and socially optimal routeing policies under three scenarios of available information at decision epochs: no, partial, and complete information. In the complete information case, we develop a new iterative algorithm to determine individually optimal policies (which are symmetric Nash equilibria), and show that such policies can be described by a switching curve. We use Markov decision processes to compute the socially optimal policies. We observe numerically that the socially optimal policy is well approximated by a linear switching curve. We prove that the control policy described by this linear switching curve is indeed optimal for the fluid version of the two-queue polling system.