More Web Proxy on the site http://driver.im/

Article

Fast solvers for queueing systems with negative customers

Authors:

Michael K. NgAuthors Info & Claims

valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodolgies and tools

Pages 13 - es

https://doi.org/10.1145/1190095.1190111

Published: 11 October 2006 Publication History

Abstract

In this paper, we are interested in solving queueing systems having Poisson batch arrivals, exponential servers and negative customers. Preconditioned Conjugate Gradient (PCG) method is applied to solving the steady-state probability distribution of the queueing system. Preconditioners are constructed by exploiting near-Toeplitz structure of the generator matrix and the Gohberg-Semumcul formula. We proved that the preconditioned system has singular values clustered around one. Therefore Conjugate Gradient (CG) methods when applied to solving the preconditioned system, we expect fast convergence rate. Numerical examples are given to demonstrate our claim.

References

[1]

A. Ben-Artzi and T. Shalom, On Inversion of Toeplitz and Close to Toeplitz Matrices, Linear Algebra Appl., 75 (1986) 173--192.

[2]

R. Chan, D. Potts and G. Steidl, Preconditioners for non-Hermitian Toeplitz systems, Numerical Linear Algebra with Applications, 8(2001)83--98.

[3]

W. Ching, Iterative Methods for Queueing Systems with Batch Arrivals and Negative Customers, BIT, 43 (2003) 285--296.

[4]

W. Ching and M. Ng, Markov Chains: Models, Algorithms and Applications. International Series on Operations Research and Management Science. Springer: New York, (2006).

Digital Library

[5]

E. Gelenbe, Random Neural Networks with Positive and Negative Signals and Product Solution, Neural Computation. 1 (1989), pp. 501--510.

Digital Library

[6]

P. Glynn, and K. Sigman, Queues with Negative Arrivals, J. Appl. Prob. 28 (1991), pp. 245--250.

[7]

E. Gelenbe, Product Form Networks with Negative and Positive Customers, J. Appl. Prob. 28 (1991), pp. 656--663.

[8]

I. Gohberg and A. Semencul, On the Inversion of Finite Toeplitz Matrices and Their Continuous Analogs, Mat. Issled., 2 (1972) 201--233.

[9]

P. Harrison, Reliability modeling Using G-queue, Euro. J. Oper. Res. 126 (2000), pp. 273--387.

[10]

G. Heinig, On the Reconstruction of Toeplitz Matrix Inverses from Columns, Linear Algebra Appl., 350 (2002) 199--212.

[11]

S. Jaffard, Propriétés des matrices "bien localisées" près de leur diagonale et quelques applications, Ann. Inst. H. Poincaré Anal. Non Linéaire, 7 (1990) 461--476.

[12]

G. Labahn and T. Shalom, Inversion of Toeplitz Matrices with only Two Standard Equations, Linear Algebra Appl., 175 (1992) 143--158.

[13]

F. Lin and W. Ching, Inverse Toeplitz preconditioners for Hermitian Toeplitz systems, Numerical Linear Algebra with Applications, 12(2005)221--229.

[14]

T. Strohmer, Four Short Stories about Toeplitz Matrix Calculations, Linear Algebra Appl., 343--344 (2002) 321--344.

[15]

M. Ng, K. Rost and Y. Wen, On Inversion of Toeplitz Matrices, Linear Algebra Appl., 348 (2002) 145--151.

[16]

R. Varga, Matrix Iterative Analysis, Prentice-Hall, New Jersey, 1963.

[17]

Y. Wen, M. Ng, W. Ching and H. Liu, A note on the Stability of Toeplitz Matrix Inversion Formulas, Appl. Math. Letters 17 (2004) 903--907.

[18]

Y. Wen, W. Ching and M. Ng, Approximate Inverse-Free Preconditioners for Toeplitz Matrices, submitted.

Cited By

Do T(2011)Bibliography on G-networks, negative customers and applicationsMathematical and Computer Modelling: An International Journal10.1016/j.mcm.2010.08.00653:1-2(205-212)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1016/j.mcm.2010.08.006
Wen YChing WNg M(2011)Approximate inverse-free preconditioners for Toeplitz matricesApplied Mathematics and Computation10.1016/j.amc.2011.01.030217:16(6856-6867)Online publication date: Apr-2011
https://doi.org/10.1016/j.amc.2011.01.030

Index Terms

Fast solvers for queueing systems with negative customers

Recommendations

Exponential queuing system with negative customers and bunker for ousted customers
Abstract
Consideration was given to the queuing system with Poisson flows of incoming positive and negative customers. For the positive customers, there is an infinite-capacity buffer. The arriving negative customer knocks out a positive customer queued in ...
A multi-server perishable inventory system with negative customer

Research highlights Studied a multi-server Inventory System with Service Facility. Derived the stability condition for the system and the solution is expressed in matrix geometric solution. Derived various system performance measures in steady state and ...
A discrete-time on-off source queueing system with negative customers

This paper studies a discrete-time single-server infinite-capacity queueing system with correlated arrivals, geometrically distributed service times and negative customers. Positive customers are generated by a Bernoulli bursty source, with geometrically ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodolgies and tools

October 2006

638 pages

ISBN:1595935045

DOI:10.1145/1190095

General Chairs:
Luciano Lenzini
University of Pisa, Italy
,
Rene Cruz
UCSD, US

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 90 of 196 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
128
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Do T(2011)Bibliography on G-networks, negative customers and applicationsMathematical and Computer Modelling: An International Journal10.1016/j.mcm.2010.08.00653:1-2(205-212)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1016/j.mcm.2010.08.006
Wen YChing WNg M(2011)Approximate inverse-free preconditioners for Toeplitz matricesApplied Mathematics and Computation10.1016/j.amc.2011.01.030217:16(6856-6867)Online publication date: Apr-2011
https://doi.org/10.1016/j.amc.2011.01.030

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents