第二节介绍了随机时间Petri网及其激发策略,特别是多重使能性。
第三部分讨论了所提出的仿真引擎,包括其架构和算法。
第四部分介绍了一个应用模拟工具在一个紧急医疗系统资源需求分析的案例研究。
最后一部分对全文进行总结。
1.顺序执行
事件序列可以用如图1所示的Petri网结构建模,其中转换用步长顺序连接到彼此。当位置p1获得一个令牌时,三个转换将从转换t1开始一个接一个地触发。
2.并发执行
在图2中,t1、t2、t3是三个平行跃迁。t0触发后,p0中的一个令牌被删除,p1、p2、p3各添加一个令牌,因此所有t1、t2、t3都被启用并可以独立触发。
3.竞争
在图3中,所有的t1、t2和t3都被启用。然而,它们在p0中竞争同一个资源(token)。当一个过渡启动时,其他两个过渡将被禁用。不过每个过渡都可以被选择启动,这就是Petri网的可解性。当过渡与随机发射时间相关联时,以最小发射时间采样的过渡将被选择发射。
4.同步
图4中,t3模型同步。只有当p3和p4至少有一个令牌时,才启用T3。
在单服务器的情况下,每个转换只能有一个实例,因此它一次只能执行一个操作。图5说明了单服务器处理三个输入的情况。p1中有三个令牌。假设t1是单个服务器。然后t1需要发射三次,每次都需要指定的发射时间才能完成。也就是说,如果触发时间是一个固定值,比如3个时间单元,并且转换在时间0开始触发,那么第一个标记在3个时间单元内从p1移动到p2。第二个令牌和第三个令牌分别在6个时间单位和9个时间单位内移动到p2。
在多服务器的情况下,每个转换代表k个服务器,因此它可以一次执行k个操作。例如,假设图6中的过渡t1是一个三重服务器,并且在初始标记的时间为0时p1中有三个令牌。T1可以同时发射并消耗这三个令牌。也就是说,所有这三个令牌都将以三个时间单位从p1移动到p2。这里的三重服务器转换相当于三个单服务器转换。
1.仿真引擎架构
1)模拟引擎。该系统是一个基于随机时间Petri网的状态转换系统,支持非马尔可夫状态转换触发时间、race和preselection状态转换触发策略以及单服务器和多服务器状态转换。
2)STPN编辑器。它是一种图形化的工具,供用户构建STPN模型。
3)一个STPN银行。它以JSON文件格式存储使用该工具构建的所有STPN模型。
4)资源配置器。它手动或自动地指定和调整由STPN建模的服务系统的资源分配。
5)算法。它为仿真引擎提供了不同的算法。每种算法代表一种仿真策略。目前有单服务器和多服务器两种情况。
6)事件数据。它存储事件名称和所有时间参数。事件数据可以独立于STPN结构进行编辑。
7)结果。模拟结果存储在MS Excel电子表格中。
2.类图
多服务器STPN模型仿真引擎的总体设计如图8中的类图所示。下面解释了10个主要的类及其功能。
PNModel类用于导入STPN模型的外部文件,并将模型存储在内部数据结构中。
PNElement类定义了Petri网模型中的元素。Arc、Place和Transition继承自PNElement类的公共属性和方法。在Arc类中,我们定义了两种类型的圆弧,一种是从位置到转换,另一种是从转换到位置。在Transition类中,我们为每个转换定义一个优先级队列,以节省其实例的触发时间。在Place类中,我们为每个位置设置了标记的数量。
ResourceMgr类指定资源类型和资源数量。
RandomNumGenerator类从不同的随机分布中生成随机数。对于指数分布,我们只需要平均时间就可以得到一个随机数。对于均匀分布,我们需要两个数字分别定义最小值和最大值r。
TranFiringTimeMgr管理每个转换的优先级队列中的转换触发时间。
Petrinet类用于计算Simulation类的可触发转换列表。在Petrinet类中,我们定义了一个全局数组列表来保存可触发的转换并在Simulation类中更新它们。
Simulation类管理STPN模型的操作,并保存仿真结果。
3.实现多服务器
像在任何典型的离散事件模拟系统中一样,我们在我们的工具中使用一个全局时钟来记录时间。时钟时间随模拟步骤的增加而增加。仿真步长可以是固定的也可以是动态的。在固定步长情况下,步长设置为1。在动态步长情况下,步长由当前时钟时间和下一个过渡的绝对触发时间之间的差距决定。我们实现了两种选择。
当启用转换时,从其分布函数中采样转换触发时间。如果它是一个单一的服务器,那么在模拟的每一步,全局时钟增加和过渡的持续发射时间减少的模拟步骤的长度。当触发时间减少到0时,将触发转换并更改令牌分布。当然,并不是所有启用的转换都会触发。如果已启用的转换在其触发时间减少到0之前被禁用,则该转换无法触发。这是由竞赛点火政策决定的。如果在转换触发之前,更多的令牌到达其输入位置,这些令牌足够使转换启用两倍或三倍,那么转换的触发行为将不会发生改变。在发射过渡器之后,它将在新的标记处重新采样。
如果新启用的转换是一个多服务器的转换,我们将遵循以下三个步骤来处理它的触发:
阶段1:在启用转换时,将令牌从传入的位置删除。对转换触发时间进行采样并插入到队列中。
阶段2:当全局时钟滴答作响时,发射时间减少,直到它下降到0,
阶段3:将令牌添加到输出位置。
如果在阶段1之后和阶段3之前,再次启用转换,我们将遵循相同的三相过程来处理新实例。也就是说,我们将维护一个队列,用于存储每个多服务器转换实例的剩余触发时间。
4.绩效评估
图9显示了典型服务系统的外部视图。过渡A是一个源过渡,它模拟客户的到来,或者一般来说,服务请求。在i处的标记代表一个客户。请注意,A和i构成一个自循环,模拟客户的连续到达。汇聚位置o的代币数量计算了系统所服务的顾客数量。图10模拟了系统的单次执行。D1, D2, …, Dk是水槽转换,它们模拟客户离开服务系统的不同方式。STPN盒子模拟了服务工作流程。为了验证正确性(没有死锁,没有悬空过渡等),我们可以在图10的模型中添加一个过渡,并将o连接到它作为输入,同时将i连接到它作为输出,然后检查新的STPN是否处理所有我们想要的属性。