运筹学第8章：标准服务系统MMn系统.ppt

第八章标准服务系统M M n系统 鱼与熊掌兼得 2 8 1M M n损失制 8 1 1M M n损失制 无限源 M M n n FIFO 令从顾客源来的顾客到达率为 每台的服务率为 则有 j j 0 1 n 1 n 0 j j j 0 1 n将 j j代入生灭方程 得 式中 称为业务量 traffic 是无量纲量 表示单位时间内要求系统提供的服务时间 和 的单位必须一致 由于纪念Erlang 用爱尔兰作单位 Erl 3 系统的服务质量 系统的质量用顾客的损失率来度量 有两种度量方法按时间计算的损失率pn 即单位时间内服务台全被占用的时间按顾客计算的损失率B 即单位时间内损失的顾客数与到达顾客数之比在本系统中有B pn En 称为爱尔兰损失公式 不是所有系统都有B pn的性质工程上经常是已知 给定B 求所需最少的服务台n求n一般有三种方法 迭代计算 查图 查表 4 求所需服务台的方法 1 查图 如书上262页2 迭代计算无法由En 给出n的逆函数 因此采用逐次试算的方法注意 En 有较简单的递推公式 3 工程上经常采用查表的方法爱尔兰表最左边一列为服务台数n 最上面一行为服务质量的不同等级 即B爱尔兰表中元素的值为 表示服务台数为n 服务质量为B时 系统最大所能承担的业务量 工程上经常用A表示 A是加入话务量 5 爱尔兰损失表 n 3 B 0 01 查表得 0 455已知n和 如何求B 线性内插法 例 n 3 2 5 由表可知B落在0 2 0 3之间 若假设在这区间所承担的业务量与B成线性关系 则有线性内插公式B2 5 0 2 0 3 0 2 2 5 1 930 2 633 1 930 0 281 6 例1M M n损失制无限源系统 已知n 3 5人 小时 平均服务时长30分钟 人 试求 1 系统中没有顾客的概率 2 只有一个服务台被占用的概率 3 系统的损失率解 由题意可知 60 30 2人 小时 所以 2 5Erl 1 p0 1 2 5 2 52 2 2 53 3 1 0 108 2 p1 p0 2 5 0 108 0 27 3 B E3 2 5 p0 3 3 0 108 2 604 0 28例2两市话局间的忙时平均呼叫次数为240 每次通话平均时长为5分钟 规定两局间中继线的服务等级为B 0 01 问 1 应配备多少条中继线 2 中继线群的利用率为多少 解 中继线群上的加入话务量为 240 5 60 20Erl 1 查262页图 n 30条 2 查爱尔兰表可知 n 30 B 0 01时可承担A 20 337 B 0 005时可承担A 19 034 因此 E30 20 0 005 0 005 20 19 034 20 337 19 034 0 008707中继线群利用率 1 B n 20 1 0 008707 30 0 660862 7 服务台利用率与服务台数量的关系 n图 当给定n和B后 系统所能承担的业务量 可以通过爱尔兰公式求出 从而可计算出服务台利用率 若保持B不变 不断增加服务台数n 也会发生变化 就可以得到 n图如下 通过观察 有几点结论 1 B不变时 随n增加 说明大电路群效率高2 n不变时 随B增加 说明效率与质量是矛盾的 高效路由 3 具有边际递减规律4 越大 系统抗过负荷能力越差 8 系统过负荷特性 B图 过负荷是指系统加入的业务量A 超过给定服务质量所能承担的业务量A过负荷用过载业务量与标准应承担的业务量的比值来表示 即 A A A A AEn A B En A B 由图可见 在同样标准的服务质量和同样的过负荷率下 大系统的质量劣化严重 说明效率与可靠性是矛盾的 9 例3某服务部门把顾客分为两组 分别组成两个单独的服务系统 各系统的到达率分别为 1 4人 小时 2 8人 小时 每人的平均占用时长都为6分钟 给定损失率为B 0 01 试求 1 分组服务时每组应配备的服务台数 2 合并为一个服务系统时 各种条件不变 应配备的服务台数 3 比较两种组织方式的服务台利用率 解 1 分组时 1 4 0 1 0 4Erl 2 8 0 1 0 8Erl查爱尔兰表 得n1 3台 n2 4台 共需7台 B1 0 005 0 005 0 4 0 349 0 455 0 349 0 0074B2 0 005 0 005 0 8 0 701 0 869 0 701 0 00795 1 1 B1 2 1 B2 n1 n2 0 17 2 合组时 12 0 1 1 2Erl 查爱尔兰表 得n 5台 节省了2台 B 0 005 0 005 1 2 1 132 1 361 1 132 0 006485 1 B n 0 238 10 8 2 1M M n损失制 有限源 M M n N n FIFO 例交换机内部有n条绳路 N条入中继线 N n 每条入中继线上的呼叫到达强度为 且为波松分布 通话时长为负指数分布 参数为m 问入中继线上呼叫的损失率为多少 上述例子就是一个M M n损失制 有限源系统 当已经接受绳路服务的中继线在通话中 该中继线上就不会有新的呼叫 因此 整个系统的呼叫到达率是与系统中被服务的中继线数相关的 这就是有限源系统的特点显然 系统在各状态下的到达率和离去率分别为 j N j j 0 1 n 1 n 0 j j j 1 n将 j j代入生灭方程 得 11 当j n时 pn表示按时间计算的损失率 下面分析按顾客计算的损失率BB 单位时间平均损失顾客数 单位时间平均到达顾客数在有限源系统中 顾客到达率随系统状态变化 因此有平均顾客到达率 又称为有效到达率 12 可见 在有限源情况下 系统按时间计算的损失率pn和按顾客计算的损失率B是不相等的 其原因就是输入过程随系统状态而变从一个极端情况看 若N n 则B 0 但pn 0虽然爱尔兰损失公式和恩格谢特损失公式都是在负指数服务时长假设下推导出来的 但已证明服务时间是其它一般平稳分布 结论仍是正确的服务台利用率 13 例4有一电话查询服务处集中答复三个查询点的所有查询事项 查询服务处与查询点之间用电话联系 查询服务处只有一名值班员答复所有的查询 已知每个查询点平均每小时有两次查询 每次平均通话12分钟 问 1 值班员空闲的概率 2 值班员打电话的概率 3 查询时值班员忙的概率 4 服务处查询电话的平均到达率 5 值班员的工时利用率 解 系统是有限源M M 1损失制 q 2 60 12 0 4Erl 1 p0 1 1 Nq 0 4545 14 8 2M M n等待制 无限源 无限容量 M M n FIFO 8 2 1系统稳态概率及等待概率令从顾客源来的顾客到达率为 每台的服务率为 则有 j j 0 j j j n j n j n将 j j代入生灭方程 得 15 当 n时 则p0中第二项不收敛 系统中队长将趋于无穷当 n时 系统有稳态 处于动态平衡 无限容量等待制 每个顾客早晚都会得到服务 因此系统完成的业务量也是 顾客进入系统必须排队等待的概率为 D爱尔兰等待公式排队等待的概率是等待制系统的重要指标之一n 1时 D 公式D的记忆法 16 8 2 2系统的各种指标 等待制系统的指标有 平均逗留队长 平均等待队长 平均逗留时长 平均等待时长和服务台利用率等 n 1时 D Ld 1 Lq 2 1 Wq 例5书上273页 17 8 2 3等待时间的概率分布 前面只推导了要等待的概率D P W 0 但在很多情况下我们希望知道等待时长的分布 即P W t 系统中有j个顾客 j n时 新来顾客要排队等待 采用FIFO规则 令新顾客到达时为0时刻 显然 只有服务台上离去j n个顾客时 新顾客才排到队首当n个服务台连续服务时 顾客离去率为n 因此服务台空出的过程是波松流 在 0 t 内空出i次的概率为 18 等待时长分布的推导 19 例6某储蓄所内 已知忙时顾客到达率 40人 小时 窗口营业员服务率为 16人 小时 要求 1 工时利用率不低于60 2 顾客平均等待时间不超过5分钟 问 设几个窗口适当 解 系统是无限源M M n等待制 40 16 2 5Erl 1 n 0 6 解出n 4 17 故n可取值3 4 2 n 3时 p0 1 2 2 3 3 3 3 2 5 1 0 045 20 例7兴建一座港口码头 只有一个装卸泊位 要求设计泊位的生产能力 能力用日装卸船只数表示 已知单位装卸能力日平均生产费用为a 2000元 船只到港后若不能及时装卸 逗留一日要损失运输费b 1500元 预计船只的平均到达率为 3只 日 设船只到达的间隔时间和装卸时间都服从负指数