基于事件调度法的排队系统仿真研究

基于事件调度法的排队系统仿真研究

0基于计算机模拟的监狱与排放系统的分析在日常生活中，随处可见队列现象，比如在超市等待账单、从银行赚钱、在车站投票等。而排队论是研究系统由于随机因素的干扰而出现排队现象的规律的一门学科。在排队论的研究中,经典的分析方法是建立其状态平衡方程,利用概率统计的知识求其平均等待时间,平均队列长度等系统指标,但排队系统的排队特征、排队规则、服务机构变得复杂时,用解析方法已无法求解。计算机模拟正是求解排队系统和分析排队系统性能的非常有效的方法。本文利用事件调度法对排队系统进行分析,以事件步长法模拟系统时钟推进,使用Matlab语言给出M/M/c型系统的仿真程序。其模拟流程和模拟程序也适用于顾客输入和服务时间均为一般分布的排队系统。仿真结果表明,该方法切实可行。1顾客的到达时间假设c个服务台并连服务,顾客源无限,随机选择空闲服务台,顾客到达时间间隔和顾客服务时间服从负指数分布,排队规则为FCFS(先到先服务),λ表示单位时间内顾客的平均到达数,μ表示单位时间内被服务完毕离去的平均顾客数,则1/λ表示相邻两个顾客到达的平均间隔时间,1/μ表示每个顾客的平均服务时间。M/M/c的性能指标如下:系统中平均顾客数:Ls=Lq+λu,排队等待的平均顾客数:Lq=(cρ)cρc!(1-ρ)2p0,顾客的平均逗留时间:Ws=Lsλ,顾客的平均等待时间:Wq=Lqλ,其中p0=[c-1∑k=01k!(λu)k+1c!⋅11-ρ⋅(λu)c]-1‚ρ=λ/μ。2服务台的服务排队系统的主要要素是顾客和服务台,顾客可以是人、机器、汽车等任何需要服务的东西。服务台可以是人、车站、码头、港口等提供服务的东西。本文主要考虑c个服务台并连服务的情形,其模型结构如图1。模型的求解以事件步长法模拟系统时钟推进,采用事件调度法作为仿真策略。通过时间进程的模拟,确定下一事件的发生。模拟流程如图2-4。3模拟编程3.1使用数据结构为了有效组织这些复杂的数据,本文使用Matlab结构体数组来实现“队列”这一常见的数据结构。记录相关信息的数据结构如图5-8。3.2hqueue服务台是否空闲的判断:当系统中的顾客数≤服务台数时(length(queue)≤c),服务台有空闲,否则为忙;是否有人排队的判断:当系统中的顾客数>服务台数时(length(queue)>c),有人排队,此时服务台忙,否则无人排队。3.3模拟时间进程假设模拟的目的是要求估计服务n个顾客后系统中的平均顾客数ˆQ(n)及平均等待时间ˆd(n),可以参照排队论得到相应的计算式:ˆd(n)=n∑i=1Di/n,ˆQ(n)=1Τ∫Τ0Q(t)dt本文采用事件步长法中的事件类型时钟值来控制模拟时间进程。由于事件步长法模拟时钟推进的随机性,计算ˆQ(n)可用ˆQ(n)=1Τm∑i=1Ri来估计,Di=Si-Ai。到达时刻由随机数产生,而Si={Ai‚若第i个顾客不要排队等待；c个服务台中最先结束服务的时刻‚否则其中Di:第i个顾客的排队等待时间;Si:第i个顾客的开始服务时刻;Ai:第i个顾客的到达时刻;Q(t):t时刻排队等待的顾客数;T:完成n个顾客服务所耗时间;d^(n)‚Q^(n):估计值;ti:第i个事件发生的时间;t0:模拟初始时间;m:在区间[t0,t0+T]上发生的事件总数;Ri:时间区间[ti-1,ti]上排队人数qi乘以时间区间长度ti-ti-1,即Ri=qi(ti-ti-1)。4顾客数额及等待时间某售票所有3个窗口,顾客的到达服从普阿松分布,平均到达率每分钟λ=0.9人,服务时间服从负指数分布,平均服务率每分钟μ=0.4人。现设顾客到达后排成一队,依次向空闲的窗口购票。这就是一个M/M/C/∞/∞型系统,其中c=3,由于λcμ=2.253＜1,不会形成无限长的队列。根据第2节可计算得:系统中平均顾客数Ls=3.95人,平均等待时间Wq=1.89分钟,平均服务时间2.5分钟,平均逗留时间Ws=4.39min。本文采用终态仿真的运行方式,在相同的初始条件下(每次模拟30天,每天从8点到16点,初始时刻系统中只有1人),经过10次独立的仿真运行,得出结果如表2。5计算机模拟仿真通过和理论值的比较,仿真结果与根据解析法得到的结果误差很小,证明了使用离散系统仿真方法模拟排队系统运行的可行性。排队系统模型应用广泛,但