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

重庆大学研究生讲义 通信网络中的排队论基础 大 t929 G U 江禹生编著 O一八年九月

I 重庆大学研究生讲义 通信网络中的排队论基础 江禹生 编著 二 O 一八年九月

目录 第1章排队论概论 1.1排队系统概述 1.1.1排队论发展历程 1.1.2排队现象 1.1.3排队系统的组成和特征 1.14经典排队系统的符号表示 1.1.5排队问题的求解 12几个重要的概率分布 121定长分布 122负指数分布 123爱尔郎( Erlang)分布 124泊松( Poisson)分布 13泊松过程 14单服务者负指数分布排队系统的分析 141系统中有个i顾客的概率 142系统的运行指标 15 Little公式及其直观意义 15.1 Little公式直观意义 152 Little公式的证明 16利用因数P的定义及其物理意义

II 目 录 第 1 章 排队论概论 1.1 排队系统概述 1.1.1 排队论发展历程 1.1.2 排队现象 1.1.3 排队系统的组成和特征 1.1.4 经典排队系统的符号表示 1.1.5 排队问题的求解 1.2 几个重要的概率分布 1.2.1 定长分布 1.2.2 负指数分布 1.2.3 爱尔郎（Erlang）分布 1.2.4 泊松（Poisson）分布 1.3 泊松过程 1.4 单服务者负指数分布排队系统的分析 1.4.1 系统中有个i 顾客的概率 1.4.2 系统的运行指标 1.5 Little 公式及其直观意义 1.5.1 Little 公式直观意义 1.5.2 Little 公式的证明 1.6 利用因数  的定义及其物理意义

第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 多队—多服务者（并列）的情形：

单队一多服务者(并列)的情形 → 多服务者(串列)的情形 口…四 多服务者(混合)的情形 今 图13排队队列与服务者 ③服务方式可以对单个顾客进行,也可以对成批顾客进行,公共汽车对站台等候 的顾客就成批进行服务。我们将只研究单个单个地服务方式。 ④和输入过程一样,服务时间也分确定型的和随机型的。自动冲洗汽车的装置对 每辆汽车冲洗(服务)的时间就是确定型的,但大多数情形的服务时间是随机型的。对 于随机型的服务时间,需要知道它的概率分布。 如果输入过程,即相继到达的间隔时间,和服务时间二者都是确定型的,那么问题 就太简单了。因此,在排队论中所讨论的是二者至少有一个是随机型的情形 ⑤和输入过程一样,服务时间的分布我们总是假定是平稳的,即分布的期望值 方差等参数都不受时间的影响 1.14经典排队系统的符号表示 个排队系统是由许多条件决定的,为了简明起见, D KEndal在1953年提出一 个分类方法,按照上述各部分的特征中最主要的、影响最大的三个,即 443

443    1    2    c   单队—多服务者（并列）的情形： 1 2 c     多服务者（串列）的情形：    1    2     c 多服务者（混合）的情形： 1    1 2 3    2 图 1.3 排队队列与服务者 ③ 服务方式可以对单个顾客进行，也可以对成批顾客进行，公共汽车对站台等候 的顾客就成批进行服务。我们将只研究单个单个地服务方式。 ④ 和输入过程一样，服务时间也分确定型的和随机型的。自动冲洗汽车的装置对 每辆汽车冲洗（服务）的时间就是确定型的，但大多数情形的服务时间是随机型的。对 于随机型的服务时间，需要知道它的概率分布。 如果输入过程，即相继到达的间隔时间，和服务时间二者都是确定型的，那么问题 就太简单了。因此，在排队论中所讨论的是二者至少有一个是随机型的情形。 ⑤ 和输入过程一样，服务时间的分布我们总是假定是平稳的，即分布的期望值、 方差等参数都不受时间的影响。 1.1.4 经典排队系统的符号表示 一个排队系统是由许多条件决定的，为了简明起见，D.G.Kendall 在 1953 年提出一 个分类方法，按照上述各部分的特征中最主要的、影响最大的三个，即

①相继顾客到达间隔时间的分布; ②服务时间的分布 ③服务者个数。 按照这三个特征分类,并用一定符号表示,称为 Kendall记号。这只对并列的服务 者(如果服务者是多于一个的话)的情形,他用的符号形式是: X/Y/Z 其中X处填写表示相继到达间隔时间的分布; F处填写表示服务时间的分布; Z处填写并列的服务者的数目。 表示相继到达间隔时间和服务时间的各种分布的符号是: M一一负指数分布(M是 Markov的字头,因为负指数分布具有无记忆性,即 Markov性); D一一确定型; E—F阶爱尔朗分布; G-一一般相互独立的时间间隔的分布; 般服务时间的分布。 例如,M/M/表示相继到达间隔时间为负指数分布,服务时间为负指数分布,单 服务者的模型;D/M/m表示确定的到达时间间隔,服务时间为负指数分布,m个平行 服务者(但顾客是一对)的模型。 在1971年一次关于排队论符号标准化会议上决定,将 Kendall符号扩充成为 X/Y/Z/A/B/C形式,其中前三项意义不变,而 A处填写系统容量限制N; B处填写顾客源数目C; C处填写服务规则,如先到先服务FCFS,后到先服务LCFS等。 即,到达过程/服务过程/服务者数/系统最大(缓冲)容量顾客源数/服务规则 并约定,如略去后三项,即指X/Y/Z/∞/∞/FCFS的情形。在本课程中只讨论先 到先服务FCFC的情形,所以略去第六项。 例如,MM/Cc/∞表示相继到达间隔时间为负指数分布,服务时间服从负指数分布, 系统有c个服务者平行服务(0<c≤∞),系统容量为无穷,于是M/M/c/∞系统是等 444

444 ① 相继顾客到达间隔时间的分布； ② 服务时间的分布； ③ 服务者个数。 按照这三个特征分类，并用一定符号表示，称为 Kendall 记号。这只对并列的服务 者（如果服务者是多于一个的话）的情形，他用的符号形式是： X /Y / Z 其中 X 处填写表示相继到达间隔时间的分布； Y 处填写表示服务时间的分布； Z 处填写并列的服务者的数目。 表示相继到达间隔时间和服务时间的各种分布的符号是： M ——负指数分布（ M 是 Markov 的字头，因为负指数分布具有无记忆性，即 Markov 性）； D ——确定型； Er —— r 阶爱尔朗分布； GI ——一般相互独立的时间间隔的分布； G ——一般服务时间的分布。 例如，M / M /1表示相继到达间隔时间为负指数分布，服务时间为负指数分布，单 服务者的模型；D/ / M m表示确定的到达时间间隔，服务时间为负指数分布，m 个平行 服务者（但顾客是一对）的模型。 在 1971 年一次关于排队论符号标准化会议上决定，将 Kendall 符号扩充成为： X /Y / Z / A/ B /C 形式，其中前三项意义不变，而 A处填写系统容量限制 N ； B 处填写顾客源数目 c ； C 处填写服务规则，如先到先服务 FCFS，后到先服务 LCFS 等。 即，到达过程/服务过程/服务者数/系统最大（缓冲）容量/顾客源数/服务规则 并约定，如略去后三项，即指 X /Y / Z /  /  / FCFS的情形。在本课程中只讨论先 到先服务 FCFC 的情形，所以略去第六项。 例如，M / // M c  表示相继到达间隔时间为负指数分布，服务时间服从负指数分布， 系统有c个服务者平行服务（0   c ），系统容量为无穷，于是 M / // M c  系统是等

待制系统; 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 ，称为顾客平均逗留时间