同情况,当然这些情况并不是彼此排斥的 ①顾客的总体(称为顾客源)的组成可能是有限的,也可能是无限的。上游河水 流入水库可以认为总体是无限的,工厂内停机待修的机器显然是有限的总体。 ②顾客到来的方式可能是一个一个的,也可能是成批的。例如到餐厅就餐就有单 个到来的顾客和受邀请来参加宴会的成批顾客,我们将只研究单个到来的情形。 ③顾客相继到达的间隔时间可以确定型的,也可以是随机型的。如在自动装配线 上装配的各部件就必须按确定的时间间隔到达装配点,定期运行的班车、班机、班轮的 到达也都是确定型的。但一般到商店购物的顾客、到医院诊病的病人、通过路口的车辆 等,它们的到达都是随机型的。对于随机型的情形,要知道单位时间内的顾客到达数或 相继到达的间隔时间的概率分布。 相继到达的间隔时间 顾客到达 图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 ，称为顾客平均逗留时间