基于Petri网的复杂空竭休假排队系统的性能评价

第３Ｏ卷第４期　２０１２年７月　应用科学学报　ＪＯＵＲＮＡＬ　ＯＦ　ＡＰＰＬＩＥＤ　ＳＣＩＥＮＣＥＳ＿——Ｅｌｅｃｔｒｏｎｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｖｌ０１．３０　Ｎｏ．４　Ｊｕ１．２０１２　

ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．０２５５—８２９７．２０１２．０４．００９　

基于Ｐｅｔｒｉ网的复杂空竭休假排队系统的性能评价　

方　欢　，　陆　阳　，ｖ，　葛方振　，　黄镇谨　

１．合肥工业大学计算机与信息学院，合肥２３０００９　２．安徽理工大学理学院，安徽淮南２３２００１　３．安徽省矿山物联网与安全监控技术重点实验室，合肥２３００８８　

摘要：针对复杂空竭排队系统难以得到性能指标解析解的问题，提出基于Ｐｅｔｒｉ网模拟的近似解方法．通　过ＣＰＮ　Ｔｏｏｌｓ建立４种休假策略下排队系统的Ｐｅｔｒｉ网模型，在定义排队系统的性能指标数学期望公式的基础　上，使用Ｄａｔａ　Ｃｏｌｌｅｃｔｏｒ采集模型模拟的动态数据，得到相关的性能指标结果和期望收益．仿真结果表明这种基　于Ｐｅｔｒｉ网模型的近似求解方法是有效的，建立的模型和基于模型的性能分析方法具有可扩展性、复用性和界面友　好性．　关键词：复杂排队系统；空竭休假服务；Ｐｅｔｒｉ网；休假策略；近似解　中图分类号：ＴＰ３９９　文章编号：０２５５—８２９７（２０１２）０４．０３７９—０８　

Ｐｅｒｆｏｒｍａｎｃｅ　Ｅｖａｌｕａｔｉｏｎ　ｆｏｒ　Ｃｏｍｐｌｅｘ　Ｑｕｅｕｅｉｎｇ　Ｓｙｓｔｅｍ　ｕｎｄｅｒ　

Ｅｘｈａｕｓｔｉｖｅ—Ｓｅｒｖｉｃｅ　Ｐｏｌｉｃｉｅｓ　Ｂａｓｅｄ　ｏｎ　Ｐｅｔｒｉ　Ｎｅｔｓ　

ＦＡＮＧ　Ｈｕａｎ　，一，ＬＵ　Ｙａｎｇ　，ｖ，ＧＥ　Ｆａｎｇ—ｚｈｅｎ　，ＨＵＡＮＧ　Ｚｈｅｎ－ｊｉｎ　ｊ．Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ，Ｈｅ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈｅｆｅｉ　２３０００９，Ｃｈｉｎａ　２．Ｃｏｌｌｅｇｅ　ｏ｛Ｓｃｉｅｎｃｅｓ，Ａｎｈｕｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏ／Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ｝Ｈｕａｉｎａｎ　２３２００１｝Ａｎｈｕｉ　Ｐｒｏｖｉｎｃｅ，Ｃｈｉｎａ　３．Ｔｈｅ　Ａｎｈｕｉ　Ｐｒｏｖｉｎｃｉａｌ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆＭｉｎｅ　ＩｏＴ　ａｎｄ　Ｍｉｎｅ　Ｓａｆｅｔｙ　Ｓｕｐｅｒｖｉｓｏｒｙ　Ｃｏｎｔｒｏｌ，Ｈｅｆｅｉ　２３００８８，Ｃｈｉｎａ　

Ａｂｓｔｒａｃｔ：Ｓｉｎｃｅ　ｉｔ　ｉｓ　ｄｉｆｆｉｃｕｌｔ　ｔｏ　ｏｂｔａｉｎ　ａｎａｌｙｔｉｃａｌ　ｓｏｌｕｔｉｏｎｓ　ｏｆ　ｐｅｒｆｏｒｍａｎｃｅ　ｉｎｄｉｃｅｓ　ｆｏｒ　ｃｏｍｐｌｅｘ　ｑｕｅｕｅｉｎｇ　ｓｙｓｔｅｍｓ，ａ　ｍｅｔｈｏｄ　ｆｏｒ　ｆｉｎｄｉｎｇ　ａｐｐｒｏｘｉｍａｔｅ　ｓｏｌｕｔｉｏｎｓ　ｉｓ　ｐｒｅｓｅｎｔｅｄ　ｂａｓｅｄ　ｏｎ　Ｐｅｔｒｉ　ｎｅｔ．Ｗｉｔｈ　ｔｈｅ　ＣＰＮ　ｔｏｏｌｓ，ａ　

Ｐｅｔｒｉ　ｎｅｔ　ｍｏｄｅｌ　ｉｓ　ｃｏｎｓｔｒｕｃｔｅｄ　ｆｏｒ　ｑｕｅｕｅｉｎｇ　ｓｙｓｔｅｍ　ｕｎｄｅｒ　ｆｏｕｒ　ｖａｃａｔｉｏｎ　ｐｏｌｉｃｉｅｓ．Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｍａｔｈｅｍａｔｉｃａｌ　ｆｏｒｍｕｌａ　ｆｏｒ　ｐｅｒｆｏｒｍａｎｃｅ　ｉｎｄｉｃｅｓ，ｐｅｒｆｏｒｍａｎｃｅ　ｉｎｄｉｃｅｓ　ａｎｄ　ｅｘｐｅｃｔｅｄ　ｐｒｏｆｉｔｓ　ａｒｅ　ｃａｌｃｕｌａｔｅｄ　ｆｒｏｍ　ｔｈｅ　ｄｙｎａｍｉｃ　ｄａｔａ　ｃｏｌｌｅｃｔｅｄ　ｂｙ　Ｄａｔａ　Ｃｏｌｌｅｃｔｏｒ　ｉｎ　ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｍｏｄｅｌ　ｓｉｍｕｌａｔｉｏｎ　ｉｓ　ｅｆｆｅｃｔｉｖｅ，ｔｈｅ　ｍｏｄｅｌｓ　ａｎｄ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ａｎａｌｙｓｉｓ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｍｏｄｅｌｓ　ｈａｖｅ　ｆｌｅｘｉｂｌｅ　ｓｃａｌａｂｉｌｉｔｙ，　ｒｅｕｓａｂｉｌｉｔｙ　ａｎｄ　ａ　ｆｒｉｅｎｄｌｙ　ｉｎｔｅｒｆａｃｅ．　Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘ　ｑｕｅｕｅｉｎｇ　ｓｙｓｔｅｍ，ｅｘｈａｕｓｔｉｖｅ　ｓｅｒｖｉｃｅ，Ｐｅｔｒｉ　ｎｅｔｓ，ｖａｃａｔｉｏｎ　ｐｏｌｉｃｙ，ａｐｐｒｏｘｉｍａｔｅ　ｓｏｌｕｔｉｏｎ　

空竭休假排队系统是休假排队系统的一个重要研　

究分支．在这类系统的研究中，最受关注的是平均队　

长、平均等待时间及平均休假服务台数目的求解问题．　

目前，对空竭休假排队系统的研究大多考虑服务台的　

数目和休假策略两个方面．根据服务台的数目可分　

为单服务台［１－３】情形和多服务台［４－６］情形．对前者的研　

究，一般采用随机过程的稳态概率法求解理论，得到　队长、等待时间等性能指标的解析解；对后者的研究，　

则利用矩阵几何方法和拟生灭随机过程对队长、等待　

时间等指标进行随机分解，从而得到相关的性能评价　

公式．从休假策略来看，分别考虑单重休假［４］、休假　

时执行不同服务速率［５］及多重休假【６】等问题．　

可以看出，这些休假排队系统的理论分析和求解　

方法建立在随机分解和矩阵几何【２－７】等方法的基础上，　

收稿日期：２０１１—０４—２８：　修订日期：２０１１，０６—１３　基金项目：国家自然科学基金（Ｎｏ．６０８７３１９５，Ｎｏ．６１０７０２２０）；高等学校博士点基金（Ｎｏ．２００９０１１１１１０００２）￣ｉ０Ｊ　作者简介：方欢，讲师，博士生，研究方向：Ｐｅｔｒｉ￣理论及应用、离散事件动态系统的建模与分析、智能控制等，Ｅ－ｍａｉｌ　ｆａｎｇｈｕａｎＯ３０７＠１６３．ｃｏｍ；陆阳，教授，博导，研究方向：计算机控制、传感器网络、可靠性工程，Ｅ－ｍａｉｌ：ｌｕｙａｎｇ．ｈｆ＠１２６．ＣＯＩＴＩ

　３８０　应用科学学报　第３０卷　

通过求解稳态概率分布得到性能指标的解析解，但这　

种求解方法存在３个难点：１）求解过程均在系统具备　

稳态分布的条件下进行，如果排队系统不满足稳态分　

布的前提条件，这种数学求解方法就不再适用．２）求　

解结论可重用性差，当排队系统的约束条件改变时，　

Ｅ述已有的结论都不能直接应用．另外，无论是单服　

务台还是多服务台，一般都忽略服务台从服务状态转　

入休假状态的系统关闭时间（ｃｌｏｓｅｔｉｍｅ）和从休假状　态转入服务状态的系统启动时间ｆｓｔａｒｔｔｉｍｅ）［１，４４３］，或　

者仅考虑了系统的启动时间［２，７１．文献『３１虽然同时考　

虑了系统的关闭时间和系统的启动时间，但是仅适用　

于单服务台的排队情形．３）当排队系统的约束因素增　

加时，在使用矩阵随机分解法或者差分方程求解法的　过程中，概率矩阵Ｒ［２－７】的求解十分困难．　

另外，针对排队系统的软件模拟问题，普遍使用　

ＭＡＴＬＡＢ软件【８］对排队系统进行离散化，再分别考虑　

排队系统的到达部分和服务部分．然而这种软件模拟　

的方法并不能实现真正意义上的并发，且ＭＡＴＬＡＢ　

缺乏图形化的模拟，故模拟效果不佳．　

Ｐｅｔｒｉ网是一种系统的数学和图形的建模和分析　

工具，特别适用于复杂系统的设计和分析．用Ｐｅｔｒｉ网　

表示并发、互斥、同步显得直接，自然，精确；同　

时，Ｐｅｔｒｉ网坚实的数学基础可以为系统模型的设计　和分析提供一种有效的方法．将Ｐｅｔｒｉ网运用到排　

队系统分析的研究不多，目前仅有一些文献［９－１１１利　

用Ｐｅｔｒｉ网对具有实际应用背景的简单排队系统进行　

研究，并得到了一些性能指标的解析解．　

对于复杂的空竭休假排队系统Ｇ　／Ｇ／ｃ／￣，尚未　有性能指标解析解求解的研究，其中ＧＴ表示输入过　

程服从一般概率分布，Ｇ表示服务时间服从一般概率　

分布，Ｃ表示服务台数目（ｃ≥１），。。表示顾客源的数　目无穷大．排队系统ＧＩ／Ｃ／ｃ／￣具有广义队列的参数　

设置，同时服务台包含开启时间和关闭时间．因此，　

寻找一种简单通用的方法得到复杂空竭休假排队系　

统Ｇ１／Ｃ／ｃ／￣的性能指标是十分必要的，即使得不到　精确的解析解，求得的近似解也至少应具有较小的误　

差．本文针对具有一般参数设置以及包含系统开启和　

关闭时间的空竭休假排队系统ＧＴ／Ｇ／ｃ／￣列举了４种　

休假策略，借助Ｐｅｔｒｉ网模型的模拟仿真给出了相关　

性能指标近似解的求解方法．这种基于模型模拟的性　

能分析方法利用ＣＰＮ　Ｔｏｏｌｓ对休假排队系统的几种　

休假策略进行建模和分析，经过给定时间长度的系统　

模拟，通过Ｄａｔａ　Ｃｏｌｌｅｃｔｏｒ采集相关数据，得到排队　

系统的平均队长、平均等待时间、服务台的休假率和　

服务台的利用率等性能评价指标．为了说明所得近似　

值的精确度，与具有精确解的两种休假策略的排队系　统进行比较，从而了解近似解的准确程度．　

１　不同休假策略下的排队系统模型　

有关颜色Ｐｅｔｒｉ网的基本概念和ＣＰＮ　Ｔｏｏｌｓ的具　

体语法构成规则可参考文献【１２—１３】，这里为了模型理　

解的方便，仅对建模过程经常使用的记号或符号作简　

要说明．　

ＣＰＮ　Ｔｏｏｌｓ中时间类型颜色集的声明格式是在普　

通声明语句后加上ｔｉｍｅｄ，如ｃｏｌｓｅｔ　Ｓｅｒｖｅ＝ｗｉｔｈ　ｓｅｒｖｅｒ　

ｔｉｍｅｄ表示带时间戳的枚举型，ｃ＠ｔ表示为颜色Ｃ贴　

上一个时间戳ｔ，ｍ＠＋　表示为ｍ增加一个时间延　

迟ｉ．后引号（、）是颜色集的构造符号，ｉ、Ｃ表示ｉ个颜　

色Ｃ．一般地，单元型变量的默认值记为（），空列表记　

为ｎｎ或『１，ｅ：：２表示取队列２的队头元素，２】一２２表　

示连接两个字表为一个表，且Ｚ２的队头在　ｌ的队尾　

之后．　

图１给出了建立层次Ｐｅｔｒｉ网休假排队系统模型　

共用的类型和变量声明，其中Ｃ，ｌａｍｄａ，ｍｕ，ｔｈｅｔａｌ　

ｓｔａｒｔｉｍｅ，ｃｌｏｓｅｔｉｍｅ分别表示服务台的数目、控制顾　

客到达时间间隔、控制服务台平均服务时间、控制服　

务台平均休假时间、控制服务台由休假状态转为服务　

状态的系统开启时间和控制服务台由服务状态转为休　

假状态的关闭时间．　

Ｔ　ｃｏｌｅｓｔ　ＵＮＩＴ－－ｕｎｉｔ　ｔｉｍｅｄ；　ｔ　ｃｏｌｅｓｔ　ＩＮＴ＝ｉｎｔ；　Ｔ　ｖａｒｐｒｏｃｔｉｍｅ：ＩＮＴ：　Ｔ　ｖａｒｖａｃｔｉｍｅ：ＩＮＴ：　Ｔ　ｃｏｌｓｅｔ　ＵＵ＝ｗｊｔｈ　ｓｅｒｖ；　ｖ　ｃｏｌｓｅｔ　ＳＴＡＴＥ＝ｗｉｔｈ　ｎｏｒｍｌｖａｃ；　，ｃｏｌｓｅｔ　Ｓｅｒｖｅｒ＝ｐｒｏｄｕｃｔ　ＵＵ　ＳＴＡＴＥ　ｔｉｍｅｄ；　，ｖａｔ　ｓｅｒｖｅｒ：Ｓｅｒｖｅｒ；　，ｃｏｌｓｅｔ　ＪｏｂＴｙｐｅ－－ｗｉｔｈ　ＡＩＢ；　Ｔ　ｃｏｌｓｅｔ　Ｊｏｂ＝ｒｅｃｏｒｄ　ｊｏｂＴｙｐｅ：ＪｏｂＴｙｐｅ　ＡＴ：ＩＮＴ＝　ｒ　Ｖａｔｉｏｂ：Ｊｏｂ；　’ｃｏｌｓｅｔ　Ｊｏｂｓ＝ｌｉｓｔ　Ｊｏｂ；　Ｔ　ｖａｒｊｏｂｓ：Ｊｏｂｓ；　Ｔ　ｃｏｌｓｅｔ　ＳｅｒｖｅｒｘＪｏｂ＝ｐｒｏｄｕｃｔ　Ｓｅｒｖｅｒ＊Ｊｏｂ　ｔｉｍｅｄ；　，ｆｕｎ　ｅｘｐＴｉｍｅ（ｍｅａｎ：ｉｎｔ）＝　ｌｅｔ　ｖａｌ　ｒｅａｌＭｅａｎ＝Ｒｅａ１．ｆｒｏｍＩｎｔ　ｍｅａｎ　ｖａｌ　ｒｖ＝ｅｘｐｏｎｅｎｔｉａｌ（（１．０／ｒｅａｌＭｅａｎ））　１１＇／　ｆｌｏｏｒ（ｒｖ＋Ｏ．５、　ｅｎｄ；　Ｔ　ｆｕｎｉｎｔＴｉｍｅＯ＝　Ｉｎｔｌｎｆ．ｔｏｌｎｔ（ｔｉｍ　））；　，ｆｕｎｎｅｗＪｏｂ０　｛ｊｏｂＴｙｐｅ＝ＪｏｂＴｙｐｅ．ｒａｎ（），　ＡＴ　＝ｉｎｔＴｉｍｅ０｝　Ｔ　ｖａｌ　ｃ：５：　ｖａｌ　ｌａｍｄａ＝６６７；　ｖａ１　ｍｕ＝２０００；　ｖａ１　ｔｈｅｔａ＝５０００；　ｖａｌ　ｓｔａｒｔｔｉｍｅ＝ｌ２０；　ｖａｌ　ｃｌｏｓｅｔｉｍｅ＝ｌ００；　图１休假排队系统模型的颜色集声明