排队论 排队论简介 研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法,又称随机服务系统理论,为运筹学的一个分支。 日常生活中存在大量有形和无形的排队或拥挤现象,如旅客购票排队,市内电话占线等现象。排队论的基本思想是 1910 年丹麦电话工程师 A.K.埃尔朗在解决自动电话设计问题时开始形成的,当时称为话务理论。他在热力学统计平衡理论的启发下,成功地建立了电话统计平衡模型,并由此得到一组递推状态方程,从而导出著名的埃尔朗电话损失率公式。自 20 世纪初以来,电话系统的设计一直在应用这个公式。30 年代苏联数学家А.Я.欣钦把处于统计平衡的电话呼叫流称为最简单流。瑞典数学家巴尔姆又引入有限后效流等概念和定义。他们用数学方法深入地分析了电话呼叫的本征特性,促进了排队论的研究。50 年代初,美国数学家关于生灭过程的研究、英国数学家D.G.肯德尔提出嵌入马尔可夫链理论,以及对排队队型的分类方法,为排队论奠定了理论基础。在这以后,L.塔卡奇等人又将组合方法引进排队论,使它更能适应各种类型的排队问题。70 年代以来,人们开始研究排队网络和复杂排队问题的渐近解等,成为研究现代排队论的新趋势。 [编辑] 排队系统模型的基本组成部分 排队系统又称服务系统。 服务系统由 服务机构 和 服务对象(顾客) 构成。 服务对象到来的时刻和对他服务的时间(即占用服务系统的时间)都是随机的。 图 1 为一最简单的排队系统模型。排队系统包括三个组成部分:输入过程、排队规则和服务机构。 [编辑] 输入过程 输入过程考察的是顾客到达服务系统的规律。它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述,一般分为确定型和随机型两种。例如,在生产线上加工的零件按规定的间隔时间依次到达加工地点,定期运行的班车、班机等都属于确定型输入。随机型的输入是指在时间t内顾客到达数 n(t)服从一定的随机分布。如服从泊松分布,则在时间t内到达n个顾客的概率为 或相继到达的顾客的间隔时间T 服从负指数分布,即 式中 λ 为单位时间顾客期望到达数,称为平均到达率;1/λ 为平均间隔时间。在排队论中,讨论的输入过程主要是随机型的。 [编辑] 排队规则 排队规则分为等待制、损失制和混合制三种。 当顾客到达时,所有服务机构都被占用,则顾客排队等候,即为等待制。 在等待制中,为顾客进行服务的次序可以是先到先服务,或后到先服务,或是随机服务和有优先权...