Optimal routeing in two-queue polling systems

I. J.B.F. Adan, V. G. Kulkarni, N. Lee, E. Lefeber

Research output: Contribution to journalArticleAcademicpeer-review

18 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)944-967
Number of pages24
JournalJournal of Applied Probability
Volume55
Issue number3
DOIs
Publication statusPublished - 1 Sep 2018

Fingerprint

Polling Systems
Queue
Optimal Policy
Server
Curve
Costs
Customers
Unit
Markov Decision Process
Control Policy
Polling
Poisson process
Nash Equilibrium
Iterative Algorithm
Control Problem
Minimise
Partial
Fluid
Scenarios

Keywords

  • Customer routeing
  • dynamic programming
  • fluid queue
  • individual optimum, social optimum
  • linear quadratic regulator
  • Nash equilibrium
  • polling system
  • Ricatti equation

Cite this

Adan, I. J.B.F. ; Kulkarni, V. G. ; Lee, N. ; Lefeber, E. / Optimal routeing in two-queue polling systems. In: Journal of Applied Probability. 2018 ; Vol. 55, No. 3. pp. 944-967.
@article{73568d3caa2540468bbb9da5fc8075b6,
title = "Optimal routeing in two-queue polling systems",
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.",
keywords = "Customer routeing, dynamic programming, fluid queue, individual optimum, social optimum, linear quadratic regulator, Nash equilibrium, polling system, Ricatti equation",
author = "Adan, {I. J.B.F.} and Kulkarni, {V. G.} and N. Lee and E. Lefeber",
year = "2018",
month = "9",
day = "1",
doi = "10.1017/jpr.2018.59",
language = "English",
volume = "55",
pages = "944--967",
journal = "Journal of Applied Probability",
issn = "0021-9002",
publisher = "University of Sheffield",
number = "3",

}

Optimal routeing in two-queue polling systems. / Adan, I. J.B.F.; Kulkarni, V. G.; Lee, N.; Lefeber, E.

In: Journal of Applied Probability, Vol. 55, No. 3, 01.09.2018, p. 944-967.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Optimal routeing in two-queue polling systems

AU - Adan, I. J.B.F.

AU - Kulkarni, V. G.

AU - Lee, N.

AU - Lefeber, E.

PY - 2018/9/1

Y1 - 2018/9/1

N2 - 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.

AB - 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.

KW - Customer routeing

KW - dynamic programming

KW - fluid queue

KW - individual optimum, social optimum

KW - linear quadratic regulator

KW - Nash equilibrium

KW - polling system

KW - Ricatti equation

UR - http://www.scopus.com/inward/record.url?scp=85056763501&partnerID=8YFLogxK

U2 - 10.1017/jpr.2018.59

DO - 10.1017/jpr.2018.59

M3 - Article

AN - SCOPUS:85056763501

VL - 55

SP - 944

EP - 967

JO - Journal of Applied Probability

JF - Journal of Applied Probability

SN - 0021-9002

IS - 3

ER -