运筹学教程课件七随机服务理论概述详解.ppt

?管理与人文学院 忻展红 1999，4 * 第七章 随机服务理论概述 确定型只是随机现象的特例 * 7.1 随机服务系统 系统的输入与输出是随机变量 A.k.Erlang 于1909~1920年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础 又称为排队论(Queuing Theory)或拥塞理论(Congestion Theory) * 与服务系统性能相关的特性 服务系统存在来自两个矛盾方面的要求 顾客希望服务质量好，如排队等待时间短，损失率低 系统运营方希望设备利用率高 给用户一个经济上能够承受的满意的质量 哪些系统特性会影响系统的性能？ 服务机构的组织方式与服务方式 顾客的输入过程和服务时间分布 系统采用的服务规则 7.1.1 服务机构的组织方式与服务方式 单台制和多台制 并联服务 串联服务 串并联服务、网络服务 全利用度、部分利用度 * 与服务系统性能相关的特性 7.1.2 输入过程和服务时间 顾客单个到达或成批到达 顾客到达时间间隔的分布和服务时间的分布 顾客源是有限的还是无限的 7.1.3 服务规则 损失制 等待制：先到先服务(FIFO)，后到先服务，随机服务，优先权服务 混合制 逐个到达，成批服务；成批到达，逐个服务 * 7.2 随机服务过程 单台服务系统、等待制、先到先服务 顾客在系统中的总时长：逗留时间=等待时长+服务时长 等待时长与顾客到达率和服务时长有关 * 当服务台连续不断服务时，有如下关系： wi+1+?i+1= wi+hi wi+hi 表示了累计的未完成的服务时长，一般地有 忙期和忙时 系统连续不断服务的时期称为忙期。而系统最繁忙的一个小时称为忙时。 排队系统的指标及其关系 1）Wq 、 Wd 分别是顾客的平均排队等待时间和平均逗留时间 2）Lq 、 Ld分别是系统平均排队的顾客数和系统的平均顾客数3）h 是顾客的平均服务时长，?是顾客的平均到达率。 4）Ln 是同时接受服务的平均顾客数(即平均服务台占用数) 5）Ld = ? Wd = ? (Wq + h ) = Lq + Ln ， Lq = ? Wq， Ln = ? h * 7.3 服务时间与间隔时间 7.3.1 概述 顾客的服务时间由于多种原因具有不确定性，最好的描述方法就是概率分布；同样顾客到达的间隔时间也具有一定的概率分布 服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验 经验分布一般采用直方图来表示，如下图 * 若统计区间分得越细，样本越多，则经验分布的轮廓越接近曲线 一般服务时间和间隔时间都是非负的连续实变量，令 h 代表服务时间，? 代表间隔时间，t 为给定的时间，则它们的概率分布函数分别表示为 F(t)=P{h? t} F(t)=P{? ? t} 它们的概率密度函数为 f(t)=F?(t)，具有性质： f(t)?0，? f(t)dt=1 服务时间落在区间(a, c)的概率为 　服务时间落在区间(t, t+?t)的概率为 P{t h ? t+?t}= f(t)?t 　平均服务时长和平均间隔时长 　平均服务时长的倒数为服务率，平均间隔时长的倒数为到达率 * 7.3.2 常用的概率分布 1、定长分布 流水线的加工时间 2、负指数分布 一类最常用的分布，如上述通话时长，可靠性 * 7.3.2 常用的概率分布 3、爱尔兰分布 一种代表性更广的分布 k 为整数，称为 k 阶爱尔兰分布；当 k=1 时，退化为负指数分布；k?? 时趋向定长分布 爱尔兰分布实际上是 k 个独立同分布的负指数分布随机变量的和的分布，即 k 个服务台的串联，每个服务台的平均服务时长为 1/k? * 7.3.3 负指数分布的特点 负指数分布之所以常用，是因为它有很好的特性，使数学分析变得方便 无记忆性。指的是不管一次服务已经过去了多长时间，该次服务所剩的服务时间仍服从原负指数分布 * 7.3.3 负指数分布的特点 一个服从负指数分布的服务，在下一瞬间结束的概率 在 ?t 内服务终结的概率只与 ? 和 ?t 成正比，与 t0 无关；因此 ? 又称为终结率，或离去率 同理，在 ?t 内服务不终结的概率为 1–? ?t +o(?t ) n 个独立同分布(负指数)的服务台同时被占用，在 ?t 内只有一个服务台终结的概率为 在 ?t 内有 k 1 个服务台终结的概率为 o(?t )，称为普通性 * 7.4 输入过程 即顾客到达的分布，可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述 间隔时间服从定长分布 单位时间内到达的顾客数服从波松分布(