运筹学 朱道立课件10

教学要求：

第十章排队论了解排队论的基本分析方法掌握基本的排队模型

会运用这些模型分析一些管理中的基本排队问题目录排队论的一些术语

到达过程和服务过程模型生灭过程M/M/1/GD/∞/∞排队系统M/M/1/GD/c/∞排队系统M/M/s/GD/∞/∞排队系统目录排队论的一些术语到达过程和服务过程模型生灭过程M/M/1/GD/∞/∞排队系统M/M/1/GD/c/∞排队系统M/M/s/GD/∞/∞排队系统实用举例情况输入过程输出过程银行顾客到达银行柜员为顾客服务比萨营业厅接到外卖比萨的请求比萨被送出医院血库血液到达病人用血海军修船厂船只老化，被送到修船厂维修船只修好，重返大海到达过程输入过程通常也叫到达过程（arrivalprocess），到达的对象叫做顾客（customer）成批到达（bulkarrival）如果在同一时刻有两个或两个顾客到达顾客被损失掉了（balked）一个顾客到达但不能进入系统有限源模型（finitesourcemodel）顾客来源于很小范围的模型输出/服务过程排队系统的输出过程经常也被称作服务过程（serviceprocess）服务时间分布（servicetimedistribution）一个顾客服务时间的概率分布服务时间分布与当前顾客数无关并行服务方式（serversinparallel）所有的服务台提供相同的服务，一个顾客只需通过一个服务台便能完成服务银行柜台串行服务方式（serversinseries）顾客必须经过几个服务台才能完成服务装配流水线排队规则排队规则是指决定哪个顾客先被服务的准则FCFS（firstcome，firstservice）顾客按照到达先后顺序接受服务LCFS（lastcome，firstservice）最近到达的顾客最先接受服务SIRO（serviceinrandomorder）规则下一个接受服务的顾客从等待顾客中随机选择有优先权的排队规则（priorityqueuingdiscipline）将所有顾客划分成若干个类，并给每一类一个优先级，在类的内部执行FCFS规则顾客进入队列方式顾客是否可以自己决定进入哪个队列是否允许顾客更换队列目录排队论的一些术语到达过程和服务过程模型生灭过程M/M/1/GD/∞/∞排队系统M/M/1/GD/c/∞排队系统M/M/s/GD/∞/∞排队系统到达过程模型假设在同一时刻最多有一名顾客到达，ti——第i个顾客到达的时间，则当i≥1时，Ti=ti+1-ti——第i个顾客和第i+1个顾客到达的间隔时间。假设Ti独立同分布，将该分布的随机变量记为A设的密度函数为a(t),对于一个很小的正实数Δt到达过程模型1/λ——平均到达间隔时间（小时）指数分布的密度函数指数分布的无记忆性引理1：如果服从指数分布，则对任意的非负常数和有证明： 由得 而 则 因此泊松分布与指数分布的关系定理1：到达间隔时间服从参数为的指数分布的充分必要条件是长度为的时间段内到达的顾客数量服从参数为的泊松分布（thePoissondistribution）。如果一个离散随机变量满足（n＝0,1,2,……） 我们就说服从参数为的泊松分布，且N的期望和方差为：

Ni——任意长度为的时间段到达的顾客的数量，由定理1：（n＝0,1,2,……）服从参数为的泊松分布，且E(Nt)=D(Nt)=λt泊松分布与指数分布的关系假设1：在一组相互不重叠的时间段中，各时间段内顾客到达的情况是相互独立的假设2：对于一个很小的实数Δt和任意值t为，在时间t到t+Δt之间有一个顾客到达的概率为λΔt+O(Δt)，O(Δt)为任意满足下式的值：

并且，在时间t到t+Δt之间没有顾客到达的概率为1-λΔt+O(Δt)

，在时间t到t+Δt之间有超过一个顾客到达的概率为O(Δt).定理2：如果假设（1）和（2）成立，则长度为t的时间段 内到达顾客数量Nt服从参数为λt的泊松分布，顾客到 达间隔时间A服从参数为λ的指数分布。泊松分布与指数分布的关系例1：一个饭店中每小时销售出去的啤酒杯数服从λ＝30杯/小时的泊松分布。求：

a）上午10点到12点之间恰好卖出60杯啤酒的概率；

b）上午9点到下午1点卖出啤酒数的均值和标准差；

c）连续卖出两杯啤酒的间隔时间在1～3分钟之间的概率解：a）上午10点到12点之间卖出的啤酒数量服从参数为2×30＝60的泊松分布， 由公式（7）得，上午10点到12点之间恰好卖出60杯啤酒得概率为：泊松分布与指数分布的关系b）由已知得＝30杯/小时，＝4小时。上午9点到下午1点卖出啤酒数的均值为4×30＝120杯。上午9点到下午1点卖出啤酒数的标准差为。c）设为相继卖出的两杯啤酒的间隔时间。每分钟卖出的啤酒数量服从参数为30/60＝0.5的指数分布，因此，随机变量X的概率密度函数为0.5e0.5t。则爱尔朗分布如果随机变量T的概率密度函数为 其中包括两个参数，到达率参数（rateparameter）R，形状参数（shapeparameter）K（为非负整数），则称T服从到达率参数为R，形状参数为K的爱尔朗分布。

（t≥0)爱尔朗分布f(t)k=1k=2k=4k=6k=20服务过程模型假设不同顾客的服务时间是相互独立的随机变量S，且S的概率密度函数为s(t)。用表示顾客服务时间的平均值，则

1/μ——每个顾客的平均服务时间

μ

——单位时间服务顾客的平均数量，通常称为服务率服务过程模型（三服务台系统）每一个服务台的服务时间都服从概率密度函数为 的指数分布顾客1顾客2顾客3顾客4服务过程模型实际情况中的服务时间往往不具有无记忆性。我们通常假设s(t)服从形状参数为k，服务率参数kμ为的爱尔朗分布。步骤1步骤1步骤1服务开始服务结束均值为1/kμ的指数分布均值为1/kμ的指数分布均值为1/kμ的指数分布排队系统的符号表示为了描述这样的排队系统，Kendall（1951）发明了下列符号。每一个排队系统由6个字母表示：

1/2/3/4/5/6。第一个字母表示到达过程的类型：

M＝到达间隔时间相互独立，且服从指数分布；

D＝到达间隔时间相互独立，且是定长的；

Ek＝到达间隔时间相互独立，且服从形状参数为的爱尔朗布；

GI＝到达间隔时间相互独立，且服从其它一般的分布。排队系统的符号表示第二个字母表示服务时间的类型：

M＝服务时间相互独立，且服从指数分布；

D＝服务时间相互独立，且是定长的；

Ek＝服务时间相互独立，且服从形状参数为的爱尔朗分布；

G＝服务时间相互独立，且服从其它一般的分布。第三个字母表示并行的服务台的数量。排队系统的符号表示第四个字母表示排队规则。

FCFS＝先到先服务；

LCFS＝后到先服务；

SIRO＝随机服务；

GD＝其他一般的规则。第五个字母表示系统最大容量（包括正在队列中等待的顾客和正在服务台接受服务的顾客）。第六个字母表示顾客源的数量。除非潜在顾客的数量和服务台的数量是同一数量级的，否则我们认为顾客源的数量为无穷个许多重要的模型的4/5/6为GD/∞/∞

。这种情况下，后三个字母通常省略。等待时间的悖论问题：假设学生中心公车的到达间隔时间服从均值为60 分钟的指数分布。如果我们到达学生中心的时间是随 机的，那么我们等待公车的平均时间是多少？

(1):由指数分布的无记忆性知，无论上一辆公车何时到达，我们平均等待时间都是60分钟。

(2):在只考虑两次到达的情况下，一个人随机到达的平均等待时间等于他在相邻两辆车到达时间的中点到达的等待时间。如果我们在两辆车到达时间的中点到达，则我们只需等待（1/2）×60=30分钟。目录排队论的一些术语到达过程和服务过程模型

生灭过程

M/M/1/GD/∞/∞排队系统M/M/1/GD/c/∞排队系统M/M/s/GD/∞/∞排队系统生灭过程系统变化的定律定律1：如果t时刻生灭过程的状态为j，则在时刻t到t+Δt之间发生一个生的概率为λjΔt+o(Δt)。其中系统从j状态转移到j+1的事件叫做一个生，λj叫做生率。在大多数排队系统中，一个生意味着一个顾客的到达。定律2：如果t时刻生灭过程的状态为j，则在时刻t到t+Δt之间发生一个灭的概率为μjΔt+o(Δt)

。其中系统从状态j转移到j-1的事件叫做一个灭，μj叫做灭率。在大多数排队系统中，一个灭意味着一个顾客的服务结束。必须注意μ0=0，否则将会出现小于0的状态。定律3：生和灭相互独立。指数分布和生灭过程的关系M/M/1/FCFS/∞/∞排队系统，到达间隔时间服从参数为λ的指数分布，服务时间服从参数为μ的指数分布如果系统在t时刻的状态为j,由指数分布的无记忆性可知，在时间段[t，t+Δt]发生一个生的概率为根据泰勒展开在时间段[t，t+Δt]发生一个生的概率为λΔt+o(Δt)。因此，状态j的生率λj即是排队系统的到达率λ。指数分布和生灭过程的关系如果时刻t系统的状态为0，则没有顾客在接受服务，因此在时间段[t，t+Δt]没有顾客完成服务。因此μ0。如果时刻t系统的状态为j≥1，则只有一个顾客在接受服务（只有一个服务台）。由指数分布的无记忆性知，一个顾客在时间段[t，t+Δt]结束服务的概率为 因此，当j≥1时，μj=μ0

。M/M/1/FCFS/∞/∞系统生灭率012j-1jj+1λλλλμμμμ状态灭（服务完成）生（顾客到达）生灭过程的稳态概率的推导关键在于对于非常小的△t，找到和的关系。下表是时刻t＋△t状态概率的计算t时刻状态t+△t时刻状态事件的概率j-1j＝（Ⅰ）j+1j＝（Ⅱ）jj＝（Ⅲ）其它状态j＝（Ⅳ）生灭过程的稳态概率的推导当时，时刻t系统的状态为j-1，时刻t+△t系统的状态为的概率为.（Ⅰ）（Ⅱ）（Ⅲ）情况类似

，在（Ⅳ）情况下，系统在t到t＋△t的时间段内必然发生超过一次的生或灭。发生这种情况的概率为。ij-1j状态时间0tt+Δt生灭过程的稳态概率的推导由＝（I）+（II）+（III）+（IV）得到：

＋将等号两端同时除以△t（），则有当j＝0时，。同马尔可夫链一样，稳态概率定义为。生灭过程的稳态概率的推导在稳定状态下（），＝0，，，，带入公式，得到当时，

（）；当j＝0时，。当时，。此公式为生灭过程流平衡方程。生灭过程流平衡方程的解将所有的用代换。从j＝0的方程，得到：将这个结果代入j＝1的方程，得：即：同理，将和带入j＝2的方程，解出的值……。定义，则可证明。因为可得。生灭过程流平衡方程的解如果是有限的，可以求出的值：，然后可以求出。如果是无限的，则该生灭过程不可能出现稳定状态。最常见的例子是如果一个系统的顾客到达率大于系统的最大服务率，那么系统中顾客将会越来越多，永远也不会出现稳定状态。应用EXCEL求解稳态概率例2：某呼叫中心（callcenter）平均每小时接到1700次呼叫。相继两个呼叫的间隔时间服从指数分布。一个服务人员平均每小时可以处理30个呼叫。每个呼叫的平均处理时间也服从指数分布。该中心允许最多25个呼叫处在等待状态，如果已经有25个呼叫处在等待状态，那么新打入的呼叫将被系统忽略。该中心拥有75个服务人员，求a)所有的服务人员都处在繁忙状态的概率，b)新拨入的呼叫被系统忽略的概率。目录排队论的一些术语

到达过程和服务过程模型生灭过程M/M/1/GD/∞/∞排队系统

M/M/1/GD/c/∞排队系统M/M/s/GD/∞/∞排队系统M/M/1/GD/∞/∞排队系统M/M/1/GD/∞/∞排队系统的顾客到达间隔时间和服务时间都服从参数分别为（单位时间段内平均到达顾客数量）和（单位时间段内平均顾客服务顾客数量）的指数分布。在第三节中，我们已经说明了可以用具有下列参数的生灭过程建立M/M/1/GD/∞/∞排队系统的模型：

稳态概率的推导因为，，……。定义，称为排队系统的通行强度（trafficintensity）。得：。假设，可以求的值，故，即。可求得，，。如果，系统将不存在稳定状态。通过前面的讨论可以得出结论：时系统也不存在稳定状态。系统中的平均顾客数量L的推导假设系统已经达到稳定状态，系统中存在顾客的平均数量，即系统达到稳定状态时顾客数量的期望值。有时我们将称为平均队长。

定义：则：从而，队列中的平均顾客数量的推导我们有时把等待在队列中的人数的期望值称为平均队列长，或平均等待队长，并用来表示这个值。如果系统中只有0或1个人，则队列中没有人等待；如果系统中有j（）个人，则队列中将有j-1个人处在等待状态。因此，如果系统已经达到稳定状态，

又因为，上式可以写成：服务中的平均顾客数量的推导系统中正接受服务的人数的期望值为。对于一个M/M/1/GD/∞/∞排队系统，当它达到稳定状态时，由于一名顾客要么在队列中等待，要么正在接受服务，所以任何排队系统（不仅仅是M/M/1/GD/∞/∞排队系统）都应有，所以队列公式设某一顾客在排队系统中逗留时间的期望值为（包括在排队等待的时间和接受服务的时间），顾客的平均排队等待时间为。只有在稳定状态已经达到时，才能计算和的值。通过著名的Little公式，可以很容易求值。＝单位时间内进入系统的平均顾客数量，＝系统中平均顾客数量，＝系统中正在排队的平均顾客数量，＝系统中正在接受服务的平均顾客数量，＝顾客在系统的平均总逗留时间，＝顾客在队列中等待的平均逗留时间，＝顾客接受服务的平均时间。定理3（Little公式）对于任何存在稳态概率分布的排队系统，下列公式成立：关于Little公式的严格证明在这里从略，只进行一些启发式讨论：考虑一个先到先服务的排队系统。假设系统已经达到稳定状态，则任意一名顾客离开系统时，系统中平均有个顾客。由于系统遵守先到先服务原则，因此这些顾客的到达时间均晚于离开顾客。由于刚离开的顾客平均在系统中逗留了小时，他在系统内逗留期间平均到达人，因此。有关的严格证明与排队系统中服务台的数量、排队规则、顾客到达时间的分布和服务时间的分布无关。储蓄所的排队系统某储蓄所只有1个柜台处理个人储蓄业务，平均每小时有10名顾客来存取，平均每位顾客的服务时间为4分钟。顾客到达间隔时间和服务时间均服从指数分布。求：a)该柜台空闲的概率.b)在队列中等待的顾客平均数量（不包括正在接受服务的顾客）.c)每位顾客在银行的平均逗留时间（包括服务时间）.d)该柜台平均每小时服务的人数.解：由已知，我们可以把该柜台看作一个＝10人/小时，＝15人/小时的M/M/1/GD/∞/∞排队系统。因此，。a），该柜台将以的概率处于空闲状态。

b）（人）。c）（人）。（小时）d）如果该柜台一直处在繁忙状态，那么平均每小时可以服务15人。由（1）可知，该柜台只有的时间处在繁忙状态。因此每小时该柜台平均服务人。加油站的排队系统假设车主在汽车油量正好消耗至油箱一半时给汽车加油。某一单泵加油站平均每小时有7.5辆车来加油。平均每辆车需要4分钟完成整个加油过程。设汽车的到达间隔时间和服务时间均服从指数分布。a）求当前状况下的L和W。b）假设由于汽油短缺，车主改成当油量消耗至不足时加油。为了建立模型方便，假设车主改成当油量消耗至时加油。由于每位加油的顾客需要购买的油量变少，每位顾客的平均服务时间减少至分钟。求情况改变后的L和W。解：a）该加油站可以看作一个＝7.5辆/小时，＝15辆/小时的M/M/1/GD/∞/∞排队系统。因此，，，因此，小时。因此，在这种情况下加油站运行良好，基本不会出现很长得队列。b）在这种情况下，该加油站可以看作一个＝2×7.5=15辆/小时，辆/小时的M/M/1/GD/∞/∞排队系统。因此，，（辆），（小时）＝20（分钟）。配件中心的管理员例5：在一个制造工厂工作的机械师必须从一个配件中心获取配件。平均每小时有10名机械师来寻找配件。目前配件中心有一名管理员，该管理员工资为6元/小时，他为一位机械师寻找配件平均需要5分钟。由于一名机械师每小时可以制造价值10元的产品，因此机械师每在配件中心逗留1小时就相当于花费了该厂10元。该厂正在决策是否花4元/小时雇佣一名管理员助手。如果雇佣，那么管理员为每位机械师的寻找配件只要平均4分钟。设机械师的到达间隔时间和管理员寻找配件的时间都服从指数分布。是否应该雇佣该助手？解：这种选择一个排队系统中的决策问题被称为排队最优化问题（queuingoptimizationproblem）。在本题中，该厂的目标是最小化服务成本和机械师空闲成本之和。在排队最优化问题中，由于顾客等待而造成的成本叫做延迟成本（delaycost）。因此，该厂的目标是最小化配件中心的管理员计算单位时间的服务成本往往很简单。最简单的计算单位时间延迟成本的方法如下所示：在本题中，因此，，现在我们比较雇佣和不雇佣该助手的情况下的单位时间期望成本。

如果不雇佣助手，＝10人/小时，＝12人/小时。小时。由于管理员工资为6元/小时，（元），（元）。每小时的期望成本为6+50＝56（元）。配件中心的管理员

如果雇佣助手，则＝10人/小时，＝15人/小时，

小时，+4=10（元），

雇佣助手后每小时的期望成本为20+10＝30元。因此，应该雇佣该助手，因为平均每小时可以节约50-20＝30元的延迟成本，大于4元/小时的助手工资。配件中心的管理员目录排队论的一些术语

到达过程和服务过程模型生灭过程M/M/1/GD/∞/∞排队系统M/M/1/GD/c/∞排队系统

M/M/s/GD/∞/∞排队系统M/M/1/GD/c/∞排队系统M/M/1/GD/c/∞排队系统与M/M/1/GD/∞/∞排队系统的差别仅在于：该系统的最大容量为c个顾客，即如果系统中已经有c个顾客，那么新到达的顾客将不能进入系统，并永远不会再回来。同在第四节一样，我们假设顾客到达间隔时间和服务时间分别服从参数为和的指数分布。状态012c-1cλλλμμμM/M/1/GD/c/∞排队系统M/M/1/GD/c/∞排队系统的生/灭率由于＝0，因此，系统永远不会达到状态c＋1或者其它数值更大的状态。M/M/1/GD/c/∞排队系统定义。如果，则M/M/1/GD/c/∞系统的稳态概率：，所以M/M/1/GD/c/∞排队系统如果，M/M/1/GD/c/∞排队系统的稳态概率：

因此对M/M/1/GD/c/∞排队系统，即使时，系统也存在稳定状态。理发店的排队系统例6：某理发店只有一名理发师，共有10个座位。顾客的到达间隔时间服从指数分布，平均每小时有20名潜在顾客到达。当店里没有坐满时，顾客将离开。理发师为一位顾客理发平均要12分钟。理发时间服从指数分布。求：a）理发师平均每小时为多少位顾客服务？b）进入理发店的顾客平均逗留多长时间？解：a）该理发店坐满的概率为，则平均每小时进入理发店的顾客数量为。所有进入理发店的顾客都要理发，因此，理发师平均每小时为位顾客理发。由已知得c＝10，＝20人/小时，＝5人/小时。则，得：，，因此，平均每小时有名顾客接受理发服务。这意味着每小时有20－5＝15名潜在顾客不能进入理发店。b）（人），（小时）

可以得出结论，这个理发店十分拥挤，建议至少再雇佣一名理发师。

目录排队论的一些术语

到达过程和服务过程模型生灭过程M/M/1/GD/∞/∞排队系统M/M/1/GD/c/∞排队系统M/M/s/GD/∞/∞排队系统M/M/s/GD/∞/∞排队系统设顾客到达间隔时间服从参数为的指数分布，服务时间服从参数为的指数分布，系统中有个并行的服务台，但是只有一个队列。如果当前系统中的顾客数量，则所有的顾客都在服务台接受服务；如果，则所有的个服务台都被占用，并且有个顾客等待在队列中。一个刚到达的顾客如果找到一个空闲的服务台则进入该服务台接受服务，如果所有的服务台都已经被占用，则加入队列等待。具有多个窗口共用一个队列的银行和邮局可以用M/M/s/GD/∞/∞排队模型建立。

M/M/s/GD/∞排队系统的生/灭率012ss+11sλλλμsμ2μM/M/s/GD/∞/∞排队系统定义