A comparative analysis of the successive lumping and the lattice path counting algorithms

DOI10.1017/JPR.2015.12zbMATH Open1343.60109arXiv1507.05301OpenAlexW2187915630MaRDI QIDQ2804417FDOQ2804417

Authors: Michael N. Katehakis, Laurens C. Smit, Floske M. Spieksma 

Publication date: 29 April 2016

Published in: Journal of Applied Probability (Search for Journal in Brave)

Abstract: This article provides a comparison of the successive lumping (SL) methodology with the popular lattice path counting algorithm in obtaining rate matrices for queueing models, satisfying the quasi birth and death structure. The two methodologies are compared both in terms of applicability requirements and numerical complexity by analyzing their performance for the same classical queueing models. The main findings are: i) When both methods are applicable SL based algorithms outperform the lattice path counting algorithm (LPCA). ii) There are important classes of problems (e.g., models with (level) non-homogenous rates or with finite state spaces) for which the SL methodology is applicable and for which the LPCA cannot be used. iii) Another main advantage of successive lumping algorithms over LPCAs is that the former includes a method to compute the steady state distribution using this rate matrix.

Full work available at URL: https://arxiv.org/abs/1507.05301

Recommendations

• A SUCCESSIVE LUMPING PROCEDURE FOR A CLASS OF MARKOV CHAINS
• On lattice path counting and the random product representation, with applications to the \(E_r/M/1\) queue and the \(M/E_r/1\) queue
• A Comparison of Alternative Approaches for Numerical Solutions of GI/PH/1 Queues
• An Analysis of the E_l/E_k/1 Queueing System by Restricted Minimal Lattice Paths
• Waiting times in classical priority queues via elementary lattice path counting

zbMATH Keywords

queueingMarkov chainssteady-state analysislattice path counting algorithmquasi birth-and-death processessuccessive lumping

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Title not available (Why is that?)
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• Semi-explicit solutions for M/PH/1-like queueing systems
• Updating the Inverse of a Matrix
• Multiplying matrices faster than coppersmith-winograd
• The combinatorics of birth-death processes and applications to queues
• Title not available (Why is that?)
• The shorter queue polling model
• Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes
• Algebraic methods for Toeplitz-like matrices and operators
• Queueing Analysis of a Jockeying Model
• On computing optimal \((Q,r)\) replenishment policies under quantity discounts
• Title not available (Why is that?)
• Erlang arrivals joining the shorter queue
• On the Maintenance of Systems Composed of Highly Reliable Components
• Title not available (Why is that?)
• Synchronized reneging in queueing systems with vacations
• The formal theory of birth-and-death processes, lattice path combinatorics and continued fractions
• Triangular \(M/G/1\)-type and tree-like quasi-birth-death Markov chains
• Quasi-Birth-and-Death Processes with an Explicit Rate Matrix
• A SUCCESSIVE LUMPING PROCEDURE FOR A CLASS OF MARKOV CHAINS
• DES AND RES PROCESSES AND THEIR EXPLICIT SOLUTIONS
• A Queueing Model to Analyze the Value of Centralized Inventory Information
• Dynamic Repair Allocation for a k−Out−of−n System Maintained by Distinguishable Repairmen
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quasi-Birth-and-Death Processes, Lattice Path Counting, and Hypergeometric Functions
• Admission and Termination Control of a Two Class Loss System

Cited In (4)

• Matrix geometric approach for random walks: Stability condition and equilibrium distribution
• Time-dependent analysis of an \(\mathrm{M}/\mathrm{M}/c\) preemptive priority system with two priority classes
• Inventory systems with stochastic and batch demand: computational approaches
• Parallel computing for Markov chains with islands and ports

Uses Software

• SMCSolver

This page was built for publication: A comparative analysis of the successive lumping and the lattice path counting algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804417)