基于malab的排队问题仿真研究

基于malab的排队问题仿真研究

1909年发表的题为《排水理论》的文章发表以来，公共交通理论在通信、军事、运输、维护、生产、服务、库存、医疗、卫生、教育和灌溉等领域的排卡系统中得到了广泛应用，并促进了研究和开发运卡理论及其应用的理论和应用。在许多排队问题的数学模型建立中,都是假定顾客到达间隔时间流为最简单流,服务时间服从负指数分布,从而利用马尔可夫随机过程建立起已知条件与必然结果间的解析性关系。但在实际系统中,顾客到达时间及服务时间并不满足这种假设,因此需要有更一般的方法。Matlab是由MathWorks公司开发的工程技术科学计算软件,以其强大的计算、绘图功能,大量可靠高效的算法库(工具箱)以及简洁易操作的编程、图形界面,深受广大科技计算和设计人员喜爱。Matlab中Simulink工具箱是一个可进行动态系统建模、仿真和统计分析的集成软件包,能处理包括线性、非线性系统、离散、连续及混合、单任务和多任务离散事件系统的工具。笔者分析了排队问题中一般的规律,利用Matlab中的Simulink工具箱,设计出对复杂的排队系统进行仿真和分析研究的Simulink模型,给出了对排队问题各性能指标的仿真计算公式,并通过实例,比较了解析解与仿真解的相应结果。1服务系统的服务能力现实世界中排队现象随处可见,如商店购物、汽车加油、轮船进港和物流调度等。各领域中排队形式和内容虽有不同,但过程有共同的特征,即由需要服务的顾客和提供服务的服务员组成服务系统,顾客到达时间和服务时间不一定确定。服务过程的随机性造成某阶段顾客排队等候服务,而某阶段服务员又空闲无事的情形。服务系统的服务能力一方面取决于服务员的数量和服务员的能力;另一方面也取决于顾客流的性质。排队问题就是要寻求顾客流、服务能力和服务系统效益的合理关系。服务系统的运行指标常用绝对通过能力、相对通过能力、系统损失率、队长、排队长、顾客逗留时间期望和排队等待时间期望等指标描述。1.1顾客的概率pnt为求得这些指标而建立的排队模型,经典的方法是,用Kolmogorov方程、生灭图和Little公式等,在特定条件下,利用Markov随机过程建立,而在统计平衡状态下求解。例如,最简单的Μ|Μ|1M|M|1排队系统,顾客到达时间间隔和服务时间分别服从参数为λ和μ的负指数分布,顾客源和排队空间无限,服务规则是先到先接受服务。在这一系统中,任一时刻t系统内有n个顾客的概率pn(t)满足方程:{dp0(t)dt=μp1(t)-λp0(t)dpn(t)dt=λpn-1(t)+μpn+1(t)-(λ+μ)pn(t)n=1,2,⋯(1)⎧⎩⎨⎪⎪⎪⎪⎪⎪dp0(t)dt=μp1(t)−λp0(t)dpn(t)dt=λpn−1(t)+μpn+1(t)−(λ+μ)pn(t)n=1,2,⋯(1)式(1)求解相当麻烦。一般求在系统运行相当长时间后的统计平衡解,即:dpn(t)dt=0时的解,可得到:pn=ρnp0,ρ=λ/μ,p0=1-ρ,n=1,2,⋯(2)从而,在系统负荷水平ρ∈(0,1)时,得到系统如下的重要指标。(1)员工休息的可能性如下p0=1-ρ=1-λ/μ(3)(2)对于系统负责人，系统中客户数的数学期望如下所示LS=∞∑k=0kpk=ρ/(1-ρ)=λ/(μ-λ)(4)(3)船长和舰队中的平均客户数如下所示L=∞∑k=1(k-1)pk=ρ21-ρ=λ2μ(μ-λ)(5)(4)客户保留时间预测如下WS=L/λ=1/(μ-λ)(6)(5)队列的等待期为W=LSλ=ρ2λ(1-ρ)=λμ(μ-λ)(7)1.2统计试验方法的求解1.2.1面向事件的仿真模型对于一般条件下的排队问题,求系统性能指标解析解相当复杂繁琐,甚至无法得到,因此,一般的方法是选用统计试验法,也就是MonteCaro方法。为了利用Matlab中的Simulink工具箱建立排队问题的仿真模型,要研究排队过程中顾客到达时间、服务开始与结束时间的关系。设排队系统中顾客到达时间间隔服从任一分布A,第n位顾客到达时间间隔为a(n),设系统中服务员总数为N,服务员m的服务时间服从分布Sm,为第n位顾客服务时的时间为sm(n)。若第n个顾客到达系统的时刻为arrive(n),开始服务时刻为start(n),结束服务时刻为over(n),则排队系统可以采用面向事件的仿真模型。仿真过程按下一最早发生的事件的时间推进。事件属性为arrive(n)、start(n)、over(n)以及系统中每一服务员的忙闲状态som(n)。服务员的忙闲状态设定为:当第m个服务员此前最后一个由该服务员服务的顾客结束服务的时间。仿真过程需设定各种属性间的关系如下:(1)设系统仿真初始时刻为0,第n位顾客到达时刻arrive(n)满足:arrive(n)=n∑i=1a(i)=arrive(n-1)+a(n)(8)(2)顾客n开始接受服务与结束服务的时间与所选择的服务员有关。可选择这N个服务员中此前最早结束服务的服务员,也可以选择期望使第n位顾客最早结束服务的服务员,这可能出现更长的等待:start(n)=max[minj∈{1,2,⋯,Ν}(soj),arrive(n)](9)当第n位顾客待定了第m个服务员为其服务时,有:over(n)=start(n)+sm(n)(10)som(n)=over(n)(11)1.2.2模型解决方案对上述中模型求解,即可得到系统中的各项指标。(1)中小型企业服务效率比较对每一服务员累计其服务时间Ss,然后比较系统总的仿真时间T,即得到服务员空闲概率为:p0(i)=1-Ss/Τ(12)整个系统服务员空闲率可用每一服务员空闲率的平均值计算:p0=1ΝΝ∑i=1p0(i)(13)从系统服务员空闲率与每一服务员的空闲率的差异可比较每一服务员的服务效率。(2)客户保留时间以等待统计在仿真时间T内服务的顾客数nt,则顾客平均逗留时间为:WS=1ntnt∑i=1[over(i)-arrive(i)](14)(3)队列的等待期为W=1ntnt∑i=1[start(i)-arrive(i)](15)(4)系统中断如下LS=λWS(16)其中,λ为顾客到达强度,即单位时间到达的顾客数平均值。(5)组长L=λW(17)2关于团队问题的simulik模拟2.1生成均匀随机数对排队问题建立的Simulink模型的信源,就是要进行的输入部分,它们是一系列的随机量,即顾客到达时间间隔随机列和各服务员进行服务时的服务时间随机列。新建一个Simulink模型,取定模型名,如Queuing。Simulink库浏览器(Simulinklibrarybrowser)Simulink中子库Sources内有均匀分布随机数发生模块。一般使用逆变换法将均匀分布随机数转换成指定分布的随机数。例如,顾客到达时间间隔如果服从参数为λ的指数分布,那么,可将服从(0,1)上的均匀分布的随机数u经变换x=-lnu/λ得到服从参数为λ的指数分布的随机数x。2.2sim选型排队模型使用离散模型仿真,按仿真过程各属性间的关系设定运算模块及信号线。其中,要用到的运算模块主要有求和模块(sum,位于Simulink库浏览器中Simulink下子库CommonlyUsedBlocks中)和单位延迟模块(UnitDelay,位于Simulink库浏览器中Simulink下子库Discrete中)。还要用到一些函数模块,简单地可用Simulink库浏览器中Simulink下子库User-DefinedFunctions中各种函数模块。2.3信宿库sisks内的实体信息排队问题Simulink模型的信宿,就是将排队问题需要的各项系统性能指标按各种最适当的形式输出。Matlab的Simulink工具箱中信宿库Sinks内有数值显示模块Display、示波器Scope、显示x-y图形模块XYGraph、数据保存模块ToFile和ToWorkspace等,以及终止仿真的Stop等常用Sink库信宿。可以根据需要,将服务员空闲率、队长和顾客逗留时间期望等性能指标按适当形式输出以供分析。2.4达到结束服务仿真过程的步长设置以事件(即每位顾客从到达到结束服务)为步长。同一状态内的指标用到达时间、开始服务时间和结束服务时间来标志。按给定的步数和总时间控制仿真的结束。3顾客期望和等待时间Μ|Μ|1系统实例:某超市有一个收款台,顾客到收款台按泊松流到达,平均每小时到达20人,收款时间服从指数分布,平均每个顾客需要2.5min。计算收款台服务员空闲率、服务台前排队顾客的期望值和每个顾客平均等待时间等性能指标。该实例是一个M|M|1排队问题,顾客到达时间间隔和服务时间都服从指数分布,其参数分别为λ=1/3和μ=1/2.5。3.1顾客期望值的确定由式(2)可知,收款台服务员空闲率为:p0=1-ρ=1-λμ=1-1/31/2.5=16服务台前排队顾客的期望值为:L=λ2μ(μ-λ)=(1/3)21/2.5×(1/2.5-1/3)=256每个顾客平均等待时间为:W=λμ(μ-λ)=3×256=252每位顾客在系统中平均逗留时间为:WS=1μ-λ=11/2.5-1/3=153.2示例simulik模拟在Matlab中创建Simulink模型如图1所示。3.2.1逆变换法m包含两个均匀分布随机量发生模块,设置好其中参数,使它与后面紧跟的函数模块In和信号放大模块一起完成用逆变换法将均匀随机数转换成满足指定参数的指数分布的随机数。3.2.2该系统包括三个郑和模块、一个延迟模块和四个离散时间跟踪模块。一个信号组合器多个信号组合向量和一个最值函数模块minmax用于计算到达时间间隔的累积，并确定到达时间间隔的rieven。所有客户保留服务时间的总和，整个客户服务时间的总时间安排，以及服务时间的总时间安排start(n)=max[arrive(n),over(n-1)]over(n)=start(n)+serve(n)3.2.3顾客总滞留时间以上Simulink模型中信宿由4个有阴影的ToWorkspace模块组成,它们分别将仿真结果顾客总等待时间wait、顾客在系统中总逗留时间stay、服务员的总服务时间serve以及排队系统运行时间over送入Matlab的Workspace中保存。信宿中,设定系统时间不超过480000min,它是由一个关系模块与常数比较(RalationalOperator模块)和停止仿真(Stop模块)构成。3.2.4仿真参数设置该Simulink模型是一个离散模型,在仿真前要对系统参数设定:仿真开始时间为1,终止时间为1000000;采用定步长离散(无连续状态)解算器,将仿真总步数(即参与仿真的顾客总数)命名为tout贮存到Workspace中。3.3顾客滞留时间仿真运行以上Simulink模型,则在Matlab的Workspace中会得到文件名为over、serve、stay、wait和tout的5个变量,它们的值分别为:over=480001.2246、serve=400394.9842、stay=2407881.6980、wait=2007486.7138、tout=160259。利用上述仿真结果,可算出服务员空闲率、顾客平均等待时间和平均逗留时间。仿真结果如表1所示。可见仿真结果与用解析方法所得结果吻合程度非常好。还要说明的是,该Simulink模型整个运行时间非常少,在普通的神舟天运F231S笔记本电脑上大约只需2s。4基于simulaid模型的仿真数据利用Matlab中Simulink工具箱对排队问题进行仿真,基于上述实例所建的模型,只要将Simulink模型中的信源(均匀分布随机数发生器)后紧跟的函数模块按逆变换法要求,改成相应的函数