管理运筹学—排队模型(免费).ppt

三 排队模型 排队系统范例 乘客等候公共汽车 某招聘会场外焦急等待的求职者 储户在银行等待服务 学生在食堂等待就餐 排队是在日常生活和生产中经常遇到的现象 例如 上 下班搭乘公共汽车 顾客到商店购买物品 病人到医院看病等等 常常出现排队和等待现象 除上述有形的排队之外 还有大量的 无形 排队现象 例如 水库的存储调节 车站 码头等交通枢纽的车船堵塞和疏导等 排队的不一定是人 也可以是物 例如 通讯卫星与地面若干待传递的信息 生产线上的原料 半成品等待加工 要降落的飞机因跑道被占用而在空中盘旋等 排队系统范例 排队系统范例 排队中的问题 排队系统范例 排队系统范例 为解决排队中存在的问题 设置候车线 为提高排队系统的服务效率 在银行 火车站售票厅等机构提倡 一米线 服务 进一步发展出排队叫号系统 在银行 医院 网通公司等服务行业已广泛应用 一 问题的描述及基本概念 1 问题的描述 在一个排队服务系统中总是包含一个或若干个 服务设施 有许多 顾客 进入该系统要得到服务 服务完毕后即自离去 倘若顾客到达时 服务系统空闲着 则到达的顾客立即得到服务 否则顾客将排队等待服务或离去 怎样才能做到既保证一定的服务质量指标 又使服务设施费用经济合理 恰当地解决顾客排队时间及服务设施费用大小这对矛盾 这就是研究随机服务系统的理论 排队论所要研究解决的问题 任何排队服务系统可以描述为以下四个方面 图1 1 输入 指顾客到达系统的情况 a 按到达时间间隔分 有 确定的时间间隔 随机的时间间隔 b 从顾客到达人数的情况看 有 单个到达 按成批到达的 c 从顾客源总体看 有 顾客源总数无限 顾客源总数有限注 只要顾客源总数足够大时 可以把顾客源有限的情况近似地当成顾客源无限情况处理 1 输入 指顾客到达系统的情况 2 输出 指顾客从得到服务到离开服务机构的情况 有 定长的服务时间随机的服务时间 3 排队服务规则 有损失制与等待制两种情况 损失制 顾客到达时 若所有服务设施被占用 则顾客自动离去 永不再来 例 电话服务系统就属这种 当一个电话打不通时需要重新拨号 意味着一个新的顾客的到来 而原来顾客已永远离去 等待制 顾客到达时 如服务设施已被占用 就留下来等待服务 一直到服务完毕才离去 3 排队服务规则 有损失制与等待制两种情况 等待制 这里分两种情况 一种是无限等待的系统 不管服务系统中已有多少顾客 新来的都进入系统 另一种是有限等待的系统 当排队系统中顾客数量超过一定限度时 新到的顾客就不再等待 而自动离开服务系统 1 输入 指顾客到达系统的情况 2 输出 指顾客从得到服务到离开服务机构的情况 对等待的系统 服务次序上一般有 先到先服务 FCFS 按到达先后次序排成队伍依次接受服务 当有多个服务设施时 一种是顾客分别在每个服务设施前排成一队 另一种是排成一个公共的队伍 当任何一个服务设施有空时 排在队首的顾客得到服务 带优先权服务 到达的顾客按重要性进行分类 服务设施优先对重要级别高的顾客服务 在级别相同的顾客中按到达先后次序排队 3 排队服务规则 有损失制与等待制两种情况 1 输入 指顾客到达系统的情况 2 输出 指顾客从得到服务到离开服务机构的情况 对等待的系统 服务次序上一般有 先到先服务 FCFS 带优先服务权 随机服务 到达服务系统的顾客不形成队伍 当服务设施有空时 随机选取一名服务 对每一等待的顾客来说 被选取的概率相等 3 排队服务规则 有损失制与等待制两种情况 1 输入 指顾客到达系统的情况 2 输出 指顾客从得到服务到离开服务机构的情况 4 服务机构 指服务设施的个数 排列及服务方式 按排列方式 多站服务系统有串联与并联之分 对S个服务站的并联系统 一次可以同时服务S个顾客 对S个服务站的串联系统 每个顾客要依次经过S个服务站 就象一个零件经过S道工序加工一样 1 输入 指顾客到达系统的情况 2 输出 指顾客从得到服务到离开服务机构的情况 3 排队服务规则 有损失制与等待制两种情况 按服务设施个数分 有一个或多个之分 通常称单站服务系统与多站服务系统 在服务方式上有 单个服务 成批服务如 公共汽车一次就装载大批乘客 根据排队系统的特征 肯达尔 Kendall 于1953年提出了排队服务系统的分类记号 2 基本记号 泊松输入或负指数分布的服务时间 定长输入或定长服务时间 爱尔朗分布的输入与服务时间 一般独立输入 一般服务时间分布 顾客输入为泊松分布 服务时间为负指数分布 有n个并联服务站的排队服务系统 定长输入 一般服务时间 单个服务站的随机服务系统 一般独立输入 爱尔朗服务时间 单个服务站的排队服务系统 输入 输出 并联的服务站数 注 如果不附加特别的说明 这种记号都指顾客总体数量无限 系统中的队长可以无限 排列规则为先到先服务 1971年国际排队符号标准会上将上述分类记号扩充到六项 记为 a b c三项同上 分别为输入 输出 或服务时间 的分布及并联的服务站数 d为系统中最多可容纳的顾客数 e为顾客源总数 f为排队服务规则 排队服务系统的分类记号 2 基本记号 输入 输出 并联的服务站数 3 基本概念及符号 1 系统状态 一个排队服务系统中的顾客数 包括正在被服务顾客数 2 队长 系统中等待服务的顾客数 它等于系统状态减去正在被服务的顾客数 3 N t 在时刻t排队服务系统中的顾客数 即系统在时刻t的瞬时状态 4 Pn t 在时刻t排队服务系统中恰好有n个顾客的概率 5 当系统中有n个顾客时 新来顾客的平均到达率 单位时间内新顾客的到达数 当对所有n值 是常数时 可用代替 3 基本概念及符号 1 系统状态 2 队长 3 N t 4 Pn t 5 7 S 排队服务系统中并联的服务站个数 6 当系统中有n个顾客时 整个系统的平均服务率 单位时间内服务完毕离去的顾客数 当 是常数时 可用代替 8 稳定状态 当一个排队服务系统开始运转时 系统状态很大程度上取决于系统的初始状态和运转经历的时间 但过一段时间后 系统的状态将独立于初始状态及经历的时间 这时称系统处于稳定状态 由于对系统的瞬时状态研究分析起来很困难 所以排队论中主要研究系统处于稳定状态的工作情况 由于稳定状态时工作情况与时刻t无关 这时Pn t 可写成Pn N t 可写成N 3 基本概念及符号 1 系统状态 2 队长 3 N t 4 Pn t 5 6 7 S 4 工作状况的主要指标 忙期 1 1 顾客在排队服务系统中 从进入到服务完毕离去的平均消耗时间W 或顾客排队等待服务的平均等待时间Wq 这对顾客来讲最关心 每个顾客希望这段时间越短越好 2 忙期指服务系统累计的工作时间占全部时间的比例 这是衡量服务机构工作强度和利用效率的指标 3 系统中平均顾客数L或平均队长Lq 这是顾客和服务机构都关心的指标 它在设计排队服务系统时也很重要 因为涉及到系统需要空间大小 5 各个指标之间的关系 设 表示单位时间内被服务完毕离去的平均顾客数 则 表示相邻两个顾客到达的平均间隔时间 表示对每个顾客的平均服务时间 因此有 平均队长 等于单位时间内平均到达的顾客人数 表示单位时间内顾客的平均到达数 乘以每个顾客在系统中的平均停留时间 系统中平均的顾客数 为单位时间内平均到达的顾客数乘以得到服务前的平均等待时间 将前两式带入第3式得 说明 Pn值当n 0时即为P0 系统中平均的顾客数 平均队长 每个顾客在系统中的平均停留时间 等于顾客在系统中的平均等待时间加上平均服务时间 因此只要求得Pn的值即可得L Lq W和Wq 由于 即是服务系统的忙期 二 输入与服务时间的分布 1 输入 最简单流 1 最简单流是指在t这段时间内有k个顾客来到服务系统的概率vk t 服从泊松分布 即 2 特性最简单流需要满足下面三个条件 平稳性指在一定时间间隔内 来到服务系统有k个顾客的概率仅与这段时间间隔的长短有关 而与这段时间的起始时刻无关 即在时间 0 t 或 a a t 内 vk t 是一样的 无后效性在不相交的时间区间内到达的顾客数是相互独立的 即在时间区间 a a t 内来到k个顾客的概率与时间a之前来到多少顾客无关 普通性在瞬时内只能有一个顾客到达 不可能有两个以上顾客同时到达 设 t 表示在 0 t 内有两个或两个以上顾客到达的概率 则有 t o t t 0 二 输入与服务时间的分布 1 输入 最简单流 1 最简单流 2 特性最简单流需要满足下面三个条件 平稳性 二 输入与服务时间的分布 1 输入 最简单流 1 最简单流 2 特性 3 最简单流的性质 在时间 t t t 内没有顾客到达的概率为 参数代表单位时间内到达顾客的平均数 在时间 t t t 内恰好有一个顾客到达的概率为 若令t代表顾客到达流为泊松分布时依次到达的两个顾客的间隔时间 则t的概率密度函数f t 为负指数分布 2 服务时间 负指数分布 负指数分布的服务时间的性质 虽然在真实的排队系统中 服务时间的概率分布可以有各种形式 但负指数分布的服务时间是最常用的 原因是它在数学上易于处理 则对每个顾客的平均服务时间为 1 如服务设施对每个顾客的服务时间服从负指数分布 负指数分布的服务时间的性质 则对每个顾客的平均服务时间为 1 如服务设施对每个顾客的服务时间服从负指数分布 2 当服务设施对顾客的服务时间t为参数的负指数分布时 1 在内没有顾客离去的概率为 2 在内恰好有一个顾客离去的概率为 3 如果足够小的话 在内有多于两个以上顾客 离去的概率为 负指数分布的服务时间的性质 3 如果服务设施对顾客的服务时间服从负指数分布 4 若干个独立的负指数分布的最小值是负指数分布 则不管对某一个顾客的服务已进行了多久 剩下来的服务时间的概率分布仍为同原先一样的负指数分布 即对任何 有 即设T1 T2 Tn分别表示参数为的独立的 负指数分布的随机变量 设U min T1 T2 Tn 则U也是负指数分布的随机变量 1 如果来到服务机构的有n类不同类型的顾客 每类顾客来到服务站的间隔时间 2 如果一个服务机构中有S个并联的服务设施 如各设施对顾客的服务时间为具有相同参数的负指数分布 于是整个服务机构的输出就是一个具有参数的负指数分布 这样 对具有多个并联服务站的服务机构就可以同具有单个服务站的服务机构一样处理 这个性质说明 为具有参数的负指数分布 则作为总体来讲 到达服务机构的顾客的时间间隔仍为负指数分布 负指数分布的服务时间的性质 4 若干个独立的负指数分布的最小值是负指数分布 三 生死过程 1 问题的描述 生死过程是用来处理输入为最简单流 服务时间为负指数分布这样一类最简单排队模型的方法 生死过程举例 各个细菌在任何时段内分裂和死亡都是独立的 并且把细菌的分裂和死亡都看成一个事件的话 假如有一堆细菌 每个细菌在时间内分裂成两个的概率 为 在时间内死亡的概率为 则在内发生两个或两个以上事件的概率为 如把细菌的分裂看成是一个新顾客的到达 细菌的死亡看成一个服务完毕的顾客的离去 则生死过程恰好反映了一个排队服务系统的瞬时状态 假如已知初始时刻细菌的个数 问经过时间t后细菌变成多少个 N t 将怎样随时间而变化 在生死过程中生与死的发生都是随机的 它们的平均发生率依赖于现有的细菌数 即系统现处的状态 2 问题的假设 1 给定N t n 到下一个生 顾客到达 的间隔时间 2 给定N t n 到下一个死 顾客离去 的间隔时间 3 在同一时刻只可能发生一个生或死 即同时只能有一个顾客到达或离去 是参数的负指数分布 是具有参数的负指数分布 将上面几个假定合在一起 则可用生死过程的发生率图来表示 图2 图中箭头指明了各种系统状态发生转换的仅有可能性 在每个箭头边上注出了当系统处于箭头起点状态时转换的平均率 注 要求系统的瞬时状态的概率分布是很困难的 所以下面只考虑系统处于稳定状态时的情形 3 生死过程的状态平衡方程 1 输入率等于输出率原则考虑系统处于一特定状态N t n n 0 1 2 假定开始计算进入这个状态和离开这个状态的次数 因为在同一时刻这两件事都只能发生一次 因此进入和离开这个状态的次数或者相等 或者刚好相差一次 2 生死过程的状态平衡方程 状态0的输入仅仅来自状态1 考虑n 0的状态 处于状态1时系统的稳定状态概率为 而从状态1进入状态0的平均转换率为 因此从状态1进入状态0的输入率为 又从其它状态进入状态0的概率为0 所以状态0的总输入率为 表1列出了各个状态的平衡方程 3 生死过程的状态平衡方程 1 输入率等于输出率原则 2 生死过程的状态平衡方程 考虑n 0的状态 所以状态0的总输入率为 类似上面的讨论 状态0的总输出率为 根据输入率等于输出率的原则 对状态0有以下状态平衡方程 生死过程的状态平衡方程 3 状态平衡方程的求解 由表1有 令 则以上各式可以通写为 因为 所以有 由可以推出 再根据前面的公式求出排队系统的其它指标 四 最简单的排队系统模型 1 顾客来源无限 队长不受限制的排队模型 1 模型的假设假定 到达排队系统的顾客的平均率为常数 即对所有n 服务机构的平均服务率也是常数 S为并联的服务站个数 多个服务站时 在单个服务站时 即服务机构总的服务效率 1 模型的假设假定 到达排队系统的顾客的平均率为常数 服务机构的平均服务率也是常数 应高于顾客的平均到达率 以保证系统最终进入稳定状态 2 服务系统各项指标的推导 说明 在单站服务系