排队论基础及应用.ppt

《排队论基础及应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、排队论及其应用Lecture4复杂马尔科夫排队模型中国科学技术大学计算机科学与技术学院田野1成批到达排队模型M[x]/M/1类似M/M/1模型，但是每次不是到达一个客户，而是到达数量为X的一批客户。X为随机变量，可以为任何正整数。Pr[到达批次大小X=x]=cx如果大小为x的客户批次到达速率为λx，则有cx=λx/λ，λ为批次到达速率M/M/1可以被视为M[1]/M/12系统里有n个客户（n>0），到达一批客户，发生状态迁移nn+x，x是到达批次的大小，批次到达速率为λ系统里有n个客户（n>0），服务器完成一个客户服务，发生状态迁移，nn-1状态n-x到达一批数目为x的客户，发生

2、状态迁移n-xn，批次到达速率为λx状态n+1完成一个客户服务，发生状态迁移n+1n3M[x]/M/1的CK等式M[x]/M/1的CK等式不是简单的生灭过程，不能使用生灭过程稳态解。4运用生成函数求解考虑两个序列{pn}：系统中有n个客户的概率序列{cn}：一次到达n个客户的概率序列{pn}和{cn}的生成函数分别是5CK等式两边乘上zn再相加，得到6这样上式变为求解，得到定义，即一次到达不多于x个客户的概率，并且7序列{}的生成函数并且因此，是序列{}的生成函数根据生成函数的性质8对P(z)，当z=1，对P’(z)，当z=1，9平均队列长度，客户在系统中平均耗时，平均等待时间1

3、0两个特例特例1：每批到达K个客户11特例2：客户批次大小服从几何分布生成函数12所以13例子：产品修复某工厂流水线作业，一名工人负责修复有瑕疵的产品。每件产品都有一处或者两处瑕疵。有一处瑕疵的产品的到达速率为λ1=1件/小时，有两处瑕疵的产品的到达速率为λ2=2件/小时，均为泊松到达。工人修复一处瑕疵平均用时10分钟，修复时间服从指数分布。每处瑕疵等待并被修复造成每小时利润损失为C1，工人每小时工资C2，修复瑕疵的代价是多少？如果安排另外一个工人专门修复有两处瑕疵的产品，代价如何？何种方案代价最小？14M[x]/M/1模型，客户=瑕疵，客户批次=产品，服务器=工人1516安排另

4、外一个工人，变成一个M/M/1模型和一个M[x]/M/1模型对M/M/1对M[x]/M/117成批服务排队模型M/M[Y]/1模型描述：单服务器单队列；服务器FCFS；无限等待位；服务器一次服务K个客户，K个客户同时完成服务；如果服务器空闲但是少于K个客户等待，服务器开始服务；服务过程中新到达的客户可以立即得到服务，直到服务器同时服务K个客户。18当系统中有n-1个客户，n>0，到达一个客户，发生状态迁移n-1n当系统中有n+K个客户，n>0，完成一批客户服务，发生状态迁移n+Kn，由于有多于K个的客户在系统中，所以完成服务个户数的必为K个对于n=0，到达一个客户，发生状态迁移0

5、1，状态1,2,...,K完成服务一批客户，发生状态迁移10,20,...,K0稳态平衡方程19解M/M[Y]/1得到这里r0是以下方程在(0,1)范围内的唯一解对比M/M/1，把ρ替换为r0。参考M/M/1的解，有20M/M[Y]/1的另一种情况考虑另外一种情况，服务器每次只服务K个客户，如果没有K个客户，服务器等待，直到队列里累积了K个客户当系统中有n-1个客户，n>0，到达一个客户，发生状态迁移n-1n当系统中有n+K个客户，n>0，完成一批客户服务，发生状态迁移n+Kn对于n=0，到达一个客户，发生状态迁移01，状态1,2,...,K-1时，不完成任何客户服务2

6、1稳态平衡方程22稳态平衡方程的第一个等式和上一种M/M[Y]/1模型的方程一样，所以对n≥K，解的形式为由于对于n

7、angDistribution）时的排队系统A.K.Erlang，丹麦数学家，排队论奠基人29爱尔兰分布（ErlangDistribution）一个随机变量T，服从Erlang分布，其概率密度函数为Erlang分布的均值、方差对给定的k，Erlang分布被称为k型Erlang分布或者Ekk=1，指数分布k=∞，常数1/μ30Erlang分布和指数分布的关系k个独立同分布（i.i.d）的指数分布随机变量之和为k型Erlang分布。如果指数分布变量均值1/kμ