排队论

排队论(Queuing Theory)

　　研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支。

　　日常生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，市内电话占线等现象。排队论的基本思想是1910年丹麦电话工程师A.K.埃尔朗在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公式。自20世纪初以来，电话系统的设计一直在应用这个公式。30年代苏联数学家А.Я.欣钦把处于统计平衡的电话呼叫流称为最简单流。瑞典数学家巴尔姆又引入有限后效流等概念和定义。他们用数学方法深入地分析了电话呼叫的本征特性，促进了排队论的研究。50年代初，美国数学家关于生灭过程的研究、英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础。在这以后，L.塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。70年代以来，人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。

　　排队系统又称服务系统。服务系统由服务机构和服务对象（顾客）构成。服务对象到来的时刻和对他服务的时间（即占用服务系统的时间）都是随机的。图1为一最简单的排队系统模型。排队系统包括三个组成部分：输入过程、排队规则和服务机构。

　　输入过程考察的是顾客到达服务系统的规律。它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。例如，在生产线上加工的零件按规定的间隔时间依次到达加工地点，定期运行的班车、班机等都属于确定型输入。随机型的输入是指在时间t内顾客到达数 n（t）服从一定的随机分布。如服从泊松分布,则在时间t内到达n个顾客的概率为

　　或相继到达的顾客的间隔时间T 服从负指数分布，即

　　式中λ为单位时间顾客期望到达数，称为平均到达率；1/λ为平均间隔时间。在排队论中，讨论的输入过程主要是随机型的。

　　排队规则分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或是随机服务和有优先权服务（如医院接待急救病人）。如果顾客来到后看到服务机构没有空闲立即离去，则为损失制。有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。

　　可以是一个或多个服务台。多个服务台可以是平行排列的，也可以是串连排列的。服务时间一般也分成确定型和随机型两种。例如，自动冲洗汽车的装置对每辆汽车冲洗（服务）时间是相同的，因而是确定型的。而随机型服务时间v 则服从一定的随机分布。如果服从负指数分布，则其分布函数是

　　式中μ为平均服务率，1/μ为平均服务时间。

　　如果按照排队系统三个组成部分的特征的各种可能情形来分类，则排队系统可分成无穷多种类型。因此只能按主要特征进行分类。一般是以相继顾客到达系统的间隔时间分布、服务时间的分布和服务台数目为分类标志。现代常用的分类方法是英国数学家D.G.肯德尔提出的分类方法，即用肯德尔记号 X/Y/Z进行分类。

　　X处填写相继到达间隔时间的分布；

　　Y处填写服务时间分布;

　　Z处填写并列的服务台数目。

　　各种分布符号有：M-负指数分布;D-确定型; Ek-k阶埃尔朗分布；GI-一般相互独立分布；G-一般随机分布等。这里k阶埃尔朗分布是指为相互独立且服从相同指数分布的随机变量时，服从自由度为 2k的χ2分布。例如,M/M/1表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布和单个服务台的模型。D/M/C表示顾客按确定的间隔时间到达、服务时间为负指数分布和C个服务台的模型。至于其他一些特征,如顾客为无限源或有限源等，可在基本分类的基础上另加说明。

　 　　研究排队系统问题的主要目的是研究其运行效率,考核服务质量,以便据此提出改进措施。通常评价排队系统优劣有 6项数量指标。

　　①系统负荷水平ρ ：它是衡量服务台在承担服务和满足需要方面能力的尺度；

　　②系统空闲概率P0：系统处于没有顾客来到要求服务的概率；

　　③队长：系统中排队等待服务和正在服务的顾客总数，其平均值记为LS；

　　④队列长：系统中排队等待服务的顾客数，其平均值记为Lg；

　　⑤逗留时间：一个顾客在系统中停留时间，包括等待时间和服务时间，其平均值记为WS；

　　⑥等待时间：一个顾客在系统中排队等待时间,其平均值记为Wg。M/M/1排队系统是一种最简单的排队系统。系统的各项指标可由图2中状态转移速度图推算出来（表1）。其他类型的排队系统的各种指标计算公式则复杂得多，可专门列出计算公式图表备查。现已开始应用计算机仿真来求解排队系统问题。

　　排队论已广泛应用于交通系统、港口泊位设计、机器维修、库存控制和其他服务系统。表2中列出排队论的应用。

　　一、超市收银台

　　随着市场经济的不断发展，城镇里的超市越来越多。在激烈的市场竞争中，如何提高经营效益、吸引更多的顾客是超市经营商最关心的问题。收银台是超市的服务窗口，不仅能够反映超市的形象更与超市的服务质量和经营效率密切相关。收银员的形象、服务态度、职业技能等固然重要，而收银台的管理与优化也是不容忽视。顾客选择超市的标准，不仅是价廉物美的商品，也有服务质量。收银台前排队成龙的超市显然不是人们希望的购物环境，多数人宁愿放弃或者稍微走远一点去购物也不愿意在拥挤中排队等待。尤其是一些成功人士，他们宁愿多花点钱也不愿意排队，对于他们来说时间就是金钱。在商品的质量和价格基本相同的条件下，服务质量才是竞争的焦点。前者可以通过采购环节加以控制，而后者只有通过收银台的增减与管理加以调节。就超市经营者而言，增加收银台就意味着增加投资，有时还有可能发生资源空闲浪费的现象；而收银台太少，排队现象就会严重，影响服务质量，造成客源流失。

　　二、超市排队系统的组成与特征

　　一般的排队服务系统(如图）有三个基本的组成部分：输入过程、排队规则和服务机构。输入过程是指顾客到达排队系统；排队规则是指顾客到达后按什么样的规则排队等待服务；服务机构是指为顾客提供服务的机构。本文所研究的排队系统是指顾客在超市里挑选好商品后，在收银台前排队等待付款的排队系统。收银台是服务台，顾客付款被认为是接受服务。输入过程是指顾客挑选好商品后来到收银台前；排队规则是指顾客按单队单服务台、多队多服务台或单队多服务台的方式排队；服务机构是服务台。

　　一般认为在超市的排队系统中，输入过程服从泊松分布，服务时间服从指数分布。用λ表示单位时间内平均到达的顾客数，用μ表示各个服务台的平均服务速率(服务员的服务能力）。用Ρ表示平均每单位时间中系统可以为顾客服务的比例，即服务强度。W_s表示顾客在系统中的平均逗留时间（包括排队等待时间和接受服务的时间），W_q表示顾客排队等待的平均时间，可通过如下公式计算：

　　在单队单服务台的情况下:

　　　　,

　　多队多服务台可看作是多个单队单服务台。在单队k个服务台的情况下:

　　，

　　三、超市收银台的优化设计

　　作为顾客来说，超市收银台越多越好越方便，而就超市经营者来说，增加收银台就要增加投资。所以应该合理的规划收银台的数量，使得既不会因为收银台的数量过多而造成资源闲置浪费，也不会因为收银台的数量过少而造成严重的排队现象。因此可对超市收银台进行管理和优化设计。

　　1.对超市布局进行合理规划，为顾客营造出温馨，简便的购物环境。让顾客在尽量短的时间内买到自己想买的商品，提高单位时间内进出超市的客流量，这样既节省了顾客的时间，也使超市增加了顾客的流量，从而使超市的经营效率得到了提高。对于大型的超市在恰当的位置增加导购员是一种很好的方法。对于第一次来消费的顾客，导购员的指导就会大量的减少他们的漫无目的的逗留时间。收银台前的管理也是非常重要的，尽量让等待的顾客按顺序排队，避免过分的拥挤和混乱。

　　2.加强培训，提高收银员的基本素质。收银台是超市中顾客接触最多的地方。可以说是超市的窗口，收银员的素质和服务质量直接影响超市的形象。如果超市位于社区内，顾客都是些老客户，他们知道哪个收银员的收银速度比较快，服务态度好，可能就会在她的通道内排队的顾客比较多，从而导致其他的收银员暂时的资源闲置。这样也不利于超市经营者的管理。

　　所以招收收银员时要适当考虑收银员的资历和形象，要对收银员的爱岗敬业精神和职业技能加强培训。要定期对收银员进行考核或开展职业技能方面的竞赛。要及时掌握收银员的工作状态、业务水平及相关资料，这不仅是对员工进行科学管理的需要，这些资料可以反映收银员的工作强度，对于管理与优化都是非常重要的数据资料。

　　3.尽量采用单队多服务台的排队规则，提高工作效率。

　　在超市排队系统中，输入过程服从泊松分布，从理论来说，采用单队多服务台的排队规则比采用多队多服务台的工作效率高。以有三个收银台的超市为例，设顾客的平均到达率为λ = 0.9(人)，平均服务率为μ = 0.4(人)，如果按多队多服务台的排队规则进行排队，则约有75%的顾客需要排队等待付款，平均等待时间约为7分钟。而按单队多服务台的排队规则进行排队，则只有约57%的顾客需要排队，平均等待时间不到2分钟。

　　4.诚信经营。在现在的市场经济条件下，谁占有了消费者的购买信心，谁就占有了市场。所以，超市经营者一定要诚信经营，让消费者在超市消费时，没有后顾之忧。使消费者相信他选中的这个超市是可以长期合作的。这样消费者和经营者就达到了和谐。

　　当今排队论研究的内容包括3个方面：系统的性态、系统的优化和统计推断，根据资料的合理建立模型，其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。利用排队论的知识来解决汽车售后服务中的排队论问题。

　　1.排队模型的建立

　　假设客户平均到达率为λ，单个服务台的平均服务率（表示单位时间被服务完的顾客数）为μ，整个服务机构的平均服务率为C^μ，系统的服务强度时才不会排成无限的队列，P_n(c)为C个服务台任意时刻系统中有n个顾客的概率；当到达率为\lambda，服务率为C^μ的过程达到稳态时，可得

　　　　(1)

　　　　(2)

　　当系统达到平衡状态时,每位顾客在系统中的等待时间w的均值为:

　　　　(3)

　　排队逗留的人数：

　　　　(4)

　　排队系统的最优化

　　在排队系统中，顾客希望服务台越多、服务效率越高、逗留时间越短越好，使自己的损失达到最小，为此4S店就要增加服务人员数，而4S店也不可能无限投入，因此就需要优化设计，目的就是使顾客损失费用和公司运营成本最低。假设服务台的个数为C，每个服务台单位时间所需的成本费为C_s，每个顾客在系统中逗留单位时间的费用为C_w，总成本为Z(c)，则目标函数：

　　minZ(c) = C_sC + C_wL_s

　　其中L_s为逗留的人数公式（4），C只能取整数。

　　设C ^* 是使目标函数C取最小值的点C ^* 满足。

　　　　L_s = L_s(C)

　　化简得：　　(5)

　　通过计算机模拟依次算出L_S(1),L_S(2),L_S(3)…相邻两项之差，看常数落在哪两者之间，从而确定使顾客损失费用和公司服务成本之和达到最优化服务台个数C的最优解C ^* 。

　　模型的求解

　　由已知易得：

　　由上表知只有维修机组个数C ^* = 4时满足公式（5），从而使得每一位客户来店等待维修时间最短，且公司成本最低的最优维修机组个数为4。

　　模型的分析当顾客平均到达率上升引起服务强度增加致使平均队长L太大，甚至由于服务强度ρ > 1使队长趋向无限时，在平均服务率不变的情况下就只能增加服务台。下面考虑有两个服务台且平均服务率相等的情况。

　　两个服务台的排队有两种形式分别由下面两图表示:左图一个队是一个M/M/2模型;右图两个队，且入队后不能换队,是两个M/M/1模型。

　　可以知道，两个服务台的两种服务形式平均队长L,等待时间W之比为：

　　就人们最关心的等待时间而言有,而当较大时，M/M/2模型的形式比2个M/M/1模型节省较多的等待时间。

　　同理可证：在有多个并列服务台的排队系统中,排成单队比排成并列多队的方案具有明显的优越性.对于设置多个服务台的随机过程，应该让顾客排成一个队。

　　接待、派工程序的设计

　　由上知，在设置4个并列维修机组的排队系统中，排成单队比排成并列4队的方案具有明显的优越性.具体的接待、派工程序如下：

　　2.服务月工作安排

　　在最优条件下，各维修机组基本上一直处于繁忙状态，但该4S店4月份与9月份来店保养客户比平均每天来店保养客户多31%及43%，因此为了在不增加员工数量且遵守国家法定工作时间的条件下完成服务月活动，只能提高各维修机组的工作效率。

　　由已知易得：4月份每小时客户平均到达率λ = 18.77(辆/h)，设每个维修机组提高效率后每小时修理的汽车数量为μ,由MATLAB计算得当μ = 4.6时即可满足条件,此时每个维修机组提高的效率为P=21.8%.同理9月份当μ = 5时即可满足条件，此时每个维修机组提高的效率P=32.4%。

　　因此，该4S店的接待、派工流程为图3，需提高的工作效率如下：

　　各维修机组在4月份、9月份需提高的工作效率

　　3.结论

　　应用排队论一方面可以有效地解决售后服务系统中人员和设备的配置问题，为公司提供可靠的决策依据；另一方面通过系统优化，找出客户和公司两者之间的平衡点，既减少排队等待时间，又不浪费公司人力物力，从而使公司和客户之间达到双赢。排队是一种司空见惯的现象，因此排队论可以用来解决许多现实问题。

• 徐光辉：《随机服务系统》，科学出版社,北京,1980。