Computing Transition Priorities for Live Petri Nets

Abstract

In this paper, we propose an approach to implementation of the algorithm for computing transition priorities for live Petri nets. Priorities are a form of constraints which can be imposed to ensure liveness and boundedness of a Petri net model. These properties are highly desirable in analysis of different types of systems, ranging from business processes systems to embedded systems. The need for them is imposed by resource limitations of real-life systems. The algorithm for computing transition priorities considered in the study has exponential time complexity, since it is based on construction and traversal of the coverability graph. However, its performance may be sufficient for the majority of real-life cases. This paper covers the design considerations of the implementation, including the approach to handling the high time complexity of the algorithm and optimizations introduced in the original algorithm. We target parallelization as the main method of performance increase. While, for some steps of the algorithm the parallelization approach proves to be viable, for others its applicability is questioned. Analysis of different design decisions is provided in the text. On the basis of the actual implementation an application for computing priorities was developed. It can be used for further analysis of the algorithm applicability for real-life cases.