Strict Minimal Siphons Computation And Liveness-Enforcing Supervisor Synthesis For S~3PR

With the competition becoming more and more serious, it is an important trend for manufacturing enterprises to adopt flexible manufacturing systems to improve the production efficiency. The high resources sharing in flexible manufacturing systems can cause deadlocks if there are not effective control methods. Deadlocks will greatly reduce the production efficiency and cause enormous economic losses, and thus dealing efficiently with deadlock problem is necessary to reach higher productivity. At present, with the continuing developments of automation level, deadlock problem in flexible manufacturing systems has become a hot spot in academic and engineering circles.As a mathematical modeling tool, a Petri net can describe resource share, conflict, mutual exclusion, concurrency, and uncertainty. In addition, it can help researchers to find out the potential deadlocks and use relevant control policies to prevent them. Therefore, Petri nets are widely used in deadlock analysis and control in flexible manufacturing systems. Among so many classes of Petri nets, S3PR nets are the commonly used one. This paper focuses on improving the computational efficiency of strict minimal siphons (SMS), simplifying the structure and improving the behavior permissiveness of a liveness-enforcing supervisor for S3PR. Its new contributions are:1. For S3PR, an algorithm is proposed to extract the set of all minimal siphons from a maximal emptied siphon based on trees. It provides the simple, direct, and convenient graphical representation of the minimal siphons extraction process, which has not been seen in any prior research.2. So far, the resource circuits-based method is one of the most effective ways to compute SMS. In this paper, an algorithm is proposed to find the set of all resource circuits in S3PR and the concept of loop resource subsets is proposed to overcome the shortcomings of the resource circuits-based method. Moreover, an algorithm to compute the set of all loop resource subsets is proposed as well as sufficient and necessary conditions for loop resource subsets to generate SMS. Finally, a fast algorithm is proposed to compute the set of all SMS in S3PR based on loop resource subsets. The flexible manufacturing system example shows that the proposed method significantly outperforms some existing methods in computational efficiency.3. Structural complexity is a main parameter to evaluate the performance of a liveness-enforcing supervisor. In this paper, a sufficient condition is proposed under which there exists a liveness-enforcing supervisor for S3PR based on complementary places. On this foundation, an algorithm is proposed to design a liveness-enforcing supervisor for S3PR based on complementary places. First, the set of all SMS is computed from an infinite-capacity net. Next, the finite-capacity net, in which liveness can be enforced, is obtained by adding capacity function to the infinite-capacity net to control the SMS. Finally, complementary-place transformation is used to transform the finite-capacity net into an infinite-capacity net. The flexible manufacturing system example shows that the proposed method can obtain a structurally simpler supervisor and it also has certain improvement in behavior permissiveness.4. Behavior permissiveness is also an important parameter to evaluate the performance of a liveness-enforcing supervisor. In this paper, an algorithm is proposed to design a liveness-enforcing supervisor for S3PR based on elementary siphons and complementary places. First, the set of elementary siphons is computed from an infinite-capacity net. Next, capacity function is added to the infinite-capacity net to control the elementary siphons. Then, the finite-capacity net, in which liveness can be enforced, is obtained by decreasing the value of capacity function. Finally, complementary-place transformation is used to transform the finite-capacity net into an infinite-capacity net. Some flexible manufacturing system examples show that the proposed method significantly outperforms some existing methods in structural complexity and provide approximate optimal behavior permissiveness.Finally, conclusions and future work on SMS computation and design of a liveness-enforcing supervisor are illustrated.