您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (1): 17-26.doi: 10.6040/j.issn.1671-9352.4.2022.8254

•   • 上一篇    下一篇

多服务器串联排队系统中平均排队时间的预测

李绎冉1,2(),赵宁1,2,张志坚1,*()   

  1. 1. 昆明理工大学理学院, 云南 昆明 650500
    2. 昆明理工大学数据科学研究中心, 云南 昆明 650500
  • 收稿日期:2022-08-12 出版日期:2024-01-20 发布日期:2024-01-19
  • 通讯作者: 张志坚 E-mail:1639061882@qq.com;zhijian@kust.edu.cn
  • 作者简介:李绎冉(1996—), 女, 硕士研究生, 研究方向为排队论. E-mail: 1639061882@qq.com
  • 基金资助:
    2021年度工业控制技术国家重点实验室开放课题(ICT2021B51)

Prediction of average queue time in multi-server tandem queueing systems

Yiran LI1,2(),Ning ZHAO1,2,Zhijian ZHANG1,*()   

  1. 1. Faculty of Science, Kunming University of Science and Technology, Kunming 650500, Yunnan, China
    2. Data Science Research Center, Kunming University of Science and Technology, Kunming 650500, Yunnan, China
  • Received:2022-08-12 Online:2024-01-20 Published:2024-01-19
  • Contact: Zhijian ZHANG E-mail:1639061882@qq.com;zhijian@kust.edu.cn

RichHTML

3

PDF (PC)

471

摘要：

研究了具有2个服务站且缓冲区无限的多服务器串联排队系统, 利用机器学习的线性回归模型和非线性回归模型对2个站的平均排队时间进行预测, 并对各种机器学习方法的预测结果进行误差分析。数值实验结果显示, 非线性回归模型优于线性回归模型, RF、XGBoost、GBDT方法可以作为分析多服务器串联排队网络的有效手段。

关键词: 串联排队系统, 多服务器, 机器学习, 平均排队时间, 模拟

Abstract:

This paper studies a multi-server tandem queueing system with two stations and infinite buffers before each station. The average queueing time of the two stations is predicted by linear regression models and nonlinear methods of machine learning, and the error in the prediction results of various machine learning methods is analyzed. Numerical experiments show that the nonlinear method exhibits better performance than the linear regression model. Moreover, the RF, XGBoost and GBDT methods are effective to predict the average waiting time of multi-server tandem queueing networks.

Key words: tandem queueing system, multi-server, machine learning, average waiting time, simulation

中图分类号: 

  • O226

图1

2个站的多服务器串联排队系统"

表1

线性回归模型预测E(QT1)的平均相对误差"

比例 MLR RR LASSO
0.05 300.99 301.11 301.61
0.10 267.60 267.67 268.10
0.15 288.79 288.91 289.34
0.20 280.00 280.06 280.48
0.25 300.53 300.61 301.05
0.30 286.05 286.14 286.51
0.40 287.56 287.71 288.01
0.50 284.37 284.47 284.78

表2

非线性回归模型预测E(QT1)的平均相对误差"

比例 DT RF GBDT XGBoost KNN
0.05 2.29 0.45 0.78 0.56 0.46
0.10 3.12 0.42 0.79 0.66 0.42
0.15 5.03 0.48 0.85 0.65 0.48
0.20 7.44 0.46 0.81 0.63 0.48
0.25 8.81 0.46 0.80 0.66 0.46
0.30 9.21 0.47 0.80 0.62 0.46
0.40 9.93 0.49 0.79 0.66 0.46
0.50 11.34 0.56 0.84 0.74 0.50

图2

第一个站平均排队时间预测效果图"

表3

第一个站平均排队时间相对误差比较(CS12=2)"

ρ 模拟值 David Hokstad Kimura Sakasegawa RF GBDT XGBoost KNN
0.10 0.85 10.03 5.94 3.95 106.99 0.23 0.23 0.18 0.25
0.20 9.58 7.72 4.66 4.65 52.31 0.11 0.11 0.16 0.12
0.30 8.58 6.10 3.79 0.55 30.90 0.08 0.07 0.09 0.10
0.40 16.62 4.82 3.14 1.74 19.57 0.13 0.13 0.16 0.13
0.50 29.40 2.03 1.12 12.08 0.11 0.10 0.13 0.12
0.60 49.78 2.37 1.70 3.11 7.78 0.10 0.10 0.14 0.10
0.70 85.40 1.57 1.25 2.99 4.74 0.08 0.09 0.12 0.09
0.80 158.60 0.96 0.88 2.41 2.66 0.14 0.13 0.16 0.17
0.90 381.07 0.65 0.68 1.21 1.36 0.32 0.33 0.46 0.35
0.95 837.03 0.51 0.47 1.48 0.18 0.53 0.52 0.61 0.49

表4

第一个站平均排队时间相对误差比较(CS12=0.9)"

ρ 模拟值 David Hokstad Kimura Sakasegawa RF GBDT XGBoost KNN
0.10 0.58 10.76 0.97 0.78 93.48 0.15 0.15 0.12 0.15
0.20 2.39 8.04 0.72 3.31 44.48 0.09 0.09 0.10 0.09
0.30 5.68 5.89 0.67 0.23 25.27 0.09 0.09 0.17 0.09
0.40 10.91 4.22 0.46 0.03 15.38 0.07 0.06 0.19 0.06
0.50 19.07 0.36 0.16 15.38 0.09 0.09 0.15 0.09
0.60 32.16 1.51 0.30 0.20 5.66 0.05 0.05 0.06 0.06
0.70 54.83 0.74 0.12 0.32 3.32 0.10 0.11 0.08 0.11
0.80 101.34 0.23 0.01 0.33 1.76 0.08 0.08 0.10 0.08
0.90 243.36 0.19 0.15 0.04 0.52 0.26 0.26 0.36 0.24
0.95 527.32 0.01 0.06 0.16 0.35 0.51 0.51 0.61 0.47

表5

线性回归模型预测E(QT2)的平均相对误差"

比例 MLR RR LASSO
0.05 32.52 32.49 32.23
0.10 28.97 28.94 28.71
0.15 28.53 28.49 28.28
0.20 28.54 28.51 28.30
0.25 28.37 28.34 28.13
0.30 29.33 29.26 29.08
0.40 29.61 29.56 29.38
0.50 30.28 30.21 30.05

表6

非线性回归模型预测E(QT2)的平均相对误差"

比例 DT RF GBDT XGBoost KNN
0.05 5.80 1.82 1.42 1.61 3.99
0.10 6.48 1.88 1.53 1.64 4.06
0.15 6.52 2.00 1.46 1.62 4.35
0.20 6.07 2.06 1.54 1.73 4.37
0.25 6.19 2.09 1.52 1.71 4.59
0.30 6.34 2.17 1.50 1.89 4.78
0.40 6.91 2.43 1.67 2.22 5.07
0.50 7.78 2.70 1.87 2.37 5.57

图3

第二个站平均排队时间预测效果"

1 ZHU Yixin . Tandem queue with group arrivals and no intermediate buffer[J]. Queueing Systems, 1994, 17 (3/4): 403- 412.
2 GóMEZ-CORRAL A . A tandem queue with blocking and markovian arrival process[J]. Queueing Systems, 2002, 41 (4): 343- 370.
doi: 10.1023/A:1016235415066
3 VAN HOUD T B , ALFA A S . Response time in a tandem queue with blocking, Markovian arrivals and phase-type services[J]. Operations Research Letters, 2005, 33 (4): 373- 381.
doi: 10.1016/j.orl.2004.08.004
4 LIAN Zhaotong , LIU Liming . A tandem network with MAP inputs[J]. Operations Research Letters: A Journal of the Operations Research Society of America, 2008, 36 (2): 189- 195.
5 WU Kan , ZHAO Ning . Dependence among single stations in series and its applications in productivity improvement[J]. European Journal of Operational Research, 2015, 247 (1): 245- 258.
doi: 10.1016/j.ejor.2015.05.028
6 吴登磊, 赵宁, 刘文奇. 基于指标比对串联排队系统平均排队时间的近似方法[J]. 南京航空航天大学学报, 2020, 52 (4): 644- 649.
WU Denglei , ZHAO Ning , LIU Wenqi . Approximation method for average queuing time of tandem queuing system based on index comparison[J]. Journal of Nanjing University of Aeronautics and Astronautics, 2020, 52 (4): 644- 649.
7 侯佳辰, 赵宁, 刘文奇, 等. 串联排队系统平均等待时间的近似分析[J]. 山西大学学报(自然科学版), 2022, 45 (1): 41- 49.
HOU Jiachen , ZHAO Ning , LIU Wenqi , et al. Approximate analysis of average waiting time of tandem queuing system[J]. Journal of Shanxi University (Natural Science Edition), 2022, 45 (1): 41- 49.
8 KIM C S , KLIMENOK V , TARAMIN O . A tandem retrial queueing system with two Markovian flows and reservation of channels[J]. Computers & Operations Research, 2010, 37, 1238- 1246.
9 DUDIN A, DUDIN S, DUDINA O. Tandem queueing system MAP| M| N| K-N→●| M| R|∞with impatient customers as a model of remote technical support[C]//2012 2nd Baltic Congress on Future Internet Communications. Vilnius: IEEE, 2012: 134-139.
10 KIM C , DUDIN A , DUDINA O , et al. Tandem queueing system with infinite and finite intermediate buffers and generalized phase-type service time distribution[J]. European Journal of Operational Research, 2014, 235 (1): 170- 179.
doi: 10.1016/j.ejor.2013.12.012
11 LAL T S S , KRISHNAMOORTHY A , JOSHUA V C . A multiserver tandem queue with a specialist server operating with a vacation strategy[J]. Automation and Remote Control, 2019, 81 (4): 760- 773.
12 BANU P , RAJENDRAN P . Performance measures of parallel tandem open queueing network[J]. International Journal of Pervasive Computing and Communications, 2021, 17 (1): 37- 48.
doi: 10.1108/IJPCC-03-2020-0012
13 SAGIR M , SAGLAM V . Optimization and analysis of a tandem queueing system with parallel channel at second station[J]. Communication in Statistics-Theory and Methods, 2021, 51 (2): 1- 14.
14 KUMAR B K , SANKAR R , KRISHNAN R N , et al. Performance analysis of multi-processor two-stage tandem call center retrial queues with non-reliable processors[J]. Methodology and Computing in Applied Probability, 2022, 24 (1): 95- 142.
doi: 10.1007/s11009-020-09842-6
15 EFROSININ D , STEPANOVA N . Estimation of the optimal threshold policy in a queue with heterogeneous servers using a heuristic solution and artificial neural networks[J]. Mathematics, 2021, 9 (11): 1267.
doi: 10.3390/math9111267
16 TAN B , KHAYYATI S . Supervised learning based approximation method for single-server open queuing networks with correlated interarrival and service times[J]. International Journal of Production Research, 2022, 60 (22): 6822- 6847.
doi: 10.1080/00207543.2021.1887536
17 KHAYYATI S , TAN B . Supervised-learning-based approximation method for multi-server queueing networks under different service disciplines with correlated interarrival and service times[J]. International Journal of Production Research, 2022, 60 (17): 5176- 5200.
doi: 10.1080/00207543.2021.1951448
18 刘顺祥. 从零开始学Python数据分析与挖掘[M]. 北京: 清华大学出版社, 2018.
LIU Shunxiang . Learning Python data analysis and mining from scratch[M]. Beijing: Tsinghua University Press, 2018.
19 郭亚亚, 赵宁, 戴琳, 等. 对M/G/m排队系统平均等待时间估计方法的数值比较[J]. 江苏科技大学学报(自然科学版), 2017, 31 (2): 252- 258.
GUO Yaya , ZHAO Ning , DAI Lin , et al. Numerical comparison of methods for estimating average waiting time in M/G/m queuing system[J]. Journal of Jiangsu University of Science and Technology (Natural Science Edition), 2017, 31 (2): 252- 258.
20 DAVID D Y . Refining the diffusion approximation for the M/G/m queue[J]. Operations Research, 1985, 33 (6): 1266- 1277.
doi: 10.1287/opre.33.6.1266
21 HOKSTAD P . Approximations for the M/G/m queue[J]. Operations Research, 1978, 26 (3): 510- 523.
doi: 10.1287/opre.26.3.510
22 KIMURA T . Approximations for the delay probability in the M/G/s queue[J]. Mathematical and Computer Modelling, 1995, 22
23 SAKASEGAWA H . An approximation formula Lq=α.ρ3/(1-ρ[J]. Annals of the Institute of Statistical Mathematics, 1977, 29 (1): 67- 75.
doi: 10.1007/BF02532775
[1] 王晓,刘重阳,胡电中,刘刚. 1,3-丙二醇间歇发酵中的时滞最优控制[J]. 《山东大学学报(理学版)》, 2024, 59(1): 124-131, 138.
[2] 王雅迪,袁海龙. 时滞Lengyel-Epstein反应扩散系统的Hopf分支[J]. 《山东大学学报(理学版)》, 2023, 58(8): 92-103.
[3] 张杰,彭国军,杨秀璋. 基于动态API调用序列和机器学习的恶意逃避样本检测方法[J]. 《山东大学学报(理学版)》, 2022, 57(7): 85-93.
[4] 李颖,张国林. 互信息和核熵成分分析的油中溶解气体浓度建模[J]. 《山东大学学报(理学版)》, 2022, 57(7): 43-52.
[5] 步宇翔, 罗奇. 液态甲胺中双稳态溶剂化双电子:神秘的自旋交叉动力学及双电子交换[J]. 《山东大学学报(理学版)》, 2021, 56(10): 113-126.
[6] 任建龙. 利用内部温度史重构表面未知热通量[J]. 《山东大学学报(理学版)》, 2019, 54(9): 83-90.
[7] 王培名,陈兴蜀,王海舟,王文贤. 多策略融合的微博数据获取技术研究[J]. 《山东大学学报(理学版)》, 2019, 54(5): 28-36, 43.
[8] 周安民,户磊,刘露平,贾鹏,刘亮. 基于熵时间序列的恶意Office文档检测技术[J]. 《山东大学学报(理学版)》, 2019, 54(5): 1-7.
[9] 屈娟,冯玉明,李艳平,李丽. 可证明的基于扩展混沌映射的匿名多服务器身份认证协议[J]. 《山东大学学报(理学版)》, 2019, 54(5): 44-51.
[10] 何新华,万帆,胡文发,郑爱兵. 复杂风险变量随机模拟下的应急供应调度[J]. 山东大学学报（理学版）, 2018, 53(5): 1-11.
[11] 曹伟东,戴涛,于金彪,王晓宏,施安峰. 化学驱模型中压力方程的交替方向解法改进[J]. 山东大学学报（理学版）, 2018, 53(10): 88-94.
[12] 马莹,张恒,苑世领. 分子模拟研究醇醚类表面活性剂耐盐机理[J]. 山东大学学报（理学版）, 2016, 51(7): 126-130.
[13] 洪丕征,刘世荣,于浩龙,郝建. 模拟氮沉降对红椎人工幼龄林土壤微生物生物量和微生物群落结构的影响[J]. 山东大学学报（理学版）, 2016, 51(5): 18-28.
[14] 何新华,胡文发,许长延,陈继红. 考虑随机性与模糊性的应急服务供应链转运策略[J]. 山东大学学报（理学版）, 2016, 51(12): 67-77.
[15] 刘连新,何伟平,刘郁,金勇. 白藜芦醇类似物热力学性质的构效关系[J]. 山东大学学报（理学版）, 2016, 51(11): 79-87.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 曾文赋1,黄添强1,2,李凯1,余养强1,郭躬德1,2. 基于调和平均测地线核的局部线性嵌入算法[J]. J4, 2010, 45(7): 55 -59 .
[2] 易超群,李建平,朱成文. 一种基于分类精度的特征选择支持向量机[J]. J4, 2010, 45(7): 119 -121 .
[3] 孙亮吉,吉国兴 . 上三角形矩阵代数上的Jordan(α,β)-导子和广义Jordan(α,β)-导子[J]. J4, 2007, 42(10): 100 -105 .
[4] 邹国平1,马儒宁1,丁军娣2,钟宝江3. 基于显著性加权颜色和纹理的图像检索[J]. J4, 2010, 45(7): 81 -85 .
[5] 陈 莉 . 不确定奇异系统的鲁棒故障诊断滤波器设计[J]. J4, 2007, 42(7): 62 -65 .
[6] 孟祥波1,张立东1,杜子平2. 均值-方差标准下带跳的保险公司投资与再保险策略[J]. 山东大学学报（理学版）, 2014, 49(05): 36 -40 .
[7] 彭振华,徐义红*,涂相求. 近似拟不变凸集值优化问题弱有效元的最优性条件[J]. 山东大学学报（理学版）, 2014, 49(05): 41 -44 .
[8] 袁晖坪 . 行（列）对称矩阵的Schur分解和正规阵分解[J]. J4, 2007, 42(10): 123 -126 .
[9] 王廷明,黎伯堂 . 一类矩阵秩恒等式的证明[J]. J4, 2007, 42(2): 43 -45 .
[10] 付永红1 ,余眝妙2 ,唐应辉3 ,李才良4 . 两水平修理策略下的M／(Mr,Gs)／1／N／N机器维修模型稳态概率算法与性能分析[J]. J4, 2009, 44(4): 72 -78 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发