An MIP-Based Deadlock Prevention Policy for Siphon Control

Abstract

Siphon plays essential role in the occurrence of deadlocks for the flexible manufacturing system (FMS) modeled by Petri nets. For siphon-based a deadlock a prevention a strategies, the selection of a siphon to be controlled in each iteration may affect the number of permissive behaviors and the a structural a complexity of a the controlled a system. For aaa class of Petri nets called systems of sequential systems with shared resources (S4PR), an iterative policy based on mixed integer programming (MIP) is introduced in this paper. In each iteration, a minimal bad siphon (MBS) with minimum number of places and resources is derived to control. Some experiments show that the resultant system obtained by the proposed strategy has simpler structure and more permissive behaviors than those obtained from existing methods. Meanwhile, the computational complexity of the policy is low because the complete state and siphon enumeration are avoided.

Keywords

• Deadlock
• siphon
• iterative
• MIP