计算机科学 ›› 2022, Vol. 49 ›› Issue (7): 304-309.doi: 10.11896/jsjkx.210500218

• 计算机网络 • 上一篇    下一篇

串联排队系统中各服务站间的关联性分析

高雅1, 赵宁2, 刘文奇2   

  1. 1 昆明理工大学理学院 昆明650500
    2 昆明理工大学数据科学研究中心 昆明650500
  • 收稿日期:2021-05-31 修回日期:2021-12-08 出版日期:2022-07-15 发布日期:2022-07-12
  • 通讯作者: 赵宁(zhaoning@kmust.edu.cn)
  • 作者简介:(751897213@qq.com)
  • 基金资助:
    国家自然科学基金(61573173)

Dependence Analysis Among Service Stations in Tandem Queueing Systems

GAO Ya1, ZHAO Ning2, LIU Wen-qi2   

  1. 1 Faculty of Science,Kunming University of Science and Technology,Kunming 650500,China
    2 Data Science Research Center,Kunming University of Science and Technology,Kunming 650500,China
  • Received:2021-05-31 Revised:2021-12-08 Online:2022-07-15 Published:2022-07-12
  • About author:GAO Ya,born in 1996,postgraduate.Her main research interests include queueing network and so on.
    ZHAO Ning,born in 1980,Ph.D,asso-ciate professor,Ph.D supervisor.Her main research interests include que-ueing theory and stochastic service systems.
  • Supported by:
    National Natural Science Foundation of China(61573173).

摘要: 串联排队系统中站与站之间存在关联性,深入分析串联排队系统中上游服务站对下游服务站的影响对研究串联排队系统性能具有重要意义。然而,串联排队系统上游服务站的输出过程通常是非更新过程,很难从理论上分析出各个站之间的关联性。文中利用指标比研究了串联排队系统各站间的关联性,通过大量的模拟实验,分析指标比与系统参数之间的关系。研究发现,上游服务站对下游服务站的平均排队时间有扩大或缩小效应。指标比是上游服务站服务时间的平方变异系数的增函数,当指标比大于1时,指标比是上游服务站与下游服务站平均服务时间之比的增函数;当指标比小于1时,指标比是上游服务站与下游服务站平均服务时间之比的减函数。因此,可以通过调整上游服务站的服务时间或平方变异系统来改变指标比,从而有效控制串联排队系统下游服务站的排队时间。

关键词: 串联排队系统, 关联性, 模拟, 排队时间, 指标比

Abstract: There is dependence among stations in tandem queueing systems.Deep analysis of the influence of the upward station on the downward station is important for studying of the performance of the tandem queueing systems.However,the departure process of the upward station is usually non-renewal process,which causes the dependence among stations is difficult to be analyzed theoretically.This paper adopts performance ratio to study the dependence among stations.By simulations,the relationship between performance ratio and system parameters are analyzed.It is found that the upward station could magnify or reduce the mean waiting time of the downward station.The performance ratio increases with the square variation coefficient of the service time at the upward station.When the performance ratio is greater than 1,it increases with the ratio of the mean service time of the upward station to the downward station.When the performance ratio is less than 1,it decreases with the ratio of the mean service time of the upward station to the downward station.The mean waiting time of the downward station could be changed by adjusting mean or square variation coefficient of the service time at the upward station.

Key words: Dependence, Performance ratio, Simulation, Tandem queueing system, Waiting time

中图分类号: 

  • O226
[1]BOXMA O,DADUNA H.The cyclic queue andthe tandemqueue[J].Queueing Systems,2014,77(3):275-295.
[2]ALFA A,LIU B.Performance analysis of a mobile communication network:the tandem case[J].Computer Communications,2004,27(3):208-221.
[3]YANG Z X,LIU W,XU D.Study of cloud service queuingmodel based on imbedding Markov chain perspective[J].Cluster Computing,2018,21(1):837-844.
[4]MARTON L.Switching control analysis and design in queuenetworks[J].Journal of the Franklin Institute,2020,357(1):19-38.
[5]HUANG D B,WANG Y F.A two-stage queueing model for coordinating the product entry-exit service of manufactures' warehouse[J].Operation Research and Mangement Science,2016,25(6):250-257.
[6]LI R,ZHAO N,LIU W Q.Optimization of buffer for series production systems with waiting timeconstraints[J].Control and Decision,2018,32(2):345-350.
[7]WANG X P,QI H,XIAO H H,et al.Co scheduling model of three gorges-gezhou dam based on series queueing network[J].Journal of Traffic and Transportation Engineering,2006,6(3):82-86.
[8]PENA L D L,FREIER M J,LOPEZ B.New queuing theory applied to port terminals and proposal for practical application in container and bulk terminals[J].Journal of Waterway,Port,Coastal and Ocean Engineering,2020,146(1):1-7.
[9]JOSEPH W J.Queuing theory and modeling emergency department resource utilization[J].Emergency Medicine Clinics of North America,2020,38(3):563-572.
[10]LUO R,SHI Y.Analysis and optimization of supermarket ope-ration mode based on queuing theory:queuingand pricing of personalized service[C]//International Conference on Management Engineering,Software Engineering and Service Sciences.2020:221-224.
[11]FRIEDMAN H.Reduction methods for tandem queueing sys-tems[J].Operations Research,1965,13(1):121-131.
[12]PINEDO M,WOLFF R.A comparison between tandem queues with dependent and independent service times[J].Operations Research,1982,30(3):464-479.
[13]GUO Z T,ZHANG W L,CHEN M Y.Network service tail latency analysis based on M/M/1 queuing model[J].Computer Science,2020,47(11):286-293.
[14]PRIYA B,RAJENDRAN P.Performance measures of parallel tandem open queueing network[J].International Journal of Pervasive Computing and Communications,2021,17(1):37-48.
[15]BLANC J,IASNOGORODSKI R,NAIN P H.Analysis of theM/G/1→./M/1 queue model[J].Queueing Systems,1988,3:129-156.
[16]WU D L,ZHAO N,LIU W Q.Mean waiting time approximation of tandem queueing systems based on performance ratio[J].Journal of Nanjing University of Aeronautics & Astronautics,2020,52(4):644-649.
[17]GUO Y J,LI Z Z.Asymptotic variability analysis for a two-stage tandem queue,part I:the functional law of the iterated logarithm[J].Journal of Mathematical Analysis and Applications,2017,450(2):1479-1509.
[18]CIVELEK I,BILLER B,WOLF A.Impact of dependence on single-server queueing systems[J].European Journal of Opera-tional Research,2021,290(3):1031-1045.
[19]WU K,ZHAO N.Dependence among single stations in series and its applications in productivity improvement[J].European Journal of Operational Research,2015,247(1):245-258.
[20]WU K,MCGINNIS L.Interpolation approximations for queuesin series[J].IISE Transactions,2013,45(3):273-290.
[1] 窦家维.
保护隐私的汉明距离与编辑距离计算及应用
Privacy-preserving Hamming and Edit Distance Computation and Applications
计算机科学, 2022, 49(9): 355-360. https://doi.org/10.11896/jsjkx.220100241
[2] 高士顺, 赵海涛, 张晓瀛, 魏急波.
一种自适应于不同场景的智能无线传播模型
Self-adaptive Intelligent Wireless Propagation Model to Different Scenarios
计算机科学, 2021, 48(7): 324-332. https://doi.org/10.11896/jsjkx.201000181
[3] 王国武, 陈元琰.
基于跳数修正和遗传模拟退火优化DV-Hop定位算法
Improvement of DV-Hop Location Algorithm Based on Hop Correction and Genetic Simulated Annealing Algorithm
计算机科学, 2021, 48(6A): 313-316. https://doi.org/10.11896/jsjkx.201000101
[4] 崔翔, 李晓雯, 陈一峯.
基于新型语言机制的异构集群应用通信优化方法
Communication Optimization Method of Heterogeneous Cluster Application Based on New Language Mechanism
计算机科学, 2020, 47(8): 17-15. https://doi.org/10.11896/jsjkx.200100124
[5] 王喆, 唐麒, 王玲, 魏急波.
一种基于模拟退火的动态部分可重构系统划分-调度联合优化算法
Joint Optimization Algorithm for Partition-Scheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing
计算机科学, 2020, 47(8): 26-31. https://doi.org/10.11896/jsjkx.200500110
[6] 程盛淦, 于浩然, 韦建文, 林新华.
基于定点压缩技术的双层粒子网格算法的设计与优化
Design and Optimization of Two-level Particle-mesh Algorithm Based on Fixed-point Compression
计算机科学, 2020, 47(8): 56-61. https://doi.org/10.11896/jsjkx.200200112
[7] 金小敏, 滑文强.
移动云计算中面向能耗优化的资源管理
Energy Optimization Oriented Resource Management in Mobile Cloud Computing
计算机科学, 2020, 47(6): 247-251. https://doi.org/10.11896/jsjkx.190400020
[8] 许子熙, 毛新军, 杨亦, 卢遥.
知识问答社区及其激励机制的建模与仿真分析
Modeling and Simulation of Q&A Community and Its Incentive Mechanism
计算机科学, 2020, 47(6): 32-37. https://doi.org/10.11896/jsjkx.191000088
[9] 谭立兴, 王福俊.
分级论辩系统的逻辑研究
On Logic of Graded Argumentation System
计算机科学, 2020, 47(5): 27-31. https://doi.org/10.11896/jsjkx.200200052
[10] 张德干, 杨鹏, 张捷, 高瑾馨, 张婷.
基于量子粒子群优化策略的车联网交通流量预测方法
New Method of Traffic Flow Forecasting of Connected Vehicles Based on Quantum Particle Swarm Optimization Strategy
计算机科学, 2020, 47(11A): 327-333. https://doi.org/10.11896/jsjkx.191200126
[11] 徐传福,王曦,刘舒,陈世钊,林玉.
基于Python的大规模高性能LBM多相流模拟
Large-scale High-performance Lattice Boltzmann Multi-phase Flow Simulations Based on Python
计算机科学, 2020, 47(1): 17-23. https://doi.org/10.11896/jsjkx.190500009
[12] 李苏婷,张严.
GSOS算子下共变-异变模拟的公理刻画
Axiomatizing Covariation-Contravariation Simulation Under GSOS Operators
计算机科学, 2020, 47(1): 51-58. https://doi.org/10.11896/jsjkx.181102026
[13] 许飞翔,叶霞,李琳琳,曹军博,王馨.
基于SA-BP算法的本体概念语义相似度综合计算
Comprehensive Calculation of Semantic Similarity of Ontology Concept Based on SA-BP Algorithm
计算机科学, 2020, 47(1): 199-204. https://doi.org/10.11896/jsjkx.181202351
[14] 王改云, 王磊杨, 路皓翔.
基于混合群智能算法优化的RSSI质心定位算法
RSSI-based Centroid Localization Algorithm Optimized by Hybrid Swarm Intelligence Algorithm
计算机科学, 2019, 46(9): 125-129. https://doi.org/10.11896/j.issn.1002-137X.2019.09.017
[15] 张焕龙, 高增, 张秀娇, 史坤峰.
混合模拟退火与蚁狮优化的图像匹配方法
Image Matching Method Combining Hybrid Simulated Annealing and Antlion Optimizer
计算机科学, 2019, 46(6): 328-333. https://doi.org/10.11896/j.issn.1002-137X.2019.06.050
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!