下载文档原格式
M/G/1型排队系统分析与仿真一、排队系统排队论(queuing theory), 或称随机服务系统理论, 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。
它是数学运筹学的分支学科。
也是研究服务系统中排队现象随机规律的学科。
广泛应用于计算机网络, 生产, 运输, 库存等各项资源共享的随机服务系统。
排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。
其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。
一般的排队过程为：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。
排队过程的一般过程可用下图表示。
我们所说的排队系统就是指图中虚线所包括的部分。
排队系统又称服务系统。
服务系统由服务机构和服务对象（顾客）构成。
服务对象到来的时刻和对他服务的时间（即占用服务系统的时间）都是随机的。
描述一个排队系统一般需要分析其三个组成部分：输入过程、排队规则和服务机构。
输入过程输入过程考察的是顾客到达服务系统的规律。
它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。
例如，在生产线上加工的零件按规定的间隔时间依次到达加工地点，定期运行的班车、班机等都属于确定型输入。
随机型的输入是指在时间t内顾客到达数n（t）服从一定的随机分布。
如服从泊松分布,则在时间t内到达n个顾客的概率为或相继到达的顾客的间隔时间T 服从负指数分布，即式中λ为单位时间顾客期望到达数，称为平均到达率；1/λ为平均间隔时间。
在排队论中，讨论的输入过程主要是随机型的。
排队规则排队规则分为等待制、损失制和混合制三种。
非强占有限优先权M/G/1排队系统>针对部分数据帧有完全优先权发送的计算机网络数据服务系统存在的网络拥塞风险问题，提出了一种非强占有限优先权M/G/1排队系统模型的方法。
该系统模型引入控制完全优先权的参数n，使得数据帧的完全优先权变成有限优先权，考虑了不同优先级队伍之间的公平性，降低了计算机网络数据服务系统拥塞的风险，使得网络系统在有限优先权下有较好的稳定性。
在模型研究中，运用全概率拆解方法获得各级队伍平均等待时间、平均逗留时间和平均队长的理论结果。
对模型采用Matlab 2010a软件实验仿真，实验得到的各级队伍平均等待时间和理论平均等待时间的平均绝对误差为0.951%。
实验中，有限优先权条件下各级顾客的平均等待时间比值显著小于完全优先权条件下各级顾客的平均等待时间比值。
实验结果表明对非强占有限优先权M/G/1排队系统模型研究的理论结果是正确的，该模型具有更稳定的系统特性。
0引言排队论是运筹学的分支，其理论得广泛应用于计算机网络数据发送服务[1]、通信系统[2]、道路交通[3]、银行[4]、地铁[5]、医院[6]等一些服务领域。
对不同领域的服务系统需要建立与之对应的排队系统模型进行研究。
当前已有很多文献对排队系统进行过深入研究。
文献[7]对强占及非强占优先权排队系统作了基础研究;文献[8]研究了非强占优先权的多服务器排队系统，将非强占优先权排队系统服务器扩充到多台经行研究;文献[9]引入绩效评价将排队系统应用在银行自动取款机(Automatic Teller Machine， ATM)系统，展示排队论在其他领域中有效的应用，此后排队论更是广泛应用于各种服务领域之中。
之后研究人员纷纷研究了多级适应性M/G/1可修排队系统[10]、M/G/1休假排队系统[11]、基于多重休假的min(N，V)策略M/G/1排队系统[12]等。
现在文献对休假排队系统和可修排队系统研究颇多，其排队系统在计算机网络[13]和通信领域[14]也有较好的应用，但对于计算机网络应用中待解决的优先权拥堵问题相关文献比较少[15]。
具有循环顾客和N策略多重休假的M/G/1重试排队系统的开题报告一、研究背景排队论是一种数学模型，可用于研究等待服务的时间、队列长度和系统利用率、效率等问题，将排队系统分为单通道排队系统和多通道排队系统。
单通道排队系统是一种只有一个服务设施的系统，即G/G/1模型，其中G表示到达过程的分布，G还表示服务时间的分布，1表示服务台的个数。
M/G/1模型是单通道排队系统中的一种，其中到达过程是泊松过程，服务时间是任意分布。
在实际生活和商业中，排队系统的运用广泛。
很多企业和服务提供者都需要通过排队系统来管理客流，优化服务体验。
例如，银行、超市、餐厅和医院等都是典型的排队系统。
通过调整服务台数量、服务时间和到达过程等因素，可以提高服务效率，减少客户等待时间和排队长度，提高客户满意度。
针对排队系统的研究，一方面是为了研究系统的性能指标，并针对实际需求提出相应的优化措施，另一方面是为了开展排队系统的理论研究，更好地理解排队系统的本质。
二、研究目的本论文将研究具有循环顾客和N策略多重休假的M/G/1重试排队系统。
循环顾客是指在同一时间内，在系统内多次接受服务的顾客。
N策略是指在服务员工作的时段内设置休息规则，即每当服务员工作了n个服务时间，他/她就会休息t个单位时间长度。
多重休假是指每个服务员可以有多个休息时间段。
本研究旨在通过建立数学模型，分析该排队系统的性能指标（如等待时间、队列长度、系统利用率等），为企业和服务提供者提供优化措施和参考建议，同时还可以丰富排队系统理论的研究。
三、研究内容本研究将分为以下几个部分：1. 排队系统的建模。
首先将建立具有循环顾客和N策略多重休假的M/G/1重试排队系统的数学模型，并简要介绍模型的基本假设和符号表示法。
2. 性能指标的计算和分析。
针对该排队系统模型，将计算并分析其关键性能指标，如等待时间、队列长度和系统利用率等，并提出相应的优化措施和建议。
3. 数值模拟和结果分析。
将针对该排队系统进行数值模拟实验，并分析不同参数设置下的结果，探讨排队系统的性能特征和规律。
带启动时间的N -策略M/G/1排队
申玉红
(德宏师范高等专科学校数学系,云南 潞西,678400)
【摘 要】本文研究了带启动时间的N -策略M/G/1排队,利用嵌入马氏链和母函数的方法,给出了此排队系统的稳态队长,并分析了系统的忙期、忙循环等性能指标。
【关键词】N -策略排队;启动时间;稳态队长;嵌入马氏链
1 引言
在许多实际系统中,为了降低成本,当服务系统中无顾客时应关闭服务设备.当有顾客到达再次工作时通常需要一个随机的启动时间[1]在经典排队系统中考虑启动时间已被研究过[2],在休假排队系统中,带启动时间的单重休假排队与多重休假排队已被研究[3,4],但在N -策略休假排队中还没有考虑过启动时间,本文研究了带启动时间的N -策略排队,给出了此排队系统的一些排队指标。
2 模型分析及相关记号
模型描述如下:带启动时间的N 策略M /G/1排队是指,顾客到达遵循参数为λ的Poisson 过程,服务时间服从一般分布,单服务台工作,一旦系统内无顾客,服务员立刻开始休假,直到到达的顾客数达到N ,服务员立刻开始一个随机长度的启动时间后,才能开始为顾客服务,直到服务台再次变成空闲。
假定到达间隔和服务时间相互独立,使用先到先服务规则。
相关记号及意义:记服务时间分布函数为B (t ),V (t )为启动时间分布函数,平均启动时间E (V )=∫∞0t dV (t ),以V 3(S ),B 3(s )分别表示V (t ),B (t )的拉普拉斯—斯蒂尔阶斯变换(简记为L S T ),μ-1和b (2)分别表示服务时间的一,二阶矩,服务强度ρ=
λμ。
3 稳态队长采用文献[1～5]中的嵌入马氏链和边际分析法求平均队长,以Q b 表示忙期开始时系统中的顾客数,则
P (Q b =j =V j -N =∫∞0
(λt )j -N (j -N )!e -λt dV (t ) j ≥N ,并有母函数
Q b (z )=∑∞j =N P (Q b -j )z j =∑∞j =N V j -N z j =z N V 3(λ(1-z ))
以L v 表示时刻t 排队系统中的顾客数,L n 是第n 个顾客完成服务离去后系统内顾客数。
{L n ,n ≥1}是队长过程的嵌入M arkov 链.在相继离去时刻系统中顾客数之间存在着关系式
收稿日期:2008-01-02
作者简介:申玉红(1982—
),女,山东菏泽人,德宏师范高等专科学校数学系硕士生,助教。
6
8 德宏师范高等专科学校学报 2008年第1期第17卷 No112008 vol 117
L n +1
=L n -1+A L n ≥1
Q b -1+A L n =0
其中A 是一个服务时间内到达的顾客数,有概率分布及母函数
a j = ∞0(λt )j j !
e -λt d (B )t j ≥0,A (z )=B 3(λ(1-z )){L n ,n ≥1}的转移矩阵P 为
P =h 0 h 1 h 2
h 3
a 0 a 1 a 2 a 3
a 0 a 1 a 2
a 0 a 1
…
…
…
这里
h j =P (Q b -1+A =j )=0 j <N -1∑j -N +2
j =1V i -1a j -N +2-i j ≥N -1
其中,h j 是忙期开始的第一个顾客离去时系统中恰有j 个顾客的概率。
当ρ<1时稳态分布存
在,记为π=(π0,π1……
),且满足πP =π,代入转移矩阵得出 πk =∑k +1
j =1πj a k +1-j k =0,1,…,N -2 πk =π0h k +∑k +1
j =1πj a k +1-j k ≥N -1于是{πk ,k ≥
0}的母函数是 L v (z )=∑N -2k =0z k
∑k +1j =1πj a k +1-j +∑∞k =N -1z k
(π0h k +∑k +1
j =1πj a k +1-j )=1
z (L v (z )-π0)B 3(λ(1-z ))+π0Q (z )B
3(λ(1-z ))由此解得
L v (z )=
π0(Q b (z -1)B 3(λ(1-z ))z -B 3(λ
(1-z ))使用正规化条件L v (1)=1,可确定π0=1-ρN +λE (V )
,代入前式得 L v (z )=1-ρN +λE (V )(Q b (z -1)B 3(λ(1-z ))z -B 3(λ
(1-z ))由E[L v ]=L v (z )′|z =1,两次使用罗比塔法则,得到
E[L v ]=ρ+λ2b (2)2(1-ρ)+N (N -1)+2N λE (V )+λ2[E (V )]22(N +λE (V ))4 忙期和忙循环
设D v 表示N -策略M/G/1排队的忙期.由于到达间隔的无后效性,由j 个顾客开始的忙期长度是经典M /G/1排队中忙期D 的j 重独立和D j ,现在忙期开始时系统中有Q b 个顾客,于是D v 有L S T ,D v 3(s )=Q b (D 3(s ))=D 3(s )N V 3(λ(1-D 3(s ))),其中D 3(s )是D 的L S T 。
平均忙期E[D v ]=
-D 3v (s )|′s =0=N +λE (V )μ(1-ρ)。
一个忙循环由空闲期,启动期和忙期合并而成.空闲长度由N 个到达间隔组成,服从Erl ang 分布,有均值N λ,平均启动时间为E (V ).所以忙循环的均值为
7
8 申玉红:带启动时间的N -策略M/G/1排队
T =N +λE (V )μ(1-ρ)+N λ+E (V )=N +λE (V )μ(1-ρ)
5 模型应用举例
1.我们考虑一个残品修理问题,假设某车间生产一种部件,出现的残品以容量N 积存,等待修理工进行修理,修理工除了修理工作之外,当没有积存的残品时,还要做另外一项辅助工作,当残品数量达到N 时,他才转入修理工作,而在修理之前有一段随机的修理准备时间,因此,对残品的修理工作是一个带启动时间的N -策略休假排队。
2.在A T M 通信网虚通道连接中,建立连接有两种不同的机制,其中转换式虚通道连接随需求的到达和离去而动态的建立和关闭.然而,过于频繁的建立连接,需要花费网络管理成本,为了适当减少重建连接的次数,要求到达缓冲器中的信元数必须达到某个值N ,服务器才予以连接,而建立连接需要一个时间,因此这是一个带启动时间的N -策略休假排队模型。
3.由于具有广阔的应用前景,近年来无线传感器网得到了广泛的关注。
在无线传感器网中,能量效率是无线传感器网设计需要考虑的一个重要性能指标。
数据块的传输是由源节点传向目的节点的,节点有两种状态,休眠状态和激活状态,当无数据块传输时其处于休眠状态,此时无能耗,当有数据块传输时处于激活状态,此时有能耗。
当有数据块到达需要传输时,节点由休眠状态转向激活状态,此时需要一个激活时间,并有一个相对大的能耗。
为了降低能耗,即减少节点转换次数,当节点处于休眠状态时,当数据块数量达到某个值N 时,节点才从休眠状态转向激活状态,直到无数据块传输时再次转向休眠。
因此这也是一个带启动时间的N -策略休假排队模型。
参考文献:
[1]田乃硕.休假随机服务系统[M ].北京:北京大学出版社,2001.
[2]唐应辉,唐小我.排队论基础与应用[M ].成都:电子科技大学出版社,2000.
[3]王铁英,韦才敏.带启动时间单重休假的M/G/1排队[J ].上海第二工业大学学报,2004,(1):14118
[4]王建军,杨德礼.带启动—关闭期的多重休假M/G/1排队[J ].燕山大学学报,2005,29(1):81121
[5]孟玉珂.排队论基础及应用[M ].上海:同济大学出版社,1989.
[6]卢锡城.A T M 网络原理和应用[M ].北京:电子工业出版社,1999.
[7]郭金淮,于宏毅,徐晓建.基于排队模型的无线传感器网性能研究[J ].计算机工程与应用,2006,08:20122.
8
8 申玉红:带启动时间的N -策略M/G/1排队 。
