运筹学实用教程_(5).ppt

运筹学实用教程（第二版）第五部分：排队论,制作单位:南京航空航天大学经济与管理学院制作人:宁安琪宁宣熙朱金福2007年6月,第八章排队论,第一节服务系统的基本概念第二节服务系统的基本数学模型生灭过程单通道服务系统m/m/1第四节多通道服务系统m/m/c第五节其它类型的服务系统第六节服务系统的优化问题第七节服务系统案例分析,第一节服务系统的基本概念,服务系统的构成,顾客服务机构（服务通道）队列服务规则服务规则是指服务机构进行服务时选择顾客的规则。一般分为先到服务（fcfs-firstcomefirstserved），后到先服务（lcfs-lastcomefirstserved），随机服务（rss-randomselectionforservice）和有优先权的服务（pr-priority）四种。,服务机构的特点,服务系统的主要分类,服务系统的运行指标,队长（ls）指系统中顾客数的数学期望值。排队长（lq）指系统内排队顾客数的数学期望值。很显然，lslq正在被服务顾客数的期望值。逗留时间（s）指一个顾客在系统中停留时间的数学期望值。等待时间（wq）指一个顾客在系统中排队等待时间的数学期望值。很显然，s等待时间服务时间忙期指服务员忙于服务的时间。与此相反的指标是闲期，指服务员空闲的时间。系统损失率即系统满员，顾客到达后马上离开的概率。,服务系统的决策变量,决定一个服务系统运行指标的变量有：顾客到达服务系统的平均速率和规律，服务机构的平均服务速率和规律，以及服务通道的数目。,顾客到达服务系统的规律,定义同时具有平稳性、无后效性和普通性的流叫做最简单流或泊松流。对泊松流从数学上可以证明，在时间t，系统内有n个顾客到达的概率服从泊松分布t0n=0，1，2，其数学期望=t，方差=t。,服务时间的分布规律,在一般情况下，当服务机构只有一个服务项目时，对一个顾客的服务时间，也就是在忙期两顾客离开系统的时间间隔，服从参数为的负指数分布,爱尔朗（erlang）分布,当服务机构是由连续的k个服务项目构成，且每个项目的服务时间都服从参数相同的负指数分布时，整个服务时间服从k阶爱尔朗分布。,服务系统模型的符号表示法,为了使用上的方便，肯达（kendal）在1953年归纳了一种服务系统的符号表示法。它用a/b/c表示一个服务系统的特征。其中a处填写顾客到达的规律；b处填写服务时间的分布规律；c处填写服务通道的数目。填写的符号有：m泊松过程或负指数分布（马尔可夫随机过程）：d确定型；ekk阶爱尔朗分布；gi一般相互独立的随机分布；g一般随机分布。如m/m/1表示顾客到达过程是泊松过程，服务时间间隔从负指数分布，单通道服务系统。,由于顾客源的性质及系统容量的大小对服务系统的运行特性有很大影响，因此在1966年am里氏（lee）在肯达符号的基础上提出再增加三个符号，即a/b/c：d/e/f。其中，d处填写服务系统的最大容量；e处填写顾客总体的数量；f处填写服务规则。例如m/ek/c：n/fcfs表示输入过程是泊松过程，服务时间服从k阶爱尔朗分布，有c个服务员，系统空间容量为n个顾客，顾客源是无限的，服务规则是先导先服务。,随机聚散系统-生灭过程,排队系统随机聚散服务系统顾客到达是“生”，顾客离开是“灭”,第二节服务系统的数学模型-生灭过程,马尔科夫随机过程生灭过程的假设条件生灭过程的状态转移图生灭过程的稳态方程little公式,一、马尔科夫随机过程,随机过程：生灭随机导致系统状态随机马尔科夫随机过程某时刻系统未来的状态只与该时刻系统状态有关，而与此时刻以前的状态无关（无后效性）泊松过程是马尔科夫过程本章主要考虑马尔科夫过程，即泊松流。,系统状态n(t)得分布具有下列性质时，称其为一个生灭过程：当n(t)=n时，顾客到达的时间间隔服从参数为的负指数分布当n(t)=n时，服务时间间隔服从参数为的负指数分布在一个无限短的时间间隔里，最多只有一个顾客到达或离去,二、生灭过程的假设条件,三、生灭过程的状态转移图,生灭过程的瞬时状态一般很难求得，但可求得稳定状态分布对于稳定的生灭状态，从平均意义上说有：“流入=流出”稳定的生灭过程可以用状态转移图表示,一般状态转移图示例,四、生灭过程的稳态方程,基本原理系统任意状态n达到稳态平衡的条件是：产生该状态的平均速率等于该状态转变成其他状态的平均速率例如，对于系统状态n=0的情况，产生和破坏该状态的可能性有两种情况。如后图所示。,n=0的状态的产生和破坏,n=1状态的产生和破坏,n=2状态的产生和破坏,状态(n-1)的产生和破坏,任意状态n的产生和破坏,生灭过程的基本公式,生灭过程的状态概率,因为,所以,即得,服务系统的其它基本指标,平均队长：系统状态的数学期望（顾客数的期望值）平均排队长：排队顾客数的期望值，假设服务台数=c,五、little公式,下列公式对任何服务系统均成立(little),其中有效到达率为,第三节单通道服务系统,m/m/1系统m/m/1/n系统m/m/1/m/m系统,一、m/m/1系统,系统状态分布,对于c=1的系统:,所以,其中,系统的分布,所以,其中,结果,系统的其它指标：平均队长,系统的其它指标：平均排队长,系统的其它指标：平均逗留时间,逗留时间分布为,所以平均逗留时间,又因为,所以平均排队时间：,讨论与little公式,1.关于：叫做服务强度，反映了服务员忙期所占的比例，同时实际上也是平均服务台数。2.指标参数之间的关系little公式,m/m/1系统举例：例8-1,有一火车售票处，设有一个售票窗口，顾客到达为泊松流，平均到达率为0.3人/分。服务时间服从负指数分布，平均服务率为0.4人/分，试求服务系统的各项指标和顾客逗留15分钟以上的概率。解：已知条件1)服务强度和空闲率,例8-1继续求解,2）系统状态的概率3）平均队长和平均排队长,例8-1继续求解,顾客的逗留时间和排队时间顾客在系统中逗留15分钟以上的概率,二、m/m/1/n系统,稳态时的状态分布,m/m/1/n的状态分布,m/m/1/n系统的空间指标,1.平均队长,2.平均排队长,当=1时：,当时：,m/m/1/n系统的有效到达率和时间指标,1.有效到达率,2.平均时间指标,指标公式的进一步讨论,2),与前面的结果一致,1)证明有效到达率公式,损失制系统m/m/1/1,当系统的容量n=1时，有,该系统中只要有人在接受服务，顾客到达即离开。这是一种完全损失制，例如打电话，有人占线，就只能重打。,m/m/1/n系统举例：例8-2,某理发店有一个理发师，有六张椅子接待人们排队等待理发。椅子坐满时，后到的旅客就离开。顾客到达为泊松流，平均到达率为3人/小时。理发平均需要15分钟，服从负指数分布。试求该理发服务系统的运行指标。解：这是一个m/m/1/7排队系统，且,例8-2的求解,1）旅客到达就理发的概率、顾客损失率和有效到达率,例8-2继续求解,2）平均队长、平均排队长、平均时间,三、m/m/1/m/m系统,典型的情况是工厂内的机器待修问题，因此俗称“机修模型”。状态转移图为,系统参数,平均到达率，设每台机器的平均故障率为，则cn,状态分布概率,求p0和pn,有效到达率和平均队长,有效到达率因此,平均队长和平均排队长,由上式得顾客平均等待时间,因此,m/m/1/m/m系统举例：例8-3,一个工人看管3台机床，每台机床每运转1小时平均出两次故障，该工人排除故障每次平均需10分钟。试求工人忙期概率，实际每小时平均修理机床数，出故障机床的平均数和机床因故障而损失的能力。解：已知(1)工人闲期概率,工人忙期概率和每小时修理机床数,工人闲期和忙期概率工人每小时修理机床数,故障机床平均数和损失的能力,故障机床平均数因故障而损失的能力，是故障机床平均数与机床总数的比值,作业,习题8.1-8.4，p.274,第四节多通道服务系统(m/m/c),m/m/c系统m/m/c/n系统m/m/c/m/m系统,第四节多通道服务系统(m/m/c),m/m/c系统m/m/c/n系统m/m/c/m/m系统,一、m/m/c系统,系统的参数为,设,m/m/c系统的状态转移图,该系统容量无限大，是等待制系统，但有c个服务台。设每服务台的服务率为,系统状态分布,因此,系统无顾客的概率,所以,顾客到达后需要等待的概率,很容易证明,顾客到达后立即能得到服务的概率,平均空间指标和平均时间指标,平均空间指标,平均时间指标little公式,关于lq的公式的推导,关于平均工作服务台数公式的推导,m/m/c系统应用举例：例8-4,在例8-1的情况下，购票顾客平均到达率增加了一倍，达0.6人/分钟，而服务速率未变，因而产生了过长的排队现象。为解决该问题，准备增加窗口。有两个方案：一个是在另一处再设一个售票点，另一个是在原售票处增设一个售票窗口，试问哪一种方案好？（从系统效率考虑）解：采用第一方案时，相当于两个m/m/1系统，假设每个售票点的平均到达率相同，即为0.3人/分钟，此时与例8-1的运行指标完全一样。,例8-4的第二方案分析,第二方案相当于m/m/2系统，参数是售票处无顾客的概率,例8-4的第二方案分析,顾客到达需要等待的概率平均排队长平均队长,例8-4的第二方案分析,顾客平均逗留时间顾客平均排队时间,例8-4的两个方案的比较,一个m/m/2系统比两个m/m/1系统服务效率高，见下表,作业,习题8，p.275,二、m/m/c/n系统,系统参数（nc),m/m/c/n的状态转移图,是每服务台的服务率,m/m/c/n系统的状态分布,顾客到达需等待的概率和平均排队长：,顾客到达需等待的概率和平均排队长：,平均排队长的另一种形式：,m/m/c/n系统的平均队长,由于,所以,m/m/c/n系统的平均服务台数,与前式比较后有,当c=1时的m/m/c/n系统,有效到达率和平均时间,可以证明当c=1时，,m/m/c/n系统举例：例8-5,某汽车加油站有两个加油机，汽车按poisson流到达，平均每分钟到达2辆；汽车加油时间服从负指数分布，平均加油时间是2分钟。又知加油站最多可停3辆等待加油的汽车，试求该系统的性能指标。,解：这是m/m/2/5排队系统，且已知,例8.5的系统空闲的概率、顾客损失率、顾客到达需等待的概率、平均服务台数、有效到达率,例8.5的平均队长、平均排队长、平均逗留时间、平均排队时间,m/m/c/c损失制系统(n=c),m/m/c/c损失制系统的运行指标,有效到达率(绝对通过能力),平均队长平均逗留时间相对通过能力服务台（通道）利用率,三、m/m/c/m/m系统,系统特征说明,系统状态转移图,是没顾客平均到达率，是每服务台平均服务率。,系统参数，系统状态转移率,系统状态分布,系统运行指标：平均排队长,平均队长和平均时间指标,m/m/c/m/m系统举例：例8.6,设有一个工人看管5台机器，每台机器正常运转的时间服从负指数分布，平均为15分钟。当发生故障后，每次修理时间服从负指数分布，平均为12分钟。试求系统的有关运行指标。解：这是m/m/1/m/m系统，并且,例8.6求解,可见工人的劳动强度太大，且技术水平不高。应增加工人或提高技术水平。,作业,习题5、6、9，p.275,第五节其它类型的服务系统,服务规则对系统运行指标的影响一般服务时间m/g/1模型,一、服务规则对系统运行指标的影响,服务规则的不同对顾客会产生较大影响但对系统没有影响，因此系统指标不变本章所学习的六个模型对非fcfs规则的系统仍然有效,二、一般服务时间m/g/1模型,服务时间一般分布时，需要知道服务时间的均值和方差。当时，排队系统可以达到平稳状态。p-k公式,关于p-k公式的讨论,1.当服务时间服从负指数分布时，因此，得到与前述结果一样。2.当服务时间为定长时，则,只有负指数分布时排队长的一半。服务时间定长时，系统是有效的。,3、非生灭过程排队模型：m/ek/1,若顾客需接受k个串行的服务台的服务后才离开，且每个服务台服务时间服从负指数分布，平均服务时间相等。若顾客以相等数量的团队到达，每个顾客都接受服务后才集体离开，且服务时间服从负指数分布。以上两种情况都可看作是m/ek/1系统，其中总服务时间服从k阶爱尔朗分布。可用当g是ek时的m/g/1模型。,erlang分布的均值、方差和阶数,总服务时间服从爱尔朗分布，其均值和方差是,由此可得爱尔朗分布的阶数：,每个服务台的平均服务时间是：,m/ek/1系统的运行指标,代入一般公式，可得：,m/ek/1系统性能的讨论,当erlang分布的阶k=1时，是负指数分布，当k增大时，它逐步趋近于正态分布，当k趋近于无穷大时，它又趋近于确定性分布。从前面的公式可看出:当k=1时，m/ek/1与负指数分布(m/m/1)的相同;当k趋近于无穷大时，又可得到m/d/1的公式。从这些公式可看出：m/m/1系统的顾客排队等待的时间最长，m/d/1系统的顾客等待的时间最短(只有m/m/1的一半)，而m/ek/1系统则处于中间，且当k增大时，系统的指标逐步变优。,一般时间分布模型举例：例8-7,有一汽车冲洗台，汽车按poisson流到达，平均每小时到达18辆；冲洗时间t的平均值=0.05小时/辆，方差var(t)=0.01(小时/辆)2，求该洗车台的运行指标，并对它进行评价。解：本例是m/g/1系统，且已知,例8-7的运行指标计算,可见顾客等待时间太长，队列也太长。主要原因是服务时间的方差太大！,m/ek/1系统应用举例：例8-8,某一电话亭顾客按poisson流到达，平均每小时到达6人，平均通话时间8分钟，方差为16分钟2。估计通话时间服从爱尔朗分布(相当于分几个阶段服务)。管理人员想知道平均排队长和顾客等待时间。解：对于本系统已知,例8-8的运行指标,erlang分布的阶,顾客平均排队长和平均排队时间,关于例8-8结果的讨论,如果服务时间服从负指数分布，则,此时顾客需要等待更长的时间。服务时间应当尽可能固定，这样可以改善系统性能。,16（分钟）2,作业,习题10，p.275,第六节服务系统的优化问题,排队系统需要优化的依据和一般解法m/m/1系统中服务率的优化m/m/c系统中服务台数的优化,一、服务系统需要优化的依据,提高服务水平可以减少顾客等待的成本，但同时增加服务机构的成本；顾客等待成本高将意味着顾客的流失，同样会减少服务机构的收益；服务机构与顾客等待的合并费用存在最小点；服务水平可用平均服务率、服务台数以及系统容量来表示。,服务系统的成本,服务系统优化分类与成本问题,排队系统优化的分类优化设计静态优化，本章考虑该类优化问题；最优控制动态优化。排队系统的服务成本容易计算或估算，但顾客排队等待的损失比较复杂，而顾客流失给服务机构带来的损失则更是不容易估计的。,服务系统优化的一般方法,可以优化合并成本，或优化系统的利润；对于连续性的优化变量可采用分析法令导数等于零；对于离散型的优化变量可采用边际分析法：最优点相对于它两边最邻近的整数点是最优的。,二、m/m/1系统中服务率的优化,优化该系统的合并成本,合并成本,从,得最优服务率,m/m/1系统服务率优化举例：例8-9,设货船按poisson流到达一港口，平均到达率为50条/天。已知船在港口停泊一天的费用为1货币单位，平均每条船的卸货费为2货币单位。要求使总费用最少的平均服务率。解：已知,例8-9的优化计算,将已知数据代入上述公式得：,此时的总费用为,三、m/m/c系统中最佳服务台数,优化的目标函数是平稳状态下单位时间合并费用的平均值。,上式中，cs是每服务台单位时间的费用。由于优化参数是服务台数，是离散的，因此采用边际分析法。,边际分析法求最佳服务台数,设c*是最佳服务台数，则边际分析法的基本公式是,具体地，也就是,最佳服务台数应当满足的条件,进一步化简得,因此得：,最佳服务台数举例：例8-10,某检验中心为各工厂服务，工厂到达服从poisson流，平均到达率为48次/天；每次来检验造成停工损失6元/天；服务时间服从负指数分布，平均服务率为25次/天；每设置一个检验员的服务成本4元/天。问应设几个检验员可使总费用的平均值最少？,例8-10的计算,解：此是为m/m/c等待制系统优化服务台数的问题，应用边际分析法。已知,设检验员数为c，则由于,边际分析函数,其中,例8-10的优化结果,为保证1p00，从上述公式可看出应当有c=2。由于,例8-10的最小总费用,因此最优检验员数为3个，此时总费用最小值为z(3)=12+6*2.645=27.87(元)。,第七节服务系统实例分析,服务银行系统的设计决策问题人事顾问决策问题,一、银行服务系统设计决策问题,某市准备在市中心设立一家银行。已知顾客的到达服从泊松分布，平均到达率为0.33人/分钟。银行出纳员的服务时间服从负指数分布，平均服务率为0.42人/分钟。要求系统中顾客平均数不超过6人，每个顾客的平均等待时间不超过5分钟。银行设计人员经过初步考虑，提出三种方案：,1）建立一个出纳员的银行系统2）建立两个出纳员的银行系统3）建立一个出纳员，但配有计算机系统，使服务时间为定常的银行系统，且服务率为0.5人/分钟。经过估算，一个出纳员的年薪