A Siphon-Based Deadlock Prevention Strategy for S³PR

Abstract

Iterative deadlock prevention strategies based on siphons have drawn increasing attention. For iterative strategies, selecting which siphon to control at each iteration has an influence on the final supervisor in structural complexity, computational complexity, and behavioral permissiveness. In this paper, we define two kinds of emptiable siphons and provide two modified mixed-integer programming (MIP) formulations to compute such siphons. On the basis of them, a three-stage iterative deadlock prevention policy that specifies the siphon control order is proposed. The experimental results show that a supervisor with a simpler structure, higher behavioral permissiveness, and lower computational complexity can be obtained by the proposed strategy since neither the exhaustive siphon enumeration nor the reachability analysis is required.

Keywords

• Deadlock prevention
• discrete event systems
• mixed integer programming
• Petri nets