JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (1): 17-26.doi: 10.6040/j.issn.1671-9352.4.2022.8254

Previous Articles     Next Articles

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

2

PDF (PC)

202

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

CLC Number: 

  • O226

Fig.1

Multi-server tandem queueing system with two stations"

Table 1

The mean relative error of predicting E(QT1) by linear regression model %"

比例 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

Table 2

The mean relative error of predicting E(QT1) by nonlinear method %"

比例 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

Fig.2

Prediction graph of the average queueing time of the first station"

Table 3

The comparison of relative error of the mean queuing time at the first station (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

Table 4

The comparison of relative error of the mean queuing time at the first station (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

Table 5

The mean relative error of predicting E(QT2) by linear regression model %"

比例 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

Table 6

The mean relative error of predicting E(QT2) by nonlinear method %"

比例 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

Fig.3

Prediction graph of the average queueing time of the second station"

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] Yadi WANG,Hailong YUAN. Hopf bifurcation analysis in the Lengyel-Epstein reaction diffusion system with time delay [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(8): 92-103.
[2] ZHANG Jie, PENG Guo-jun, YANG Xiu-zhang. Malicious evasion sample detection based on dynamic API call sequence and machine learning [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(7): 85-93.
[3] LI Ying, ZHANG Guo-lin. Modeling for dissolved gases concentration based on mutual information and kernel entropy component analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(7): 43-52.
[4] BU Yuxiang, LUO Qi. Bistable solvated dielectron in liquid methylamine: intriguing spin crossover dynamics and dielectron exchanges [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(10): 113-126.
[5] REN Jian-long. Reconstruction of unknown surface heat flux from an internal temperature history [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(9): 83-90.
[6] An-min ZHOU,Lei HU,Lu-ping LIU,Peng JIA,Liang LIU. Malicious Office document detection technology based on entropy time series [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(5): 1-7.
[7] Juan QU,Yu-ming FENG,Yan-ping LI,Li LI. An anonymous and provably remote user authentication protocol using extended chaotic maps for multi-server system [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(5): 44-51.
[8] HE Xin-hua, WAN Fan, HU Wen-fa, ZHENG Ai-bing. Emergency supply scheduling optimization under stochastic simulation of complex risk variables [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(5): 1-11.
[9] CAO Wei-dong, DAI Tao, YU Jin-biao, WANG Xiao-hong, SHI An-feng. Improvement on the solution of pressure equation based on alternating direction in chemical flooding model [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 88-94.
[10] DAI Zhong-hua, FEI Yong-kang, ZHAO Bo, WANG Ting. Research on the localization of firmware vulnerability based on stain tracking [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(9): 41-46.
[11] . Salt-tolerant mechanism of alcohol ether carboxylate investigated by molecular dynamics simulation [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(7): 126-130.
[12] HE Xin-hua, HU Wen-fa, XU Chang-yan, CHEN Ji-hong. Collaborative transshipment strategy of service supply chain for emergencies based on stochastic and fuzzy simulation [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(12): 67-77.
[13] LIU Lian-xin, HE Wei-ping, LIU Yu, JIN Yong. QSPR study on thermodynamic properties of resveratrol analogues [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(11): 79-87.
[14] CHEN Li, YANG Rui, MA Zhan-you. Performance analysis of Geom/G/1 queue with multiple vacations and set-up/close down period based on simulation experiment [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(08): 46-50.
[15] YANG Wen-bin, LI Yan-ling. Dynamics research in a predator-prey system with a nonlinear growth rate [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(03): 80-87.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] ZENG Weng-fu1, HUANG Tian-qiang1,2, LI Kai1, YU YANG-qiang1, GUO Gong-de1,2. A local linear emedding agorithm based on harmonicmean geodesic kernel[J]. J4, 2010, 45(7): 55 -59 .
[2] YI Chao-qun, LI Jian-ping, ZHU Cheng-wen. A kind of feature selection based on classification accuracy of SVM[J]. J4, 2010, 45(7): 119 -121 .
[3] SUN Liang-ji,JI Guo-xing . Jordan(α,β)-derivations and generalized Jordan(α,β)-derivations on upper triangular matrix algebras[J]. J4, 2007, 42(10): 100 -105 .
[4] ZOU Guo-ping1, MA Ru-ning1, DING Jun-di2, ZHONG Bao-jiang3. Image retrieval based on saliency weighted color and texture[J]. J4, 2010, 45(7): 81 -85 .
[5] CHEN Li . The robust fault diagnosis filter design for uncertain singular systems[J]. J4, 2007, 42(7): 62 -65 .
[6] MENG Xiang-bo1, ZHANG Li-dong1, DU Zi-ping2. Investment and reinsurance strategy for insurers under #br# mean-variance criterion with jumps#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(05): 36 -40 .
[7] PENG Zhen-hua, XU Yi-hong*, TU Xiang-qiu. Optimality conditions for weakly efficient elements of nearly preinvex set-valued optimizaton#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(05): 41 -44 .
[8] YUAN Hun-ping . Schur factorization and normal matrices factorization of row (column) symmetric matrices[J]. J4, 2007, 42(10): 123 -126 .
[9] WANG Ting-ming,LI Bo-tang . Proof of a class of matrix rank identities[J]. J4, 2007, 42(2): 43 -45 .
[10] FU Yonghong 1, YU Miaomiao 2*, TANG Yinghui 3, LI Cailiang 4. [J]. J4, 2009, 44(4): 72 -78 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd