运筹学 第1-3节.pptVIP

第一节 引 言 第二节 排队系统的描述 第三节 到达间隔分布和服务时间分布 某服务机构是单服务台，先到先服务，对 41 个顾客记录到达时刻 τ 和服务时间 s（单位为分钟），如下表所示，在表中，以第 1 号顾客到达时刻为 0 。全部服务时间为127 分钟。 2 2 2 81 21 9 1 142 41 0 1 3 80 20 8 3 4 139 40 1 8 4 72 19 10 4 2 135 39 0 2 3 70 18 7 2 5 133 38 0 5 1 65 17 7 3 3 130 37 0 3 2 62 16 2 1 6 129 36 0 1 1 61 15 3 2 1 127 35 3 9 2 52 14 7 6 2 121 34 5 3 1 49 13 7 4 4 117 33 3 2 4 47 12 0 1 8 116 32 0 2 5 45 11 0 2 1 114 31 0 7 2 38 10 0 5 2 109 30 0 2 1 36 9 1 3 1 106 29 5 10 3 26 8 0 1 2 105 28 6 4 3 22 7 2 4 2 101 27 5 3 4 19 6 5 6 3 95 26 10 7 2 12 5 7 3 1 92 25 2 1 9 11 4 6 4 5 88 24 6 5 1 6 3 2 2 6 86 23 3 4 7 2 2 2 3 3 83 22 0 2 5 0 1 (5)w i (4)t i (3)s i (2) τi (1) i (5)w i (4)t i (3)s i (2) τi (1) i 40 合 计 1 10 以上 1 9 1 8 2 7 2 6 3 5 6 4 8 3 10 2 6 1 次 数 到达间隔/分钟 41 合 计 1 9 以上 1 8 1 7 2 6 4 5 5 4 7 3 10 2 10 1 次 数 服务时间/分钟 到达间隔分布表 服务时间分布表 平均间隔时间 = 142 / 40 = 3.55 （分钟/人） 平均到达率 = 41 / 142 = 0.28 （人/分钟） 平均服务时间 = 127 / 41 = 3.12 （分钟/人） 平均服务率 = 41 / 127 = 0.32 （人/分钟） 二、泊松流 N(t)：在时间区间 [ 0，t ) 内到达的顾客数。 pn(t1, t2)：在时间区间 [ t1，t2 ) 内有 n 个顾客到达的概率。 当 pn(t1，t2) 合于下列三个条件时，称顾客到达形成泊松流： （1）在不相重叠的时间区间内顾客到达数是相互独立的。 （2）对充分小的△t，在时间区间[t，t + △t )内有 1 个顾客到达的概率与 t 无关，而约与区间长△t 成正比，即 排队 无限排队（等待制排队系统） 有限排队 损失制排队系统 混合制排队系统 K= 0 K= ∞ 3. 排队规则 先到先服务（FCFS）：按顾客到达的先后对顾客进行服务。 后到先服务（LCFS）：后到达的顾客先进行服务。如当需求发生时，总是先取出后存入仓库的货物，满足需求。 具有优先权的服务（PS）：服务台根据顾客的优先权进行服务，优先权高的先接受服务。如并未得患者应优先治疗；加急的信息应优先处理。 4. 服务机制 排队系统的服务机制主要包括： 服务员的数量及其连接形式（串联或并联）。 顾客是单个还是成批接受服务。 服务时间的分布。 上述因素中，服务时间分布更重要。 记某服务台的服务时间为V，其分布函数为 B(t)，密度函数为 b(t)，则常见的分布有： 定长分布（D）：每个顾客接受服务的时间是一个确定的常数。 负指数分布（M）：每个顾客接受服务的时间相互独立，具有相同的负指数分布： ，为一常数 k 阶爱尔朗分布（Ek）：每个顾客接受服务的时间服从 k 阶爱尔朗分布，其密度函数为： 当 k=1 时：爱尔朗分布即为负指数分布； 当 k 增加时：爱尔朗分布逐渐变为对称分布； 当 k 30 时：爱尔朗分布近似于正态分布； 当 k→∞时：爱尔朗分布为完全非随机分布。 由此可知：爱尔朗分布可看成是完全随机与完全非随机之间的分布，能更广泛地适应于现实世界。 D.G. Kendall提出了一种目前在排队轮中被广泛采用的“Kendall记号”来表示不同的排队模型，其形式为： 二、排队系统的符号表示 顾客相继到达时间间隔的分布 服务时间的分布 服务台的个数 系统的容量 顾客源的数目 服务规则 X / Y / Z / A / B / C 顾客相继到达时间间隔为负指数分布 服务时间为负指数分布 单个服务台 系统容量为无限 顾客源无限 先到先服务 M / M / 1 / ∞ / ∞ / FCFS X / Y / Z / ∞ / ∞ / FCFS X / Y /