2019年运筹学实用教程.ppt

运筹学实用教程排队论第八章排队论第一节服务系统的基本概念第二节服务系统的基本数学模型——生灭过程单通道服务系统[M/M/1]第四节多通道服务系统[M/M/C]第五节其它类型的服务系统第六节服务系统的优化问题第七节服务系统案例分析第一节服务系统的基本概念服务系统的构成顾客服务机构（服务通道）队列服务规则服务规则是指服务机构进行服务时选择顾客的规则。一般分为先到服务（FCFS-FirstComeFirstServed），后到先服务（LCFS-LastComeFirstServed），随机服务（RSS-RandomSelectionforService）和有优先权的服务（PR-Priority）四种。服务机构的特点服务系统的主要分类单通道单通道—顾客源无限，系统空间无限顾客源无限，系统空间有限顾客源有限，系统空间有限多通道—顾客源无限，系统空间无限多通道单通道混合制损失制等待制服务系统多通道顾客源无限，系统空间有限顾客源有限，系统空间有限服务系统的运行指标队长（Ls）指系统中顾客数的数学期望值。排队长（Lq）指系统内排队顾客数的数学期望值。很显然，Ls＝Lq＋正在被服务顾客数的期望值。逗留时间（Ｗs）指一个顾客在系统中停留时间的数学期望值。等待时间（Wq）指一个顾客在系统中排队等待时间的数学期望值。很显然，Ｗs＝［等待时间］＋［服务时间］忙期指服务员忙于服务的时间。与此相反的指标是闲期，指服务员空闲的时间。系统损失率即系统满员，顾客到达后马上离开的概率。服务系统的决策变量决定一个服务系统运行指标的变量有：顾客到达服务系统的平均速率和规律，服务机构的平均服务速率μ和规律，以及服务通道的数目。顾客到达服务系统的规律定义同时具有平稳性、无后效性和普通性的流叫做最简单流或泊松流。对泊松流从数学上可以证明，在时间t，系统内有n个顾客到达的概率服从泊松分布t0n=0，1，2，…其数学期望μ=λt，方差=λt。()()!ntntPten服务时间υ的分布规律在一般情况下，当服务机构只有一个服务项目时，对一个顾客的服务时间，也就是在忙期两顾客离开系统的时间间隔，服从参数为μ的负指数分布()()!ntntPten()tfte1()E21[]D爱尔朗（Erlang）分布当服务机构是由连续的k个服务项目构成，且每个项目的服务时间都服从参数相同的负指数分布时，整个服务时间服从k阶爱尔朗分布。1()()(1)!kktkkktbtek1()ET21[]DTk服务系统模型的符号表示法为了使用上的方便，肯达（Kendal）在1953年归纳了一种服务系统的符号表示法。它用[A/B/C]表示一个服务系统的特征。其中A处填写顾客到达的规律；B处填写服务时间的分布规律；C处填写服务通道的数目。填写的符号有：M——泊松过程或负指数分布（马尔可夫随机过程）：D——确定型；Ek——k阶爱尔朗分布；GI——一般相互独立的随机分布；G——一般随机分布。如[M/M/1]表示顾客到达过程是泊松过程，服务时间间隔从负指数分布，单通道服务系统。由于顾客源的性质及系统容量的大小对服务系统的运行特性有很大影响，因此在1966年A·M·里氏（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时，服务时间间隔服从参数为的负指数分布在一个无限短的时间间隔里，最多只有一个顾客到达或离去二、生灭过程的假设条件三、生灭过程的状态转移图生灭过程的瞬时状态一般很难求得，但可求得稳定状态分布对于稳定的生灭状态，从平均意义上说有：“流入=流出”稳定的生灭过程可以用状态转移图表示一般状态转移图示例012nn-10122n1nn1231nn1n四、生灭过程的稳态方程基本原理系统任意状态n达到稳态平衡的条件是：产生该状态的平均速率等于该状态转变成其他状态的平均速率例如，对于系统状态n=0的情况，产生和破坏该状态的可能性有两种情况。如后图所示。n=0的状态的产生和破坏012nn-10122n1nn1231nn1n0011ppn=1状态的产生和破坏012nn-10122n1nn1231nn1n1112200)(pppn=2状态的产生和破坏012nn-10122n1nn1231nn1n2223311)(ppp状态(n-1)的产生和破坏012nn-10122n1nn1231nn1n11122)(nnnnnnnppp任意状态n的产生和破坏012nn-10122n1nn1231nn1nnnnnnnnppp)(1111生灭过程的基本公式,2,1,,01210121012101210120120101npCpCppppppnnnnnnnnnnnn则记生灭过程的状态概率1100110001,111)1(1nnnnnnnnnnnnCCpCppCpCpp因为所以即得服务系统的其它基本指标平均队长：系统状态的数学期望（顾客数的期望值）平均排队长：排队顾客数的期望值，假设服务台数=C0nnsnpL1)(CnnqpCnL五、Little公式下列公式对任何服务系统均成立(Little)eqqessLWLW,eqsqsLLWW,10nnneP其中有效到达率为第三节单通道服务系统M/M/1系统M/M/1/N系统M/M/1/m/m系统一、M/M/1系统系统状态分布nn,)1(nnnC对于C=1的系统:所以其中系统的分布所以其中0ppnn1111111010nnnnp,2,1,0,)1(npnn结果系统的其它指标：平均队长111)1()()1()()1()1(0010ddddddnnpLnnnnnnnns系统的其它指标：平均排队长)(1)1()1(220111ssnnnnnnqLpLpnppnL系统的其它指标：平均逗留时间tetTP)()(1)(TEWs11)()()(sqqqsq逗留时间分布为所以平均逗留时间又因为所以平均排队时间：讨论与Little公式1.关于：叫做服务强度，反映了服务员忙期所占的比例，同时实际上也是平均服务台数。2.指标参数之间的关系—Little公式qqssqsqsWLWLWWLL,(1(平均服务时间）平均服务台数）M/M/1系统举例：例8-1有一火车售票处，设有一个售票窗口，顾客到达为泊松流，平均到达率为0.3人/分。服务时间服从负指数分布，平均服务率为0.4人/分，试求服务系统的各项指标和顾客逗留15分钟以上的概率。解：已知条件1)服务强度和空闲率4.0,3.025.01,75.0/0P例8-1继续求解2）系统状态的概率3）平均队长和平均排队长,3,2,175.025.0)1(0nPPnnnn)(25.2375.0)(33.04.03.0人人sqsLLL例8-1继续求解顾客的逗留时间和排队时间顾客在系统中逗留15分钟以上的概率)5.74.0/110/1()(5.73.025.2)(103.03sqqssWLWLW分钟分钟22.0)15(5.1)(15eetP二、M/M/1/N系统稳态时的状态分布NnNnNnnn,,2,1,,01,,2,1,0,NnppNnNnCnnnnn,,2,1,,0,,2,1,0M/M/1/N的状态分布1,111,1111111111101211100NpNppNNNNnnNnnNnn时，上式当所以，，因为M/M/1/N系统的空间指标1.平均队长1,211,1)1(111NNLNNs1,)1(2)1(1,1)1(11NNNNLNNq2.平均排队长111112001011001)1(1)1)(1(1)1)(1()1)(1(1)1(1)1(NNNNNNNNNnnNnnNnnsNNNpddpddpnpnpL2111000NnNpnnpLNnNnnNnns当=1时：当时：11,)1(2)1(1,1)1(1)1()1(10111NNNNpLpnppnLNNsNnnNnnNnnqM/M/1/N系统的有效到达率和时间指标1.有效到达率2.平均时间指标001)1()1(pCppeNe1,)1(seqqNsessWLWpLLW指标公式的进一步讨论)1(0pLCLLssq2)与前面的结果一致)1()111(1)1()1()1(11)1(01111ppNNNNNNNNe1)证明有效到达率公式损失制系统M/M/1/1当系统的容量N=1时，有0,1)1(0,11,1101110qeseqsWLWppLpLpp该系统中只要有人在接受服务，顾客到达即离开。这是一种完全损失制，例如打电话，有人占线，就只能重打。M/M/1/N系统举例：例8-2某理发店有一个理发师，有六张椅子接待人们排队等待理发。椅子坐满时，后到的旅客就离开。顾客到达为泊松流，平均到达率为3人/小时。理发平均需要15分钟，服从负指数分布。试求该理发服务系统的运行指标。解：这是一个M/M