排队论基础及应用

1排队论及其应用Lecture4复杂马尔科夫排队模型中国科学技术大学计算机科学与技术学院田野2成批到达排队模型M[x]/M/1类似M/M/1模型，但是每次不是到达一个客户，而是到达数量为X的一批客户。X为随机变量，可以为任何正整数。Pr[到达批次大小X=x]=cx如果大小为x的客户批次到达速率为λx，则有cx=λx/λ，λ为批次到达速率M/M/1可以被视为M[1]/M/13系统里有n个客户（n0），到达一批客户，发生状态迁移nn+x，x是到达批次的大小，批次到达速率为λ系统里有n个客户（n0），服务器完成一个客户服务，发生状态迁移，nn-1状态n-x到达一批数目为x的客户，发生状态迁移n-xn，批次到达速率为λx状态n+1完成一个客户服务，发生状态迁移n+1nM[x]/M/1的CK等式M[x]/M/1的CK等式不是简单的生灭过程，不能使用生灭过程稳态解。41101()(1)nnnnkkkpppcnpp5运用生成函数求解考虑两个序列{pn}：系统中有n个客户的概率序列{cn}：一次到达n个客户的概率序列{pn}和{cn}的生成函数分别是0()nnnPzpz1()nnnCzczCK等式两边乘上zn再相加，得到601111nnnnnnnnnkknnnnkpzpzpzpczz111()()nnkkknnnkknkpcpczCzPz是系统大小和批次大小这两个随机变量之和的概率,根据生成函数性质，1101()(1)nnnnkkkpppcnpp这样上式变为求解，得到定义，即一次到达不多于x个客户的概率，并且700()(())(())()()PzPzpPzpCzPzz00(1)()(1)[1()]1()1(),()1pzpPzzzCzrzCzCzrCzz其中1[]xxiiCPXxc1xxCC8序列{}的生成函数并且因此，是序列{}的生成函数根据生成函数的性质1()()1CzCzz(1)[],'(1)[(1)]/2CEXCEXX即平均均值大小xC111111()11xxxixiixiiixxiixiiCzCzczczzczzz1111()1xxxxxxxxCzCzzCzz[]xCPXx9对P(z)，当z=1，对P’(z)，当z=1，00(1)1,(1),1(1)nnpPpPrC同时所以01[]1prEX0[(1)'(1)]'(1),'(1),1(1)nnrCCPnpLPrC同时所以22[[][]][]2(1)2(1)rEXEXrEXL[]1rEX是稳态存在的必要和充分条件[][]EXrEX平均队列长度，客户在系统中平均耗时，平均等待时间100(1)qLLpL[]LWEX[]qqLWEX11两个特例特例1：每批到达K个客户2[]1,=K/2(1)21rEXKL22(1)2(1)qKLL排队队列长度:特例2：客户批次大小服从几何分布生成函数121(1),(01)xxc11(1)()(1),1nnnzCzzz100(1)(1)()1[1()](1)(1)1[(1)]1(1)1[(1)]1[(1)](1)[(1)][(1)]nnnnnzPzzrzCzzzzzzzz13所以11(1)[(1)][(1)](1)[(1)][(1)]nnnnp14例子：产品修复某工厂流水线作业，一名工人负责修复有瑕疵的产品。每件产品都有一处或者两处瑕疵。有一处瑕疵的产品的到达速率为λ1=1件/小时，有两处瑕疵的产品的到达速率为λ2=2件/小时，均为泊松到达。工人修复一处瑕疵平均用时10分钟，修复时间服从指数分布。每处瑕疵等待并被修复造成每小时利润损失为C1，工人每小时工资C2，修复瑕疵的代价是多少？如果安排另外一个工人专门修复有两处瑕疵的产品，代价如何？何种方案代价最小？15M[x]/M/1模型，客户=瑕疵，客户批次=产品，服务器=工人121221,2,3,6,1/3,2/3[]1/34/35/3[]1/38/331/2,5/6ccEXEXr16253[]62752(1)2(1)6rEXL200111/1.1371/2.637()6327.551/1.1371/2.6371117.551.1371.1372.6372.637nnnnPzzzzzzz0.116(0.880)0.050(0.379)nnnp12127CostCLCCC212()33Czzz17安排另外一个工人，变成一个M/M/1模型和一个M[x]/M/1模型对M/M/1对M[x]/M/1111/0.21/L2132/3321212/3KL112212'()23.22CostCLLCCC21',3.8CostCostCC若则必须满足18成批服务排队模型M/M[Y]/1模型描述：单服务器单队列；服务器FCFS；无限等待位；服务器一次服务K个客户，K个客户同时完成服务；如果服务器空闲但是少于K个客户等待，服务器开始服务；服务过程中新到达的客户可以立即得到服务，直到服务器同时服务K个客户。19当系统中有n-1个客户，n0，到达一个客户，发生状态迁移n-1n当系统中有n+K个客户，n0，完成一批客户服务，发生状态迁移n+Kn，由于有多于K个的客户在系统中，所以完成服务个户数的必为K个对于n=0，到达一个客户，发生状态迁移01，状态1,2,...,K完成服务一批客户，发生状态迁移10,20,...,K0稳态平衡方程1012(),(1)()nnKnKpppnpppp20解M/M[Y]/1得到这里r0是以下方程在(0,1)范围内的唯一解对比M/M/1，把ρ替换为r0。参考M/M/1的解，有000(1)(0,01)nnprrnr1()0KDD00,1qrLLLr001,(1)qr21M/M[Y]/1的另一种情况考虑另外一种情况，服务器每次只服务K个客户，如果没有K个客户，服务器等待，直到队列里累积了K个客户当系统中有n-1个客户，n0，到达一个客户，发生状态迁移n-1n当系统中有n+K个客户，n0，完成一批客户服务，发生状态迁移n+Kn对于n=0，到达一个客户，发生状态迁移01，状态1,2,...,K-1时，不完成任何客户服务稳态平衡方程22110()()(1)nnKnnnKnKpppnKpppnKpp23稳态平衡方程的第一个等式和上一种M/M[Y]/1模型的方程一样，所以对n≥K，解的形式为由于对于nK由于，可得1,nnKnppp001(1)nnnprppnK0,nnpCr00KKpCrp00KpCr000nKnKKpprr24递归解得其中综合两种情况100000(1)(1)1()nnnKprnKrpprnK120nnpCCr1022000,(1)CpCCprr25111000101210020001+100020(1)11(1)111(1)(1)(+)(1)(1)nKnKnnKKKrprrrrKrrrrrKrr+1000(+)0Krrr已知是方程的解,所以001rpK26例子：洗车洗车站改进了洗车通道，一次可以洗两辆车。车辆平均每小时到达20辆，泊松过程；洗车平均耗时5分钟，指数分布。洗车站平均有多少辆车。[Y]M/M/120,12,2K第一类模型求方程在（0，1）范围内的解显然r=1是一个解，解得2731232200rr3212322041335rrrrr0(369)/60.884r007.65.91qrLLLr辆车,辆车0.000.100.200123456789101112131415nProbabilityDistributionNumberofCustomersProb(n)2829爱尔兰(Erlangian)排队模型目前讨论过的所有排队模型，均假设：客户到达是泊松过程（到达时间间隔服从指数分布），服务时间服从指数分布这些模型不能刻画所有的排队系统考虑：到达时间间隔或者服务时间服从爱尔兰分布（ErlangDistribution）时的排队系统A.K.Erlang，丹麦数学家，排队论奠基人30爱尔兰分布（ErlangDistribution）一个随机变量T，服从Erlang分布，其概率密度函数为Erlang分布的均值、方差对给定的k，Erlang分布被称为k型Erlang分布或者Ekk=1，指数分布k=∞，常数1/μ1()()(0)(1)!kkktkfttetk211[][]ETVarTk31Erlang分布和指数分布的关系k个独立同分布（i.i.d）的指数分布随机变量之和为k型Erlang分布。如果指数分布变量均值1/kμ，则它们之和的均值为1/μ，方差为1/kμ2例如：一个产品经过4道检验工序，每道工序平均耗时1/4μ，则整个检验时间平均1/μ，服从4型Erlang分布。工序11/4μ工序21/4μ工序31/4μ工序41/4μ32Erlang服务时间排队模型M/Ek/1考虑一个排队模型：客户泊松到达，服务器有k个服务阶段，每个耗时1/kμ，指数分布。服务器仍然只能一次服务一个客户，即当前客户完成最后一个服务阶段，下一客户才能开始第一阶段的服务。令pn,i为系统中有n个客户，且包括当前的服务阶段，被服务客户还有i个阶段需要完成（在第k-i个阶段）的概率。情况1：被服务客户在阶段i，1≤i≤k-1，n≥2，客户到达，(n,i)(n+1,i)，(n-1,i)(n,i)完成一个阶段服务，(n,i+1)(n,i)情况2：被服务客户在阶段k，n≥2客户到达，(n,i)(n+1,i)，(n-1,i)(n,i)完成一个阶段服务，(n+1,1)(n,k)情况3：n=1，1≤i≤k-1客户到达，(1,i)(2,i)，完成一个阶段服务，(1,i+1)(1,i)情况4：n=1，i=k客户到达，(1,k)(2,k)，完成一个阶段服务，(2,1)(1,k)情况5：n=0，(0)(1,k)，(1,1)(0)3334,,11,,1,11,1,1,11,2,1001,1()(2,11)()(2)()(11)()ninininknnkiikkpkppnikkpkppnkpkpikkpkpppkp35求解M/Ek/1难以直接求解。每个到达客户需要获得k个阶段服务（先后为k,k-1