基于Petri网求解网络最大流的并发仿真方法  

Concurrent Approach to the Max Flow of Network Based on Petri Net

作　　者：胡雄鹰[1,2] 胡斌[1] 张金隆[1] 刘天印[1] 蒋国银[1] 

机构地区：[1]华中科技大学管理学院,湖北武汉430074 [2]武汉工程大学管理学院,湖北武汉430074

出　　处：《武汉理工大学学报（信息与管理工程版）》2010年第1期27-30,共4页Journal of Wuhan University of Technology：Information & Management Engineering

基　　金：湖北省教育厅科学研究基金资助项目(Q20081502);湖北省企业竞争力研究中心资助项目(Qyjzl2007y0012)

摘　　要：通过将网络映射为Petri网形式的大量Petri网仿真实验得知,没有任何控制且并发运行的网络,其流量不能总是自行达到理论最大值,究其原因在于托肯在路径选择时随机经过了易拥堵结点与不拥堵结点。针对性地采取相应的网络控制策略,对网络从库所参数、弧参数和变迁参数3个方面进行单一或组合的设置,使得托肯优先经过不拥堵结点。运行调整后的网络,托肯沿网络从起点出发在各个局部并发地移动,遍历每一可能达到的结点,直至终点,网络流量达到其理论最大值,网络流实现全局最优。基于Petri网求解网络最大流的并发仿真方法为大规模网络最大流问题的分布式计算提供了一个新思路。With network mapped to the form of Petri net, Petri net simulation implements many times. The results show that when the network runs concurrently without any control, the flow in the network cannot always achieve the theoretical maximum value on its own. The reason of which is that when token chooses the path of running, it passes randomly between the easy- congestion node and the non - congestion node. The appropriate network control strategy was taken from the place parameters, arc parame- ters,transition parameters for single or combination of settings in order to give token priority of starting to pass the non - conges- tion node. When it ran the adjusted network, tokens transited along the network from the starting point of departure and concur- rently moved in all local area, and traversed each node that can be reached to the end point of network while the network reached its theoretical maximum network flow and achieved the global optimum. The concurrent approach to find the max flow of network based on Petri net provided a new idea for solving maximum flow of large - scale network by distributed computing simulation method.

关 键 词：网络 最大流 PETRI网 并发 

分 类 号：F224.33[经济管理—国民经济]