排队论(数学建模)

《排队论(数学建模)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章排队论模型排队论起源于1909年丹麦电话工程师A.K．爱尔朗的工作，他对电话通话拥挤问题进行了研究。1917年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅

2、在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机性。可以说排队现象几乎是不可避免的。排队论（QueuingTheory）也称随机服务系统理论，就是为解决上述问题而发展的一门学科。它研究的内容有下列三部分：（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。（ii）最优化问题，又分静态最优和动态最优，前者指最优设计。后者指现有排队系统的最

3、优运营。（iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。这里将介绍排队论的一些基本知识，分析几个常见的排队模型。§1基本概念1.1排队过程的一般表示下图是排队论的一般模型。图1排队模型图中虚线所包含的部分为排队系统。各个顾客从顾客源出发，随机地来到服务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服

4、务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。1.2排队系统的组成和特征一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下：1.2.1输入过程输入过程是指顾客到来时间的规律性，可能有下列不同情况：（i）顾客的组成可能是有限的，也可能是无限的。-118-（ii）顾客到达的方式可能是一个—个的，也可

5、能是成批的。（iii）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响；否则是相关的。（iv）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，否则是非平稳的。1.2.2排队规则排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和混合制三种。（i）损失制（消失制）。当顾客到达时，所有的服务台均被占用，顾客随即离去。（ii）等待制。当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去。例如出故障的机器排队等待维修就是这种情况。（ii

6、i）混合制。介于损失制和等待制之间的是混合制，即既有等待又有损失。有队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就离去。排队方式还分为单列、多列和循环队列。1.2.3服务过程（i）服务机构。主要有以下几种类型：单服务台；多服务台并联（每个服务台同时为不同顾客服务）；多服务台串联（多服务台依次为同一顾客服务）；混合型。（ii）服务规则。按为顾客服务的次序采用以下几种规则：①先到先服务，这是通常的情形。②后到先服务，如情报系统中，最后到的情报信息往往最有价值，因而常被优先处理。③随机服务，服务台

7、从等待的顾客中随机地取其一进行服务，而不管到达的先后。④优先服务，如医疗系统对病情严重的病人给予优先治疗。1.3排队模型的符号表示排队模型用六个符号表示，在符号之间用斜线隔开，即X/Y/Z/A/B/C。第一个符号X表示顾客到达流或顾客到达间隔时间的分布；第二个符号Y表示服务时间的分布；第三个符号Z表示服务台数目；第四个符号A是系统容量限制；第五个符号B是顾客源数目；第六个符号C是服务规则，如先到先服务FCFS，后到先服务LCFS等。并约定，如略去后三项，即指X/Y/Z/∞/∞/FCFS的情形。我们只讨论先到先服务FCFS

8、的情形，所以略去第六项。表示顾客到达间隔时间和服务时间的分布的约定符号为：M—指数分布（M是Markov的字头，因为指数分布具有无记忆性，即Markov性）；D—确定型（Deterministic）；E—k阶爱尔朗(Erlang)分布；kG—一般（general）服务时间的分布；GI—一般相互独立（GeneralIn