Shadow-routing based control of flexible multiserver pools in overload

Alexander L. Stolyar, Tolga Tezcan

Research output: Contribution to journalArticle

Abstract

We consider a general parallel server system model with multiple customer classes and several flexible multiserver pools, in the many-server asymptotic regime where the input rates and server pool sizes are scaled up linearly to infinity. Service of a customer brings a constant reward, which depends on its class. The objective is to maximize the long-run reward rate. Our primary focus is on overloaded systems. Unlike in the case when the system is not overloaded, where the main decision is how to allocate resources to incoming customers, in this case it is also crucial to determine which customers will be admitted to the system. We propose a real-time, parsimonious, robust routing policy, SHADOW-RM, which does not require the knowledge of customer input rates and does not solve any optimization problem explicitly, and we prove its asymptotic optimality. Then, by combining SHADOW-RM with another policy, SHADOW-LB, proposed in our previous work for systems that are not overloaded, we suggest policy SHADOW-TANDEM, which automatically and seamlessly detects overload and reduces to one of the schemes, SHADOW-RM or SHADOW-LB, accordingly. Extensive simulations demonstrate a remarkably good performance of proposed policies.

Original languageEnglish (US)
Pages (from-to)1427-1444
Number of pages18
JournalOperations Research
Volume59
Issue number6
DOIs
StatePublished - Nov 1 2011
Externally publishedYes

Fingerprint

Servers
Routing
Overload
Reward

Keywords

  • Large flexible server pools
  • Many-server asymptotics
  • Queueing networks
  • Revenue maximization
  • Routing and scheduling
  • Shadow routing

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Cite this

Shadow-routing based control of flexible multiserver pools in overload. / Stolyar, Alexander L.; Tezcan, Tolga.

In: Operations Research, Vol. 59, No. 6, 01.11.2011, p. 1427-1444.

Research output: Contribution to journalArticle

@article{dbb75a64f1bb41e38282091395174fb0,
title = "Shadow-routing based control of flexible multiserver pools in overload",
abstract = "We consider a general parallel server system model with multiple customer classes and several flexible multiserver pools, in the many-server asymptotic regime where the input rates and server pool sizes are scaled up linearly to infinity. Service of a customer brings a constant reward, which depends on its class. The objective is to maximize the long-run reward rate. Our primary focus is on overloaded systems. Unlike in the case when the system is not overloaded, where the main decision is how to allocate resources to incoming customers, in this case it is also crucial to determine which customers will be admitted to the system. We propose a real-time, parsimonious, robust routing policy, SHADOW-RM, which does not require the knowledge of customer input rates and does not solve any optimization problem explicitly, and we prove its asymptotic optimality. Then, by combining SHADOW-RM with another policy, SHADOW-LB, proposed in our previous work for systems that are not overloaded, we suggest policy SHADOW-TANDEM, which automatically and seamlessly detects overload and reduces to one of the schemes, SHADOW-RM or SHADOW-LB, accordingly. Extensive simulations demonstrate a remarkably good performance of proposed policies.",
keywords = "Large flexible server pools, Many-server asymptotics, Queueing networks, Revenue maximization, Routing and scheduling, Shadow routing",
author = "Stolyar, {Alexander L.} and Tolga Tezcan",
year = "2011",
month = "11",
day = "1",
doi = "10.1287/opre.1110.0960",
language = "English (US)",
volume = "59",
pages = "1427--1444",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "6",

}

TY - JOUR

T1 - Shadow-routing based control of flexible multiserver pools in overload

AU - Stolyar, Alexander L.

AU - Tezcan, Tolga

PY - 2011/11/1

Y1 - 2011/11/1

N2 - We consider a general parallel server system model with multiple customer classes and several flexible multiserver pools, in the many-server asymptotic regime where the input rates and server pool sizes are scaled up linearly to infinity. Service of a customer brings a constant reward, which depends on its class. The objective is to maximize the long-run reward rate. Our primary focus is on overloaded systems. Unlike in the case when the system is not overloaded, where the main decision is how to allocate resources to incoming customers, in this case it is also crucial to determine which customers will be admitted to the system. We propose a real-time, parsimonious, robust routing policy, SHADOW-RM, which does not require the knowledge of customer input rates and does not solve any optimization problem explicitly, and we prove its asymptotic optimality. Then, by combining SHADOW-RM with another policy, SHADOW-LB, proposed in our previous work for systems that are not overloaded, we suggest policy SHADOW-TANDEM, which automatically and seamlessly detects overload and reduces to one of the schemes, SHADOW-RM or SHADOW-LB, accordingly. Extensive simulations demonstrate a remarkably good performance of proposed policies.

AB - We consider a general parallel server system model with multiple customer classes and several flexible multiserver pools, in the many-server asymptotic regime where the input rates and server pool sizes are scaled up linearly to infinity. Service of a customer brings a constant reward, which depends on its class. The objective is to maximize the long-run reward rate. Our primary focus is on overloaded systems. Unlike in the case when the system is not overloaded, where the main decision is how to allocate resources to incoming customers, in this case it is also crucial to determine which customers will be admitted to the system. We propose a real-time, parsimonious, robust routing policy, SHADOW-RM, which does not require the knowledge of customer input rates and does not solve any optimization problem explicitly, and we prove its asymptotic optimality. Then, by combining SHADOW-RM with another policy, SHADOW-LB, proposed in our previous work for systems that are not overloaded, we suggest policy SHADOW-TANDEM, which automatically and seamlessly detects overload and reduces to one of the schemes, SHADOW-RM or SHADOW-LB, accordingly. Extensive simulations demonstrate a remarkably good performance of proposed policies.

KW - Large flexible server pools

KW - Many-server asymptotics

KW - Queueing networks

KW - Revenue maximization

KW - Routing and scheduling

KW - Shadow routing

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

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

U2 - 10.1287/opre.1110.0960

DO - 10.1287/opre.1110.0960

M3 - Article

AN - SCOPUS:84855325146

VL - 59

SP - 1427

EP - 1444

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 6

ER -