下载文档原格式
-118-第六章 排队论模型排队论起源于1909年丹麦电话工程师A. K．爱尔朗的工作，他对电话通话拥挤问题进行了研究。
1917年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理论的几个问题的解决”。
排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。
排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。
此时要求服务的数量超过服务机构（服务台、服务员等）的容量。
也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。
这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。
由于顾客到达和服务时间的随机性。
可以说排队现象几乎是不可避免的。
排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展的一门学科。
它研究的内容有下列三部分：（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。
（ii）最优化问题，又分静态最优和动态最优，前者指最优设计。
后者指现有排队系统的最优运营。
（iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。
这里将介绍排队论的一些基本知识，分析几个常见的排队模型。
§1 基本概念1.1 排队过程的一般表示 下图是排队论的一般模型。
图1 排队模型图中虚线所包含的部分为排队系统。
各个顾客从顾客源出发，随机地来到服务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。
凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。
对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。
《运筹学》第六章排队论习题转载请注明1. 思考题（1）排队论主要研究的问题是什么；（2）试述排队模型的种类及各部分的特征；（3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义；（4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念； （5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分布的主要性质；（6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系与区别。
2．判断下列说法是否正确（1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍为普阿松分布；（3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布； （4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流； （5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大量实际系统的统计研究，这样的假定比较合理；（6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态；（7）排队系统中，顾客等待时间的分布不受排队服务规则的影响；（8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间少于允许队长无限的系统；（9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分布的方差越大时，顾客的平均等待时间就越长； （10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。
3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负指数分布，平均需19分钟，求： （1）店内空闲的时间； （2）有4个顾客的概率； （3）至少有一个顾客的概率； （4）店内顾客的平均数； （5）等待服务的顾客数； （6）平均等待修理的时间；（7）一个顾客在店内逗留时间超过15分钟的概率。
《运筹学》第六章排队论习题转载请注明1. 思考题（1）排队论主要研究的问题是什么；（2）试述排队模型的种类及各部分的特征；（3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义；（4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念； （5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分布的主要性质；（6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系与区别。
2．判断下列说法是否正确（1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍为普阿松分布；（3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布； （4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流； （5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大量实际系统的统计研究，这样的假定比较合理；（6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态；（7）排队系统中，顾客等待时间的分布不受排队服务规则的影响；（8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间少于允许队长无限的系统；（9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分布的方差越大时，顾客的平均等待时间就越长； （10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。
3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负指数分布，平均需19分钟，求： （1）店内空闲的时间； （2）有4个顾客的概率； （3）至少有一个顾客的概率； （4）店内顾客的平均数； （5）等待服务的顾客数； （6）平均等待修理的时间；（7）一个顾客在店内逗留时间超过15分钟的概率。
《运筹学》第六章排队论习题1. 思考题（1）排队论主要研究的问题是什么；（2）试述排队模型的种类及各部分的特征；（3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义；（4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念； （5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分布的主要性质；（6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系与区别。
2．判断下列说法是否正确（1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍为普阿松分布；（3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布； （4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流； （5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大量实际系统的统计研究，这样的假定比较合理；（6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态；（7）排队系统中，顾客等待时间的分布不受排队服务规则的影响；（8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间少于允许队长无限的系统；（9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分布的方差越大时，顾客的平均等待时间就越长； （10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。
3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负指数分布，平均需19分钟，求： （1）店内空闲的时间； （2）有4个顾客的概率； （3）至少有一个顾客的概率； （4）店内顾客的平均数； （5）等待服务的顾客数； （6）平均等待修理的时间；（7）一个顾客在店内逗留时间超过15分钟的概率。
《运筹学》第六章排队论习题及答案《运筹学》第六章排队论习题1. 思考题（1）排队论主要研究的问题是什么；（2）试述排队模型的种类及各部分的特征；（3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义；（4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念；（5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分布的主要性质；（6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系与区别。
2．判断下列说法是否正确（1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（2）假如到达排队系统的顾客来⾃两个⽅⾯，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍为普阿松分布；（3）若两两顾客依次到达的间隔时间服从负指数分布，⼜将顾客按到达先后排序，则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布；（4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流；（5）在排队系统中，⼀般假定对顾客服务时间的分布为负指数分布，这是因为通过对⼤量实际系统的统计研究，这样的假定⽐较合理；（6）⼀个排队系统中，不管顾客到达和服务时间的情况如何，只要运⾏⾜够长的时间后，系统将进⼊稳定状态；（7）排队系统中，顾客等待时间的分布不受排队服务规则的影响；（8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间少于允许队长⽆限的系统；（9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的⽅差⼤⼩有关，当服务时间分布的⽅差越⼤时，顾客的平均等待时间就越长；（10）在机器发⽣故障的概率及⼯⼈修复⼀台机器的时间分布不变的条件下，由1名⼯⼈看管5台机器，或由3名⼯⼈联合看管15台机器时，机器因故障等待⼯⼈维修的平均时间不变。
3．某店有⼀个修理⼯⼈，顾客到达过程为Poisson 流，平均每⼩时3⼈，修理时间服从负指数分布，平均需19分钟，求：（1）店内空闲的时间；（2）有4个顾客的概率；（3）⾄少有⼀个顾客的概率；（4）店内顾客的平均数；（5）等待服务的顾客数；（6）平均等待修理的时间；（7）⼀个顾客在店内逗留时间超过15分钟的概率。
第6章 排队论在日常生活和工作中，人们常常会为了得到某种服务而排队等候。
比如顾客到商店购买东西，病人到医院看病，汽车进加油站加油，轮船进港停靠码头等，都会因为拥挤而发生排队等候的现象。
这时，商店的售货员和顾客，医院的医生和病人，加油站的加油泵和待加油的汽车，码头的泊位和停泊的轮船等，形成了各自的排队服务系统，简称排队系统。
在一个排队系统中，通常包括一个或多个“服务设施”，服务设施可以指人，如售货员，医院大夫等。
也可以是物，如加油泵、码头泊位等。
同时还包括许多进入排队系统要求得到服务的“顾客”。
这里的顾客是指请求服务的人或物。
如到医院看病的病人，或等待加油的汽车等。
作为顾客总希望一到系统马上就能得到服务，但客观情况并非如此。
由于顾客的到达和服务机构对每个顾客的服务时间具有随机性，因此出现排队现象几乎是不可避免的。
当然，为了方便顾客减少排队时间，排队系统可以多开设服务设施。
但那将增加系统的投资和运营成本，还可能发生空闲浪费。
排队论（Queueing Theory ）是为解决上述问题而发展起来的一门学科。
排队论起源于上世纪初，当时的美国贝尔（Bell ）电话公司发明了自动电话后，满足了日益增长的电话通讯的需要。
但另一方面，也带来了新的问题，即如何合理配置电话线路的数量，以尽可能减少用户的呼叫次数。
如今，通讯系统仍然是排队论应用的主要领域。
同时在运输、港口泊位设计、机器维修、库存控制等领域也获得了广泛的应用。
6. 1 排队系统的基本概念6. 1. 1排队系统的一般表示一个排队系统可以抽象描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务。
服务完毕后就自行离开。
其中把要求得到服务的对象称为顾客，而把服务者统称为服务设施或服务台。
在排队论中，把顾客的到达和离开称为排队系统的输入和输出。
而潜在的顾客总体又称为顾客源或输入源。
因此任何一个排队系统是一种输入－输出系统，其基本结构如图6-1所示。
排队系统图6-16. 1. 2排队系统的特征由排队系统的基本结构可知，任何一个排队系统的特征可以从以下三个方面加以描述。
第六章排队论模型排队论起源于1909年丹麦电话工程师A. K．爱尔朗的工作，他对电话通话拥挤问题进行了研究。
1917年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理论的几个问题的解决”。
排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。
排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。
此时要求服务的数量超过服务机构（服务台、服务员等）的容量。
也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。
这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。
由于顾客到达和服务时间的随机性。
可以说排队现象几乎是不可避免的。
排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展的一门学科。
它研究的内容有下列三部分：（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。
（ii）最优化问题，又分静态最优和动态最优，前者指最优设计。
后者指现有排队系统的最优运营。
（iii）排队系统的统计推断，即判断一个给定的排队系统符合于那种模型，以便根据排队理论进行分析研究。
这里将介绍排队论的一些基本知识，分析几个常见的排队模型。
§1 基本概念1.1 排队过程的一般表示下图是排队论的一般模型。
一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。
凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。
对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。
因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。
1.2 排队系统的组成和特征一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下：1.2.1 输入过程输入过程是指顾客到来时间的规律性，可能有下列不同情况：（i）顾客的组成可能是有限的，也可能是无限的。
（ii）顾客到达的方式可能是一个—个的，也可能是成批的。
（iii ）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响；否则是相关的。
（iv ）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，否则是非平稳的。
1.2.2 排队规则排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和混合制三种。
（i ）损失制（消失制）。
当顾客到达时，所有的服务台均被占用，顾客随即离去。
（ii ）等待制。
当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去。
例如出故障的机器排队等待维修就是这种情况。
（iii ）混合制。
介于损失制和等待制之间的是混合制，即既有等待又有损失。
有队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就离去。
排队方式还分为单列、多列和循环队列。
1.2.3 服务过程（i ）服务机构。
主要有以下几种类型：单服务台；多服务台并联（每个服务台同时为不同顾客服务）；多服务台串联（多服务台依次为同一顾客服务）；混合型。
（ii ）服务规则。
按为顾客服务的次序采用以下几种规则：①先到先服务，这是通常的情形。
②后到先服务，如情报系统中，最后到的情报信息往往最有价值，因而常被优先处理。
③随机服务，服务台从等待的顾客中随机地取其一进行服务，而不管到达的先后。
④优先服务，如医疗系统对病情严重的病人给予优先治疗。
1.3 排队模型的符号表示排队模型用六个符号表示，在符号之间用斜线隔开，即C B A Z Y X /////。
第一个符号X 表示顾客到达流或顾客到达间隔时间的分布；第二个符号Y 表示服务时间的分布；第三个符号Z 表示服务台数目；第四个符号A 是系统容量限制；第五个符号B 是顾客源数目；第六个符号C 是服务规则，如先到先服务FCFS ，后到先服务LCFS 等。
并约定，如略去后三项，即指FCFS /////∞∞Z Y X 的情形。
我们只讨论先到先服务FCFS 的情形，所以略去第六项。
表示顾客到达间隔时间和服务时间的分布的约定符号为：M —指数分布（M 是Markov 的字头，因为指数分布具有无记忆性，即Markov 性）；D —确定型（Deterministic ）； k E —k 阶爱尔朗(Erlang)分布；G —一般（general ）服务时间的分布；GI —一般相互独立（General Independent ）的时间间隔的分布。
例如，1//M M 表示相继到达间隔时间为指数分布、服务时间为指数分布、单服务台、等待制系统。
c M D //表示确定的到达时间、服务时间为指数分布、c 个平行服务台（但顾客是一队）的模型。
1.4 排队系统的运行指标为了研究排队系统运行的效率，估计其服务质量，确定系统的最优参数，评价系统的结构是否合理并研究其改进的措施，必须确定用以判断系统运行优劣的基本数量指标，这些数量指标通常是：(i)平均队长：指系统内顾客数（包括正被服务的顾客与排队等待服务的顾客）的数学期望，记作s L 。
(ii)平均排队长:指系统内等待服务的顾客数的数学期望，记作q L 。
(iii)平均逗留时间：顾客在系统内逗留时间（包括排队等待的时间和接受服务的时间）的数学期望，记作s W 。
（iv ）平均等待时间：指一个顾客在排队系统中排队等待时间的数学期望，记作q W 。
（v ）平均忙期：指服务机构连续繁忙时间（顾客到达空闲服务机构起，到服务机构再次空闲止的时间）长度的数学期望，记为b T 。
还有由于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等，这些都是很重要的指标。
计算这些指标的基础是表达系统状态的概率。
所谓系统的状态即指系统中顾客数， 如果系统中有n 个顾客就说系统的状态是n ，它的可能值是（i ）队长没有限制时， ,2,1,0=n ，（ii ）队长有限制，最大数为N 时，N n ,,1,0 =，（iii ）损失制，服务台个数是c 时，c n ,,1,0 =。
这些状态的概率一般是随时刻t 而变化，所以在时刻t 、系统状态为n 的概率用)(t P n 表示。
稳态时系统状态为n 的概率用n P 表示。
§2 输入过程与服务时间的分布排队系统中的事件流包括顾客到达流和服务时间流。
由于顾客到达的间隔时间和服务时间不可能是负值，因此，它的分布是非负随机变量的分布。
最常用的分布有泊松分布、确定型分布，指数分布和爱尔朗分布。
2.1 泊松流与指数分布设)(t N 表示在时间区间),0[t 内到达的顾客数（0>t ），令),(21t t P n 表示在时间区间))(,[1221t t t t >内有)0(≥n 个顾客到达的概率，即)0,(})()({),(121221≥>=-=n t t n t N t N P t t P n当),(21t t P n 合于下列三个条件时，我们说顾客的到达形成泊松流。
这三个条件是：1o在不相重叠的时间区间内顾客到达数是相互独立的，我们称这性质为无后效性。
2o 对充分小的t ∆，在时间区间),[t t t ∆+内有一个顾客到达的概率与t 无关，而约与区间长t ∆成正比，即)(),(1t o t t t t P ∆+∆=∆+λ（1） 其中)(t o ∆，当0→∆t 时，是关于t ∆的高阶无穷小。
0>λ是常数，它表示单位时间有一个顾客到达的概率，称为概率强度。
3o 对于充分小的t ∆，在时间区间),[t t t ∆+内有两个或两个以上顾客到达的概率极小，以致可以忽略，即∑∞=∆=∆+2)(),(n nt o t t t P （2） 在上述条件下，我们研究顾客到达数n 的概率分布。
由条件2o ，我们总可以取时间由0算起，并简记)(),0(t P t P n n =。
由条件1o 和2o ，有)()()(000t P t P t t P ∆=∆+∑=-=∆=∆+n k k k n n n t P t P t t P 0,2,1),()()( 由条件2o 和3o 得)(1)(0t o t t P ∆+∆-=∆λ因而有 tt o t P t t P t t P ∆∆+-=∆-∆+)()()()(000λ， tt o t P t P t t P t t P n n n n ∆∆++-=∆-∆+-)()()()()(1λλ. 在以上两式中，取t ∆趋于零的极限，当假设所涉及的函数可导时，得到以下微分方程组：)()(00t P dtt dP λ-=， ,2,1),()()(1=+-=-n t P t P dtt dP n n n λλ. 取初值1)0(0=P ，),2,1(0)0( ==n P n ，容易解出t et P λ-=)(0；再令t n n e t U t P λ-=)()(，可以得到)(0t U 及其它)(t U n 所满足的微分方程组，即 ,,2,1),()(1 ==-n t U dtt dU n n λ 1)(0=t U ，0)(=t U n .由此容易解得 ,2,1,!)()(==-n e n t t P t nn λλ. 正如在概率论中所学过的，我们说随机变量)}()()({s N t s N t N -+=服从泊松分布。
它的数学期望和方差分别是t t N E λ=)]([；t t N λ=)](Var[。
当输入过程是泊松流时，那么顾客相继到达的时间间隔T 必服从指数分布。
这是由于),0{[}{t P t T P =>内呼叫次数为零t e t P λ-==)(}0那么，以)(t F 表示T 的分布函数，则有⎩⎨⎧<≥-==≤-0,00,1)(}{t t e t F t T P t λ 而分布密度函数为0,)(>=-t e t f t λλ.对于泊松流,λ表示单位时间平均到达的顾客数,所以λ1就表示相继顾客到达平均间隔时间，而这正和ET 的意义相符。
对一顾客的服务时间也就是在忙期相继离开系统的两顾客的间隔时间，有时也服从指数分布。
这时设它的分布函数和密度函数分别是t e t G μ--=1)(，t e t g μμ-=)(我们得到 μ=>∆∆+≤<=∆>∆+≤→∆→∆}{}{lim }|{lim 00t T tP t t T t P t t T t t T P t t 这表明，在任何小的时间间隔),[t t t ∆+内一个顾客被服务完了（离去）的概率是)(t o t ∆+∆μ。
