A recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks

M. I. Vidalis, H. T. Papadopoulos

Research output: Contribution to journalArticle

11 Citations (Scopus)

Abstract

This paper is concerned with reliable multistation series queueing networks. Items arrive at the first station according to a Poisson distribution and an operation is performed on each item by a server at each station. Every station is allowed to have more than one server with the same characteristics. The processing times at each station are exponentially distributed. Buffers of nonidentical finite capacities are allowed between successive stations. The structure of the transition matrices of these specific type of queueing networks is examined and a recursive algorithm is developed for generating them. The transition matrices are blockstructured and very sparse. By applying the proposed algorithm the transition matrix of a K-station network can be created for any K. This process allows one to obtain the exact solution of the large sparse linear system by the use of the Gauss-Seidel method. From the solution of the linear system the throughput and other performance measures can be culculated.

Original languageEnglish
Pages (from-to)853-883
Number of pages31
JournalComputers and Operations Research
Volume28
Issue number9
DOIs
Publication statusPublished - Aug 2001
Externally publishedYes

Fingerprint

Multi-server
Queueing networks
Queueing Networks
Transition Matrix
Recursive Algorithm
Linear systems
Servers
Server
Gauss-Seidel Method
Poisson distribution
Finite Capacity
Sparse Linear Systems
Performance Measures
Buffer
Throughput
Exact Solution
Linear Systems
Series
Processing
performance

Keywords

  • Blocking phenomenon
  • Finite queues
  • Large sparse matrices
  • Markov chains
  • Multistation multiserver queueing networks
  • Numerical solution
  • Quasi-birth-death processes

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this

@article{4ff53eaa998a4b28b0e9820cacc00307,
title = "A recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks",
abstract = "This paper is concerned with reliable multistation series queueing networks. Items arrive at the first station according to a Poisson distribution and an operation is performed on each item by a server at each station. Every station is allowed to have more than one server with the same characteristics. The processing times at each station are exponentially distributed. Buffers of nonidentical finite capacities are allowed between successive stations. The structure of the transition matrices of these specific type of queueing networks is examined and a recursive algorithm is developed for generating them. The transition matrices are blockstructured and very sparse. By applying the proposed algorithm the transition matrix of a K-station network can be created for any K. This process allows one to obtain the exact solution of the large sparse linear system by the use of the Gauss-Seidel method. From the solution of the linear system the throughput and other performance measures can be culculated.",
keywords = "Blocking phenomenon, Finite queues, Large sparse matrices, Markov chains, Multistation multiserver queueing networks, Numerical solution, Quasi-birth-death processes",
author = "Vidalis, {M. I.} and Papadopoulos, {H. T.}",
year = "2001",
month = "8",
doi = "10.1016/S0305-0548(00)00012-5",
language = "English",
volume = "28",
pages = "853--883",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier",
number = "9",

}

TY - JOUR

T1 - A recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks

AU - Vidalis, M. I.

AU - Papadopoulos, H. T.

PY - 2001/8

Y1 - 2001/8

N2 - This paper is concerned with reliable multistation series queueing networks. Items arrive at the first station according to a Poisson distribution and an operation is performed on each item by a server at each station. Every station is allowed to have more than one server with the same characteristics. The processing times at each station are exponentially distributed. Buffers of nonidentical finite capacities are allowed between successive stations. The structure of the transition matrices of these specific type of queueing networks is examined and a recursive algorithm is developed for generating them. The transition matrices are blockstructured and very sparse. By applying the proposed algorithm the transition matrix of a K-station network can be created for any K. This process allows one to obtain the exact solution of the large sparse linear system by the use of the Gauss-Seidel method. From the solution of the linear system the throughput and other performance measures can be culculated.

AB - This paper is concerned with reliable multistation series queueing networks. Items arrive at the first station according to a Poisson distribution and an operation is performed on each item by a server at each station. Every station is allowed to have more than one server with the same characteristics. The processing times at each station are exponentially distributed. Buffers of nonidentical finite capacities are allowed between successive stations. The structure of the transition matrices of these specific type of queueing networks is examined and a recursive algorithm is developed for generating them. The transition matrices are blockstructured and very sparse. By applying the proposed algorithm the transition matrix of a K-station network can be created for any K. This process allows one to obtain the exact solution of the large sparse linear system by the use of the Gauss-Seidel method. From the solution of the linear system the throughput and other performance measures can be culculated.

KW - Blocking phenomenon

KW - Finite queues

KW - Large sparse matrices

KW - Markov chains

KW - Multistation multiserver queueing networks

KW - Numerical solution

KW - Quasi-birth-death processes

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

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

U2 - 10.1016/S0305-0548(00)00012-5

DO - 10.1016/S0305-0548(00)00012-5

M3 - Article

VL - 28

SP - 853

EP - 883

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 9

ER -