管理科学方法 演示课件 V6.1版 浙江工商大学 工程管理系 2009年9月

第5章 随机服务系统 本章学习要求 掌握几个经典排队模型的构建，包括 ●基本排队模型 [M/M/1]:[//FCFS] 第5章 随机服务系统 本章学习要求 掌握几个经典排队模型的构建，包括 ●基本排队模型 [M/M/1]:[//FCFS] ●有限队列模型 [M/M/1]:[N//FCFS] ●有限顾客源模型[M/M/1]:[∞/m/FCFS] ●多服务台模型[M/M/c]:[∞/∞/FCFS] ●多服务台系统容量有限模型[M/M/c]:[N/∞/FCFS] ●多服务台顾客源有限模型[M/M/c]:[∞/m/FCFS]

5.1 基本排队模型 [M/M/1]:[//FCFS] 单服务台损失制是最经典的问题之一。 设系统中只有一个服务员（n=1），顾客到达符合泊松 分布，顾客到达速率为且与时间无关。如果顾客到达时 服务员正忙着，顾客立即离去。服务时间T服从负指数分 布，速率为µ     因为系统中只有一个服务员，故系统只有两种可能的状态： 0： 服务员空闲 1： 服务员正在为顾客服务

说明： 表示一个顾客 单服务台损失制的系统的状态转移图如下 进入系统时， 系统就从状态 “0”以转换速率  变换到状态 “1”。当服务完    表示一个顾客 进入系统时， 系统就从状态 “0”以转换速率  变换到状态 “1”。当服务完 毕，顾客离开系统，系统从状态“1”以服务速率µ变到状态“0”。

把“转入=转出”看作系统的稳态， 即： P0 = µP1 又因为 P0 + P1 =1 故： P0 = µ/（+µ） （闲着概率）   把“转入=转出”看作系统的稳态， 即： P0 = µP1 又因为 P0 + P1 =1 故： P0 = µ/（+µ） （闲着概率） P1 = /（+µ） （忙着概率）

5.1.2 单服务台等待制I [M/M/1]:[//FCFS]   特征：输入为Poisson流，服务时间服从负指数分布，一个服务台，队列容量无限，顾客源数量无限，服务规则是先到先服务。这是一类最常见的排队问题。 n+1 1 2 n-1 n P0 P1 P2 Pn-1 Pn Pn+1  

系统处于稳态时，对每个状态来说，转入=转出。 对于状态n来说，有： Pn-1+µPn+1 = (µ+)Pn n≥1 2 n-1 n P0 P1 P2 Pn-1 Pn Pn+1     系统处于稳态时，对每个状态来说，转入=转出。 对于状态n来说，有： Pn-1+µPn+1 = (µ+)Pn n≥1 对于状态“0”，有： P0 = µP1

对于状态“0”到状态“n”，存在以下稳态方程：   状 态 转 入 转 出 µP1 ＝ P0 1 P0 + µP2 ＝ P1 + µP1 ┊ ┊ ┊ n Pn-1+ µPn+1 ＝ Pn+ µPn

  求解以上方程组可以得到： P 0 = 1- ρ 0≤ ρ=  /µ ≤1 P n = ρn(1- ρ) n=0,1,2,… 1 2 状 态 转 入 转 出 µP1 = P0 1 P0 + µP2 = P1 + µP1 ┊ ┊ ┊ n Pn-1+ µPn+1 = Pn+ µPn ┊ ┊ n+1 1 2 n-1 n P0 P1 P2 Pn-1 Pn Pn+1     求解以上方程组可以得到： P 0 = 1- ρ 0≤ ρ=  /µ ≤1 P n = ρn(1- ρ) n=0,1,2,…

根据题意, =100辆/小时，1/ =15秒=1/240 小时/辆 即： ＝240 辆/小时。 例: 高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求： 1）收费处空闲的概率; 2) 忙的概率； 3）系统中分别有1、2、3辆车的概率。 根据题意, =100辆/小时，1/ =15秒=1/240 小时/辆 即： ＝240 辆/小时。     以下代入公式分别计算

=100辆/小时，＝240 辆/小时 ρ=  /µ = 100/240 = 5/12 例: 高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求： 1）收费处空闲的概率; 2) 忙的概率； 3）系统中分别有1、2、3辆车的概率。 =100辆/小时，＝240 辆/小时     ρ=  /µ = 100/240 = 5/12 系统空闲的概率为： P0 = 1- ρ = 1- 5/12 = 0.583 系统忙的概率为 : 1- P0 = 1- (1- ρ) = ρ = 0.417 系统中有1辆车的概率为 : P1 = ρ1(1- ρ) = 0.243 系统中有2辆车的概率为： P2 = ρ2(1- ρ) = 0.101 系统中有3辆车的概率为: P3 = ρ3(1- ρ) = 0.042

运行指标分析 系统中的平均顾客数： L s = ρ /(1- ρ) 队列中的平均顾客数： Lq = ρ2 /(1- ρ)   系统中的平均顾客数： L s = ρ /(1- ρ) 队列中的平均顾客数： Lq = ρ2 /(1- ρ) 顾客在系统中的平均逗留时间 : WS = 1 / （µ- ） 顾客在队列中的平均逗留时间 : Wq = ρ / （µ- ）= ρ WS __________________________

5.2 有限队列模型 [M/M/1]:[N//FCFS] 5.2.1 单服务台等待制II [M/M/1]:[N//FCFS]  ←离去 队 列 _______________________________________________ 系 统 状 态 转 移 图 1 2 N-1 N P0 P1 P2 PN-1 PN  

仿照前面的方法,解以上方程组,整理后可以得到： ρ= 1时: k=0,1,2,…,N (特殊情形) ρ≠1时: k=0,1,2,…,N 状 态 转 入 转 出 µP1 = P0 ┊ Pk-1 + µPk+1 = Pk + µPk N PN-1 = µPN 1 2 N-1 N P0 P1 P2 PN-1 PN     仿照前面的方法,解以上方程组,整理后可以得到： ρ= 1时: k=0,1,2,…,N (特殊情形) ρ≠1时: k=0,1,2,…,N

运行指标分析 （ρ≠1）   系统中的平均顾客数： 队列中的平均顾客数： 顾客在系统中的平均逗留时间 : 顾客在队列中的平均逗留时间 :

这是一个 [ M / M / 1 ]:[ 5 /  / FCFS ] 的排队系统 =4人/小时，=6人/小时，=2/3 例: 一个单人理发店，除理发椅外还有4把椅子供顾客等候。顾客到达时如没有座位空闲便离去。顾客到达的平均速率为4人/小时，理发的平均时间为10分钟/人。顾客到达服从Poisson流，理发时间服从负指数分布。求： 1、顾客到达不用等待就可理发的概率； 2、理发店里的平均顾客数以及等待理发的平均顾客数； 3、顾客来店理发一次平均花费的时间以及平均等待的时间； 4、顾客到达后因客满而离去的概率； 5、增加一张椅子可以减少的顾客损失率。 这是一个 [ M / M / 1 ]:[ 5 /  / FCFS ] 的排队系统 =4人/小时，=6人/小时，=2/3     以下代入公式计算→

1、顾客到达不用等待就可理发的概率： P0=0.356 2、理发店里的平均顾客数: L S=1.423 (人) 等待理发的平均顾客数: L q=0.788 (人) 3、顾客来店理发的时间: W s=22.4 (分钟) 平均等待的时间: W q=12.4 (分钟) 4、顾客因客满而离去的概率: P5=0.048 5、增加一张椅子可以减少的顾客损失率: P5-P6=0.0169

5.2.2 多服务台等待制 II [M/M/c]:[N /  /FCFS] 1 2 c-1 c P0 P1 P2 Pc-1 Pc Pc+1   2 3 c (c-1) N-1 N Pn-1 Pn 这是一个[M/M/3]:[N/∞/FCFS] 排队模型的状态转移图

5.3 有限顾客源模型[M/M/1]:[∞/m/FCFS] 单服务台等待制III [M/M/1]:[ / m/FCFS] 服务台 需要服务 m-n 服务完毕 队列(n个)   现实情形：有m台机器在运转，单位时间内平均出现故障的机器数为λ，修理工修理一台设备的平均服务时间μ，已修复的机器仍然可能再出现故障。

关键点：有限源系统顾客的平均到达率为  e =  ( m – n ) n m-n 1 2 n+1 m  服务台 (m-n+1) m 需要服务 m-n 服务完毕 队列(n个) 关键点：有限源系统顾客的平均到达率为  e =  ( m – n ) 1 2 n n+1 m-1 m m (m-1) (m-n) (m-n+1)  

应用：车间有5台机器，每台机器的连续运转时间服从负指 数分布， 平均连续运行时间15分钟。有一个修理工 每次修理时间服从负指数分布,平均每次12分钟。求: (1)修理工空闲的概率→P0 (2)五台机器都出故障的概率→P5 (3)出故障的平均台数→LS (4)平均停工时间→? (5)平均等待修理时间→Wq (6)评价这个系统的运行情况→WS  

5.4 多服务台模型[M/M/c] 多服务台等待制I[M/M/c]:[ /  /FCFS] 各服务台互相独立且服务速率相同，即 ρ＜1

关键不同点：当顾客进入到达 c 数目以后，系统的 服务速率维持 c 不变，在这之前，… … 1 2 c-1 c P0 P1 P2 Pc-1 Pc Pc+1   2 3 c (c-1) n 关键不同点：当顾客进入到达 c 数目以后，系统的 服务速率维持 c 不变，在这之前，… …

应用：某售票处有三个窗口，顾客到达服从Poisson流， 到达速率为 0.9人／分，售票时间服从负指数分 布，每个窗口的平均售票速率为0.4人／分。顾客 到达后排成一队，依次到空闲窗口购票。求： (1)所有窗口都空闲的概率→P0 (2)平均队长→LS (3)平均等待时间→Wq 逗留时间→Ws (4)顾客到达后必须等待的概率→P(n≥3) → P(n=3)

补充： 排队系统对比 三个不同系统的对比 多服务台单队 =0.9 =0.4 =0.4 =0.4 =1.2 =0.9 联合运行 =0.3 =0.4 =0.3 =0.4 =0.4 多服务台单队 多服务台多队 =0.3 =0.4 =0.9 =0.4 =0.4 =1.2 =0.9 联合运行

本章作业 一、求下述三个不同服务系统的Ls、Lq、Ws、Wq 多服务台单队 =0.9 =0.4 =0.4 =0.4 =1.2 =0.3 =0.4 =0.3 =0.4 =0.4 多服务台单队 多服务台多队 =0.3 =0.4 =0.9 =0.4 =0.4 =1.2 =0.9 联合运行

作业答案 三个不同系统的对比 多服务台单队 多服务台多队 联合运行 L 3.95 3 Lq 1.70 2.25 W 4.39 10 3.33 Wq 1.89 7.5 2.49

二、对减轻当前银行排队现象的思考

补充：排队论与排序问题 问题 问题：有Ｎ个待加工的零件，需要依次在Ｍ台机器上进行加工，要求尽早完成加工任务。 设每个零件各道工序所需加工时间已知且不完全相同，则如果加工次序安排得不尽合理，就会出现？ 工序１ 工序２ 工序３

如果Ｎ个零件的加工次序能得到最科学的安排，就可以最大限度地减少零件等待机器或机器等待零件的时间，使零件加工的整个时间流程最短。 其他应用：１、军事——多兵种通过几个隘口 　　　　　２、建筑——安排不同工序的若干工程 　　　　　３、幼儿园——小朋友洗澡 … … 零件Ｎ 工序１ 工序２ 零件２ 零件１ 工序３

模型 排序领域的研究成果 Johnson算法（1954年） 针对机器数目Ｍ＝２，Ｎ个零件的问题。 公认的第一个真正意义上的排序数学模型 　　　公认的第一个真正意义上的排序数学模型 … … 零件Ｎ 工序１ 工序２ 零件２ 零件１

Johnson排序算法介绍 先作零件加工时间的工时矩阵： a1 a2 … … an b1 b2 … … bn 机器１ 机器２ 零件n 零件１ 基本思路：尽量减少零件在机器２上等待加工时间。因此，把机器２上加工时间长的零件先加工，短的后加工。

分类 按机器数目的排序分类 排序问题分类 注 释 单台机器 可以找到最优解 两台机器 部分问题有多项式复 杂性算法 排序问题分类 注 释 单台机器 可以找到最优解 两台机器 部分问题有多项式复 杂性算法 多台机器 无一般的多项式复杂性 算法

R.W. Conway: 《Theory of Scheduling》(作业计划理论) 排序问题是一个迷人的挑战性问题。尽管问题本身容易表达，也容易看到所需要的是什么，但是朝着求解的方向做任何推进都是极端困难的。 许多能干的人都研究过这个问题，但是他们都一无所获。 由于挫折和失败都不在文献中报道，问题就继续吸引着新的探索者。他们不相信结构如此简单的问题竟然会那么复杂难解。直到他们亲自尝试后才明白。

Manne数学规划排序模型介绍（1959） p11 p12 … … p1m p21 p22 … … p2m … … … … … =(pik) 已知第i个零件在第k台机器上的加工时间为pik，因此有矩阵： p11 p12 … … p1m p21 p22 … … p2m 　　 … … … … … =(pik) pn1 pn2 … … pnm 零件n … … 如何确定每一个零件在各台机器上的开始加工时间？

t11 t12 … … t1m t21 t22 … … t2m … … … … … =(tik) tn1 tn2 … … tnm Manne模型（1959） 设每个零件在各台机器上的开始加工时间矩阵为T，因此： t11 t12 … … t1m t21 t22 … … t2m 　　 … … … … … =(tik) tn1 tn2 … … tnm … …

tjk tik pik pjk tjk – tik ≥pik tik – tjk ≥pjk 对于两个零件 i 和 j 来说，如果 i 排在 j 之前加工，有： tjk – tik ≥pik 如果 i 排在 j 之后加工，有： tik – tjk ≥pjk

yij = 上述两个相互矛盾不可以同时成立，因此引入 0-1变量: 在机器k上，零件i 先于零件j 加工（不一定直接领先） 0 在机器k上，零件j 先于零件i 加工（不一定直接领先） 再设M是充分大的正数，则前两约束可统一为

(M + pjk) yij + (tik – tjk) ≥pjk (M + pik) (1- yij ) + (tjk – tik) ≥pik 当某个零件的排序存在优先权时，如 零件i 必须优先于零件 j 时，有： tik + pik ≤ tjk 如果排在最后加工 的零件是l , 最长流程是f , 有： tlk + plk ≤ f

(M + pjk) yij + (tik – tjk) ≥pjk 因此，完整的Manne模型为： tik + pjk ≤ tjk (M + pjk) yij + (tik – tjk) ≥pjk (k) (M + pik) (1- yij ) + (tjk – tik) ≥pik MIN f st tik + pik ≤ tjk 变量非负约束、0-1约束略

Manne模型分析 对于一个没有优先权的问题，该模型的规模为：变量总数是 mn(n+1)/2， 约束方程总数为mn2 。 例如对于一个 4╳3的排序问题，变量总数是30个，约束方程总数为48个。 对于更大的问题，虽然可以列出模型，但是求解困难。

算法 算法分类 精确性算法 启发式算法 计算机仿真

谢 谢 欢迎浏览 www. e d u j o b. org