Design heuristic for parallel many server systems

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We study a parallel queueing system with multiple types of servers and customers. A bipartite graph describes which pairs of customer-server types are compatible. We consider the service policy that always assigns servers to the first, longest waiting compatible customer, and that always assigns customers to the longest idle compatible server if on arrival multiple compatible servers are available. For a general renewal stream of arriving customers, general service time distributions that depend both on customer and on server types, and general customer patience distributions, the behavior of such systems is very complicated. Key quantities for their performance are the matching rates, the fraction of services for each pair of compatible customer-server. Calculation of these matching rates in general is intractable, it depends on the entire shape of service time distributions. We suggest through a heuristic argument that if the number of servers becomes large, the matching rates are well approximated by matching rates calculated from the tractable bipartite infinite matching model. We present simulation evidence to support this heuristic argument, and show how this can be used to design systems with desired performance requirements.

LanguageEnglish
Pages259-277
JournalEuropean Journal of Operational Research
Volume273
Issue number1
DOIs
StatePublished - 1 Jan 2019

Fingerprint

Servers
Server
Customers
Heuristics
Assign
Model Matching
Design
Renewal
Parallel Systems
Queueing System
Bipartite Graph
System Design
Computer systems
Entire
Requirements
Simulation

Keywords

  • Matching rates
  • Multi-type customers and servers
  • Parallel service systems
  • Queueing
  • Resource pooling

Cite this

@article{11fd8ca87287424e85ca032d6641cb62,
title = "Design heuristic for parallel many server systems",
abstract = "We study a parallel queueing system with multiple types of servers and customers. A bipartite graph describes which pairs of customer-server types are compatible. We consider the service policy that always assigns servers to the first, longest waiting compatible customer, and that always assigns customers to the longest idle compatible server if on arrival multiple compatible servers are available. For a general renewal stream of arriving customers, general service time distributions that depend both on customer and on server types, and general customer patience distributions, the behavior of such systems is very complicated. Key quantities for their performance are the matching rates, the fraction of services for each pair of compatible customer-server. Calculation of these matching rates in general is intractable, it depends on the entire shape of service time distributions. We suggest through a heuristic argument that if the number of servers becomes large, the matching rates are well approximated by matching rates calculated from the tractable bipartite infinite matching model. We present simulation evidence to support this heuristic argument, and show how this can be used to design systems with desired performance requirements.",
keywords = "Matching rates, Multi-type customers and servers, Parallel service systems, Queueing, Resource pooling",
author = "Adan, {Ivo J.B.F.} and Boon, {Marko A.A.} and Gideon Weiss",
year = "2019",
month = "1",
day = "1",
doi = "10.1016/j.ejor.2018.08.042",
language = "English",
volume = "273",
pages = "259--277",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

Design heuristic for parallel many server systems. / Adan, Ivo J.B.F.; Boon, Marko A.A.; Weiss, Gideon.

In: European Journal of Operational Research, Vol. 273, No. 1, 01.01.2019, p. 259-277.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Design heuristic for parallel many server systems

AU - Adan,Ivo J.B.F.

AU - Boon,Marko A.A.

AU - Weiss,Gideon

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We study a parallel queueing system with multiple types of servers and customers. A bipartite graph describes which pairs of customer-server types are compatible. We consider the service policy that always assigns servers to the first, longest waiting compatible customer, and that always assigns customers to the longest idle compatible server if on arrival multiple compatible servers are available. For a general renewal stream of arriving customers, general service time distributions that depend both on customer and on server types, and general customer patience distributions, the behavior of such systems is very complicated. Key quantities for their performance are the matching rates, the fraction of services for each pair of compatible customer-server. Calculation of these matching rates in general is intractable, it depends on the entire shape of service time distributions. We suggest through a heuristic argument that if the number of servers becomes large, the matching rates are well approximated by matching rates calculated from the tractable bipartite infinite matching model. We present simulation evidence to support this heuristic argument, and show how this can be used to design systems with desired performance requirements.

AB - We study a parallel queueing system with multiple types of servers and customers. A bipartite graph describes which pairs of customer-server types are compatible. We consider the service policy that always assigns servers to the first, longest waiting compatible customer, and that always assigns customers to the longest idle compatible server if on arrival multiple compatible servers are available. For a general renewal stream of arriving customers, general service time distributions that depend both on customer and on server types, and general customer patience distributions, the behavior of such systems is very complicated. Key quantities for their performance are the matching rates, the fraction of services for each pair of compatible customer-server. Calculation of these matching rates in general is intractable, it depends on the entire shape of service time distributions. We suggest through a heuristic argument that if the number of servers becomes large, the matching rates are well approximated by matching rates calculated from the tractable bipartite infinite matching model. We present simulation evidence to support this heuristic argument, and show how this can be used to design systems with desired performance requirements.

KW - Matching rates

KW - Multi-type customers and servers

KW - Parallel service systems

KW - Queueing

KW - Resource pooling

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

U2 - 10.1016/j.ejor.2018.08.042

DO - 10.1016/j.ejor.2018.08.042

M3 - Article

VL - 273

SP - 259

EP - 277

JO - European Journal of Operational Research

T2 - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -