1st International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Fast solvers for queueing systems with negative customers

  • @INPROCEEDINGS{10.1145/1190095.1190111,
        author={You-Wei  Wen and Wai-Ki  Ching and Michael K.  Ng},
        title={Fast solvers for queueing systems with negative customers},
        proceedings={1st International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ACM},
        proceedings_a={VALUETOOLS},
        year={2012},
        month={4},
        keywords={Queueing Systems Negative Customer Gohberg-Semencul Formula Preconditioned Conjugate Gradient method Preconditioners.},
        doi={10.1145/1190095.1190111}
    }
    
  • You-Wei Wen
    Wai-Ki Ching
    Michael K. Ng
    Year: 2012
    Fast solvers for queueing systems with negative customers
    VALUETOOLS
    ACM
    DOI: 10.1145/1190095.1190111
You-Wei Wen1,*, Wai-Ki Ching2,*, Michael K. Ng3,*
  • 1: Department of Mathematics, The University of Hong Kong, Pokfulam Road, Hong Kong.
  • 2: Advanced Modeling and Applied Computing Laboratory, Department of Mathematics, The University of Hong Kong, Pokfulam Road, Hong Kong.
  • 3: Department of Mathematics, The Hong Kong Baptist University, Kowloon Tong, Kowloon, Hong Kong.
*Contact email: wenyouwei@gmail.com, wching@hkusua.hku.hk, mng@math.hkbu.edu.hk

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.