在生产和日常生活中，经常可以碰到各种各样的服 务系统。如上下班乘公共汽车，公共汽车与乘客构成 个服务系统：到商店买东西，售货员与顾客也构成一个 服务系统，都有等候服务的问题。 有些场合下，服务系统的构成没有那么明显。如从 长春往北京打电话，由于长春、北京之间同一时间内允 许通话对数是有限的，因此，要求通话的人数超过这个 限度时，就要排队等候。虽然打电话的人分散在全市各 处，彼此互不见面，但他们与长话台一起构成一个服务 系统。他们在长话台前排成一个无形的队伍，就如同排 队等候公共汽车的乘客队伍一样。 般在一个排队服务系统中总是包含一个或若干个 “服务设施”，有许多“顾客”进入该系统要求得到服 务，服务完毕后即自行离去。倘若顾客到达时，服务系 统空闲着，则到达的顾客立即得到服务，否则顾客将排 队等待服务或离去
§1 排队服务系统的基本概念 ◼ 在生产和日常生活中，经常可以碰到各种各样的服 务系统。如上下班乘公共汽车，公共汽车与乘客构成一 个服务系统；到商店买东西，售货员与顾客也构成一个 服务系统，都有等候服务的问题。 ◼ 有些场合下，服务系统的构成没有那么明显。如从 长春往北京打电话，由于长春、北京之间同一时间内允 许通话对数是有限的，因此，要求通话的人数超过这个 限度时，就要排队等候。虽然打电话的人分散在全市各 处，彼此互不见面，但他们与长话台一起构成一个服务 系统。他们在长话台前排成一个无形的队伍，就如同排 队等候公共汽车的乘客队伍一样。 ◼ 一般在一个排队服务系统中总是包含一个或若干个 “服务设施” ，有许多“顾客”进入该系统要求得到服 务，服务完毕后即自行离去。倘若顾客到达时，服务系 统空闲着，则到达的顾客立即得到服务，否则顾客将排 队等待服务或离去
如在用自动机床进行生产的车间，一个工人往往要看若干 台机床，当机床发生故障或要求加料、更换刀具时，要求 工人进行修理或照管。在同一时间内，一个工人只能在 台机床上修理或照管，如这时又有别的机床需要该工人修 理或照管，就必须等待。这样，工人与需要修理或照管的 机床之间就构成了一个服务系统，这里工人是“服务设 施”，“顾客”是要求修理或照管的机床。又如，一 座水 库，上游的水滚滚而来，如果调节得好，水库水位保持在 安全理想水平，既起到防洪作用，又保证正常发电、航运 和灌溉。如调节不好，水库水位过高或过低，就影响水库 综合效能的发挥。这里，水库与水构成一个服务系统，水 库是“服务设施”，水就是要求得到服务的“顾客” 类似例子还可以举出很多，如医院和等待诊治的病人； 机场跑道同要求起飞降落的飞机；港口泊位与进港待泊的 船只；车站售票口与排队买票的旅客之间都构成了一个个 排队服务系统
上面说的“顾客”是对要求得到服务的对象的代称， 可以是人，也可以是物； “服务设施” 也可以各种各样。 如在用自动机床进行生产的车间，一个工人往往要看若干 台机床，当机床发生故障或要求加料、更换刀具时，要求 工人进行修理或照管。在同一时间内，一个工人只能在一 台机床上修理或照管，如这时又有别的机床需要该工人修 理或照管，就必须等待。这样，工人与需要修理或照管的 机床之间就构成了一个服务系统，这里工人是“服务设 施” ， “顾客”是要求修理或照管的机床。又如，一座水 库，上游的水滚滚而来，如果调节得好，水库水位保持在 安全理想水平，既起到防洪作用，又保证正常发电、航运 和灌溉。如调节不好，水库水位过高或过低，就影响水库 综合效能的发挥。这里，水库与水构成一个服务系统，水 库是“服务设施” ，水就是要求得到服务的“顾客” 。 类似例子还可以举出很多，如医院和等待诊治的病人； 机场跑道同要求起飞降落的飞机；港口泊位与进港待泊的 船只；车站售票口与排队买票的旅客之间都构成了一个个 排队服务系统
服务设施用在母个顾客身上的服务时间世是固定的，就 象工厂流水生产线的生产那样有固定的节拍，那么这类服 务系统的设计计算是比较方便的。但在大多数的服务系统 中，情况不是这样，顾客的到达经常是随机的，并且服务 设施用于每个顾客身上的服务时间往往也是随机的，对于 这样一类随机服务系统的设计计算就要困难得多。 车站的售票口应开设多少个比较合适呢？开设越多， 方便旅客，减少排队时间，但售票口增多了，就要增加服 务人员及相应的设施，增加服务费用。这样，顾客排队时 间的长短与服务设施规模的大小就构成设计随机服务系统 的一对矛盾。有些场合下，如公共汽车的班次可以随季节 及顾客到达规律的变化进行调整，但另一些场合，服务设 施的规模，如机场跑道、港口泊位、电话线路等一旦建成 则变动不易，因此需要有一个进行设计计算遵循的理论依 据。到底怎样才能做到既保证一定的服务质量指标，又使 服务设施费用经济合理，恰当地解决顾客排队时间与服务
如果到达服务系统的顾客完全按固定的间隔时间到达， 又服务设施用在每个顾客身上的服务时间也是固定的，就 象工厂流水生产线的生产那样有固定的节拍，那么这类服 务系统的设计计算是比较方便的。但在大多数的服务系统 中，情况不是这样，顾客的到达经常是随机的，并且服务 设施用于每个顾客身上的服务时间往往也是随机的，对于 这样一类随机服务系统的设计计算就要困难得多。 车站的售票口应开设多少个比较合适呢？开设越多， 方便旅客，减少排队时间，但售票口增多了，就要增加服 务人员及相应的设施，增加服务费用。这样，顾客排队时 间的长短与服务设施规模的大小就构成设计随机服务系统 的一对矛盾。有些场合下，如公共汽车的班次可以随季节 及顾客到达规律的变化进行调整，但另一些场合，服务设 施的规模，如机场跑道、港口泊位、电话线路等一旦建成 则变动不易，因此需要有一个进行设计计算遵循的理论依 据。到底怎样才能做到既保证一定的服务质量指标，又使 服务设施费用经济合理，恰当地解决顾客排队时间与服务
排队论的理论起源于对电话服务系统的研究。从1909 年开始，丹麦的电话工程师爱尔朗(A.K.Eelang)等人在 这方面进行了长期的工作，取得了最早的成果。以后排队 论陆续应用于陆空交通、机器管理、水库设计和可靠性理 论等方面。六十年代，随着电子计算机蓬勃发展的需要， 又应用于计算机网络的最优设计。在接近九十年的历史中 排队论无论在理论或应用上都有了飞速进展。由于在电子 计算机上进行数字模拟技术的发展，排队论已成为解决工 程设计和管理问题的有力工具
设施费用大小这对矛盾，就是研究随机服务系统的理论— —排队论所要研究解决的问题。 排队论的理论起源于对电话服务系统的研究。从1909 年开始，丹麦的电话工程师爱尔朗（A.K.Eelang）等人在 这方面进行了长期的工作，取得了最早的成果。以后排队 论陆续应用于陆空交通、机器管理、水库设计和可靠性理 论等方面。六十年代，随着电子计算机蓬勃发展的需要， 又应用于计算机网络的最优设计。在接近九十年的历史中， 排队论无论在理论或应用上都有了飞速进展。由于在电子 计算机上进行数字模拟技术的发展，排队论已成为解决工 程设计和管理问题的有力工具
现实中的排队现象是多种多样的， 般排队系统都有 下述三个基本组成部分（图10-1） 顾客源 顾客到来 排队结构 服务规则 服务机构 离去 排队规厕 排队系统 图10-1 1.输入过程 指顾客到达服务系统情况 (1)顾客总体（顾客源）的组成可能是有限的，也可能 是无限的。上游河水流入水库可以认为总体是无限的：工 内停机待修的机器，显然是有限的总体。 (2)顾客相继到达的时间间隔可以是确定的，也可以是 随机的。如自动装配线上装配的各部件一般按确定的时间 间隔到达装配点；但到医院就诊的病人，到餐厅就餐的顾
1.1 排队系统 ◼ 现实中的排队现象是多种多样的，一般排队系统都有 下述三个基本组成部分（图10-1）。 顾客源 顾客到来 排队规则 排队结构 服务规则 服 务 机 构 离去 排队系统 图10-1 1.输入过程——指顾客到达服务系统情况。 ⑴顾客总体（顾客源）的组成可能是有限的，也可能 是无限的。上游河水流入水库可以认为总体是无限的；工 厂内停机待修的机器，显然是有限的总体。 ⑵顾客相继到达的时间间隔可以是确定的，也可以是 随机的。如自动装配线上装配的各部件一般按确定的时间 间隔到达装配点；但到医院就诊的病人，到餐厅就餐的顾
顾客的到达万式可能是 批的。我们将只研究单个到达的情形。 2.排队规则 (1)顾客到达时，如果所有服务台都被占用，则顾客 离开服务系统，这种方式称为即时制或损失制。例如旅 客到旅店住宿就属于这种方式。另外一种情形，当服务 合被占用时，后来的顾客就排队等待服务，称为等待制 (2)有的服务系统对进入排队系统的顾客数有一定限 制，象理发店供等待服务的顾客坐的椅子的座位数是有 限的。大多数服务系统可以认为系统对顾客是没有限制 的。 (3)在多服务台情况下，队列的数目可以是单列，也 可以是多列。 (4)等待服务的次序，最常见的是先到先服务；还有 带优先权的服务，如加急电报、医院的急诊等；随机服 务，指服务台随机对等待的顾客进行服务；后到先服务 如乘坐电梯的顾客先入后出，后入先出
客等，他们的到达都是随机的。 ⑶顾客的到达方式可能是一个一个的，也可能是成 批的。我们将只研究单个到达的情形。 2.排队规则 ⑴顾客到达时，如果所有服务台都被占用，则顾客 离开服务系统，这种方式称为即时制或损失制。例如旅 客到旅店住宿就属于这种方式。另外一种情形，当服务 台被占用时，后来的顾客就排队等待服务，称为等待制。 ⑵有的服务系统对进入排队系统的顾客数有一定限 制，象理发店供等待服务的顾客坐的椅子的座位数是有 限的。大多数服务系统可以认为系统对顾客是没有限制 的。 ⑶在多服务台情况下，队列的数目可以是单列，也 可以是多列。 ⑷等待服务的次序，最常见的是先到先服务；还有 带优先权的服务，如加急电报、医院的急诊等；随机服 务，指服务台随机对等待的顾客进行服务；后到先服务， 如乘坐电梯的顾客先入后出，后入先出
()从服务设施的数量上可分为单服务台与多服务台。 (2)在多服务台情形，服务台可能是并列的，也可能 是串列的。并列服务系统可以同时对多个顾客进行服务 而串列情况下，每个顾客要依次经过各个服务台的服务 才能离开系统。图10-2中(a)是多队多台并列情形； (b)是单队多台并列情形；(c)是单队多台串列情形。 (3)服务时间可以分成确定型和随机型两种情形。自 动机床对零件的加工时间是确定型的，大多数情况服务 时间是随机型的。 2000 1 000>2〉 2 12…amn n (c) 2000 (b) 图10-2
3.服务机构 ◼ ⑴从服务设施的数量上可分为单服务台与多服务台。 ◼ ⑵在多服务台情形，服务台可能是并列的，也可能 是串列的。并列服务系统可以同时对多个顾客进行服务， 而串列情况下，每个顾客要依次经过各个服务台的服务 才能离开系统。图10-2中（a）是多队多台并列情形； （b）是单队多台并列情形；（c）是单队多台串列情形。 ◼ ⑶服务时间可以分成确定型和随机型两种情形。自 动机床对零件的加工时间是确定型的，大多数情况服务 时间是随机型的。 ○○○ … ○○○ ○○○ ○○○ … ○○○ ○○○ … ○○○ （ 图10-2 a） （b） （c） 1 2 1 1 2 2 n n ○○○ n
按照排队系统组成部分的主要特征可以对排队模型进 行分类。1971年排队论符号标准化会议决定，排队模型 分类符号为： X/Y/Z/A/B/C ■其中X处填写顾客相继到达时间间隔的分布； Y处填写服务时间的分布： Z处填写并列的服务台数量： A处填写系统容量限制； B处填写顾客源数量： C处填写服务次序，如先到先服务FCFS;后到先 服务LCFS等，如果略去该项则表示先到先服务。 0 表示相继到达间隔时间和服务时间的各种分布符号 是： M 负指数分布(Markov)
1.2 排队模型的分类 ◼ 按照排队系统组成部分的主要特征可以对排队模型进 行分类。1971年排队论符号标准化会议决定，排队模型 分类符号为： ◼ X/Y/Z/A/B/C ◼其中 X处填写顾客相继到达时间间隔的分布； ◼ Y处填写服务时间的分布； ◼ Z处填写并列的服务台数量； ◼ A处填写系统容量限制； ◼ B处填写顾客源数量； ◼ C处填写服务次序，如先到先服务FCFS；后到先 服务LCFS等，如果略去该项则表示先到先服务。 ◼ 表示相继到达间隔时间和服务时间的各种分布符号 是： ◼ M ——负指数分布（Markov） ◼ D ——确定型分布（Deterministic）
分师时间间(Genera Independent G 般服务时间的分布(General) 例如：MM/1/∞/∞表示顾客相继到达的间隔时间为负 指数分布，服务时间为负指数分布，单服务台， 系统对 顾客无限制，顾客源无限，先到先服务的服务模型。 1.3排队模型的参数 在排队系统的分析计算中，要用到下面一些概念和符号： (1)P,(t) 在时刻t系统中恰好有n个顾客的概率。 (2)N(t) 在时刻服务系统中的顾客数。 (3)稳定状态 当一个排队服务系统开始运转时， 系统状态很大程度上取决于系统的初始状态和运转经历 的时间，但过去一段时间后，系统的状态将独立于初始 状态及经历的时间，这时称系统处于稳定状态。在稳定 状态下，系统处于某一状态的概率是一个常数。所以P, (t)可写为P。由于对系统的瞬时状态分析比较困难， 所以排队论中主要研究系统处于稳定状态的工作情况
◼ Ek——k阶爱尔朗分布（Erlang） ◼ GI——一般独立分布的时间间隔（General Independent） ◼ G——一般服务时间的分布（ General ） 例如：M/M/1/∞/∞表示顾客相继到达的间隔时间为负 指数分布，服务时间为负指数分布，单服务台，系统对 顾客无限制，顾客源无限，先到先服务的服务模型。 1.3 排队模型的参数 在排队系统的分析计算中，要用到下面一些概念和符号： ◼ ⑴Pn（t）——在时刻t系统中恰好有n个顾客的概率。 ◼ ⑵N（t）——在时刻t服务系统中的顾客数。 ◼ ⑶稳定状态——当一个排队服务系统开始运转时， 系统状态很大程度上取决于系统的初始状态和运转经历 的时间，但过去一段时间后，系统的状态将独立于初始 状态及经历的时间，这时称系统处于稳定状态。在稳定 状态下，系统处于某一状态的概率是一个常数。所以Pn （t）可写为Pn。由于对系统的瞬时状态分析比较困难， 所以排队论中主要研究系统处于稳定状态的工作情况
,(单位时间到达的顾客数)，则1入表示相邻两个顾 客到达的平均间隔时间。如60分钟内到达30个顾客，则 平均到达率入=30÷60=1/2（人/分钟），平均间隔时间 为1/入，=2（分钟），即平均每隔2分钟来1人。 (⑤)wn一当系统有个顾客时，整个系统的服务率 (单位时间服务完的顾客数)，则1/，表示对每个顾客 的平均服务时间。如60分钟内服务完3个顾客，则平均服 务率，=3÷60=0.05（人/分钟），对每个顾客的平均服 务时间为11，=20（分钟)，【 即平均每20分钟服务完1人。 (6)Ls 稳态下，系统中顾客数的平均值。一般 日 L-P =()Lq 稳态下，队列中顾客数的平均值（平均队长）。 ■ 人n-cp 这里C为服务设施的数量
◼ ⑷λn——当系统有n个顾客时，新来顾客的平均到达 率（单位时间到达的顾客数），则1/ λn表示相邻两个顾 客到达的平均间隔时间。如60分钟内到达30个顾客，则 平均到达率λn=30÷60=1/2（人/分钟），平均间隔时间 为1/ λn =2（分钟），即平均每隔2分钟来1人。 ◼ ⑸μn——当系统有n个顾客时，整个系统的服务率 （单位时间服务完的顾客数），则1/ μn表示对每个顾客 的平均服务时间。如60分钟内服务完3个顾客，则平均服 务率μn=3÷60=0.05（人/分钟），对每个顾客的平均服 务时间为1/ μn=20（分钟），即平均每20分钟服务完1人。 ◼ ⑹Ls——稳态下，系统中顾客数的平均值。一般 ◼ Ls = ◼⑺Lq——稳态下，队列中顾客数的平均值（平均队长）。 ◼ Lq = 这里C为服务设施的数量。 λn n=0 nPn = n 0 n-cPn
