Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies For S~3PR

This thesis focuses on deadlock control for S3PR nets. The main purpose of deadlock control is to find a maximally permissive control policy that is of polynomial complexity.A deadlock prevention policy that adds a new place whose control depth is one for every strict minimal siphon is proposed. The necessary and sufficient condition of deriving a liveness-enforcing supervisor for an S3PR net under this policy is obtained by analyzing its reachability graph. The condition is that the reachability graph of the S3PR has no obstinate markings that are determined on the basis of the fact that an internal transition of a siphon must be enabled in its empty-before marking. A net which has a liveness-enforcing supervisor is called a feasible net and its supervisor is maximally permissive. The concepts of empty-before markings, empty markings, key resources and neighboring resources are proposed for the first time in this paper.Even for a simple automated manufacturing system, the computation of a maximally permissive deadlock avoidance policy is in sense NP-hard. A maximally permissive deadlock avoidance policy for an S3PR net without a resource that has unit capacity is proposed. This policy is implemented by means of deciding whether a saturated recourse-transition circuit exists in a subsequent marking. Based on the relationship between the resource-transition circuits and the siphons, it is proved that this policy can be applied to feasible nets and it has polynomial complexity. The definition of a weakly-dependent S3PR net is then presented. Some special properties of this kind of nets are obtained because of its special structures. Finally, it is proved that this policy can also be applied to some weakly-dependent S3PR nets which satisfy certain conditions.