Large-scale service systems with packing constraints and heterogeneous servers

Research output: Contribution to journalConference article

Abstract

A service system with multiple types of arriving customers and multiple types of servers is considered. Several customers (possibly of different types) can be placed for concurrent service into same server, subject to "packing" constraints, which depend on the server type. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered such that the customer arrival rates grow to infinity. We consider two variants of the model. For the infinite-server model, we prove asymptotic optimality of the Greedy Random (GRAND) algorithm in the sense of minimizing the weighted (by type) number of occupied servers in steady-state. (This version of GRAND generalizes that introduced in [1] for the homogeneous systems, with all servers of same type.) We then introduce a natural extension of GRAND algorithm for finite-server systems with blocking. Assuming subcritical system load, we prove existence, uniqueness, and local stability of the large-scale system equilibrium point such that no blocking occurs. This result strongly suggests a conjecture that the steady-state blocking probability under the algorithm vanishes in the large-scale limit.

Original languageEnglish (US)
Pages (from-to)42-44
Number of pages3
JournalPerformance Evaluation Review
Volume44
Issue number2
DOIs
StatePublished - Sep 29 2016
Event18th Workshop on MAthematical Performance Modeling and Analysis, MAMA 2016 and 2016 Greenmetrics Workshop - Antibes Juan-les-Pins, France
Duration: Jun 14 2016 → …

Fingerprint

Servers
Blocking probability
Large scale systems

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Large-scale service systems with packing constraints and heterogeneous servers. / Stolyar, Alexander L.

In: Performance Evaluation Review, Vol. 44, No. 2, 29.09.2016, p. 42-44.

Research output: Contribution to journalConference article

@article{eb9ad5125b334078b83d15cd9ce3450a,
title = "Large-scale service systems with packing constraints and heterogeneous servers",
abstract = "A service system with multiple types of arriving customers and multiple types of servers is considered. Several customers (possibly of different types) can be placed for concurrent service into same server, subject to {"}packing{"} constraints, which depend on the server type. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered such that the customer arrival rates grow to infinity. We consider two variants of the model. For the infinite-server model, we prove asymptotic optimality of the Greedy Random (GRAND) algorithm in the sense of minimizing the weighted (by type) number of occupied servers in steady-state. (This version of GRAND generalizes that introduced in [1] for the homogeneous systems, with all servers of same type.) We then introduce a natural extension of GRAND algorithm for finite-server systems with blocking. Assuming subcritical system load, we prove existence, uniqueness, and local stability of the large-scale system equilibrium point such that no blocking occurs. This result strongly suggests a conjecture that the steady-state blocking probability under the algorithm vanishes in the large-scale limit.",
author = "Stolyar, {Alexander L.}",
year = "2016",
month = "9",
day = "29",
doi = "10.1145/3003977.3003992",
language = "English (US)",
volume = "44",
pages = "42--44",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

TY - JOUR

T1 - Large-scale service systems with packing constraints and heterogeneous servers

AU - Stolyar, Alexander L.

PY - 2016/9/29

Y1 - 2016/9/29

N2 - A service system with multiple types of arriving customers and multiple types of servers is considered. Several customers (possibly of different types) can be placed for concurrent service into same server, subject to "packing" constraints, which depend on the server type. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered such that the customer arrival rates grow to infinity. We consider two variants of the model. For the infinite-server model, we prove asymptotic optimality of the Greedy Random (GRAND) algorithm in the sense of minimizing the weighted (by type) number of occupied servers in steady-state. (This version of GRAND generalizes that introduced in [1] for the homogeneous systems, with all servers of same type.) We then introduce a natural extension of GRAND algorithm for finite-server systems with blocking. Assuming subcritical system load, we prove existence, uniqueness, and local stability of the large-scale system equilibrium point such that no blocking occurs. This result strongly suggests a conjecture that the steady-state blocking probability under the algorithm vanishes in the large-scale limit.

AB - A service system with multiple types of arriving customers and multiple types of servers is considered. Several customers (possibly of different types) can be placed for concurrent service into same server, subject to "packing" constraints, which depend on the server type. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered such that the customer arrival rates grow to infinity. We consider two variants of the model. For the infinite-server model, we prove asymptotic optimality of the Greedy Random (GRAND) algorithm in the sense of minimizing the weighted (by type) number of occupied servers in steady-state. (This version of GRAND generalizes that introduced in [1] for the homogeneous systems, with all servers of same type.) We then introduce a natural extension of GRAND algorithm for finite-server systems with blocking. Assuming subcritical system load, we prove existence, uniqueness, and local stability of the large-scale system equilibrium point such that no blocking occurs. This result strongly suggests a conjecture that the steady-state blocking probability under the algorithm vanishes in the large-scale limit.

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

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

U2 - 10.1145/3003977.3003992

DO - 10.1145/3003977.3003992

M3 - Conference article

AN - SCOPUS:85011298592

VL - 44

SP - 42

EP - 44

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 2

ER -