《运筹学》10-服务系统规划课件.ppt

管理运筹学10-服务系统规划,第十章 服务系统规划,第一节：服务排队现象及其建模第二节：排队系统的常用分布第三节：单服务台模型第四节：多服务台模型第五节：其他服务时间分布模型第六节：服务系统规划的应用,第一节 服务排队现象及其建模,顾客的到达可以是相互独立的，就是说，以前的到达情况对以后顾客的到来没有影响，否则就是有关联的。例如，工厂内的机器在一个短的时间区间内出现停机（顾客到达）的概率就受已经待修或被修理的机器数目的影响。本章主要讨论的是相互独立的情形。输入过程可以是平稳的，或称对时间是齐次的，是指描述相继到达的间隔时间分布和所含参数（如期望值、方差等）都是与时间无关的，否则称为非平稳的。非平稳情形的数学处理是很困难的。,第一节 服务排队现象及其建模,2.排队规则 顾客到达时，若所有服务台都正被占用，在这种情形下顾客可以随即离去，也可以排队等候。随即离去的称为即时制或称损失制（因为失掉许多顾客）；排队等候的称为等待制。普通市内电话的呼唤属于前者，而登记市外长途电话的呼唤属于后者。,第一节 服务排队现象及其建模,对于等待制，为顾客进行服务的次序可采用下列各种规则：1）先到先服务，即按顾客到达次序接受服务，这是最通常的情形。2）后到先服务，如乘电梯的顾客常是后入先出的。仓库中存放的厚钢板也是如此。在情报系统中，最后到达的信息往往是最有价值的，而采用后到先服务（指被采用）的规则。3）随机服务，指服务员从等待的顾客中随机选取其一进行服务，而不管到达的先后，如电话交换台接通呼唤的电话就是如此。4）有优先权的服务，如医院对病情严重的患者将给予优先治疗。,第一节 服务排队现象及其建模,从占有的空间来看，队列可以排在具体的处所（如售票处、候诊室等），也可以是抽象的（如向电话交换台要求通话的呼唤）。由于空间的限制或其他原因，有的系统要规定容量（即允许进入排队系统的顾客数）的最大限制；有的没有这种限制（即认为容量可以是无限的）。,第一节 服务排队现象及其建模,从队列的数目看，可以是单列，也可以是多列。在多列的情形，各列间的顾客有的可以相互转移，有的不能（如用绳子或栏杆隔开）。有的排队顾客因等候时间过长而中途退出，有的不能退出（如高速公路上的汽车流），必须坚持到被服务为止。本章将只讨论各队列间不能互相转移，也不能中途退出的情形。,第一节 服务排队现象及其建模,3.服务机构从机构形式和工作情况来看有以下几种情况。服务机构可以没有服务员，也可以有一个或多个服务员（服务台、通道、窗口等）。例如，在敞架售书的书店，顾客选书时就没有服务员，但交款时可能有多个服务员。在有多个服务台的情形中，它们可以是平行排列（并列）的，可以是前后排列（串列）的，也可以是混合的。如图9-2所示。,第一节 服务排队现象及其建模,第一节 服务排队现象及其建模,第一节 服务排队现象及其建模,第一节 服务排队现象及其建模,服务方式可以对单个顾客进行，也可以对成批顾客进行，公共汽车对在站台等候的顾客就成批进行服务。本章将只研究单独的服务方式。和输入过程一样，服务时间也分确定型的和随机型的。自动冲洗汽车的装置对每辆汽车冲洗（服务）的时间就是确定型的，但大多数情形的服务时间是随机型的。对于随机型的服务时间，需要知道它的概率分布。和输入过程一样，服务时间的分布总假定是平稳的，即分布的期望值、方差等参数都不受时间的影响。,第一节 服务排队现象及其建模,三、排队模型的分类为了区别各种排队系统，根据输入过程、排队规则和服务机构的变化对排队模型进行描述或分类。1953年肯道尔（Kendall）提出一个分类方法，称为Kendall符号，其形式是 X/Y/Z；在1971年一次关于排队论符号标准化国际会议上，将Kendall符号扩充为以下标准形式：X/Y/Z/A/B/C 或者 X/Y/Z:A/B/C,第一节 服务排队现象及其建模,Kendall各符号的意义：(1)X:表示顾客相继到达时间间隔的概率分布，可以取 M、D、Ek、G等，其中：M 表示到达过程为泊松过程或负指数分布；D 表示定长输入；Ek 表示K阶爱尔朗（Erlang）分布；G 表示一般相互独立的随机分布；(2)Y:表示服务时间分布，所用符号与X相同,第一节 服务排队现象及其建模,Z：表示服务台个数，取正整数。1表示单个服务台，s 表示多个服务台。A：表示系统中顾客容量限制，或称等待空间容量。B：表示顾客源限制，可取正整数或，即有限与无限两种。C：表示服务规则，如先到先服务（FCFS），后到先服务(LCFS)等。并规定，若略去后三项，即指X/Y/Z/FCFS的情形。本章只讨论先到先服务FCFS的情形，因此一般略去第六项。,第一节 服务排队现象及其建模,四、排队问题的求解一个实际的系统模型在分析求解时，先要研究整个系统的组成部分属于哪种类型，如顾客的输入过程、排队规则、服务机构的组织结构等。其中，顾客的相继到达间隔和服务时间的分布都需要通过统计检验后确定。解排队问题的目的是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统的结构是否合理，研究设计改进措施等。因此必须确定用以衡量系统运行优劣的基本数量指标，解决排队问题首先要求出这些数量指标的概率分布或特征数。常用的系统运行指标有如下几个。,第一节 服务排队现象及其建模,(1)损失率在损失制服务系统中，由于服务台全被占用而使顾客损失的概率，是损失制系统的主要服务质量指标。,第一节 服务排队现象及其建模,(2)队长与队列长队长指服务系统中逗留的顾客总数，其期望值记作Ls；队列长指服务系统中排队等待的顾客总数，其期望值记作Lq,第一节 服务排队现象及其建模,(3)逗留时间和等待时间逗留时间指一个顾客进入服务系统后到离开服务系统的时间，包括等待时间和接受服务的时间，其期望值记作Ws；等待时间是顾客排队等待服务的时间，其期望值记作Wq；一般系统中，等待时间是主要的质量指标，但有些系统，如码头卸船则不仅要计算等待时间，也要计算服务时间。,第一节 服务排队现象及其建模,(4)服务设施利用率服务设施利用率指服务设施包括服务台的工时利用情况。这是一个重要的经济效益指标，这一指标往往是和服务质量指标相矛盾的。,第一节 服务排队现象及其建模,(5)忙期忙期指服务台不间断地为顾客一段时间的长度。对服务台来说，忙期与闲期总是交替出现的。忙期长说明服务台的工时利用率高，工作强度大。,第一节 服务排队现象及其建模,计算上述指标的基础是表达系统状态的概率。所谓系统状态是指系统中逗留的顾客数，如果系统中有 j个顾客，就说明系统处于j状态。系统状态一般是随时间改变的，我们通常只计算在时刻t系统状态为j的概率，用Pj(t)表示。系统状态数受系统容量和排队规则的限制。例如，在损失制系统中，系统状态数最多和服务台数相等，而在队长不受限制的系统中，系统状态数可以是无限的。,第一节 服务排队现象及其建模,求状态概率Pj(t)，先要建立含Pj(t)的方程组，因j只能是非负整数，而t是连续变量，所建立的方程组一般属微分方程组，其解是瞬态性质，不容易求解。因此，我们常取稳态解，即令 lim t Pj(t)=Pj稳态解的物理意义是，当系统开始运行一定长度的时间后，系统的状态概率分布逐渐趋于稳定，不再随时间的变化而变化。,第一节 服务排队现象及其建模,实际上，并不需要t，系统才会稳定下来。如百货商场刚开门时，顾客必然进的多，出的少，Pj(t)随时间改变，但当过一段时间后，进、出的顾客大体上就达到平衡，状态概率就呈现稳定状态，所以稳态也称统计平衡状态。求稳态概率是，只需令Pj(t)=0 即可。,第二节 排队系统的常用分布,在排队系统中，顾客相继到达的时间间隔与服务的时间分布主要有:负指数分布;泊松分布;爱尔朗分布等。,第二节 排队系统的常用分布,一、泊松过程设N(t)表示在0,t)时段内到达的顾客数(t0)令Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(n0)个顾客到达（随机事件）的概率，即:,第九章 服务系统规划,当 Pn(t1,t2)符合以下三个条件时，就说顾客的到达形成泊松流。在不相重叠的时间区间内顾客到达数是相互独立的，称为无后效性。对充分小的t，在时间区间 t,t+t)内有1个顾客到达的概率与t无关，近似与区间长t成正比，即 其中，o(t)，当 t 0时，是关于t的高阶无穷小。0是常数，表示单位时间有一个顾客到达的概率，称为概率强度。对于充分小的 t，在时间区间t,t+t)内有2个或2个以上顾客到达的概率极小，以至于可以忽略，即,第二节 排队系统的常用分布,第二节 排队系统的常用分布,在上述条件下，我们研究顾客到达数n的概率分布.由条件，我们总可以取时间由0算起,简记Pn(0,t)=Pn(t)由条件和，容易推得在t,t+t)区间内没有顾客到达的概率在求Pn(t)时，用通常建立未知函数的微分方程的方法，先求未知函数Pn(t)由时刻t到t+t的改变量，从而建立t时刻的概率分布与t+t时刻概率分布的关系方程。对于区间 0,t+t)可分成两个互不重叠的区间 0,t)和 t,t+t)。现在到达总数n，分别出现在这两区间上，只有以下三种情况。各种情况出现个数和概率见下表9-2。,第二节 排队系统的常用分布,表9-2 各种情况出现个数和概率,第二节 排队系统的常用分布,在0,t+t)内到达n个顾客应是表中互不相容的情况之一，所以概率Pn(t+t)应是表中三个概率之和（各 o(t)合为一项）,令t 0,得下列方程，并注意到初始条件，则有,第二节 排队系统的常用分布,当n=0时，(B)、(C)两种情况不存在，所以得解上述两式，就得Pn(t)表示长为t的时间区间内到达n个顾客的概率，由上式(9-9)，根据概率论可知，随机变量N(t)=N(s+t)-N(s)服从泊松分布。期望值EN(t)=t；方差VarN(t)=t期望值与方差相等，是泊松分布的一个重要特征，可以利用此性质对一个经验分布是否合于泊松分布进行初步的判别。,第二节 排队系统的常用分布,二、负指数分布若随机变量T的概率密度为则称T服从负指数分布。其分布函数为数学期望 方差 标准差,第二节 排队系统的常用分布,负指数分布有以下性质：(1)密度函数fT(t)对时间t严格递减(2)由条件概率公式容易证明 称为无记忆性或马尔可夫性。若T表示排队系统中顾客到达的间隔时间，该性质说明一个顾客到来所需的时间与过去一个顾客到来所需的时间s 无关，这种情形下的顾客到达是完全随机的；,第九章 服务系统规划,(3)当输入的过程是泊松流时，那么顾客相继到达的间隔时间T必须服从负指数分布。这是因为对于泊松流,在 0,t)区间内至少有1个顾客到达的概率是 此概率又可以表示为 因此，相继到达的间隔时间是独立且为同负指数分布（密度函数 e-t,t 0），与输入过程为泊松流（参数为）是等价的。所以在Kendall记号中都用M表示。对于泊松流，表示单位时间平均到达的顾客，所以1/就表示相继顾客到达平均间隔时间，而这正和ET的意义相符。,第二节 排队系统的常用分布,第九章 服务系统规划,服务时间v是对一顾客的服务时间，也就是在忙期相继离开系统的两顾客的间隔时间，一般也服从负指数分布。设它的分布函数和密度分别是其中，表示单位时间接受服务的顾客数，称为平均服务率1/=E(v)表示一个顾客的平均服务时间，即期望值。,第二节 排队系统的常用分布,第九章 服务系统规划,三、爱尔朗分布若随机变量V具有下述密度函数：则称V服从参数为的k阶爱尔朗分布，记为 V Ek()。由概率论，若随机变量为 V Ek()，则其期望与方差为,第二节 排队系统的常用分布,第九章 服务系统规划,爱尔朗分布具有已下性质(1)当k=1时，爱尔朗分布就成为指数分布；当k增大，方差 减小，的取值密集于均值 附近，爱尔朗分布近似于正态分布；当k 时，D(V)0,V趋近于常数，爱尔朗分布近似于定长分布。,第二节 排队系统的常用分布,第九章 服务系统规划,(2)设随机变量 V1,V2,V3,Vk相互独立且服从于相同参数k的指数分布。设V=V1+V2+V3+Vk=Vi，则V Ek()性质的实际意义：假设一个服务系统具有个串联服务台，每台服务时间Vi(i=1,2,k)相互独立，都服从具有参数k 的指数分布，而且k个服务台依次全部完成对一个顾客的服务后，下一个顾客才进入第一个服务台开始接受服务，那么该系统对任一顾客服务时间 为：,第二节 排队系统的常用分布,第九章 服务系统规划,单服务台的排队系统，它的输入过程服从泊松分布的过程，服务时间服从负指数分布。讨论以下三种情形：标准的 M/M/1模型，即 M/M/1/；系统容量有限，即M/M/1/N/；顾客源为有限，即 M/M/1/m。,第三节 单服务台模型,第九章 服务系统规划,一、标准的 M/M/1模型（M/M/1/）标准的 M/M/1 模型的排队系统符合以下条件：输入过程顾客源是无限的，顾客单个到来，相互独立，一定时间的到达数服从泊松分布，到达过程是平稳的。排队规则单队，队长无限制，先到先服务。服务机构各顾客的服务时间是相互独立的，服从相同的负指数分布。此外，假设顾客相继到达的间隔时间和服务时间是相互独立的。,第三节 单服务台模型,第九章 服务系统规划,分析标准的M/M/1 模型首先要求出系统在任意时刻t的状态n（系统中有n个顾客）的概率Pn(t)，它决定了系统的运行的特征。因已知到达规律服从参数为的泊松过程，服务时间服从参数为的负指数分布，所以在 t,t+t)时间区间内分为：有1个顾客到达的概率为t+o(t)；没有顾客到达的概率为1-t+o(t)。当有顾客在接受服务时，1个顾客被服务完了（离去）的概率为 t+o(t)，没有离去的概率为 1-t+o(t)。多于1个的顾客到达或离去的概率是o(t)，可忽略不计。,第三节 单服务台模型,第九章 服务系统规划,在t+t时刻，系统中有n个顾客（n0）存在以下四种情况：,第三节 单服务台模型,表9-3系统中有n个顾客的情形,第九章 服务系统规划,由于这四种情况是互不相容的，所以Pn(t+t)应是这四项之和，即（将关于t)的高阶无穷小合并为一项）令t 0，则关于Pn(t)的微分方程,第三节 单服务台模型,第九章 服务系统规划,当n=0，则只有表9-3中的(A)，(B)两种情况，即同理可得此时系统状态(n)随时间变化的过程就成为生灭过程的一个特殊情形。,第三节 单服务台模型,第九章 服务系统规划,解方程(9-16)与(9-17)很复杂，求得的解（瞬态解）不便于应用，因此只研究稳态的情况，此时 Pn(t)与t无关，可写成 Pn，它的导数为0由以上的微分方程可得这是关于Pn(t)的差分方程。它表明了各状态间的转移关系如图9-3所示.,第三节 单服务台模型,图9-3 状态转移关系,第九章 服务系统规划,由图9-3可知，状态0转移到状态1的转移率为 P0(t)，状态1转移到状态0的转移率为 P1(t)。状态0必须满足以下平衡方程 P0(t)=P1(t)同样对任何 n1的状态，可得（9-19）平衡方程。求解（9-18）可得P1将其代入（9-19），令 n=1，可得所以P2同理依次推得Pn,第三节 单服务台模型,第九章 服务系统规划,设(否则队列将排至无限长)，由概率的性质可知,将Pn的关系代入，得因此，系统状态为n 的概率：由（9-20）式，=1-P0，它描述了服务机构的繁忙程度；所以又称服务机构的利用率。,第三节 单服务台模型,第九章 服务系统规划,有实际的意义根据表达式的不同，可以有不同的解释。当 时，是平均到达率与平均服务率之比；即在相同时区内顾客到达的平均数与被服务的平均数之比。若表示为，它为一个顾客的服务时间与到达间隔时间之比；称 为服务强度，或称 为话务强度（早期排队论是爱尔朗等人在研究电话理论时用的术语，沿用至今）。,第三节 单服务台模型,第九章 服务系统规划,以（9-20）式为基础，可以算出系统的各个运行指标。在系统中的平均顾客数（队长期望值）(2)在队列中等待的平均顾客数（队列长期望值）,第三节 单服务台模型,或者,第九章 服务系统规划,关于顾客在系统中逗留的时间W(随机变量)，在 M/M/1情形下，它服从参数为-的负指数分布，即分布函数 概率密度 在系统中顾客逗留的时间的期望值 在队列中顾客等待时间的期望值,第三节 单服务台模型,第九章 服务系统规划,以上公式总结：,第三节 单服务台模型,它们之间的关系如下：称为Little(李特尔)公式,第九章 服务系统规划,例9-1在集装箱堆场中的作业集装箱泊位遵从先到先服务，车辆经过作业泊位服从负指数分布，每辆车平均需要15秒。车辆进入车道服从泊松分布，平均每小时3辆。解：对此队列分析如下：模型为M/M/1/.(1)先确定参数值：由题意知，这是单服务台模型系统，有=3(辆/小时)=60/15=4(辆/小时)故服务强度为=/=3/4=0.75(2)计算稳态概率 p0=1-=1-0.75=0.25;pn=n p0其中，p0是车道空闲的概率，也是车辆不必等待立即就能进入车道的概率。而车辆需要等待的概率，也是车道繁忙的概率为p(n0)=1-p0=1-0.25=0.75,第三节 单服务台模型,第九章 服务系统规划,计算系统的主要工作指标：此模型的平均有效到达率，即是到达率,第三节 单服务台模型,第九章 服务系统规划,为使车辆平均逗留时间不超过半分钟，车辆经过车道的平均时间应减少到多少？由于将=3代入上式解得：5车辆经过车道的平均时间为即车辆经过车道的平均时间至少应减少3分。,第三节 单服务台模型,第九章 服务系统规划,二、系统的容量有限的情况（M/M/1/N/）若系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如果系统中已有N个顾客，那么这个顾客就被拒绝进入系统（如图9-4）。,第三节 单服务台模型,图9-4 有容量限制的情形,当N=1时，为即时制的情形；当N，为容量无限制的情形。,第九章 服务系统规划,若只考虑稳态的情形，各状态间概率强度的转换关系如图9-5。,第三节 单服务台模型,图9-5状态间概率强度的转换关系,第九章 服务系统规划,根据图9-5列出状态概率的稳态方程：解此方程与解（9-18）与（9-19）是相似的，不同的是令，得,第三节 单服务台模型,第九章 服务系统规划,对于的取值略去=1 情形的讨论。当容量没有限制时，设 1 时，损失率PN（表示被拒绝排队的顾客平均数PN）很大。,第三节 单服务台模型,第九章 服务系统规划,关于有效到达率e当研究顾客在系统平均逗留时间Ws 和队列中平均等待时间Wq 时，尽管（9-22）式仍可利用，但要注意平均到达率是在系统中有空时的平均到达率，当系统已满(n=N)时，则到达率为0，因此需要求出有效到达率e=(1-PN)可验证：,即e=(1-P0),第三节 单服务台模型,第九章 服务系统规划,根据（9-25）可以得出以下指标：(1)队长（期望值）(2)队列长（期望值）(3)顾客逗留时间（期望值）(4)顾客等待时间（期望值）,第三节：单服务台模型,第九章 服务系统规划,此模型系统的性能指标（当1 时）,第三节 单服务台模型,第九章 服务系统规划,例9-2 集装箱堆场的某作业集装箱泊位共7个。当7个处理台都满时，后来到的集装箱不进入该作业线。集装箱的平均到达率为3个/小时，处理一个集装箱平均需要15分。解：则N=7为系统中最大的顾客数，=3个/小时，=4个/小时。(1)由题意知，模型为（M/M/1/N/）先确定参数：由题意知，服务强度=/=3/4=0.75(2)求某集装箱一到达就能进行作业的概率。这种情形相当于作业线内没有集装箱，所求概率,第三节 单服务台模型,第九章 服务系统规划,(3)求作业线上集装箱的期望值；需要等待的集装箱的期望值(4)求有效到达率e e=(1-P0)=2.11-(1-0.2778)=2.89(个小时)(5)求一集装箱在作业线内逗留的期望时间；等待时间(6)在可能到来的集装箱进入其它作业线的概率(Pn7)。这就是求作业线内有7个集装箱的概率,第三节 单服务台模型,第九章 服务系统规划,三、顾客源有限的情形(M/M/1/m)该模型中，设顾客总数为m，当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源。如此循环往复。模型符号的第4项为，表示系统的容量没有限制，但实际上它决不会超过m，所以跟写成(M/M/1/m/m)的意义相同。典型的有限顾客源问题是机器维修问题。有m台机器在运转，单位时间内平均出现故障的机器数即为顾客平均到达率，修理工修理一台设备的平均时间即为平均服务时间，已修复的机器仍可能再出现故障（如图9-6）。,第三节 单服务台模型,图9-6有限顾客源问题,第九章 服务系统规划,关于平均到达率在无限源的情形是按全体顾客来考虑的；在有限源的情形必须按每个顾客来考虑。为简单起见，设各个顾客的到达率都是相同的（的含义是每台机器单位运转时间内发生故障的概率或平均次数），这时在系统外的顾客平均数为m-Ls，对系统的有效到达率e应为 e=(m-Ls),第三节 单服务台模型,第九章 服务系统规划,对于此模型的分析依然可以沿用前面的方法。在稳态的情况下，考虑状态间的转移率如图9-7所示。,第三节 单服务台模型,图9-7状态转移,第九章 服务系统规划,根据图9-7列出状态概率的稳态方程：解此差分方程，用递推的方法,第三节 单服务台模型,得,第九章 服务系统规划,系统的各项指标:,第三节 单服务台模型,第九章 服务系统规划,在机器故障问题中Ls就是平均故障台数，而(m-Ls)表示正常运转的平均台数。,第三节 单服务台模型,第九章 服务系统规划,单队、并列的多服务台（服务台数为c）的情形，讨论以下三种情形：(1)标准的M/M/c模型(M/M/c/);(2)系统容量有限制(M/M/c/N/)；(3)有限顾客源(M/M/c/m)。,第四节 多服务台模型,第九章 服务系统规划,一、标准的M/M/c模型(M/M/c/)标准M/M/c模型的各种特征与标准的M/M/1模型的规定相同。另规定各服务台工作是相互独立的（非协作）且平均服务率相同1=1=c=。因此整个服务机构的平均服务率c（当nc时）；n（当nc时）。令，仅当 时才不会排成无限长的队列，称为此系统的服务强度（或服务机构的平均利用率）（如图9-8）。,第四节 多服务台模型,第九章 服务系统规划,这个系统的特点是，系统的服务速率与系统中的顾客数有关。当1nc时，系统中的顾客全部在服务台中，系统的服务率为n，状态的转移率nPn；当nc时，因为只有c个服务台，最多有c个顾客在被服务，n-c个顾客在等候，因此系统的服务率为c，状态的转移率应为cPn。,第四节 多服务台模型,图9-8 多服务台服务系统,第九章 服务系统规划,第四节 多服务台模型,图9-9多服务台服务系统状态转移,第九章 服务系统规划,第四节 多服务台模型,由图9-9可得：类似的有Pi=1，且1用递推解差分方程（9-29），求得状态概率：,第九章 服务系统规划,系统的运行指标平均队长平均等待时间和逗留时间（由little公式求得）,第四节 多服务台模型,例：某售票所有三个窗口，顾客到达服从Poisson过程，到达=0.9 人/分钟，服务=0.4人/分钟。设顾客到达后依次排成一队向空闲的窗口购票，如图 a.,图 a,=0.9,属于M/M/c型系统 c=3,/=2.25,=/c=2.25/3 1,符合要求.,整个售票所空闲概率,平均队长,平均等待时间和逗留时间,顾客到达后必须等待概率,M/M/c型系统和c个M/M/1型系统的比较,以上例说明,设顾客到达后在每个窗口前各排一队(其它条件不变),共三队,每队平均到达率为:,M/M/c型系统和c个M/M/1型系统的比较,结果比较,第九章 服务系统规划,二、系统容量有限的情形(M/M/c/N/)设系统的容量最大限制为N(Nc)，当系统中顾客数n已到达N（即队列中顾客数已达(N-c)时），以后到达的顾客将被拒绝，其余条件与标准的M/M/c 模型相同。此时系统的状态概率:其中（不必对 加以限制）,第四节 多服务台模型,第九章 服务系统规划,系统的运行指标：由于公式复杂，现有一些专门的图表可供查阅。,第四节 多服务台模型,第九章 服务系统规划,当N=c（即时制）的情形，典型的例子是街头的停车场就不允许排队等待空位。有：当n=c时，即关于Pc 的公式，被称为爱尔朗呼唤损失公式，是A.K.Erlang 早在1917年发现的，并广泛应用于电话系统的设计中。此时系统的运行指标：,第四节 多服务台模型,第九章 服务系统规划,三、顾客源为有限的情形(M/M/c/m)设顾客源为有限数m（mc），与单服务台情形类似，顾客的到达率是按单个顾客来考虑的，在机器管理问题中，共有m台机器，有c个修理工人，顾客到达就是机器出了故障，而每个顾客的到达率 是指每台机器单位运转时间出故障的期望次数。系统中顾客数n就是出故障台数，当nc时，所有的故障机器都在被修理，有(c-n)个修理工人在空闲；当cnm时，有(n-c)台机器在停机等待修理，而修理工都在忙碌状态。假定这c个工人修理技术相同，修理时间都服从参数为的负指数分布，并假定故障的修复时间和正在生产的机器是否发生故障是相互独立的。,第四节 多服务台模型,第九章 服务系统规划,其中,第四节 多服务台模型,由于P0,Pn计算公式过于复杂，有专门的表格可以供查阅。,第九章 服务系统规划,系统的性能指标平均顾客数（即平均故障台数）：有效的到达率e为每个顾客的到达率乘以在系统外（正常运转）的机器的期望数：e=(m-Ls)；在机器故障问题中，即单位时间m台机器平均出现故障的次数。,第四节 多服务台模型,第九章 服务系统规划,本节讨论服务时间是任意分布的情形，当然，对任何情形都有下面的关系：E系统中顾客数=E队列中顾客数+E服务机构中顾客数E在系统中逗留时间=E排队等待时间+E服务时间其中，E.表示求期望值，用符号表示：Ls=Lq+LseWs=Wq+ET,第五节 其他服务时间分布模型,第九章 服务系统规划,一、一般分布模型(M/G/1/)该模型的基本条件：(1)输入过程顾客源是无限的，到达过程服从参数为的泊松过程；(2)排队规则单队，队长无限制，先到先服务；(3)服务机构单服务台，G表示服务时间T的分布为任意的概率分布，但已知E(T)和方差Var(T)。此模型被称为单服务台泊松到达、任意服务时间的排队模型。,第五节 其他服务时间分布模型,第九章 服务系统规划,在稳态情况下，当=E(T)1时，可以证明:此公式又称P-K（Pollaczek-Khint chine）公式。只要知道、E(T)、Var(T)，无论服务时间T服从什么分布，均可用P-K公式求出平均队长Ls。其它的运行指标：,第五节 其他服务时间分布模型,第九章 服务系统规划,二、定长分布模型(M/D/1/)服务时间为确定的常数，如在一条装配线上完成一件工作的时间一般都是常数。自动汽车冲洗台，冲洗一辆汽车的时间就是常数，可得：,第五节 其他服务时间分布模型,第九章 服务系统规划,三、爱尔朗服务时间(M/Ek/1/)此模型中每一个顾客必须一次经过k个服务台，接受k次服务后才构成一个完整服务过程。在每个服务台的服务时间Ti相互独立，并服从相同的负指数分布（参数为k），那么 服从k阶爱尔朗分布。,第五节 其他服务时间分布模型,第九章 服务系统规划,对于(M/Ek/1/)模型（除服务时间外，其它条件与标准的M/M/1/型相同）,第五节 其他服务时间分布模型,第九章 服务系统规划,一、排队系统经济分析试图完全消除排队现象是不现实的，那样显然会造成服务人员和设施的严重浪费。另一方面，如果设施不足或服务低水平，将导致过多的等待，因而产生生产和社会损失。从经济角度考虑，一般排队系统的费用应该包含于以下两个方面：服务费用。它随着服务水平（反映在服务能力和服务台数量方面）的提高而增加，是服务水平的递增函数。顾客等待的机会损失（费用）。顾客由于等待，产生一系列的损失（时间上、心理上、社会上等）用经济费用进行的估算，称为顾客等待的机会损失。它随服务水平的提高而下降，是服务水平的递减函数。,第六节 服务系统规划的应用,第九章 服务系统规划,这两方面构成的函数呈现为一条如图所示的U型曲线。,第六节 服务系统规划的应用,图9-10 费用与服务水平之间的关系F1、F2、Y分别是服务费用函数、等待费用函数、合成费用函数。,第九章 服务系统规划,系统的最优化的目标就是寻求这个合成费用曲线的最小点。在这种意义下，排队系统的最优化问题通常分为两类：一类称之系统的静态最优设计，目的在于使设备到达最大效益，或者说，在保证一定服务质量指标的前提下，要求机构最为经济；另一类叫做系统动态最优运营，是指一个给定排队系统，如何运营可使某个目标函数得到最优。本节只讨论系统静态的最优设计问题。,第六节 服务系统规划的应用,第九章 服务系统规划,归纳起来，排队系统常见的优化问题在于：确定服务台的最优平均服务率*；确定最佳服务台数量s*；选择最为合适的服务规则；确定上述几个量得最优组合。研究排队系统的根本目的在于以最少的设备得到最大的效益，或者说，在一定的服务质量的指标下要求机构最为经济。,第六节 服务系统规划的应用,第九章 服务系统规划,二、M/M/1系统的最优平均服务率1标准的M/M/1模型设c1为当=1时服务系统单位时间的平均费用，并且这个平均费用与评级均服务率成正比例；cw为平均每个顾客在逗留单位时间的损失；Y为整个系统单位时间的平均总费用。其中c1、cw均为已知（以下情形相同）。目标函数：将M/M/1模型的平均队长公式L=/(-)代入(9-41)式，得：,第六节 服务系统规划的应用,第九章 服务系统规划,显然，Y是关于决策变量的一元非线性函数。由一阶最优性必要条件（驻点条件）解得驻点取算术平方根是为了保证，这样，系统才能达到稳态。又知二阶充分条件成立：于是，式(9-43)给出的*为(,)上的全局唯一最小点。将*带入(9-42)中，可得最小的总平均费用,第六节 服务系统规划的应用,第九章 服务系统规划,若设cw为平均每个顾客在队列中等待单位时间的损失，则需要M/M/1模型的平均队列长公式 代入式(9-41)中的L，类似可得一阶最优性必要条件：这是一个关于的4次方程，实际中一般采用数值法（如牛顿法）来确定其根（最优服务率）*。,第六节 服务系统规划的应用,第九章 服务系统规划,2.系统中顾客最大限制为N的情形在这情形下，系统中如已有N个顾客，则后来的顾客即被拒绝，可知：PN 被拒绝的概率；1-PN 能被接受的概率；(1-PN)单位时间实际进入服务机构顾客的平均数。在稳定状态下，它也等于单位时间内实际服务完成的平均顾客数。,第六节 服务系统规划的应用,第九章 服务系统规划,设每服务1人能收入G元，于是单位时间收入的期望值是(1-PN)G元。纯利润：最优的解*应该符合上式(9-45)。上式中c1、G、N都是给定的，但要由上式中解出*是很复杂的。通常是通过数值计算来求*的，或将上式左方（对一定的N）作为的函数作出图形进行求解。,第六节 服务系统规划的应用,第九章 服务系统规划,3.顾客源为有限的情形按机械故障问题来考虑。设共有机器m台，各台连续运转时间服从负指数分布。有1个修理工人，修理时间服从负指数分布。当服务率=1时的修理费用c1，单位时间每台机器运转可得收入G元。平均运转台数为m-Ls，所以单位时间纯利润：,第六节 服务系统规划的应用,第九章 服务系统规划,当给定m、G、c1、，要由上式中解出*是很困难的，通常是利用泊松分布表通过数值计算来求得，或将上式左方（对一定的m）作为的函数作出图形进行求解。,第六节 服务系统规划的应用,第九章 服务系统规划,三、M/M/c系统的最优服务台数c设排队系统M/M/c，确定最佳服务台数c的目标函数为：其中：c为待定的共享并联服务台的个数；Y(c)为整个系统单位时间的平均费用，它是关于服务台数c的函数；c2为每个服务台单位时间内的平均费用（各服务台相同）；cw为平均每个顾客在系统中逗留单位时间的损失；L(c)为平均队长，它是关于服务台数c的函数。,第六节 服务系统规划的应用,第九章 服务系统规划,要确定最优服务台数c1,2,，使由于c取值离散，不能采用微分方法或非线性规划的方法，因此，只需要同时满足下式即可：采用差分法，可导出另一关系式。把式(9-50)代入式(9-51)中，得,第六节 服务系统规划的应用,第九章 服务系统规划,令依次计算时的值，根据落在哪两个差值之间就可确定c*。另外，若设cw为平均每个顾客在队列中等待单位时间的损失，则需要M/M/c模型的平均队列长公式Lq(c)取代式(9-50)中的L(c)，由于在此情况下不需求导数，所以只要把相应公式中的L(c)用Lq(c)取代即可。,第六节 服务系统规划的应用,第九章 服务系统规划,11.3 其他模型选介,例7 某储蓄所有一个服务窗口，顾客按泊松分布平均每小时 到达10人。为任一顾客办理存款、取款等业务的时间 V(小时)N(0.05,0.012).试求该储蓄所空闲的概率及其主要工作指标。解,从而根据波拉切克欣钦公式，可以导出：,(11-53),进而按(11-1)式可算出L,W,Wq;其中e=。,2=0.012(小时/人)2,=10(人/小时),第九章 服务系统规划,11.3 其他模型选介,=0.26(人),该储蓄所空闲的概率：,=1-0.5=0.5,=10(0.05)=0.5,P0=1-,L=Lq+,则,主要指标,=0.26+0.5,=0.76(人),=0.076(小时),5(分钟),=0.026(小时),2(分钟),第九章 服务系统规划,11.3 其他模型选介,二、M/D/1系统,该系统对各顾客服务时间相互独立且为同一个常数，故有 E()=,例8 某检测站有一台自动检测机器性能的仪器，检测每台机器都需6分钟。送检机器按泊松分布到达，平均每小时4台。试求该系统的主要工作指标。,D()=0(=2),(11-54),第九章 服务系统规划,11.3 其他模型选介,=4台/小时=6分钟/台=0.1小时/台 2=0，,L=Lq+=2/15+0.4=8/15(台),Wq=Lq/=2/4(15)=1/30(小时)=2(分钟),W=Wq+1/=2+6=8(分钟),解,第九章 服务系统规划,11.3 其他模型选介,该系统对任一顾客的服务时间 VEk()，有 E(V)=1/，D(V)=1/k2(=2),三、M/Ek/1系统,(11-55),第九章 服务系统规划,11.3 其他模型选介,例9 一个质量检查员平均每小时收到两件送来检查的样品，每件样品要一次完成5项检验才能判断是否合格。据统计，每项检验所需时间的期望值都是4分钟，每项检验的时间和送检产品到到达间隔都为指数分布。问一件样品从送到至检查完毕预期要多少时间？解=2 件/小时 k=5,i=1，2，3，4，5,1/=20(分钟/件)=1/3(小时/件),由,有,则,第九章 服务系统规划,=/=2(1/3)=2/3 Lq=Wq=Lq/=4/5/2=2/5(小时)W=Wq+1/=2/5+1/3=11/15(小时)=44(分钟),11.3 其他模型选介,第九章 服务系统规划,c1 当=1时 服务系统单位时间的平均费用 cw 平均每个顾客在系统逗留单位时间的损失 y 整个系统单位时间的平均总费用 其中c1，cw可知，目标函数为y=c1+cwL,11.3 其他模型选介,11.3.2 排队系统的优化设计,设,(11-56),将 L=/（-）代入上式，得 y=c1+cw/（-）,求导,得,第九章 服务系统规划,11.3 其他模型选介,解得驻点,(11-57),又由,0,（因）,知：*为（，）上的全局唯一极小点；代入(11-56)得,(11-58),另若cw 平均每个顾客在系统等待单位时间的损失，则(11-56)中的L需用,代替；,这时*不宜用解析公式表示，可用 非线性规划 的 数值法 求解。,第九章 服务系统规划,设目标函数为f(s)=c2s+cwL(s)其中：s 并联服务台的个数(待定)f(