Software Development And Research On Minimal Siphons For Ordinary Petri Net And S~3PR Net

Flexible manufacture system is a typical resource allocation system,which consists of a series of public resources and a number of sequential concurrent workflows.It is easy to happen deadlock if public resources are lack of effective control and management.Deadlock will result in workflow stagnation,performance degradation of the system,economic loss,and even other serious consequences.Deadlock detection and prevention in flexible manufacture system is very important and has become a research hotspot.Petri net is a kind of modeling and analysis tool for discrete event system,which is widely used in the research of modeling,performance analysis and deadlock control of flexible manufacture system.Siphon is closely related to the phenomenon of deadlock.After modeling the flexible manufacture system with Petri net,deadlock means that there are some siphons to be emptied.The existing deadlock prevention strategies of flexible manufacture system usually add monitors on siphons to keep them never be emptied.These algorithms need to calculate the minimal siphons first.In theory,the number of the siphons grows exponentially with increase of the Petri net scale,a lot of deadlock prevention strategies can not be applied to large scale systems due to the computational efficiency of the minimal siphons.Many scholars have devoted themselves to the research of minimal siphons,and put forward a lot of algorithms to calculate minimal siphons,but the computational efficiency is still not high enough.Cordone et al proposed a enumeration algorithm for minimal siphons based on problem decomposition,which is widely used and is one of the algorithms with high computational efficiency.In this paper,we propose an improved algorithm based on local partitioning minimal siphon enumeration algorithm.S3PR net is a subclass of Petri net,it is also widely used in the research of modeling and deadlock control of flexible manufacture system.This paper presents an algorithm for computing the strict minimal siphons in S3PR net for large scale systems.Main tasks are as follow:1.According to the local decomposition method of Cordone and the improved GPMSE algorithm proposed by Wang,the improved LPMSE algorithm is designed by using new measures in this paper.2.This paper proposes an algorithm for computing the strict minimal siphons in S3PR net based on problem decomposition.This part includes the specific method of problem decomposition,this method is used to calculate all the ideal resource subnets,and then find all the strict minimal siphons by ideal resource subnets.3.The software for calculating minimal siphons is developed based on the algorithms proposed in this paper,we will introduce the software development environment and development tools,then make a detailed description of the main data structures and the design of the classes.