排队系统中的泰勒展开方法

doi:10.15960/j.cnki.issn.1007-6093.2021.03.009

运筹学学报 ›› 2021, Vol. 25 ›› Issue (3): 147-159.doi: 10.15960/j.cnki.issn.1007-6093.2021.03.009

排队系统中的泰勒展开方法

胡建强, 戴伟民^*

复旦大学管理学院, 上海 200433

收稿日期:2021-03-15 发布日期:2021-09-26
通讯作者: 戴伟民 E-mail:20110690008@fudan.edu.cn
基金资助:
国家自然科学基金（Nos.72033003，71720107003）

Taylor expansion method for queueing systems

HU Jianqiang, DAI Weimin^*

School of Management, Fudan University, Shanghai 200433, China

Received:2021-03-15 Published:2021-09-26

摘要/Abstract

摘要： 综述了排队系统中的泰勒展开方法。它由Gong和Hu在1990s首次提出，并在最近几年里有了一些新的发展。首先，通过GI/GI/1队列的简单例子介绍其基本原理；其次，展示如何应用该方法分析相关性队列和离去过程；然后，阐述如何基于该方法发展排队网络近似的高阶矩方法；最后，讨论未来的几个可能研究方向。

关键词: 泰勒展开, 排队论, 相关队列, 排队网络近似

Abstract: In this paper, we give an overview on the Taylor expansion method developed in 1990s by Gong and Hu for the study of queueing systems, which have recently been found some new promising applications. We first use the GI/GI/1 queue to illustrate how the method works, then discuss how it can be applied to correlated queues, to analyzing the departure processes of queueing systems, and to developing high-order approximations for queueing networks. We also discuss several possible future research directions in this area.

Key words: Taylor expansion, queueing systems, correlated queues, queueing network approximation

中图分类号:

O226
F224.34

胡建强, 戴伟民. 排队系统中的泰勒展开方法[J]. 运筹学学报, 2021, 25(3): 147-159.

HU Jianqiang, DAI Weimin. Taylor expansion method for queueing systems[J]. Operations Research Transactions, 2021, 25(3): 147-159.

参考文献

[1] Erlang A K. Sandsynlighedsregning og telefonsamtaler[J]. Nyt tidsskrift for Matematik, 1909, 20:33-39.
[2] Jackson J R. Jobshop-like queueing systems[J]. Management Science, 1963, 10(1):131-142.
[3] Kelly F P. Reversibility and Stochastic Networks[M]. New Jersey:Wiley, 1979.
[4] Baskett F, Chandy K M, Muntz R R, et al. Open, closed and mixed networks of queues with different classes of customers[J]. Journal of the ACM, 1975, 22(2):248-260.
[5] Hu J Q, Nananukul S, Gong W B. A new approach to (s, S) inventory systems[J]. Journal of Applied Probability, 1993, 30(4):898-912.
[6] Zhu Y, Li H. The Maclaurin expansion for a G/G/1 queue with Markov-modulated arrivals and services[J]. Queueing Systems, 1993, 14(1):125-134.
[7] Dai W, Hu J Q. On correlated queues[EB/OL]. (2021-05-29)[2021-03-05]. https://gitee.com/daiweimin/Paper/blob/master/On%20Correlated%20Queues.pdf.
[8] Hu J Q. The departure process of the GI/G/1 queue and its Maclaurin series[J]. Operations Research, 1996, 44(5):810-815.
[9] Girish M K, Hu J Q. Higher order approximations for tandem queueing networks[J]. Queueing Systems, 1996, 22(3):249-276.
[10] Girish M K, Hu J Q. Higher order approximations for the single server queue with splitting, merging and feedback[J]. European Journal of Operational Research, 2000, 124(3):447-467.
[11] Hu J Q. Analyticity of single-server queues in light traffic[J]. Queueing Systems, 1995, 19(1):63-80.
[12] Householder A S, Kantorovich L V, Krylov V I. Approximate methods of higher analysis[J]. Mathematics of Computation, 1960, 14(69):90.
[13] Gong W B, Hu J Q. The Maclaurin series for the GI/G/1 queue[J]. Journal of Applied Probability, 1992, 29(1):176-184.
[14] Girish M K, Hu J Q. An interpolation approximation for the GI/G/1 queue based on multipoint PadWapproximation[J]. Queueing Systems, 1997, 26(3):269-284.
[15] Gong W B, Nananukul S, Yan A. PadWapproximation for stochastic discrete-event systems[J]. IEEE Transactions on Automatic Control, 1995, 40(8):1349-1358.
[16] Girish M K, Hu J Q. Approximations for the departure process of the G/G/1 queue with Markov-modulated arrivals[J]. European Journal of Operational Research, 2001, 134(3):540-556.
[17] Whitt W. Performance of the queueing network analyzer[J]. Bell System Technical Journal, 1983, 62:2817-2843.
[18] Tijms H C. Stochastic Modelling and Analysis:A Computational Approach[M]. New Jersey:Wiley, 1986.
[19] Daley D J, Rolski T. Light traffic approximations in queues[J]. Mathematics of Operations Research, 1991, 16:57-71.
[20] Johnson M A, Taaffe M R. An investigation of phase-distribution moment-matching algorithms for use in queueing models[J]. Queueing Systems, 1991, 8(1):129-147.
[21] Johnson M A, Taaffe M R. A graphical investigation of error bounds for moment-based queueing approximations[J]. Queueing Systems, 1991, 8(1):295-312.
[22] Lei L, Hu J Q, Zhu C. Discrete-event stochastic systems with copula correlated input processes[J/OL]. (2021-08-17)[2021-03-05]. IISE Transactions, https://www.tandfonline.com/doi/full/10.1080/24725854.2021.1943571.
[23] Iyer S K, Manjunath D. Correlated bivariate sequences for queueing and reliability applications[J]. Communications in Statistics-Theory and Methods, 2004, 33(2):331-350.
[24] Conolly B W. The waiting time process for a certain correlated queue[J]. Operations Research, 1968, 16(5):1006-1015.
[25] Conolly B W, Choo Q H. The waiting time process for a generalized correlated queue with exponential demand and service[J]. SIAM Journal on Applied Mathematics, 1979, 37(2):263-275.
[26] Hadidi N. Queues with partial correlation[J]. SIAM Journal on Applied Mathematics, 1981, 40(3):467-475.
[27] Hadidi N. Further results on queues with partial correlation[J]. Operations Research, 1985, 33(1):203-209.
[28] Iyer S K, Manjunath D. Queues with dependency between interarrival and service times using mixtures of bivariates[J]. Stochastic Models, 2006, 22(1):3-20.
[29] Panda G, Banik A D, Chaudhry M L. Stationary distributions of the R[X]/R/1 cross-correlated queue[J]. Communications in Statistics-Theory and Methods, 2017, 46(17):8666-8689.
[30] Kim B, Kim J. The waiting time distribution for a correlated queue with exponential interarrival and service times[J]. Operations Research Letters, 2018, 46(2):268-271.
[31] Hu J Q, Zhang C, Zhu C. (s, S) inventory systems with correlated demands[J]. INFORMS Journal on Computing, 2016, 28(4):603-611.

排队系统中的泰勒展开方法

Taylor expansion method for queueing systems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	王慧宁, 徐秀丽. 基于PH服务的工作休假排队的流体模型[J]. 运筹学学报, 2019, 23(2): 57-66.
[2]	张宏波. 带有Bernoulli控制策略的M/M/1多重休假排队模型[J]. 运筹学学报, 2013, 17(3): 93-100.
[3]	张宏波, 封平华. 对 M/T-SPH/1 排队平稳队长的分析[J]. 运筹学学报, 2011, 15(2): 110-118.
[4]	张淞钛, 徐秀丽. 具有两类故障特性的M/M/1排队系统均衡分析[J]. 运筹学学报, 2019, 23(4): 131-142.