排队论的应用

排队论的应用——食堂排队问题刘文骁摘要本文通过运筹学中排队论的方法，为食堂排队问题建立模型，研究学生排队就餐时间节约的影响因素，通过简单计算，得出影响最大因素。排队论是通过研究各种服务系统的排队现象，解决服务系统最优设计和最优化控制的一门科学。本文将根据食堂排队状况建立数学模型，运用排队论的观点进行分析，找出可以减少排队时间的最大影响因素。关键词排队论；M/M/s模型；食堂排队引言在学校里，常常可以看到这样的情况：下课后，许多同学正想跑到食堂买饭，小小的买饭窗口前没过几分钟便排成了长长的队伍，本来空荡荡的食堂立即变得拥挤不堪。饥肠辘辘的学生门见到这种长蛇阵，怎能不怨声载道。减少排队等待时间，是学生们十分关心的问题。1.多服务台排队系统的数学模型1.1排队论及M/M/s模型排队论是研究排队系统(又称为随即服务系统)的数学理论和方法，是运筹学的一个重要分支。在日常生活中，人们会遇到各种各样的排队问题。排队问题的表现形式往往是拥挤现象。排队系统的一般形式符号为：X/Y/Z/A/B/C。其中：X表示顾客相继到达时间间隔的分布；Y表示服务时间的分布；Z表示服务台的个数；A表示系统的容量，即可容纳的最多顾客数；B表示顾客源的数目；C表示服务规则。排队论的基本问题是研究一些数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征；系统数量指标的统计推断和系统的优化问题等。当系统运行一定时间达到平稳后，对任一状态n来说，单位时间内进入该状态的平均次数和单位时间内离开该状态的平均次数应相等，即系统在统计平衡下“流入=流出”。据此，可得任一状态下的平衡方程如下：由上述平衡方程，可求的：平衡状态的分布为：)1(,2,1,0npCpnn其中：)2(,2,1,11021nCnnnnn有概率分布的要求：10nnp，有：1100pCnn，则有：)3(1100nnCp注意：（3）式只有当级数onnC收敛时才有意义，即当onnC时才能由上述公式得到平稳状态的概率分布。1.2M/M/s等待制多服务台模型设顾客单个到达，相继到达的时间间隔服从参数为的指数分布，系统中具有S个服务员，每个服务台的服务时间相互独立，且服从参数为的指数分布。当顾客到达时，若有空闲的服务台则可以马上接受服务，否则便排成一个队列等待，等待空间为无限。下面讨论这个排队系统的平稳分布：即nNpp),2,1,0(n为系统达到平稳状态后队长N的概率分布，注意到对个数为S的多服务台系统，有：,2,1,0,nn，和,1,,2,1,0ssnsnnn，即：sspps，则当P1时，由(1)式，(2)式，(3)式，得：snpsssnpnpnsnnn00!1)4(,,2,1!1其中：)5(!!1100nnipnnii公式(4)和公式(5)给出了在平和条件下系统中顾客数为n的概率，当sn时，即系统中顾客数大于或等于服务台的个数，这时来的顾客必须等待，因此即：)6(1,01pspscssnn！(6)式成为Erlang等待公式，它给出了顾客到达系统是需要等待的概率。对多服务台等待制排队系统，由已得到的平稳分布可得平均排队长qL为：2010011!!!sssnnssssnssnsnsnqspddspsnsppsnL记系统中正在接受服务的顾客的平均数为s，显然s也是正在忙的服务台的平均数，故：(7)式说明平均在忙的服务台个数不依赖于服务台个数S，这时一个特殊的结果。由(7)式，可得到平均队长L为：L=平均排队长+正在接受服务的顾客的平均数qL对多服务台系统，Little公式依然成立。即有平均逗留时间LW;平均等待时间1WLWqq。2.实例分析2.1模型假说假定学生在高峰期这段时间达到的人数是无限的，并且一次以参数的泊松过程达到，达到的时间间隔是随机的，服从负指数分布。每个服务窗口以并联的方式连接，且每个窗口对学生来说都是一样的，服务时间服从参数为的负指数分布。食堂实行先来先服务原则，且学生可自由在队列间进行转移，并总向最短的对转移，没有学生会因为队列过长而离去，故可认为排队方式是单一队列等待制。一般打到饭的同学都能找到座位吃饭，故我们可认为，食堂的可容纳学生数是足够的，所以解决食堂的拥挤现象，主要是解决排长队与服务窗口的问题。以下数据来源于网络（作者：李晟源）：高峰期食堂的学生流分布情况：共统计了3059人次的数据(以10秒为一个单位)，见下表：表一每10秒到达人数123457频数257441894956350161由概率论的知识可知，若分布满足kppkk1，则该分布为泊松分布。(其中kp为泊松分布的密度，为泊松分布的参数)由上表可知=3.39。2.2模型建立及求解基于以上的假设，我们的模型符合排队论中的多服务台等待模型(M/M/s).该模型的特点是：服务系统中有s个窗口(即s个服务员)，学生按泊松流来到服务系统，到达强度为；服务员的能力都是，服务时间服从指数分布，每个顾客的平均服务时间t。当顾客到达时，如果所有服务员都忙着，顾客便参加排队等待服务，一直等到有服务员为他服务为止。由我的调查数据可知6,5.1,39.3st(食堂现有窗口6个)带入以上各式可得：服务员能力：67.01t系统服务强度：09.5，因为85.0609.5ss1,所以极限存在。空闲概率：031.0!!1100nnipnnii系统中排队顾客的平均数：271!20sssqspL顾客平均排队时间：96.739.327qqLW顾客平均逗留时间：46.95.196.7tWWq系统中顾客的平均数：09.3209.527qLL由此可见，当我们在这个时间段去食堂吃饭时，一进门就会发现里面已经是人满为患了，几乎不可能找到空闲的窗口。而且，已经有32个同学在排队买饭，27个人这在排队等待，平均一个窗口5人。当我们开始排队时要过80秒钟才轮到我们，要过95秒钟才能吃到可口的饭菜，来填饱我们的肚子。2.3模型分析对于学生来说中午的时间是很有限的，能尽快吃上饭对我们来说是很重要的。同时，学生在食堂的排队的平均逗留时间qW很大程度上可以决定学生对食堂的选择，所以食堂的工作人员也希望尽可能的满足学生的要求。研究学生平均逗留时间qW将是解决本模型的关键所在，平均逗留时间qW是由平均排队时间W和平均服务时间t组成。我个人认为15秒的平均服务时间t对于服务员来说已经是极限了，如果在加快速度反而可能手忙脚乱，增大出错的可能性，到时反而会降低效率，一次我认为平均服务时间t不可改变，是个常数。至于平均排队时间W我们有公式可知它由顾客到达强度，每个顾客的平均服务时间t和窗口数S来决定的，由于学生对食堂的选择有一定的偏好，即一般都会去同一个食堂吃饭，因此我们可以认为学生流是稳定的，即为常数，由上面的分析可知t也是常数因此能对平均排队时间构成影响的就只有窗口S了。对于我们大学食堂，每层12个窗口，往往只有7-8个窗口有人排队，其余窗口无人光顾，这大大增加了我们的排队时间。根本原因在于4-5个窗口的饭菜口味太差，导致学生不愿购买。参考文献：[1]胡运权，运筹学教程清华大学出版社，1988[2]许久平，胡只能等，运筹学（类）（第二版）科学出版社，2004[3]韩中庚，数学建模方法及其应用（第二版）高等教育出版社，2009薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿羁膂莈蚅袇膁蒀蒈螃膀膀蚃虿腿节蒆羈芈莄蚁袄芈蒆蒄螀芇膆蚀蚆袃莈蒃蚂袂蒁螈羀袁膀薁袆袁芃螆螂袀莅蕿蚈衿蒇莂羇羈膇薇袃羇艿莀蝿羆蒂薆螅羅膁蒈蚁羅芄蚄罿羄莆蒇袅羃蒈蚂螁羂膈蒅蚇肁芀蚁薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿羁膂莈蚅袇膁蒀蒈螃膀膀蚃虿腿节蒆羈芈莄蚁袄芈蒆蒄螀芇膆蚀蚆袃莈蒃蚂袂蒁螈羀袁膀薁袆袁芃螆螂袀莅蕿蚈衿蒇莂羇羈膇薇袃羇艿莀蝿羆蒂薆螅羅膁蒈蚁羅芄蚄罿羄莆蒇袅羃蒈蚂螁羂膈蒅蚇肁芀蚁薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅