Analysis of transient queues with semidefinite optimization
type: Item
instance of: scholarly article
title: Analysis of transient queues with semidefinite optimization
zbMATH Open document ID: 1278.60140
author: Takayuki Osogami
author: Rudy Raymond
published in: Queueing Systems
publication date: 2013-02-18T00:00:00Z
review text: Upper bounds on the tail distribution of the waiting time \(W_n\) of customer \(n\) in the \(\mathrm{GI}/\mathrm{GI}/1\) queueing system are derived, using a limited number of the moments of the service times and that of the interarrival times. In particular, it is proved (using two first moments) that the asymptotics of the probability \(\operatorname{P}(W_n>y)\) as \(y \to \infty\) is proportional to \(n\) and \(1/y^2\). The upper bound on the tail probability of the maximum waiting time in the first busy period depending on the initial state is obtained. This then is used to derive an upper bound on the expected maximum of the waiting time during the first busy period. This bound is agreed with the well-known Kingman's bound. The main contribution of the paper is the application of the semidefinite programming approach, which is well-know technique in the area of optimization. Thus, this approach is an alternative to the known methods for deriving the bounds, such as Markov inequality, large deviations, Wald martingales. Some illustrative numerical results are given as well.
Mathematics Subject Classification ID: 60K25
Mathematics Subject Classification ID: 90B22
zbMATH DE Number: 6136950
zbMATH Keywords: semidefinite programming
zbMATH Keywords: duality
zbMATH Keywords: \(\mathrm{G}/\mathrm{G}/1\) system
zbMATH Keywords: transient
zbMATH Keywords: bounds
zbMATH Keywords: moments
zbMATH Keywords: occupation measure
reviewed by: Evsei Morozov
MaRDI profile type: Publication
full work available at URL: s11134-012-9309-7
OpenAlex ID: W2074256831
cites work: Q4264741
cites work: A semidefinite programming approach to the optimal control of a single server queueing system with imposed second moment constraints
cites work: Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
cites work: A semidefinite optimization approach to the steady-state analysis of queueing systems
cites work: Optimization of multiclass queueing networks with changeover times via the achievable region approach. I: The single-station case
cites work: Optimization of multiclass queueing networks with changeover times via the achievable region approach. II: The multi-station case
cites work: Optimal Inequalities in Probability Theory: A Convex Optimization Approach
cites work: Inequalities for moments of tails of random variables, with a queueing application
cites work: Q4886156
cites work: Q4438206
cites work: Computing Moments of the Exit Time Distribution for Markov Processes by Linear Programming
cites work: Some inequalities for the queue GI/G/1
cites work: Q4134686
cites work: Q3093181
cites work: SDP vs. LP Relaxations for the Moment Approach in Some Performance Evaluation Problems
cites work: PRICING A CLASS OF EXOTIC OPTIONS VIA MOMENTS AND SDP RELAXATIONS
cites work: Exponential bounds with applications to call admission
DOI: 10.1007/S11134-012-9309-7
Recommended article: A semidefinite optimization approach to the steady-state analysis of queueing systems
Recommended article: Erratum to: ``Analysis of transient queues with semidefinite optimization''
Recommended article: Semi-Analytical Methods for Complex Optimization of Non-Markov Queueing Networks
Recommended article: Transient analysis of queues with heterogeneous arrivals
Recommended article: Transient analytical solution of M/D/1/N queues
Recommended article: Transient queueing analysis
Recommended article: Research and optimization of semi-Markov queueing models
Recommended article: Optimization of Queues Using an Infinitesimal Perturbation Analysis-Based Stochastic Algorithm with General Update Times
Recommended article: An optimization problem in queueing theory and a numerical solution method
description: scientific article; zbMATH DE number 6136950