重庆大学：《通信网络中的排队论基础》研究生课程（讲义）第1章排队论概论（编著：江禹生）.pdf_大学文库

第1章排队论概论 1.1排队系统概述 1.1.1排队论发展历程排队论(又称随机服务系统理论)是研究系统由于随机因素的干扰而出现排队(或拥塞)现象的规律性的一门学科,它适用于一切服务系统,包括通信系统、交通与运输系统、生产与服务系统、管理运筹系统和计算机系统等。可以说,凡是出现拥塞现象的系统,都属随机服务系统。排队论发展过程中产生过以下标志性事件: ①排队论源于电话服务理论的研究,1909年丹麦电话工程师 A.K. Erlang开创性论文“概率论和电话通话”的发表,标志排队论的诞生。 ②20世纪30年代法国的 E Pollaczek、苏联的 A Khinchine提出了有名的P-K ( Pollaczek Khinchin,朴拉切克一辛欣)均值公式,二人被称为排队论的先驱 ③第二次世界大战后,英国的 D.C Kendall系统地阐述排队问题,并利用嵌入马尔可夫链推动了排队论的进一步发展(1951年,1953年)。 ④排队论与存量理论、水库问题联系始于20世纪50年代末到60年代初。 ⑤20世纪60年代,近似法、排队上下限的研究成果开始应用于生产线、交通线 ⑥20世纪T0年代,用于计算机网络及通信,在排队研究中模拟技术继50年代后再度成为注意对象 ⑦20世纪80、90年代,排队论被进一步用于网络性能分析(如端到端流控等)。 ⑧计算机网络中排队分析的有效性依赖于数据通信量的泊松性质,这是排队分析的基础。归纳起来,排队论的发展基本上经历了三个阶段。在第二次世界大战以前,其研究多侧重于电话和远距离通信方面,这阶段发展较缓慢。第二次世界大战以后,由于排队论渗透到军事、经济、生产与服务、管理等多种部门,于是迎来了理论和应用的较大发展,使之成为运筹学和管理科学的一个热门分支。上个世纪70年代以来,随着计算机的不断更新和发展,通信网的建立和完善,信息科学、生命科学及控制理论的蓬勃发展均涉及到最优设计与最佳服务问题,从而使排队理论与应用获得质和量上飞速的发展。计算机通信网目前大都采用分组交换,数据信息是以分组为单位传送的,各分组到 438

438 第 1 章排队论概论 1.1 排队系统概述 1.1.1 排队论发展历程排队论（又称随机服务系统理论）是研究系统由于随机因素的干扰而出现排队（或拥塞）现象的规律性的一门学科，它适用于一切服务系统，包括通信系统、交通与运输系统、生产与服务系统、管理运筹系统和计算机系统等。可以说，凡是出现拥塞现象的系统，都属随机服务系统。排队论发展过程中产生过以下标志性事件： ① 排队论源于电话服务理论的研究，1909 年丹麦电话工程师 A.K.Erlang 开创性论文“概率论和电话通话”的发表，标志排队论的诞生。 ② 20 世纪 30 年代法国的 F.Pollaczek、苏联的 A.Khinchine 提出了有名的 P K （Pollaczek-Khinchin，朴拉切克－辛欣）均值公式，二人被称为排队论的先驱。 ③ 第二次世界大战后，英国的 D.C.Kendall 系统地阐述排队问题，并利用嵌入马尔可夫链推动了排队论的进一步发展（1951 年，1953 年）。 ④ 排队论与存量理论、水库问题联系始于 20 世纪 50 年代末到 60 年代初。 ⑤ 20 世纪 60 年代，近似法、排队上下限的研究成果开始应用于生产线、交通线。 ⑥ 20 世纪 70 年代，用于计算机网络及通信，在排队研究中模拟技术继 50 年代后再度成为注意对象。 ⑦ 20 世纪 80、90 年代，排队论被进一步用于网络性能分析（如端到端流控等）。 ⑧ 计算机网络中排队分析的有效性依赖于数据通信量的泊松性质，这是排队分析的基础。归纳起来，排队论的发展基本上经历了三个阶段。在第二次世界大战以前，其研究多侧重于电话和远距离通信方面，这阶段发展较缓慢。第二次世界大战以后，由于排队论渗透到军事、经济、生产与服务、管理等多种部门，于是迎来了理论和应用的较大发展，使之成为运筹学和管理科学的一个热门分支。上个世纪 70 年代以来，随着计算机的不断更新和发展，通信网的建立和完善，信息科学、生命科学及控制理论的蓬勃发展均涉及到最优设计与最佳服务问题，从而使排队理论与应用获得质和量上飞速的发展。计算机通信网目前大都采用分组交换，数据信息是以分组为单位传送的，各分组到

达网络节点(即分组交换机)进行存储转发的过程中,当多个分组要去往同一输出链路, 那么就要进行排队。计算机通信网就是一个大的排队系统,网内分组的到达是随机的、具有突发性的。我们可借助于排队论分析计算机通信网内分组的传输时延以及流量等问题。所以说排队论广泛应用于计算机通信领域,是计算机通信网的基础理论之一。网络排队模型是计算机网络设计、建模、性能分析和预测的有力工具。 1.1.2排队现象排队是日常生活和工作中常见的现象。例如顾客到商店购买物品,当售货员较少而顾客较多时就会岀现排队。车站和码头交通枢纽的车船堵塞和疏导、故障机器的停机待修、水库的存储调节等等都是有形或无形的排队现象。此时要求服务的数量超过服务机构(服务者)的容量,也就是说,到达的顾客不能立即得到服务,因而出现了排队现象。由于顾客到达和服务时间的随机性,可以说排队现象几乎是不可避免的。如果增添服务设备,就要增加投资或发生空闲浪费;如果服务设备太少,排队现象就会严重,对顾客个人和对社会都会带来不利影响。众所周知,一个电话系统的功能是按照用户(或顾客)需求在主叫用户与被叫用户之间提供通信路由(或称通信信道,也称话路)。如果在每一对电话用户之间提供条固定的通信路由,由于其成本接近天文数字,而不可能办到。为了解决这个问题,必须建立和保持通话的路由是“公用”的,即需要时选用,话毕时释放。这就隐含着这样一种可能性:由于某一时刻恰好没有空闲的路由可选用,这个呼叫就不能建立。亦即, 不可能真正做到随时都能“按需”实现任意双方用户之间的通信要求,存在着(系统的) “供”和(顾客的或用户的)“需”之间的矛盾。类似的问题不仅仅只限于电话系统, 在许多系统的设计中都存在类似的矛盾。表1.列举了一些例子说明现实中形形色色的排队系统。表1.1排队系统举例系统顾客要求服务内容服务机构修理厂不能运转的机器修理修理技工零配件库房修理技工领取修配零件发放修配零件的管理员电话呼叫通话交换机通信网信息包传输信道计算机网络存储转发分组交换机 439

439 达网络节点（即分组交换机）进行存储转发的过程中，当多个分组要去往同一输出链路，那么就要进行排队。计算机通信网就是一个大的排队系统，网内分组的到达是随机的、具有突发性的。我们可借助于排队论分析计算机通信网内分组的传输时延以及流量等问题。所以说排队论广泛应用于计算机通信领域，是计算机通信网的基础理论之一。网络排队模型是计算机网络设计、建模、性能分析和预测的有力工具。 1.1.2 排队现象排队是日常生活和工作中常见的现象。例如顾客到商店购买物品，当售货员较少而顾客较多时就会出现排队。车站和码头交通枢纽的车船堵塞和疏导、故障机器的停机待修、水库的存储调节等等都是有形或无形的排队现象。此时要求服务的数量超过服务机构（服务者）的容量，也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。由于顾客到达和服务时间的随机性，可以说排队现象几乎是不可避免的。如果增添服务设备，就要增加投资或发生空闲浪费；如果服务设备太少，排队现象就会严重，对顾客个人和对社会都会带来不利影响。众所周知，一个电话系统的功能是按照用户（或顾客）需求在主叫用户与被叫用户之间提供通信路由（或称通信信道，也称话路）。如果在每一对电话用户之间提供一条固定的通信路由，由于其成本接近天文数字，而不可能办到。为了解决这个问题，必须建立和保持通话的路由是“公用”的，即需要时选用，话毕时释放。这就隐含着这样一种可能性：由于某一时刻恰好没有空闲的路由可选用，这个呼叫就不能建立。亦即，不可能真正做到随时都能“按需”实现任意双方用户之间的通信要求，存在着（系统的） “供”和（顾客的或用户的）“需”之间的矛盾。类似的问题不仅仅只限于电话系统，在许多系统的设计中都存在类似的矛盾。表 1.1 列举了一些例子说明现实中形形色色的排队系统。表 1.1 排队系统举例系统顾客要求服务内容服务机构修理厂不能运转的机器修理修理技工零配件库房修理技工领取修配零件发放修配零件的管理员电话呼叫通话交换机通信网信息包传输信道计算机网络分组存储转发分组交换机

机场飞机起飞降落跑道医院病人诊断或动手术医生(或包括手术台) 水库上游河水进入水库放水,调整水位水闸管理员这些系统的共同特征是:顾客的到达以及要求服务的持续时间一般是随机发生且难以预测的。排队现象有的是以有形的形式出现,例如上下班坐公共汽车等,这种排队称为有形排队。而有的是以无形的形式出现,例如有许多顾客同时打电话到订购处订购车票,其中一个顾客正在通话时,其他顾客就不得不在各自的电话机旁等待,他们可能分散在各个地方,但却形成一个无形的队列等待通话,这种排队现象称为无形排队。排队系统也称为“随机服务系统”,排队论则相应地称为“随机服务系统理论”,它是为解决上述问题而发展起来的。排队论是研究拥挤现象的一门学科。 1.1.3排队系统的组成和特征排队过程的一般模型如图1.1所示。各个顾客由顾客源出发,到达服务机构(服务者)前排队等候接受服务,服务完了后就离开。排队结构指队列的数目和排列方式,排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。排队系统就是指图1.1中虚线所包含的部分顾客源到排队结构服务机构顾客离去输出排队规则服务规则排队系统图1.1排队过程的一般模型现实中的排队现象是多种多样的,对上面所说的“顾客”和“服务者”,要作广义地理解。它可以是人,也可以是非生物;队列可以是具体地排列,也可以是无形的(例如向电话交换要求通话的呼叫);顾客可以走向服务机构,也可以相反(如送货上门)。一般的排队系统都有三个基本组成部分:输入过程、排队规则、服务机构。现在分别说明各部分的特征。 1、输入过程输入过程是描述顾客来源及顾客是按怎样的规律到达排队系统,可能有下列各种不

440 机场飞机起飞降落跑道医院病人诊断或动手术医生（或包括手术台）水库上游河水进入水库放水，调整水位水闸管理员这些系统的共同特征是：顾客的到达以及要求服务的持续时间一般是随机发生且难以预测的。排队现象有的是以有形的形式出现，例如上下班坐公共汽车等，这种排队称为有形排队。而有的是以无形的形式出现，例如有许多顾客同时打电话到订购处订购车票，其中一个顾客正在通话时，其他顾客就不得不在各自的电话机旁等待，他们可能分散在各个地方，但却形成一个无形的队列等待通话，这种排队现象称为无形排队。排队系统也称为“随机服务系统”，排队论则相应地称为“随机服务系统理论”，它是为解决上述问题而发展起来的。排队论是研究拥挤现象的一门学科。 1.1.3 排队系统的组成和特征排队过程的一般模型如图 1.1 所示。各个顾客由顾客源出发，到达服务机构（服务者）前排队等候接受服务，服务完了后就离开。排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。排队系统就是指图 1.1 中虚线所包含的部分。排队结构服务机构顾客到达输入顾客离去输出排队规则服务规则顾客源排队系统图 1.1 排队过程的一般模型现实中的排队现象是多种多样的，对上面所说的“顾客”和“服务者”，要作广义地理解。它可以是人，也可以是非生物；队列可以是具体地排列，也可以是无形的（例如向电话交换要求通话的呼叫）；顾客可以走向服务机构，也可以相反（如送货上门）。一般的排队系统都有三个基本组成部分：输入过程、排队规则、服务机构。现在分别说明各部分的特征。 1、输入过程输入过程是描述顾客来源及顾客是按怎样的规律到达排队系统，可能有下列各种不

同情况,当然这些情况并不是彼此排斥的 ①顾客的总体(称为顾客源)的组成可能是有限的,也可能是无限的。上游河水流入水库可以认为总体是无限的,工厂内停机待修的机器显然是有限的总体。 ②顾客到来的方式可能是一个一个的,也可能是成批的。例如到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客,我们将只研究单个到来的情形。 ③顾客相继到达的间隔时间可以确定型的,也可以是随机型的。如在自动装配线上装配的各部件就必须按确定的时间间隔到达装配点,定期运行的班车、班机、班轮的到达也都是确定型的。但一般到商店购物的顾客、到医院诊病的病人、通过路口的车辆等,它们的到达都是随机型的。对于随机型的情形,要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布。相继到达的间隔时间顾客到达图12顾客到达排队系统的间隔时间 ④顾客的到达可以是相互独立的,就是说,以前的到达情况对以后顾客的到来没有影响,否则就是有关联的。例如,工厂内的机器在一个短的时间区间内出现停机(顾客到达)的概率就受已经待修或被修理的机器数目的影响。我们主要讨论的是相互独立的情形 ⑤输入过程可以是平稳的,或称对时间是齐次的,是指描述相继到达的间隔时间分布和所含参数(如期望值、方差等)都是与时间无关的,否则称为非平稳的。非平稳情形的数学处理是很困难的 2、排队规则排队规则是指服务允许不允许排队,顾客是否愿意排队。 ①顾客到达时,如所有服务者都正被占用,在这种情形下顾客可以随即离去,也可以排队等候。随即离去的称为即时制或称损失制,因为这将失掉许多顾客;排队等候的称为等待制。普通市内电话的呼唤属于前者。对于等待制,为顾客进行服务的次序接受可以采用下列各种规则:先到先服务,后

441 同情况，当然这些情况并不是彼此排斥的。 ① 顾客的总体（称为顾客源）的组成可能是有限的，也可能是无限的。上游河水流入水库可以认为总体是无限的，工厂内停机待修的机器显然是有限的总体。 ② 顾客到来的方式可能是一个一个的，也可能是成批的。例如到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客，我们将只研究单个到来的情形。 ③ 顾客相继到达的间隔时间可以确定型的，也可以是随机型的。如在自动装配线上装配的各部件就必须按确定的时间间隔到达装配点，定期运行的班车、班机、班轮的到达也都是确定型的。但一般到商店购物的顾客、到医院诊病的病人、通过路口的车辆等，它们的到达都是随机型的。对于随机型的情形，要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布。相继到达的间隔时间顾客到达时间           图 1.2 顾客到达排队系统的间隔时间 ④ 顾客的到达可以是相互独立的，就是说，以前的到达情况对以后顾客的到来没有影响，否则就是有关联的。例如，工厂内的机器在一个短的时间区间内出现停机（顾客到达）的概率就受已经待修或被修理的机器数目的影响。我们主要讨论的是相互独立的情形。 ⑤ 输入过程可以是平稳的，或称对时间是齐次的，是指描述相继到达的间隔时间分布和所含参数（如期望值、方差等）都是与时间无关的，否则称为非平稳的。非平稳情形的数学处理是很困难的。 2、排队规则排队规则是指服务允许不允许排队，顾客是否愿意排队。 ① 顾客到达时，如所有服务者都正被占用，在这种情形下顾客可以随即离去，也可以排队等候。随即离去的称为即时制或称损失制，因为这将失掉许多顾客；排队等候的称为等待制。普通市内电话的呼唤属于前者。对于等待制，为顾客进行服务的次序接受可以采用下列各种规则：先到先服务，后

到先服务,随机服务,有优先权的服务等。先到先服务(FCFS),即按到达次序接受服务,这是最通常的情形。后到先服务(LCFS),如乘用电梯的顾客常常是后进先出的。仓库中存放的厚钢板也是如此。在情报系统中,最后到达的信息往往是最有价值的,因而常采用后到先服务 (指被采用)的规则。随机服务,指服务者从等待的顾客中随机地选取其一进行服务,而不管到达的先后, 如电话交换台接通呼唤的电话就是如此。有优先权的服务,如医院对于病情严重的患者将给予优先治疗。 ②从占有的空间来看,对列可以排在具体的处所(如售票处、候诊室等),也可以是抽象的(如向电话交换机要求通话的呼唤)。由于空间的限制或其它原因,有的系统要规定容量(即允许进入排队系统的顾客数)的最大限;有的没有这种限制(即认为容量可以是无限的)。 ③从队列的数目看,可以是单列,也可以是多列。在多列的情形,各列间的顾客有的可以互相转移,有的不能(如用绳子或栏杆隔开)。有的排队顾客因等候时间过长而中途退出,有的不能退出(如高速公路上的汽车流),必须坚持到服务为止。我们只讨论各列间不能相互转移、也不能中途退出的情形。 3、服务机构刻划服务机构的主要方面为:一是服务者的数目;在多个服务者的情形下,是串联或是并联。二是顾客所需的服务时间服从什么样的概率分布,每个顾客所需的服务时间是否相互独立,是成批服务或是单个服务等。从机构形式和工作情形来看有以下几种情况。 ①服务机构可以没有服务者,也可以有一个或多个服务者(通道、窗口等)。例如, 在敞架售书的书店,顾客选书时就没有服务者,但交款时可能有多个服务者。在有多个服务者的情形中,它们可以是平行排列(并列)的,可以是前后排列 (串列)的,也可以是混合的。图13说明这些情形。单队一单服务者的情形多队一多服务者(并列)的情形: 442

442 到先服务，随机服务，有优先权的服务等。先到先服务（FCFS），即按到达次序接受服务，这是最通常的情形。后到先服务（LCFS），如乘用电梯的顾客常常是后进先出的。仓库中存放的厚钢板也是如此。在情报系统中，最后到达的信息往往是最有价值的，因而常采用后到先服务（指被采用）的规则。随机服务，指服务者从等待的顾客中随机地选取其一进行服务，而不管到达的先后，如电话交换台接通呼唤的电话就是如此。有优先权的服务，如医院对于病情严重的患者将给予优先治疗。 ② 从占有的空间来看，对列可以排在具体的处所（如售票处、候诊室等），也可以是抽象的（如向电话交换机要求通话的呼唤）。由于空间的限制或其它原因，有的系统要规定容量（即允许进入排队系统的顾客数）的最大限；有的没有这种限制（即认为容量可以是无限的）。 ③ 从队列的数目看，可以是单列，也可以是多列。在多列的情形，各列间的顾客有的可以互相转移，有的不能（如用绳子或栏杆隔开）。有的排队顾客因等候时间过长而中途退出，有的不能退出（如高速公路上的汽车流），必须坚持到服务为止。我们只讨论各列间不能相互转移、也不能中途退出的情形。 3、服务机构刻划服务机构的主要方面为：一是服务者的数目；在多个服务者的情形下，是串联或是并联。二是顾客所需的服务时间服从什么样的概率分布，每个顾客所需的服务时间是否相互独立，是成批服务或是单个服务等。从机构形式和工作情形来看有以下几种情况。 ① 服务机构可以没有服务者，也可以有一个或多个服务者（通道、窗口等）。例如，在敞架售书的书店，顾客选书时就没有服务者，但交款时可能有多个服务者。 ② 在有多个服务者的情形中，它们可以是平行排列（并列）的，可以是前后排列（串列）的，也可以是混合的。图 1.3 说明这些情形。单队—单服务者的情形：    1 多队—多服务者（并列）的情形：

待制系统; M/G/1/∞表示相继到达间隔时间为负指数分布,顾客所需的服务时间为独立、服从一般概率分布,系统中只有一个服务者,容量为无穷的等待制系统 GI/M/1/∞表示输入过程为顾客独立到达且相继到达的间隔时间服从一般概率分布,服务时间是相互独立、服从负指数分布,系统中只有一个服务台,容量为无穷的等待制系统; E/G/K表示相继到达的间隔时间独立、服从P阶爱尔朗分布,服务时间为独立服从一般概率分布,系统中只有一个服务者,容量为K(1≤K<∞)的混合制系统; D/M/c/K表示相继到达的间隔时间独立、服从定长分布,服务时间相互独立、服从负指数分布,系统中有c个服务者平行服务,容量为K(1≤K<∞)的混合制系统。 1.1.5排队问题的求解个实际问题作为排队问题求解时,首先要研究它属于哪个模型,其中只有顾客到达的间隔时间分布和服务时间的分布需要实测的数据来确定,其它因数都是在问题提出时给定的。解排队问题的目的,是研究排队系统运行的效率,估计服务质量,确定系统参数的最优值,以决定系统结构是否合理、研究设计改进措施等。所以必须确定用以判断系统运行优劣的基本数量指标,解排队问题就是首先求出这些数量指标的概率分布。这些指标通常是系统中的顾客数、逗留时间和忙期。 1、系统中的顾客数系统中的顾客数i是一个离散型随机变量。i的期望值记作N,称为系统平均顾客数系统中排队等待服务的顾客数(也是一个随机变量),它的期望值记作N,称为系统平均等待顾客数。系统中的顾客数=排队等待服务的顾客数十正在接受服务的顾客数一般情形,N,(或N)越大,说明服务率越低,排队成龙,是顾客最讨厌的。 2、逗留时间或花费时间逗留时间指一个顾客在系统中的停留时间,它是一个连续型随机变量,有时也称其为花费时间或系统时间。它的期望值记作W,称为顾客平均逗留时间。 445

445 待制系统； M G/ /1/表示相继到达间隔时间为负指数分布，顾客所需的服务时间为独立、服从一般概率分布，系统中只有一个服务者，容量为无穷的等待制系统； GI M/ /1/表示输入过程为顾客独立到达且相继到达的间隔时间服从一般概率分布，服务时间是相互独立、服从负指数分布，系统中只有一个服务台，容量为无穷的等待制系统； / /1/ EG K r 表示相继到达的间隔时间独立、服从 r 阶爱尔朗分布，服务时间为独立、服从一般概率分布，系统中只有一个服务者，容量为 K （1 K  ）的混合制系统； D/ // McK 表示相继到达的间隔时间独立、服从定长分布，服务时间相互独立、服从负指数分布，系统中有c个服务者平行服务，容量为 K （1 K  ）的混合制系统。 1.1.5 排队问题的求解一个实际问题作为排队问题求解时，首先要研究它属于哪个模型，其中只有顾客到达的间隔时间分布和服务时间的分布需要实测的数据来确定，其它因数都是在问题提出时给定的。解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理、研究设计改进措施等。所以必须确定用以判断系统运行优劣的基本数量指标，解排队问题就是首先求出这些数量指标的概率分布。这些指标通常是系统中的顾客数、逗留时间和忙期。 1、系统中的顾客数系统中的顾客数i 是一个离散型随机变量。i 的期望值记作 Ns ，称为系统平均顾客数。系统中排队等待服务的顾客数（也是一个随机变量），它的期望值记作 Nq ，称为系统平均等待顾客数。系统中的顾客数＝排队等待服务的顾客数＋正在接受服务的顾客数一般情形， Ns （或 Nq ）越大，说明服务率越低，排队成龙，是顾客最讨厌的。 2、逗留时间或花费时间逗留时间指一个顾客在系统中的停留时间，它是一个连续型随机变量，有时也称其为花费时间或系统时间。它的期望值记作Ws ，称为顾客平均逗留时间

重庆大学：《通信网络中的排队论基础》研究生课程（讲义）第1章 排队论概论（编著：江禹生）

重庆大学：《通信网络中的排队论基础》研究生课程（讲义）第1章排队论概论（编著：江禹生）