An algorithm to evaluate implementation cost for liveness-enforcing supervisors designed by deadlock prevention policy

Abstract

Deadlock prevention policy is widely used to design the liveness-enforcing supervisors because of its advantage that deadlocks are considered and solved in design and planning stages for flexible manufacturing systems modeled with Petri nets. However, how to evaluate the implementation cost of these liveness-enforcing supervisors is not done in the existing literature. This article proposes an algorithm to evaluate the implementation cost performance of different liveness-enforcing supervisors designed by deadlock prevention policy. By designing a multiple objective linear programming problem associated with two parameters (denoted as f 1 and f 2 ) to characterize the corresponding implementation costs for the added control places and the related input and out transitions and control arcs, the proposed algorithm first obtains the variable regions of f 1 and f 2 And then a satisfactory level coefficient (denoted as λ ) concentrating on the optimal compromise solutions of f 1 and f 2 (denoted as f 1 * and f 2 * ) is solved by a linear programming problem. As a result, the implementation cost performance of the corresponding liveness-enforcing supervisor can be indicated conveniently on the basis of the values of λ , f 1 * , and f 2 * . The practical potential of the proposed algorithm is demonstrated via a theoretical analysis and several widely used examples from the existing literature.