第九章 运筹学排队论2

第八章排队论排队（queue）是社会活动中经常遇到的现象，如顾客到商店购物，学生去图书馆借书，病人上医院看病，仪器等待维修等等，当售货员、图书管理员、医生和修理员的数量满足不了顾客或病人及时服务的需要时，就出现了排队等待的现象．由于接受服务的顾客数和服务时间的随机性，排队现象是不可避免的．当然增加服务能力可以减少排队现象，但这样势必增加投资，有时因供大于求造成资源浪费．因此，在这样一个排队系统中，作为管理人员不但需要了解排队等待服务的顾客数，等待服务时间长度，系统内服务设施的空闲率等数量指标的变化规律，而且需要在满足顾客服务基本要求的条件下，研究如何提高服务质量、降低排队系统运行成本等问题．排队论就是解决这类问题的一门科学．在排队系统中要求得到某种服务的对象统称为顾客（customer），为顾客服务者统称为服务台（service facility）．根据顾客和服务台的不同情况，组成不同的排队系统．本章研究的主要内容是排队系统的状态概率、队长、等待时间、服务时间、服务台利用效率等运行指标，以及排队系统的优化问题．第一节排队系统的基本概念一、排队系统的组成一个排队系统或称服务系统（service system），有三个基本组成部分：即输入过程（arrival process）、排队规则（queue discipline）和服务规则（service discipline）．图8-1给出了排队系统的一般结构．1．输入过程：指顾客到达排队系统的规律，可用到达时间间隔或单位时间内顾客到达数的概率分布来描述；按到达的时间间隔分有确定的时间间隔和随机的时间间隔；按顾客到达的方式有单个到达和成批到达；从顾客源总体看，分有限源总体和无限源总体．2．排队规则：排队系统一般分为等待制、损失制和混合制．(1) 等待制 顾客到达系统时，如果服务台没有空闲，则顾客排队等候服务．等待制服务的方式有：① 先到先服务（first come first service ，FCFS ）：按顾客到达先后给予服务，这是最常见的服务规则．② 后到先服务（last come first service ，LCFS ）：如情报收集中最后到达的信息最有价值，往往最先采用．③ 优先权服务（priority ，PR ）：如医院对危重病人给予优先治疗．④ 随机服务（service in random order ，SIRO ）：排队系统随机抽取等待服务的顾客．(2) 损失制 顾客到达系统时，如果服务台没有空闲，则顾客离去，另求服务．如没有足够医生或医疗器械救治急诊患者，医院药物、卫生材料暂缺等．(3) 混合制 它是介于等待制和损失制之间的形式．方式有：① 队伍长度有限，当队伍的长度小于N 时，新到顾客就排队等待；当队伍长度为N 时，新来顾客离去．如患者住院所需要的病床数有限就属此类．② 等待时间有限，新到顾客排队等候服务，一段时间后仍未得到服务，顾客离去．例如医院血库的血浆、生物制剂等．③ 逗留时间（等待时间与服务时间之和）有限，顾客在系统中的逗留时间不得超过确定的时间．例如药品的有效期．3．服务机构：指排队系统中服务台的个数、排列及服务方式．排队系统中服务台的个数可以是一个或多个．多个服务台可以是串联或并联．排列结构大体有：(1) 单服务台、单列图8-2输出(2) 多服务台、单队列（多队列）(3) 多服务台串列(4) 多服务台混合医院里的CT室就是(1)的例子，口腔科、理疗室就是(2)的例子，先挂号候诊再住院手术就是(3)或(4)的例子．服务方式上有单个服务，也有成批服务的，如医院里的上下电梯．二、排队系统的评价指标排队论研究的问题，可以分成两大类，第一类问题是在服务设施设置之前，根据顾客输入过程与服务过程的要求，结合对系统的一定数量指标与服务过程要求（如规定服务质量的必需水平），确定服务设施（如诊断室、检验科、供应中心等等）的图8-3图8-4图8-5…图8-6规模；第二类问题是对已有的服务系统施以最优控制，改进和提高排队系统工作效率．排队系统的数量指标主要有：1．单位时间内到达的顾客数的期望值，即单位时间内的平均到达率，记作λ．而λ1表示相邻两个顾客到达的平均间隔时间．2．单位时间内服务的顾客数的期望值，即单位时间内顾客的平均离去率，记作μ．同样，μ1表示每个顾客的平均服务时间．3．在时刻t时排队系统中恰有n个顾客的概率()tPn ，显然()tP为系统空闲率．4．系统内的平均顾客数称为队长（queue length），记作L．5．系统内排队等待服务的平均顾客数称为等待队长，记作qL．6．顾客从进入系统到接受完服务后离开系统的平均时间称为平均逗留时间，记作W．7．顾客在系统内排队等待服务的平均时间称为平均等待时间(waiting time)，记作qW．三、排队模型的符号表示由于排队系统的特征可以有许许多多的组合，从而形成不同的排队模型．本章采用A/B/C/m/N形式表示不同排队模型．其中：A——顾客到达间隔时间概率分布B——服务时间的概率分布C——服务台数m——顾客源总数N——系统内顾客的容量例如：M/M/ 1 / ∞/ 12排队模型的特点是：顾客到达间隔时间和服务时间均服从负指数分布（M指负指数分布，具有无记忆性，即Markov性），单服务台，顾客来源总体数无限，系统的顾客容量为12．四、排队系统的常见分布顾客到达和离开分别构成排队系统的输入与输出过程流．到达分布和离开分布确定了到达系统和离开系统的顾客数这两个随机变量的分布．求解排队系统有关数量指标问题，首先要确定顾客到达流的概率分布，即在一定的时间间隔内来n 个顾客的概率是多大．其次是要确定顾客离开流的概率分布，即在一定的时间内服务完m 个顾客的概率是多大．实际问题研究中，可根据原始资料测算顾客在单位时间平均到达流的经验分布，然后按照统计学的方法（例如，2χ检验法）确定资料适合于哪种理论分布，并估计理论分布的参数值，这是确定排队模型的前提．1．泊松分布（Poisson distribution ）在排队论中，最基本的排队模型是在给定时间内到达系统的顾客数服从泊松分布，即顾客到达流是泊松流（也称最简单流）．它具有如下性质：(1) 平稳性：在时间+t △t 内，到达n 个顾客的概率只与△t 和n 的大小有关，而与时刻起点t 无关．(2) 无后效性：在时间+t △t 内到达n 个顾客的概率与起始时刻之前到达多少个顾客无关．(3) 普通性：对于充分小的时间间隔△t ，在时间+t △t 内最多有一个顾客到达系统．即在时间+t △t 内有2个或2个以上顾客到达的概率极小，有()0lim2=∆+∑∞=→∆t t P n nt可以证明，在长为t 的时间内到达n 个顾客的概率为：()(),2,1,00!)(=>=-n t e n t t P tn n λλ （8-1）当1=t 时，即单位时间内到达n 个顾客的概率为：()λλ-==e n P P nn n !1其中λ为单位时间内到达系统的顾客的期望值． 2．负指数分布(negative exponential distribution )理论上可以证明若顾客在单位时间内到达系统的个数X 是服从参数为λ的泊松分布，则顾客到达系统的间隔时间T 服从参数为λ的负指数分布，反之亦然．即同一随机过程可从两种不同的角度用两种分布来描述．负指数分布的概率密度为：)0()(>=-t e t f tT λλ间隔时间T 的期望值。

运筹学中的排队论分析与应用运筹学是一门研究如何最优化决策的学科。

在现代社会中，许多场景下都存在排队现象，例如银行、超市、机场等场所。

排队论作为运筹学的一个重要分支，专门研究如何通过合理的排队策略来优化服务效率与用户体验。

本文将介绍排队论的基本原理、应用场景以及如何利用排队论进行实际问题的分析与解决。

一、排队论的基本原理排队论是研究排队系统的理论与方法，其基本原理包括排队模型、排队规则以及排队指标。

1. 排队模型排队模型是对排队系统进行抽象和建模的过程，常用的排队模型有M/M/1、M/M/c、M/G/1等。

其中，M表示顾客到达过程符合泊松分布，而服务过程符合指数分布；1表示一个服务台，c表示多个服务台；G表示总体服从一般分布。

2. 排队规则排队规则是指在排队系统中，顾客到达和离开的规则。

常用的排队规则有先到先服务（First-Come-First-Serve，简称FCFS）、最短作业优先（Shortest Job First，简称SJF）、优先级法则等。

3. 排队指标排队指标是对排队系统性能的度量，常用的排队指标包括平均等待时间、平均逗留时间、系统繁忙度等。

这些指标可以帮助我们评估排队系统的效率，并进行比较和优化。

二、排队论的应用场景排队论的应用场景非常广泛，几乎可以涵盖各个行业。

下面以几个典型的应用场景为例，介绍排队论在其中的分析与应用。

1. 银行排队银行是排队论的典型应用场景之一。

通过排队论的分析，银行可以确定合理的柜台数量和工作人员配置，以减少客户的等待时间和提高服务效率。

此外，银行还可以考虑引入预约系统、自助服务等方式，进一步优化排队系统。

2. 售票窗口排队售票窗口也是一个常见的排队场景，如电影院、火车站等。

利用排队论，可以根据顾客到达的速率和服务时间的分布，预测等待时间，并提前安排足够的窗口进行服务，以提高售票效率和用户体验。

3. 交通信号灯优化交通信号灯的优化也可以借助排队论的方法。

通过对道路上车辆到达和通过的流量进行统计和分析，可以调整信号灯的信号周期和配时方案，以减少交通拥堵和减少等待时间。

解：计算结果如下表所示：
λμρP0 Ls(人) Lq(人) Ws(分) Wq(分)
1 4 0.25 0.75 0.33 0.083 20 5
2 4 0.5 0.5 1 0.5 30 15
3 4 0.75 0.25 3 2.25 60 45
4 4 1 0 ∞∞∞∞
上述数据可做如下分析：
⑴当λ为1和2时，从病人的角度来看，基本不需要候诊（Wq为5分钟和15分钟）符合病人的利益，从医院的角度看，医生平均有50%-70%的时间空闲
⑵当λ=3时，候诊病人平均2-3人，候诊平均需要45分钟，因为是急诊，给病人带来痛苦，而医务人员的空闲时间很少。

⑶当λ=4时，λ=μ由于顾客到达是随机的，候诊队列和候诊时间都将无限延长
综上分析：作为医院管理者，当发现病人的到达率为每小时3-4人时，就要考虑增加医务人员。

第十五次作业解答习题6：（P221）9；（9）某汽车修理部有4个修理工，每个修理工可以单独修理汽车，也可以和其他修理工合作共同修理汽车。

前来修理部寻求修理的汽车按泊松流到达，平均每天到达2辆。

当修理部内有4辆汽车时，后来的汽车将离去。

修理一辆汽车所需时间服从负指数分布，若一个修理工修理一辆汽车，则平均需3天；若两个修理工修理1辆汽车，则平均需2天；若3或4个修理工修理一辆汽车，则平均需1.5天。

试求： ①画出系统状态转移图； ②求系统状态概率； ③求系统损失率；④求系统中平均的汽车数量；⑤求每辆汽车在系统中逗留的时间。

解：依题意，因为修理工可以相互合作也可以单独工作，可以把他们看成最多有4个服务台的一个修理小组，所以该系统为M/M/4/4/∞/FCFS 损失制排队系统。

2λ=辆／天，修理部的修理速度μ是一个变化的参数，具体如下：11(1/1.5)2/3μ=⨯=；22(1/2)1μ=⨯=；32(1/3)1(1/2)7/6μ=⨯+⨯=；44(1/3)4/3μ=⨯=。

150.75210c λρμ===⨯ （1）状态转移速度图：（2）系统状态概率：011103p p p p λμ=⇒=；022112100()8/326p p p p p p p λμμλ+=+⇒=-=；133223210()(32)(7/6)72/7p p p p p p p λμμλ+=+⇒=-=；244334320()(19/62)/3)108/7p p p p p p p λμμλ+=+⇒=-=。

由41kk p==∑可得，10[13672/7108/7]7/2500.028p -=++++==；120.084;0.168;p p ==340.288;0.432p p ==。

（3）系统损失率40.432p p ==损。

（4）系统中平均的汽车数量4110.08420.16830.28840.4320.0840.3360.864 1.728 3.012s n n L np ===⨯+⨯+⨯+⨯=+++=∑。