管理运筹学服务系统规划

服务系统规划第一节：服务排队现象及其建模第二节：排队系统的常用分布第三节：单服务台模型第四节：多服务台模型第五节：其他服务时间分布模型第六节：服务系统规划的应用一、现实中的服务排队现象所谓排队，是指需要得到某种服务的对象加入等待的队列。需要得到服务的对象泛称为顾客，而从事服务的设施或人等泛称为服务台。顾客与服务台构成一个系统，称为服务系统。在一个服务系统中，若某一时刻顾客的数目超过服务台的数目，则称为拥挤，这时必然导致一些顾客不能立即得到服务而需要等待，从而产生排队现象。由于拥挤而产生排队现象的服务系统称为排队系统。在日常的工作与生活中，人们经常会遇到各种各样的服务系统如进食堂就餐、到图书馆借书、去车站乘公共汽车、去医院看病、到售票处购票、上高速公路行驶（如图9-1）等，食堂的服务员与就餐者、图书馆的管理员与借阅者、公共汽车与乘客、医生与病人、售票员与顾客、高速公路与车辆均构成了服务系统。在各种排队系统中：①顾客可以是人，也可以是物。如待分类的图书、待送的邮件，等等，这些是有形的顾客；还有无形的顾客，如呼叫电话、故障信号、新闻、事务，等等。因此顾客的等待排队也可以是有形的或无形的，集中的或分散的。②服务台可以是人，如维修工人；也可以是设施，如投币电话亭；还可以是一个系统，如医生、护士、手术台、手术机械、药品等的有机整体构成一个服务台；服务台可以是固定的，也可以是流动的，如沿街叫卖的个体商贩；服务方式也可以是登门服务，如自来水、供电、煤气公司派人到用户住址看表计价，维修工人到故障机器前进行维修，等等。表9-1现实中的各种服务系统顾客服务内容服务台考生报名登记招考登记员病人诊断病情医生电话呼叫通话交换台驶入港口的货船装（卸）货装（卸）货码头（泊位）文件稿打字打字员提货单提取存货仓库管理员不能运转的机器修理修理技工上游河水进入水库放水，调整水位水闸管理员进入我方阵地的敌机我方高射炮进行射击我方高射炮二、排队系统的组成和特征一般的排队系统都有三个基本组成部分：①输入过程；②排队规则；③服务机构。1.输入过程输入即指顾客到达排队系统，可能有以下各种不同情况。⑴顾客的总体（顾客源）的组成可能是有限的，也可能是无限的。上游河水流入水库可以认为总体是无限的，工厂内停机待修的机器显然是有限的总体。⑵顾客到来的方式可能是一个一个的，也可能是成批的。例如到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客，我们将只研究单个到来的情形。⑶顾客相继到达的间隔时间可以是确定型的，也可以是随机型的。如在自动装配线上装配的各部件就必须按确定的时间间隔到达装配点，定期运行的班车、班轮、班机的到达也都是确定型的。但一般到商店购物的顾客、到医院诊病的病人、通过路口的车辆等，它们的到达都是随机型的。对于随机型的情形，要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布。⑷顾客的到达可以是相互独立的，就是说，以前的到达情况对以后顾客的到来没有影响，否则就是有关联的。例如，工厂内的机器在一个短的时间区间内出现停机（顾客到达）的概率就受已经待修或被修理的机器数目的影响。本章主要讨论的是相互独立的情形。⑸输入过程可以是平稳的，或称对时间是齐次的，是指描述相继到达的间隔时间分布和所含参数（如期望值、方差等）都是与时间无关的，否则称为非平稳的。非平稳情形的数学处理是很困难的。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是连续变量，所建立的方程组一般属微分方程组，其解是瞬态性质，不容易求解。因此，我们常取稳态解，即令limt→Pj(t)=Pj稳态解的物理意义是，当系统开始运行一定长度的时间后，系统的状态概率分布逐渐趋于稳定，不再随时间的变化而变化。实际上，并不需要t，系统才会稳定下来。如百货商场刚开门时，顾客必然进的多，出的少，Pj(t)随时间改变，但当过一段时间后，进、出的顾客大体上就达到平衡，状态概率就呈现稳定状态，所以稳态也称统计平衡状态。求稳态概率是，只需令Pj(t)=0即可。在排队系统中，顾客相继到达的时间间隔与服务的时间分布主要有:1.负指数分布;2.泊松分布;3.爱尔朗分布等。一、泊松过程设N(t)表示在[0,t)时段内到达的顾客数(t0)令Pn(t1,t2)表示在时间区间[t1,t2)(t2t1)内有n(n≥0)个顾客到达（随机事件）的概率，即:当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)}服从泊松分布。期望值E[N(t)]=t；方差Var[N(t)]=t期望值与方差相等，是泊松分布的一个重要特征，可以利用此性质对一个经验分布是否合于泊松分布进行初步的判别。二、负指数分布若随机变量T的概率密度为则称T服从负指数分布。其分布函数为数学期望方差标准差负指数分布有以下性质：(1)密度函数fT(t)对