排队论基础及应用

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

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

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

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

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

6、务,22,稳态平衡方程,23,稳态平衡方程的第一个等式和上一种M/MY/1模型的方程一样，所以对nK，解的形式为 由于 对于n0时的情况，这是因为尽管高优先级客户优先获得服务，但是不能取代正在获得服务的低优先级客户（非先占优先）。如果是先占优先，则L2、Lq2、Wq2均为10时的取值。,62,扩展：如果低优先级客户服务速率为1，高优先级客户服务速率为2。（Morse, 1958）,求解方法与上一模型一样,63,对上述排队系统，定义 上式中Lq写为 1981年，Miller得出系统中优先级1的客户数量为n1的概率,64,最后，考虑客户分为类型1客户和类型2客户（比如大人和小孩），到达速率和服务速

7、率分别为1，1和2，2，但是排队不考虑优先级。,65,比较,我们考虑了三种排队系统： 有优先级，客户服务时间一样，1，2， 有优先级，客户服务时间不同， 1，2，1， 2 无优先级，客户服务时间不同， 1，2，1， 2 比较第一种和第二种，当 ， ，这时1，2决定何种排队模型更优,66,比较第二种和第三种，它们的队列长度差别 如果 ，上式1，表示引入优先级会延长等待时间。 。 规则：服务所需时间短的客户优先（priority assigned by shortest processing time, 简称SPT规则）,67,例：理发店,一个理发店只有一位理发师。平均每小时有五位顾客立法，到达可

8、视为泊松过程。到理发店的顾客中有1/3是理平头的，理平头平均耗时5分钟，而其余理发顾客平均耗时12.5分钟，均服从指数分布。理发师考虑优先给平头顾客理发，问这样做是否有助于缩短顾客的平均等待时间。,68,平头优先： 不考虑优先：,先剪平头可以缩短等待时间,69,多个优先级,前面的讨论限于两个优先级。 我们考虑一个服务器，客户有多个（大于2个）优先级的情况。排队规则仍然是非先占优先的。 假设客户分为r个优先级，其中第k个优先级客户的到达速率为k，平均服务时间为1/k。泊松到达，指数服务时间。 定义：,70,当1，系统有稳态 考虑一个优先级为i的客户，他在队列中的等待时间为Tq。当该客户进入队列时

9、，假设队列中已有n1个优先级为1的客户，n2个优先级为2的客户，.，nr个优先级为r的客户。并且假设在该客户在队列中等待期间，有n1个优先级为1的客户，n2个优先级为2的客户，.，nr个优先级为r的客户进入队列。令S0表示该客户到达时正在被服务客户的剩余服务时间；Sk表示服务nk个优先级为k的客户的时间；Sk表示服务nk个优先级为k的客户的时间。,71,令Wq(i)表示优先级为i的客户的平均队列等待时间 求S0 服务一个客户的时间分布 另外,72,因此 由于nk和每个客户的服务时间Sk(n)是独立的,73,Littles law 类似地 因此 求解可得 注意,r元线性方程组,74,整个排队系统的平均队列长度 如果不考虑优先级，即r种类型的按照FCFS获得服务，SPT规则继续有效，即如果按照优先级高低，有 ，则引入优先级可以最大地缩短客户的平均等待时间。 引入优先级，缩短平均等待时间的代价是客户在等待时间上的不公平。这是一个 Efficiency-Fairness Tradeoff,75,多服务器优先级排队模型M/M/c/PR,考虑多个服务器的优