**排队论在食堂系统中的应用
每次下课的时候，同学们都争相跑向食堂去买饭，卖饭窗口前没一会儿便排成了长长的队伍，食堂也立即变得拥挤不堪。
学生食堂的卖饭窗口个数和同学们吃饭的方便程度有关。窗口太少，吃饭高峰期同学排队等待时间很长,经常引发学生的不满情绪。而窗口太多，又会造成资源浪费，增加食堂成本。为此，我选择了学生食堂二楼作为研究对象来分析这个问题，看能否为食堂合理设置服务窗口提出建议，在这两者之间进行权衡，找到最佳的窗口数量。
预备知识
1.1 排队过程的一般模型：
各个顾客由顾客源（总体）出发，到达服务机构（服务台、服务员）前排队等候接受服务，服务完成后离开。我们说的排队系统就是图中虚线所包括的部分。
image.png
一般的排队系统都有三个基本组成部分：输入过程；排队规则；服务机构。
一 输入过程
输入过程考察的是顾客到达服务系统的规律。可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。对于随机型的情形，要知道单位时间内的顾客到达数或到达的间隔时间的概率分布。
- 排队规则
排队规则分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或是随机服务和有优先权服务。如果顾客来到后看到服务机构没有空闲立即离去，则为损失制。有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。
- 服务机构
可以是一个或多个服务台。服务时间一般也分成确定型和随机型两种。但大多数情形服务时间是随机型的。对于随机型的服务时间，需要知道它的概率分布。
二模型理论分析
1.2.1模型分类
排队模型的表示：
X/Y/Z/A/B/C
X—顾客相继到达的间隔时间的分布；
Y—服务时间的分布；
M—负指数分布、D—确定型、Ek —k阶爱尔朗分布。
Z—服务台个数；
A—系统容量限制（默认为∞）；
B—顾客源数目（默认为∞）；
C—服务规则 （默认为先到先服务FCFS)。
1.2.2 模型求解
一个实际问题作为排队问题求解时，只有顾客到达的间隔时间分布和服务时间的分布须要实测的数据来确定，其他的因素都是在问题提出时给定的。并且必须确定用以判断系统运行优劣的基本数量指标，解排队问题就是首先求出这些数量指标的概率分布或特征值。这些指标通常是：
（1）队长：系统中排队等待服务和正在服务的顾客总数，其期望值记为
image.png
排队长（队列长）：系统中排队等待服务的顾客数，其期望值记为
image.png
[系统中顾客数]=[在队列中等待服务的顾客数]+[正被服务的顾客数]
（2）逗留时间：一个顾客在系统中停留时间，包括等待时间和服务时间，其
其期望值记为
image.png
等待时间：一个顾客在系统中排队等待时间,其期望值记为
image.png
[逗留时间]=[等待时间]+[服务时间]
（3）忙期：从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度；
系统状态：即指系统中的顾客数；
状态概率：用
image.png
表示,即在t时刻系统中有n个顾客的概率；
要解决排队问题，首先要确定排队系统的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统计出它们的经验分布，然后与理论分布拟合，若能对应，我们就可以得出上述的分布情况。
1、经验分布
经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。
2、泊松分布
下面我们在一定的假设条件下，推出顾客的到达过程就是一个泊松过程。
若设
image.png
表示在时间区间[0,t)内到达的顾客数(t>0)，
image.png
表示在时间区间
image.png
(t2>t1)内有n(≥0)个顾客到达的概率，即
image.png
（t2>t1，n≥0）
当
image.png
符合于下述三个条件时，我们说顾客到达过程就是泊松过程。
(1)再不相重叠的的时间区间内顾客到达数是相互独立的。
(2)对于足够小的Δt，在时间区间[t，t+Dt)内有1个顾客到达的概率为
image.png
（λ>0 是常数，称为概率强度）。
(3)对充分小的Δt,在时间区间[t,t+Δt）内有2个或2个以上顾客到达的概率是Δt一高阶无穷小，即
image.png
为了求
image.png
，需要研究它在时刻t到t+Δt时刻的改变量，也就是要建立
image.png
的微分方程。就可以得到：
image.png
t>0，n=0,1,2,…
负指数分布
设T为时间间隔，分布函数为
image.png
，即
image.png
。此概率等价于在[0，t）区间内至少有1个顾客到达的概率。 没有顾客到达的概率为：
image.png
，则
image.png
（t>0），其概率密度函数为：
image.png
（t>0）。
由前知，λ表示单位时间内顾客平均到达数，这里1/λ表示顾客到达的平均间隔时间，两者是吻合的。
下面我们再谈一下服务时间的分布：
对顾客的服务时间ν，实际是系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，即：
image.png
其中：m表示单位时间内能被服务完成的顾客数，即平均服务率。1/m表示一个顾客的平均服务时间。令[图片上传失败...(image-66c5ad-1602761504886)] 则ρ称为服务强度。
食堂窗口与就餐人员之间是服务机构与顾客的关系，可以用服务系统模型来表示，就餐人员打饭的过程，即为顾客接受服务机构服务的过程。
image.png
故可以用排队论模型中有关服务系统的理论来分析和解决该问题。
学生到食堂就餐的时刻可以认为是随机的，若用N(t)表示[0,t)时间内到达该服务系统的顾客数，则对于任意一个给定的时刻t,N(t)的值都是随机的，即随机变量族{N(t)|t∈[0,A)}是一个随机过程.同样,打饭需要的时间长短因人而异，也认为是随机的，若用V(n)表示第n位顾客所需的服务时间,则有随机变量族{Vn,n=1,2,…}。
我们将学生就餐的过程看作是泊松过程进行讨论。
为了使模型便于求解，假定每个工作人员的打饭效率相同，每个窗口的饭菜相同，即不会出现某个窗口“扎堆”排长队或无人问津的现象。由于每个窗口独立排队、服务,这里把m个窗口服务X位顾客的情况等同为1个窗口服务情况来讨论.又假定食堂服务系统的容量无限,来到食堂就餐的学生不会在未打好饭之前离去.这样,得到一个输入过程为最简单流,服务时间为负指数分布,1个服务台,系统容量无限,顾客源数无限的等待制排队模型.
这里,对有关符号的数量指标加以说明:
λ ——单位时间内平均到达的顾客数,即平均到达率;
μ ——单位时间内受到服务的顾客数,即平均服务率;
t ——每位顾客的平均服务时间;
Lq ——等待队长的期望值;
Wq ——等待时间的期望值.
现对食堂二楼的4个服务窗口进行讨论:
在11:40至12:20之间的40分钟为大家用餐的高峰,每4分钟为1个时段,统计到达人数,如下表.
<colgroup><col width="80"><col width="44"><col width="44"><col width="44"><col width="44"><col width="44"><col width="44"><col width="44"><col width="44"><col width="44"><col width="44"></colgroup>
image.png
求得平均到达率为:
λ= 5.94 (人/分钟)
相应地,对其中50名顾客接受服务的时间进行统计,得到下表.
<colgroup><col width="84"><col width="61"><col width="61"><col width="73"><col width="73"><col width="73"><col width="73"></colgroup>
image.png
求得平均服务时间为:
t = 0.157(分钟)
平均服务率为:
μ =1/t= 6.37 (顾客/分钟)
等待队长的期望值为:
Lq = 12.88(顾客)
等待时间的期望值为:
Wq =Lq /λ= 2.17(分钟)
由上述模型求出的平均服务时间为9.4秒,这与实际情况大体吻合;等待队长的期望值为12.88人,明显偏长,但实际上,高峰期往往排队会更长些,这主要是因为在高峰期,用餐人数比闲时明显增多,且持续时间较长;相应地,现实中高峰期的等待时间也比求得的平均等待时间(2.17分钟)要久.另外,实际上并不是每个窗口的饭菜都一样的,存在个别窗口很受欢迎或不受欢迎的情况,造成该窗口前的排队明显过长.就餐人员排队时间过长,自然会产生不满情绪。[图片上传失败...(image-44f3e3-1602761504888)]
相应地,在就餐人数较少时,单位时间到达的顾客数明显少于单位时间工作人员所能服务的人数,造成资源浪费,增加了食堂的成本.[图片上传失败...(image-6b2218-1602761504888)]
因此,该食堂的窗口设置尚不够合理.现从就餐人员排队时间过长引起不满和食堂资源浪费增加成本两个方面来考虑改进窗口设置.
11:40前, 3个窗口即可; 11:45应开放4个窗口;11:55应开放5个窗口,以防止出现排队过长的现象;直到12:15再减少为4个窗口,至此时,5、6、7时段排队的就餐人员已经服务完毕;12:20后只需2个窗口即可.调整后,各时段能够服务人数和需要排队等待人数如下表.（该表显示了不同时段的窗口数以及服务情况）
image.png
这里做出说明,大约到11:58,到就餐人数的才达到5个窗口能够服务的人数,按平均服务时间来算,11:45至11:48之间的3分钟时间内,5个窗口的服务能力有剩余,完全能够完成之前排队人员的服务.
窗口调整后的等待时间(和部分取最大值)仅为调整前(2.17分钟)的一半:(6.6+19.6+8.6)/5×0.157=1.09(分钟),改进的效果十分明显.
对于食堂的运营成本, 其它因素不变的情况下,这里只讨论人力部分.该食堂11:30至12:20之间营业,每个窗口有1名工作人员,总的人力成本为:50×4=200(人·分钟).调整窗口设置后,11:30至11:40只需最多2个窗口,12:20至12:30也只需最多2个窗口,总的人力成本最多为:2×10+3×5+4×10+5×20+4×5+2×10=190(人·分钟).
可以看出，窗口设置按照该方案调整后，食堂的运营成本也会相应减少。食堂可以根据这个结论进行参考并相应调整窗口数量，得到最优方案。
心得体会：
以上就是我在学习了排队论这门课程后对食堂窗口问题的分析，过程中结合了网上查找的相关文献以及资料来帮助自己完成。通过这次作业，我尽量认真分析了网上相关文献内容并将课上学习的内容相结合，对排队论的理解更加深刻。
在此也十分感谢魏老师在课上的认真讲解，并能将理论与实际生活相结合，让我学到很多知识并激发了我对这门学科的学习兴趣。
【参考文献】
-
排队论再学校食堂窗口服务中的应用，刘亚国，河源职业技术学院
-
北京师范大学学一食堂排队分析，艾博，北京师范大学
-
排队论，陆传赉，北京邮电大学出版社
网友评论