排队论在学校食堂窗口服务中的应用
题 目:排队论在学校食堂窗口服务中的应用
授课老师: 宋月 学 院: 数学与统计学院 专 业: 数学与应用数学 学生姓名: 闵滔 学 号:
摘 要 通过应用排队论,为食堂窗口服务工作构建相应的定量模型,为节约学生排队就餐时间,提高食堂服务质量、效率,以及平衡学生排队时间与 食堂收益之间的关系,优化食堂资源配置提供一种较有效的管理决策手段。
关键词 排队论,M/M/s模型,灵敏度,等待损失
ABSTRACT: Through the application of queuing theory, build corresponding quantitative math. model of cafeteria window service in order to save dining time, improve service quality、efficiency and balance the relationship between students’ queuing time and the canteen revenues. This provides a more effective management method of optimizing the allocation of resources. Key words: Queuing theory, M/M/s model,Sensitivity,Waiting loss
1 引 言
在学校里,我们常常可以看到这样的情景:下课后,许多同学争先恐后 跑向食堂去买饭,小小的卖饭窗口前没过几分钟便排成了长长的队伍,本来空荡荡的食堂也立即变得拥挤不堪。饥肠咕噜的同学们见到这种长蛇阵,怎能不怨声载道。西北民族大学,这个拥有着2万多人的学校,由于近年来学校学生人数的增加,这种现象变得尤为严重。增加窗口数量,减少排队等待时间,是我们学生十分关心的问题。然而就食堂的角度来说,虽说增加窗口数量可以减少排队等待时间,提高学生对该食堂的满意度,从而赢得更多的学生到该食堂就餐,但是同时也会增加食堂的运营成本,因此如何在这两者之间进行权衡,找到最佳的窗口数量,对学生和食堂双方来说都是很重要的。 排队论是通过研究各种服务系统的排队现象,解决服务系统最优设计和最优化控制的一门科学。本论文将根据食堂排队状况建立数学模型,运用排队论的观点进行分析,通过比较各方面因素的关系,为其拥挤状况找到一个较合理的解决方案。
2 基本原理
2.1 多服务台排队系统的数学模型--M/M/c/∞/∞模型
排队论是研究排队系统(又称为随机服务系统)的数学理论和方法,是运筹学的一个重要分支。在日常生活中人们会遇到各种各样的排队问题。排队问题的表现形式往往是拥挤现象。排队系统的符号一般形式为:X/Y/Z/A/B/C。
其中:X表示顾客相继到达时问间隔的分布;Y表示服务时间的分布;Z表示服务台的个数;A表示系统的容量,即可容纳的最多顾客数;B表示顾客源
的数目;C表示服务规则。 排队论的基本问题是研究一些数量指标在瞬时或平稳状态下的概率分布及其数字特征,了解系统运行的基本特征;系统数量指标的统计推断和系统的优化问题等。
当系统运行一定时间达到平稳状态后,对任一个状态 n来说,单位时内进入该状态的平均次数和单位时间内离开该状态的平均次数应相等,即系统
【2】
在统计平衡下“流入=流出”。
据此.可得任一状态下的平衡方程如下:
μp=μp
1: λp+μp=(λ+μ)p 2:λp+μp=(λ+μ)p
0:
1
1
2
2
1
1
1
1
1
3
3
2
2
2
„„ n:
λp
n-1
n-1
+μ
n+1
p
n+1
=
(λ+μ)p
n
n
n
由上述平衡方程,可求得:
平衡状态的分布为:pn=cnp0,n=1,2,... (1)
...其中:c=
n-1n
n-2
n
n-1
(2)
1
∞
⎡⎤
由概率分布的要求:∑pn=1 ,有: ⎢1+∑cn⎥
n=0⎣n=0⎦
∞
p
n
=1, (3)
注意:(3)式只有当级数 ∑cn收敛时才有意义,
n=0
∞
即当∑cn
n=0
∞
2.2 M/M/s等待制多服务台模型。
设顾客单个到达,相继到达的时间间隔服从参数为 λ的指数分布,系统中共有 S个服务员,每个服务台的服务时间相互独立,且服从参数为 μ的指数分布。当顾客到达时,若有空闲的服务台则可以马上接受服务,否则便
【1】
排成一个队列等待,等到有空间服务台时再接收服务。
下面讨论这个排队系统的平稳分布。记: p=p{N=n} (n=0,1,2...) 为系统达到平稳状态后队长 N的概率分布, 注意到对个数为 S的多服务台系统, 有: λn=λ, n-0,1,2...
和μn=nμ n=0,1,2...,μn=sμ n=s,s+1...
记ρs=ρ/s=
λ
, s/μ
n
则当ρ
1λ⎫有 pn=⎛ ⎪
n!⎝n!⎭
1=pns!sn-s
p
n=1,...s (4)
⎛λ⎫
μ⎪⎪⎝⎭
n
p
, n≥s
⎡nρiρn+1⎤
其中:p0=⎢∑+⎥ (5)
i!n!n-ρ⎣i-0⎦
-1
公式(4)和公式(5)给出了在平衡条件下系统中顾客数为n的概率,
当 n≥s时,即系统中顾客数大于或等于服务台个数,这时再来的顾客必须等待,
因此记: c(s,ρ)=∑
n-1∞
ρ
pn
=
s
s!1-s
p0 (6)
式(6)称为Erlang 等待公式,它给出了顾客到达系统时需要 等待的概率。
对多服务台等待制排队系统,由已得到的平稳分布可得平均排 队长Lq 为:
Lq=
n=s+1
∑(n-s)pn=
s
∞
∞
pρ
s
s!
∑(n-s)ρs
n=ss
∞
n-s
=
pρ
s!
pρρsn⎫d⎛
∑ρ⎪=0
dρs⎝n=1s⎭s!1-ρ2
s
记系统中正在接受服务的顾客的平均数为s,显然s也是正在 忙的服务台的平均数,故:
s=∑n
n=0-
s-1
--
p
n
+s∑
n=0
∞
p=∑
n
n=0
s-1
nρn!
n
p
+
(7)
s
s!1-ρ
s
s
n-1s-1
⎡s-1⎤
ρρ⎥=ρ+p0=p0ρ⎢∑⎢n=1n-1!s-1!1-ρs⎥⎣⎦
式(7)说明,平均在忙的服务台个数不依赖于服务台个数s,由(7)式,
可得到平均队长L 为:L = 平均排队长+正在接受服务的顾客的平均数= Lq+ρL ,
对多服务台系统,Little 公式依然成立,即有平均逗留时间W=待时间Wq=
L
λ
;平均等
L
λ
q
=W-
1
μ
。
【4】
3.实例分析
3.1 模型假设
3.1.1 假定学生在高峰期这段时间达到的人数是无限的,并且依次以参数为λ 的泊松过程达到,达到的时间间隔是随机的,服从负指数分布。 3.1.2 每个服务窗口以并联的方式连接,且每个窗口对学生来说都是一样的,服务时间服从参数为μ 的负指数分布。
3.1.3 食堂实行先来先服务原则,且学生可自由在队列间进行转移,并总向较短的队进行转移,没有学生会因为队列过长而离去,故可认为排队方式是单一队列等待制。由于周六周日学校大多数学生没课,故学生去食堂的时间较为分散,很少发生排长队的现象,我们在此就不做分析了。我们仅就周一至周五的食堂拥挤情况进行分析。经我们观察发现,一般打到饭的同学都能找到座位吃饭,故我们可认为,食堂的容纳学生数是足够的,所以解决食堂拥挤状况,主要是解决排长队与服务窗口的问题。我们统计了从某周一到周五12:45 至13:15 高峰期食堂的学生流分布情况:共统计了1129人次的数据(以10 秒为一个时间单位), 见下表:(部分数据)表一
由概率论的知识可知,若分布满足
k
=
λ
k
,【3】
k-1
则该分布为泊松分布(其中pk为泊松分布的密度,λ为泊松分布的参数)。 由上表可得 λ=3.43。经检验,该分布近似于泊松分布。虽然我们仅仅调查了一周的数据,但考虑到学生到食堂就餐具有较大的稳定性,所以认为调查的数据还是较为可靠的。另外在非高峰时段很少发生排队现象,故在此我们也不做分析。
3.2 模型建立及求解
基于以上的假设,我们的模型符合排队论中的多服务台等待模型(M/M/s)。该模型的特点是:服务系统中有s 个窗口(即s个服务员),学生按泊松流来到服务系统,到达强度为λ ;服务员的能力都是μ,服务时间服从指数分布,每个顾客的平均服务时间t 。当顾客到达时,如果所有服务员都忙着,顾客便参加排队,等待服务,一直等到有服务员为他服务为止。由我们调查的数据可知λ = 3.43, t=1.5, s= 6 (食堂现有窗口6 个)代入以上各式
-
μ = -= 0 . 67
可得:服务员能力:系统服务强度:ρ=
t
1
λ
=5.12 , μ
ρ
s=
5.12
=0.85
因为平均每一个窗口的服务强度ρs=空闲概率:
tn+1
⎡⎛n⎤⎫
ρρ ⎪⎥ ,其中n为一窗口的总顾客数,i为正在+p0=⎢∑⎪⎢ t=0i!⎪n!n-ρ⎥⎢⎝⎥⎭⎣⎦
接受服务的顾客数,则系统中排队顾客的平均数:Lq=顾客平均排队时间: W=
pρρ
s!1-ρ
s
s
s
2
=32 ,
L
λ
q
=
-
32
=9.3 , 3.43
顾客平均逗留时间:Wq=W+t=9.3+1.5=10.8 , 系统中顾客的平均数:L=Lq+ρ=32+5.12=37.12 ,
由此可见,当我们中午在12:45 至13:15 这个时间段去食堂吃饭时,一进门就会发现里面已经人满为患,几乎不可能找到空闲的窗口。而且,已经有37个同学正在排队买饭。32 个人正在排队等待,平均一个窗口6人。当我们开始排队时,要过93秒钟才轮到我们,要过108秒钟我们才能吃上可口的饭菜,来填饱我们的肚子。为了检验我们的数据与事实相符,我们特地亲身体验了一番,下表是
我们的统计数据(仅对一个窗口而言):表二
忽略那些随机因素,我们得到的那些结论和实际数据还是较为符合的,可见我们的模型还是很成功的。 3.3 模型分析
对于学生来说,中午的时间是很有限的,能尽快吃上饭对我们来说是很重要的。同时,学生在食堂排队的平均逗留时间Wq很大程度上可以决定学生对食堂的选择,所以食堂工作人员也希望能尽可能的满足学生的需求。研究学生平均逗留时间Wq,将是解决本模型的关键所在。平均逗留时间Wq 是由平均排队时间W和平均服务时间t 组成。我们认为15 秒的平均服务时间t对
-
于服务员来说已经是极限了,如果再加快速度反而可能手忙脚乱,增大出错的可能性,到时反而会降低效率,故我们认为平均服务时间t 不可改变,是个常数。至于平均排队时间W,我们由公式可知它是由顾客到达强度λ,每个顾客的平均服务时间t 和窗口数s来决定的,由于学生对于食堂的选择都有一定的偏好,即一般都会去同一个食堂吃饭,所以我们可以认为学生流是稳定的,即λ为常数,由上面的分析又可知t 也是常数,因此能对平均排队时间构成影响的就只有窗口数了,下面我们就s的取值对W的影响进行分析: 由matlab 我们可以得到它们两者之间的散点图:
-
散点图
拟合图
注:在上图中我们把W 的单位改成了秒。从图中可看出我们各点之间的变化规律较为平稳,所以我们有可能用多次多项式将其拟合,所以我们又用matlab 对其进行了三次多项式的拟合,从而得到了它们的拟合图。 它们之间的二次多项式关系式是:y=-4.3+112.8x-981.6x2+2836.6x3 ,
从图中可以看出,随着窗口数的增加,平均排队等待时间急剧减少,当窗口数达到5以后时,变化趋于平缓。从拟合图中,我们只能看出窗口数与平均排队等待时间的大致关系,为了得到更精确的分析,我们将用灵敏度的观点进行讨论。
由于窗口数s 只能是整数,我们得到如表三的对应关系:表三(单位:秒)
下面我们分析平均排队时间对窗口数的灵敏度: 灵敏度Q(s,W)=
∆W/∆s【4】
,
W/s
由此我们可得不同的窗口数s 下的灵敏度:表四 由此可见,平均排队时间W 对窗口数十分敏感,均达到了16以上,其中以窗口数从6 变成7 时尤为明显,而其他几种情况虽也很敏感,但是平均排队时间变化的绝对值很小,大小不超过4 秒钟。
4窗口优化设计
由于对于学生方面来说,当然是排队等待时间越短越好;而对于食堂方面来说,窗口数的增加一方面会导致成本的增加,带来大的成本压力;另一方面会缩短排队时间,即意味着它能为更多学生服务,所以它是否会增加窗口数就取决于成本和收益的大小关系。因此,需要对系统进行优化,在成本和利益之间寻求可能有的平衡点。我们可以把该系统优化表述为:寻求最佳的服务窗口数量s,使系统总费用C(s)最小。那么:minC(s)=C(s)⋅s+C(W)⋅L, 其中:s为并联的窗口台数量,C(s)是关于窗口台数量的费用,Cs是单位时间里平均每个窗口的费用,Cw为平均每个学生在系统中等待(或逗留)单位时间的等待损失,L是平均队长。
在理论上,上述目标函数存在着优化解。一般来说,每增加一个窗口,需要多配备一名服务人员以及一些配套的设施。所以增加窗口数所带来的成
本等于新增服务人员的工资加上配套设施的维修与清洗费。新增窗口得到的收益是很难估量的。在此我们引入等待损失的概念,即由于排队等待食堂所减少的收益,得到等待损失等于食堂单位时间收益乘以平均等待时间乘以顾客数。我们调查得知服务人员的每月平均工资为1200元,即每周平均280元。至于配套设施的维修与清洗,我们可大致认为其每周不超过300元。由此可知每增加一个窗口,食堂的成本每周就得增加280元。至于食堂从每个学生身上可获得多少利润,因为学生要的菜不同,而且菜的利润也不同,所以是很难确定的,故我们由一般规律假定其每十秒钟可得0.5元利润。
所以,学生因等待而使食堂发生的损失C=0.5×1129W,当窗口数从6 变为7 时,食堂可少损失ΔC=0.5×1129×ΔW=0.5×1129× (3.2-0.523)=1151.16元。由此可知最佳的窗口数为7。
5结果分析
一般而言,我们会认为增加窗口数量,则会减少排队等待时间。然而就食堂的角度来说,虽说增加窗口数量可以减少排队等待时间,提高学生对该食堂的满意度,从而赢得更多的学生到该食堂就餐,但是同时也会增加食堂的运营成本。通过对食堂排队状况的模型求解,考虑到食堂运营成本等因素, 从而得出最佳的窗口数量为7。从各窗口排队情况来看,我们发现其中打快餐窗口的排队现象较突出,因此我们认为最佳选择是在食堂多加一个打快餐窗口,作为新增加的第7个窗口,以此缓解拥挤现象,减少排队等待时间,从而提高学生对食堂的满意度。
6结束语
通过对本次课程论文的设计,使我们进一步掌握了排队论及其相关理论知识,并学会如何将理论运用于实践,从而解决实际生活当中遇到的各种问题。排队论是通过研究由于随机因素而产生的拥挤现象,解决服务系统最优设计和最优化控制的一门科学。本论文将根据食堂排队状况建立数学模型,运用排队论的观点进行分析,通过比较各方面因素的关系,为其拥挤状况找到了一个较合理的解决方案。根据模型分析,考虑到食堂成本等各个因素从而得出解决此问题的方法,即通过增加窗口来改善排队等待现象,以减少排队等待时间,从而提高学生对食堂的满意度。排除论作为研究服务系统中排除现象随机规律的学科,如能将其运用于食堂服务系统的规划当中,有重要的实践意义。文章根据排对论的思想建立了食堂的排队服务模型。通过对模型的优化设计,科学地确定了食堂服务的最佳窗口数量,并通过实例说明了该方法的计算过程,证明排队论在食堂服务系统优化中具有实际用途。