信息与控制
Information and Control
1999年　第28卷　第4期　Vol.28　No.4　1999



逆向仿真在不可控到达排队系统中的应用

宣慧玉　王丽娟

　　摘　要: 针对传统的离散事件系统仿真技术在排队系统进行设计方面存在的不足和困难,本文提出采 用一种新的仿真技术——离散事件系统逆向仿真来解决,并以单急救站系统为例,介绍了逆向 仿真应用于该系统进行结构设计的具体方法和过程,最后通过正向仿真对设计结果进行检验, 说明了利用逆向仿真求解该类问题的可行性和有效性. 
　　关键词: 逆向仿真,排队系统,系统设计
　　中图分类号：TP11　　　　　　文献标识号：B
APPLICATION OF INVERSE SIMULATION IN QUEUING SYSTEM
WITH UNCONTROLLABLE ARRIVING
XUAN Huiyu　WANG Lijuan
(The Management School of Xi'an Jiaotong University, 710049)
Abstract: For the deficiency and difficulty of traditional simulation applied to designing a queuing system, this article addressed that it can be improved by using a new simulation technique named inverse simulation in Discrete-Event System. Taking a Emergency Ambulance Services (EAS) system (one station) as an example, the me thod and process of inverse simulation for designing this system's configuration is introduced. Finally the designing consequence is validated with forward simu lation, which shows the feasibility and efficiency of new technique in solving t his sort of problems.
　　Key words: inverse simulation, queuing system, system design

1　引言
　　对排队系统而言,仿真在系统求解中的功能主要体现在以下几方面:分析现行系统的运行状况,预测未来系统的性能指标,设计和改造系统.由于传统的仿真方法是在已知或预定系统的服务台结构和系统输入的前提下对系统的性能和输出进行测度,则利用其对系统的性能进行分析和预测是非常方便、有效的,在此基础上可对系统的结构等加以调整,以使系统的运行达到比较理想的状态,这便是传统仿真用于改造系统的功能.但从根本上讲,传统仿真方法并不是一种设计工具.针对系统结构设计功能,由于系统的服务台结构才是待求的目标,限于上面所说的传统仿真方法的特点,其做法是:先预定系统结构,根据在不同结构下所测定的系统性能是否满足一定的要求来选择确定决策者认为最满意的设计方案(即结构设置).这事实上属于一种对预提供的一定数量的方案进行择优选取的方法,而这些方案通常是在求解过程中产生的.整个求解过程是一个不断试探、检验的寻优过程,需要反复多次进行“结构调整—性能测试”的仿真运行,往往显得繁杂、低效率.另外,实际中还存在这样一种情况,在顾客的到达 规律可以人为控制和干预的排队系统中,如制造系统,为了保证系统按照一定的要求进行输出 ,要求设计出相应的输入和服务台结构.这个问题利用传统的仿真方法来求解,无疑更加困难.针对以上问题,本文提出可以采用一种新的仿真技术—逆向仿真来解决.并以一个单急救站 系统为例,介绍了该技术在顾客随机到达的排队系统中的具体应用及其逆向特色.
2　逆向仿真
　　这里所说的逆向仿真是针对离散事件系统而提出的.其基本的求解思路是:根据系统的输出或 性能要求来逆向推算出系统的输入和(或)系统结构.通过逆向仿真模型的建立及运行，得到满足一定要求下的服务台结构或输入规律，也就实现了离散事件系统的设计，这样大大简化了利用传统仿真方法解决此类问题的反复寻优运行的过程,提高了仿真技术应用于系统设计方面的效率和可行性.
　　正向仿真中,模型是在按照系统中各类事件发生的先后顺序对事件由前向后不断处理的过程 中推进的,系统前面产生的事件是决定后面有关事件发生的基础,其过程不可逆转;而逆向仿真则不然,以结构设计为例,由于仿真过程中系统结构的变化是在一定条件下发生的,在进行条件的判断,以及结构调整后引起系统现有状态发生变化时,都很可能需要特殊的,与正向仿真不同性质的(逆向)处理方法.
　　在排队系统中,有这样二类系统.其中一类,它的输入即顾客的到达完全是随机的、不可控的, 而系统的输出即顾客的离开规律则不是研究者所关心的.而另一类系统如加工系统,它的输入 是人为安排的、可控的，关心的是它的输出规律.这二类系统在逆向仿真时求解问题、已知 参数不同，所以处理方法也不同．
　　在到来不可控的排队系统中输入是人的行为，它的服务对象是顾客,服务质量是第一位的.而 直接关系到该类系统服务质量高低的关键因素就是服务台的结构(数量).因此,对该类系统根 据服务质量进行合理的服务台结构设计是一个非常现实的问题.而服务质量往往表现在等待 时间,顾客都希望尽快得到服务,在该类不可控到达的排队系统的逆向仿真中以允许的等待时 间为准则,不断调整系统的结构,最后输出系统稳态运行时(或仿真结束时)的结构配置数，图1表示了这类到达不可控排队系统在传统仿真与逆向仿真中到达事件处理的不同流程.
　　　　
图1(a)　传统仿真中到达处理流程　　　　　图1(b)　逆向仿真中到达处理流程

3　实例研究
3.1　背景介绍
　　假设有这样一种情况:某一地区经过规划建设了一片新的居民区,包括生活、工作、学习、卫 生等各种设施,除了医院以外,为了满足居民急救服务的需要,该区决定设立一个本区急救站, 可问题是在站内配置多少辆救护车才算合适呢？很明显,这正是一个不可控到达排队系统的服务台结构设计问题.
　　本急救系统的工作流程是这样的:急救站在某时刻接到一个急救呼叫,在得知对方所处位置及 有关病情后,派出本站的一辆空闲救护车(如果有的话)以及相应的医护人员和医疗设备,赶往呼叫所在地(病人所在地),在对病人作出初步的诊断、急救处理后,送往医院作进一步治疗(或者在送往医院的路上进行急救处理),然后由医院返回急救站;或者,在急救处理后,病人病情得到控制或好转,不需再送到医院,便从该病人所在地直接返回急救站(后一种情况发生的相对较少).从上面的急救过程描述可知,一般情况下,救护车的服务时间(从出发到返回)明显分为五段:从急救站出发到病人所在地时间(T1),在病人所在地处理病人的时间(T2),将病人送到医院的时间(T3),在医院停留(将病人送下救护车)的时间(T4),以及从医院返回急救站的时间(T5).如图2所示.

图2　单急救系统中各项时间参数的描述

　　其中:t0—顾客到达时刻； t1—救护车出发时刻；t2—救护车到达病人所在地时刻； t3—救护车出发到医院时刻；t4—救护车到达医院时刻； t5—救护车从医院开始返回时刻；t6—救护车返回急救站时刻
　　这里需要强调两个概念:(1)救护车的等待时间(WT)是指从顾客发出求救信号到救护车从某地 开始出发进行服务的一段时间.这段时间并不是每个顾客都有,故以虚线表示;(2)系统的响应时间就是指救护车的等待时间和时间T1之和,即顾客实际得到急救处理之前需要等待的时间.
　　对系统响应时间作出的规定,也正是对该急救系统服务质量所作的要求,就是说本急救系 统的服务质量标准特征:正常情况下从接到顾客急救信号到救护车赶到病人所在地的时间不 得超过10分钟,这个指标是本系统设计的准则.这里所说的“正常情况”是相对于非正常情况 (如市内交通非正常性堵塞,天气情况非常恶劣等)而言的.显然,在本区急救站负责的区域内, 要求救护车从本站出发到本区最远的地方的运行时间正常情况下都不得超过10分钟.
3.2　逆向仿真建模
　　所谓逆向仿真模型,是指反映、体现逆向仿真求解问题的方法和过程的数学模型.它设计系统 结构的原理就是,在满足一定的条件(系统的设计准则)下通过特定的方式对系统的服务台结 构进行不断调整.正是由于在逆向仿真中,系统最终的服务台结构是在逆向仿真模型运行的过 程中由系统的设计准则约束着不断地自动调整而形成的,这样的系统设计方法从理论上讲才 是科学的和有效的.
　　单急救站系统的逆向仿真核心流程是这样的:仿真运行中,一个急救呼叫到达,急救站先查询 一下本站是否有空闲的救护车,若有,则救护车立即出发,使该顾客得到服务;若没有,则首先 判断正常情况下救护车从急救站到病人所在地需要运行的时间(T1)是多少,因为本系统服 务质量标准要求的最大响应时间是10分钟,从而可以得出顾客应该得到响应(即得到急救处理 )的最晚时刻(LAT=CLOCK+10,CLOCK是仿真时钟的当前值),则救护车最晚出发的时刻(LST)便是(LAT-T1)的值,然后查询在这个时刻前是否有可归来并能对该顾客提供服务的救护车(这里特别指出并不是所有在这段时间内归来的救护车都能对该顾客提供服务,是因为在该顾客之前 可能还有别的在等待的顾客,则归来的救护车很可能将首先对其前面的顾客进行服务,从而该 顾客便得不到归来车的服务),若有,则该顾客加入排队,等待服务;若没有,则急救站立即增添一辆救护车来对顾客提供服务,从此救护车数量(服务台结构)发生变化,而仿真模型以后就在这变化了的服务台结构上继续运行,按照上述的规则不断处理顾客的到达事件和其它事件,调 整服务台结构.
　　在该流程中,体现模型运行的仿真时钟仍是正向推进的,即从已发生事件的发生时刻向未发生 事件的发生时刻移动,但在决定是否应对服务台结构进行调整的时候,发生了事件及时间的逆 推现象,即由后面将要发生的事件的发生时刻(顾客得到响应的最晚时刻LAT)来逆向推算出前 面应发生的事件的发生时刻(救护车出发的最晚时刻LST),并且,通过查询在LST之前是否有可 对顾客提供服务的救护车,决定了在当前时刻(CLOCK)是发生增加救护车事件,还是发生顾客 加入排队事件,这些都是在正向仿真中不可能出现的逆向推算及逆向决定现象.且正是这种逆 向操作方法,实现了在满足系统服务质量的前提下充分利用现有资源从而达到节约资源(减少 需增加资源的可能性)的系统结构设计思想.
　　很显然,顾客的到达事件是促使服务台结构发生变化的主动事件,即在处理顾客的到达事件时 ,由服务质量标准(第一要求)和节约成本的经济原则(第二要求)共同约束着、控制着服务台 结构所发生的变化,这是该系统逆向仿真模型中最重要的部分.在仿真过程中,另一类要处理 的事件就是救护车的返回事件,即标志着服务台对上一个顾客的服务已经结束,可以接受新的 服务任务的事件.图3所示的就是该单急救站系统的逆向仿真总流程框图,或称系统的 逆向仿真整体模型.


图3　单急救站系统的逆向仿真总流程图
3.3　逆向仿真模型的运行和输出结果
　　在本系统的逆向仿真中设定该区居民发出呼叫的时间间隔是均值为2（分钟）的指数分布， 每次呼叫的允许等待时间为10分钟．对上述单急救站系统的逆向仿真模型在充实有关数据的 基础上进行编程,并上机调试、运行,最后输出运行结果即急救站应配置的救护车数量Na.该急救系统是一天24小时连续值班, 其仿真运行终止时间可视为趋于无限,故对该系统的仿 真属于稳态型仿真.对其仿真结果进行分析时,需要首先确定系统是否达到稳态运行状态, 则 稳态运行下的系统结构参数值就是所要求解的结果.判断系统是否处于稳态运行的标准是:系 统的结构参数值在一个合理长的时间段内基本保持不变.为此,我们采用设定不同的仿真运行 时间,以观察输出结果的变化情况和记录仿真运行过程中结构参数值变为最终输出值时的时 刻,以与仿真运行总时间进行比较两种方法相结合的方法,确定了可以保证本急救系统达到稳 态运行状态的仿真运行总时间Tt=2000(小时).在此仿真时间下多次(>20次)运行该系统的逆 向仿真模型,通过对多次仿真输出的结果Na进行统计分析,得出本急救站应配置的救护车数量 为11辆(均值10.6,90%置信度下的置信区间为[10.35,10.85]).也就是说, 在使所有顾客得 到服务质量标准内的服务的要求下,本急救站应配置11辆救护车.
3.4　逆向仿真结果的检验
　　因为逆向仿真还是一种求解问题的新方法,它所得到的结果(结构设计方案)是否合理、正确, 将直接影响到该技术的可行性和有效性.因此,需要对其结果采用适当的方法进行检验.
　　采用传统的仿真方法来对逆向仿真输出的结果进行分析和验证,是实现对逆向仿真方法进行 验证的一种选择.通过对初步设计好结构的系统进行传统的仿真,可以测出在该结构之上,系 统运行的状况如何,有关的系统性能指标是否与既定的标准或要求相符,如有需要还可在此基 础上对系统结构作进一步的调整(这在传统的正向仿真应用中是经常可以看到的).传统的正 向仿真作为一种成熟的技术方法,它对逆向仿真技术的验证必然具有较强的说服力.
　　我们对单急救站系统逆向仿真的输出结果即救护车的配置数为11（辆）作为服务台数目，建 立了该系统的正向仿真模型(该模型的建立较典型、简单,这里不再作具体介绍),多次运行该 模型,通过对其输出的系统性能参数之一即得到响应的时间超过10分钟的顾客占总顾客数的 比例RE10经过统计分析,发现该比例为零,说明由逆向仿真得到的结构设计方案已满足 本系统的服务质量要求，使所有顾客都能在10分钟之内得到该救护站的服务.
　　但是,仅仅这样的检验结果并不能表明该方案就是最优的设计方案.因为还存在一个显然的问 题该设计方案是否是设计要求下最经济的方案？很明显,如果该方案与设计要 求下最经济的方案相差较大,如最后验明只要有6辆救护车就可满足服务要求,则所得到的11 辆救护车的设计方案就可以认为毫无意义.为此,我们将急救站应配置的救护车数量向下调整 为10,重新运行该系统的正向仿真模型,对该条件下的输出参数RE10进行统计分析,发现该比 例值明显大于零,但不大于十万分之一.但当Na为9时,则响应时间超过10分钟的比例就大大提 高.这个结论充分证明了由逆向仿真设计出的结构方案是满足设计要求的条件下最经济的方 案.以上检验过程说明了利用逆向仿真对本系统进行服务台结构设计的可行性和高效性,一定 程度上也说明了逆向仿真是一种方便、快捷、有效的设计工具.
4　结束语
　　传统的离散事件仿真技术是研究、分析各类排队系统性能的有效方法．本文提出的逆向仿真 技术则是解决其逆问题即排队系统设计的有效方法．我们以单救护站系统为例，对逆向仿真 建模、求解方法进行了研究与实践，并作了验证．在计算机上构建仿真模型，从而实现对真 实系统的模拟，这一思想已被非常广泛地应用于各个领域．构建逆向仿真模型，逆向模拟系 统的运行，求解逆向问题，这一思想也将会用于各类仿真技术与仿真应用领域．文章中的工作仅仅是逆向仿真研究的初步工作,我们还对多救护站及站间互相支援的整个救 护系统进行了逆向仿真，也对另一类到达可控、以输出求输入的加工系统进行了研究．但是 ，对逆向仿真这一新技术无论在理论上以及实际应用中都需要做更多、更深入的研究工作．


作者简介：宣慧玉,女,55岁,教授．研究领域为系统仿真,人工智能.
　　　　　王丽娟,女,24岁,硕士. 研究领域为系统仿真,管理信息系统.
作者单位：西安交通大学管理学院　西安　710049
参考文献
1　Jerry Banks, John Carson 著,侯炳辉,张金水译,离散事件系统模拟,清华 大学出版社,1988
2　鲍居武. 仿真数据分析方法及其应用,学苑出版社,1993
3　Zhiwei Zhu, Mark A.Mcnew, Jim Lee. Modeling Time_Varied Arrival Rates: An Ap plication Issue in Queuing Systems. Simulation, 1994,62(4):146～154
收稿日期:1997-08-12
