An analysis of nonstationary coupled queues

详细信息    查看全文

• 作者：Jamol Pender
• 关键词：Coupled processors ; Abandonment ; Dynamical systems ; Discontinuous coefficients ; Time ; varying rates ; Polynomial chaos ; Hermite polynomials
• 刊名：Telecommunication Systems
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：61
• 期：4
• 页码：823-838
• 全文大小：2,338 KB
• 参考文献：1.Askey, R., & Wilson, J. (1985). Some basic hypergeometric orthogonal polynomials that generalize Jacobi polynomials. Memoirs of the American Mathematical Society, 54, 1–55.CrossRef
  2.Andradottir, S., Ayhan, H., & Down, D. (2001). Server assignment policies for maximizing the steady state throughput of finite state queueing systems. Management Science, 47, 1421–1439.CrossRef
  3.Blanc, J. P. C. (1988). A numerical study of a coupled processor model. Computer Performance and Reliability, 2, 289–303.
  4.Blanc, J. P. C., Iasnogorodski, R., & Nain, Ph. (1988). Analysis of the \(M/G//1 \rightarrow / M/1\) Model. Queueing Systems, 3, 129–156.CrossRef
  5.Boxma, O., & Ivanovs, J. (2013). Two coupled Levy queues with independent input. Stochastic Systems, 3(2), 574–590.CrossRef
  6.Cameron, R., & Martin, W. (1947). The orthogonal development of non-linear functionals in series of Fourier-Hermite functionals. Annals of Mathematics, 48, 385–392.CrossRef
  7.Cohen, J. W., & Boxma, O. (2000). Boundary Value Problems in Queueing System Analysis. Oxford: Elsevier.
  8.Engblom, S., & Pender, J. (2014). Approximations for the Moments of Nonstationary and State Dependent Birth-Death Queues. Cornell University. Available at: http://​www.​columbia.​edu/​~jp3404
  9.Fayolle, G., & Iasnogorodski, R. (1979). Two Coupled Processors: The reduction to a Riemann-Hilbert Problem. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 47, 325–351.CrossRef
  10.Knessl, C., & Morrison, J. A. (2003). Heavy traffic analysis of two coupled processors. Queueing Systems, 30, 173–220.CrossRef
  11.Knessl, C. (1991). On the diffusion approximation to two parallel queues with processor sharing. IEEE Trans on Automatic Control, 30, 173–220.
  12.Konheim, A. G., Meilijson, I., & Melkman, A. (1981). Processor sharing of two parallel lines. Journal of Applied Probability, 18, 952–956.CrossRef
  13.van Leeuwaarden, J., & Resing, J. A. C. (2005). Tandem queue with coupled processors: Computational issues. Queueing Systems, 50, 29–52.CrossRef
  14.Mandelbaum, A., Massey, W. A., & Reiman, M. (1998). Strong approximations for Markovian service networks. Queueing Systems, 30, 149–201.CrossRef
  15.Massey, W. A., & Pender, J. (2011). Skewness variance approximation for dynamic rate multi-server queues with abandonment. Performance Evaluation Review, 39, 74–74.CrossRef
  16.Massey, W. A., & Pender, J. (2013). Gaussian skewness approximation for dynamic rate multi-server queues with abandonment. Queueing Systems, 75, 243–277.CrossRef
  17.Massey, W. A., & Pender, J. (2014). Approximating and Stabilizing Dynamic Rate Jackson Networks with Abandonment. Cornell University, . Available at: http://​www.​columbia.​edu/​~jp3404
  18.Osogami, T., Harcol-Balter, M., & Scheller-Wolf, A. (2003). Analysis of cycle stealing with switching cost. ACM Sigmetrics, 31, 184–195.CrossRef
  19.Ogura, H. (1972). Orthogonal functionals of the Poisson process. IEEE Transactions on Information Theory, 18, 473–481.CrossRef
  20.Pender, J. (2014). Gram Charlier expansions for time varying multiserver queues with abandonment. SIAM Journal of Applied Mathematics, 74(4), 1238–1265.CrossRef
  21.Pender, J. (2013). Laguerre Polynomial Approximations for Nonstationary Queues, Cornell University. Available at: http://​www.​columbia.​edu/​~jp3404
  22.Pender, J. (2015). Nonstationary loss queues via cumulant moment approximations, Cornell University. Probability in Engineering and Informational Sciences, 29(1), 27–49.CrossRef
  23.Pender, J. (2014). Sampling the Functional Forward Equations: Applications to Nonstationary Queues. Cornell University. Technical Report. Available at: http://​www.​columbia.​edu/​~jp3404
  24.Pender, J. (2014). Gaussian Approximations for Nonstationary Loss Networks. Cornell University. Technical Report. Available at: http://​www.​columbia.​edu/​~jp3404
  25.Resing, J., & Ormeci, L. (2003). A tandem queueing model with coupled processors. Operations Research Letters, 31, 383–389.CrossRef
  26.Stein, C. M. (1986). Approximate Computation of Expectations (Vol. 7)., Lecture Notes Monograph Series Hayward: Institute of Mathematical Statistics.
  27.Wright, P. E. (1992). Two parallel processors with coupled inputs. Advances in Applied Probability, 24, 986–1007.CrossRef
  28.Xiu, D., & Karniadakis, G. E. (2002). The Wiener-Askey polynomial chaos for stochastic differential equations. SIAM Journal on Scientific Computing, 24(2), 619–644.CrossRef
  
• 作者单位：Jamol Pender (1)
  
  1. School of Operations Research and Information Engineering, Cornell University, Ithaca, USA
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Business Information Systems
  Computer Communication Networks
  Artificial Intelligence and Robotics
  Probability Theory and Stochastic Processes
  
• 出版者：Springer Netherlands
• ISSN：1572-9451

文摘

We consider a two dimensional time varying tandem queue with coupled processors. We assume that jobs arrive to the first station as a non-homogeneous Poisson process. When each queue is non-empty, jobs are processed separately like an ordinary tandem queue. However, if one of the processors is empty, then the total service capacity is given to the other processor. This problem has been analyzed in the constant rate case by leveraging Riemann Hilbert theory and two dimensional generating functions. Since we are considering time varying arrival rates, generating functions cannot be used as easily. Thus, we choose to exploit the functional Kolmogorov forward equations (FKFE) for the two dimensional queueing process. In order to leverage the FKFE, it is necessary to approximate the queueing distribution in order to compute the relevant expectations and covariance terms. To this end, we expand our two dimensional Markovian queueing process in terms of a two dimensional polynomial chaos expansion using the Hermite polynomials as basis elements. Truncating the polynomial chaos expansion at a finite order induces an approximate distribution that is close to the original stochastic process. Using this truncated expansion as a surrogate distribution, we can accurately estimate probabilistic quantities of the two dimensional queueing process such as the mean, variance, and probability that each queue is empty.