现代通信网络中的随机过程_第二章_排队论基础.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.19M 资料格式：pdf 举报版权申诉

littlechenlin-7354711-_排队论基础.pdf-第1页.png

第1页 / 共24页

littlechenlin-7354711-_排队论基础.pdf-第2页.png

第2页 / 共24页

littlechenlin-7354711-_排队论基础.pdf-第3页.png

第3页 / 共24页

littlechenlin-7354711-_排队论基础.pdf-第4页.png

第4页 / 共24页

littlechenlin-7354711-_排队论基础.pdf-第5页.png

第5页 / 共24页

littlechenlin-7354711-_排队论基础.pdf-第6页.png

第6页 / 共24页

littlechenlin-7354711-_排队论基础.pdf-第7页.png

第7页 / 共24页

littlechenlin-7354711-_排队论基础.pdf-第8页.png

第8页 / 共24页

文本预览

现代通信网络中的排队理论第 2 章排队论基础 2.1 概述排队论所讨论的是一个系统对一群体提供某种服务时该群体占用此服务时所呈现的状态。在界定排队问题中，必须交代清楚的事项包括： 1．群体到达系统的情况； 2．系统对群体中各分子提供服务时化去的时间的长短； 3．系统提供服务的先后次序。到达系统的个体称作“顾客”，提供服务的系统可由一个或者一个以上的“服务台”组成，“服务时间”相当于顾客占用服务台的时间，而服务台对顾客提供服务的次序称作“排队规则”。服务系统的状态通常是以停留在服务系统上的顾客数量来表示，这个数量称作“队列长度”或者简称为“队长”。有时也以顾客停留在系统上的时间表示，这段时间称作“等待时间”，等待时间由两部分组成，其一为顾客等候使用服务台的“延误时间”，其二为占用服务台的时间，也即“服务时间”。在各种排队系统中，随机性是它们的一个共同特性，而且起着根本性的作用。顾客的到达间隔时间与顾客所需的服务时间中，至少有一个具有随机性，否则问题就太简单了。排队论主要研究描述系统的一些主要指标的概率特性，分为三大部分： 1．排队系统的性态问题研究排队系统的性态问题就是研究排队系统的概率规律，主要包括系统的队长（系统中的顾客数）、顾客的延误时间和等待时间、以及忙期等的概率分布，包括它们的瞬时性质和统计平衡下的性态。排队系统的性态问题是 79

第 2 章排队论基础排队论研究的核心，是排队系统的统计推断和最优化问题的基础。从应用方面考虑，统计平衡下的各个指标的概率性质尤其重要。 2．排队系统的统计推断为了了解和掌握一个正在运行的排队系统的规律，就需要通过多次观测、搜集数据，然后用数理统计的方法对得到的数据进行加工处理，推断出所观测的排队系统的概率规律，从而应用相应的理论成果来研究和解决该排队系统的有关问题。排队系统的统计推断是已有理论成果应用实际系统的基础性工作，结合排队系统的特点，发展这类特殊随机过程的统计推断方法是非常必要的。 3．排队系统的最优化问题排队系统的最优化包括系统的最优设计（静态最优）和已有系统的最优运行控制（动态最优），前者是在服务系统设置之前，对未来运行的情况有所估计，使设计人员有所依据，例如电话局的规模、水库容量的大小、机场跑道数目的设计等；后者是对已有的排队系统寻求最优运行策略，例如库房领取工具，当排队领取工具的工人太多，就增设服务员，这样虽然增加了服务费用，但另一方面却减少了工人领取工具的等待时间，即增加了工人有效的生产时间，这样带来的好处可能远超过服务费用的增加。因此，对一个排队系统的设计或运行管理，就需要考虑顾客与服务双方的利益，以便在某种合理的指标上使系统达到最优化。对大多数实际系统来说，若把输入看作是由客观条件决定的，不受控制（有时也可采取控制输入的手段），则解决这种问题的关键是确定服务率或服务台数或选取顾客的服务规则或这几种量的组合，使之在某种意义下系统达到最优。优化的指标函数可以是时间，也可以是费用或收入。学习和应用排队论知识就是解决客观系统的最优设计或运行管理，创造更好的经济效益和社会效益。描述排队系统的主要数量指标有： 80

现代通信网络中的排队理论 1．队长与等待队长队长是指在系统中的顾客数（包括正在接受服务的顾客），而等待队长是指系统中排队等待的顾客数，它们都是随机变量，是顾客和服务机构双方都十分关心的数量指标，应确定它们的分布及有关矩（至少是期望平均值）。显然，队长等于等待队长加上正在被服务的顾客数。 2．顾客在系统中的延误时间与等待时间顾客的延误时间是指从顾客进入系统的时刻起直到开始接受服务止这段时间，而等待时间是顾客在系统中的延误时间与服务时间之和。在假定到达与服务是彼此独立的条件下，延误时间与服务时间是相互独立的。延误时间与等待时间是顾客最关心的数量指标，应用中关心的是统计平衡下它们的分布及期望平均值。 3．系统的忙期与闲期从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲，这段时间是系统连续繁忙的时间，我们称为系统的忙期，它反映了系统中服务台的工作强度。与忙期对应的是系统的闲期，即系统连续保持空闲的时间长度。在排队系统中，统计平衡下忙期与闲期是交替出现的。而忙期循环是指相邻的两次忙期开始的间隔时间，显然它等于当前的忙期长度与闲期长度之和。 4．离去过程离去过程是指接受服务完毕的顾客相继离开系统的过程。刻画一个离去过程的主要指标是相继离去的间隔时间和在一段已知时间内离去顾客的数目，这些指标从一个侧面也反映了系统的工作效率。此外，在不同的排队系统中，还会涉及到其它数量指标，例如在损失制与混合制排队系统中，顾客的损失率及单位时间内损失的平均顾客数，在多 81

第 2 章排队论基础服务台并行服务的系统中，某个时刻正在忙的服务台数目，以及系统的利用率等。 2.2 排队问题的界定要说明一个排队问题，必须了解顾客到达的过程、服务时间、排队规则以及服务系统的结构。到达过程通常可用两个连续到达时刻的间隔，或简称为“到达间隔”来表示，单位时间内平均到达的个数称作“到达率”，其值等于平均到达间隔的倒数。一、到达过程到达过程的形式可以是下列任何一种。 1．规则到达也就是每隔一固定的时间就有一个顾客到达。这类到达间隔在实际问题上并不常见。在自动化生产线上，有时进料问题可以是这种形式的到达过程。 2．完全随机到达又称泊松到达过程。到达间隔为指数分布，各个间隔为相同分布而互相独立的随机变量。这种形式具有的特性往往使得数学推演极为简单，同时在应用方面也颇符合实际，因此也是最为普遍采用的形式。 3．一般相同而独立的到达或称更新到达过程。这类形式比之第二类较具一般性，各个到达间隔为相互独立、相同分布的随机变量，但是不一定是指数分布。在正常情形下，机器的故障发生常常用这类假设，连续两次故障间隔即为一到达间隔。 4．成批到达前述三类到达都是先假定一次只有一个顾客到达服务系统，在实例中却不乏成批到达的情形。工厂、商店进货通常总是一次到达许多件。有时虽然 82

现代通信网络中的排队理论一次仅有一个顾客到达，但是在极短的时间内有多个到达时也可以看成是成批到达。至于到达的批量可以为常数，也可以是随机变量。 5．非平稳性到达在某些情形下，到达频率可以因时而异。最常见的实例是交通问题和电话通讯问题。上下班时车辆拥挤，而上班时间电话使用频率也较高，在数学模型里这类问题都假设为到达率是时间的函数。 6．依态到达到达率也可以因服务系统的状态而定。生意清淡的饭店难以吸引顾客，高朋满座的地方也会使人不耐久候而转往他家，在这些情况下，到达率都和队列长度有关。有时也因延误时间长短而定，高朋满座的饭店如果座位极多，那么懂得排队论概念的人就知道饭店的队列虽长，但是因为(服务台座位) 多，那么延误时间就会比较短，只须稍候片刻就极可能挨到座位。 7．连续到达上面列举的各类都是假设顾客到达数是离散可数的，在有些排队问题（如水库管理）里到达却是一个连续变量，有时为了方便起见，我们也可以把离散的假定为连续到达，以简化计算或推演求解，明显的例子是大都市车辆在马路上川留不息，由于数量庞大，有时可当作流体来处理。二、服务时间服务时间的类别也有多种，通常是以服务时间长度的分布来表示。平均服务时间的倒数称作“服务率”，也可视作服务台在被占用期间，单位时间内可以完成服务的平均次数。到达率与服务率之间的关系是度量服务系统负荷量的重要指标。服务时间的分布见概率论常见概率分布。三、排队规则 1．先到先占先到服务台的顾客有优先占用服务台的权利。这是最常见的一种排队规 83

第 2 章排队论基础则。 2．后到先占后到服务台的顾客有优先占用服务台的权利。后到先占的安排尚可进一步分为“抢占”与“非抢占”两种，“抢占”是指后来者可以即刻占用服务台（不论服务台是否已被占用），“非抢占”是指后来者必须等到目前占用者完成服务离开服务台后才能占用。这多用于存货系统的盘存以及在某些情况下计算机内部的调度（堆栈），在一般排队问题上极为少见。 3．优先占用到达服务台的顾客可以分成数类，每一类都有不同的占用优先权，优先权高者先占用服务台。和后到先占相同的是，也可以分为抢占与非抢占，在允许抢占的情形下，被抢占的顾客再度占用服务台时，通常假设服务由上次中断处继续下去，这种情形称作“续接”；但有时却得重新开始，这时称作“重复”。重复开始的服务时间可以与上一次相同，也可以不同。优先占用在排队问题上有一个重要应用，通过优先权的安排可以使得服务系统操作成本降低。 4．循环占用在允许优先占用时，可以证明对需要服务时间短的给予高优先权的方式是减少平均等待时间的好办法。但是在实际问题上有时无法预知服务时间的长短，这种情形可用循环占用的方法来弥补。所谓循环占用，是让每一顾客有权占用服务台一固定时间，假设为Δ，如果过了Δ时刻服务仍未终止，那么占用者就移至队列的末端等候再度轮到自己占用服务台。这个办法对于需要服务时间短的顾客提供较早完成使用服务台的机会。当Δ→∞时，循环占用对使用服务台的顾客不具有任何限制， 84

现代通信网络中的排队理论此时排队规则就等于先到先占。循环占用在两种情况下不便使用，一种是服务过程不能中断的情形，如医院的手术台，救火的消防车；另一种情形是每次被抢占时接续成本太高，如生产线上更换工具化时太多的情形下，就不应当常替换产品的种类。 5．共同占用所有在服务系统上的顾客同时占用服务台，如果有 n 个顾客占用，那么每个顾客只使用服务台的 n-1 容量，如果服务率为μ，那么每个顾客所享有的服务率就变成μ/n。共同占用是循环占用Δ→0 时的极限状态。 6．占而不用在某些情形下，服务台可以被占用，但是并不提供任何服务，占有服务台的顾客自己不使用服务台，也不让其他人使用。这种现象的发生至少有两种情况：第一种是除去服务台之外，顾客尚需别种资源才能进行服务活动，例如物件加工不但需要机器，也要工人，当工人离开机器时，作为服务台的机器，就被加工物件（顾客）占而不用了；第二种情况发生于“纵列队列”的排队问题，假定顾客先后使用两个服务台，而这两个服务台之间仅有有限的空间，那么当第一个服务台上的顾客在完成服务后能否加入第二个服务台的等候队列就完全决定于第二个队列的长度。如果第二个队列的长度已挤满了两个服务台之间的空间时，那么在第一个服务台上的这个顾客因为无处可去，只能占据服务台而等到第二个队列空出一个位子之后才能离开第一个服务台，在该顾客加入第二个队列之前就形成占而不用的情形。这种情形常见于流水线生产线上。在数学上，占而不用是相当难处理的问题，目前还不存在简单的解。四、服务系统结构 85

第 2 章排队论基础排队问题依其服务台的数目以及队列的组成来区分，有下列几种： 1．单一服务台系统系统仅有一个服务台。如图所示，方块代表服务台而圆圈代表顾客，箭头表示顾客流动的方向。图 2.1 单一服务台系统 2．多道服务台系统系统中有数个完全相同的服务台（假定为 n 个），到达的顾客可以使用其中任何一个服务台。如下图所示。图 2.2 多道服务台系统如果到达者只排一个队列，那么在服务台全被占满时，该服务系统的排队情形就近似于单一服务台系统，如果每个服务台的服务率为μ，队列的随机行为接近单一服务台以服务率 nμ的随机行为。假定到达这被依次安排去不同的服务台，那么服务系统就有 n 个队列，每个队列的随机行为完全相同，整个服务系统就如同 n 个单一服务台系统，如果到达率为λ，则每个单一服务台的到达率就是λ/n。 86

分享到：

赞收藏

资料库

现代通信网络中的随机过程_第二章_排队论基础.pdf

相关推荐

课程资源

热门标签

最新资料