General mixed integer programming-based liveness test for system of sequential systems with shared resources nets

For a system of sequential systems with shared resources (S⁴R), a typical class of Petri net models of flexible manufacturing systems (FMS), current deadly marked siphon (DMS) detection approaches based on mixed integer programming (MIP) cannot detect siphons that cause livelocks in systems. Thus a deadlock-free system cannot be further controlled. Moreover, most of these methods cannot obtain a minimal DMS directly. This study proposes the concept of extended DMS (EDMS) on the basis of max"-controllability condition of siphons. Accordingly, a more general MIP testing approach that can detect the minimal EDMS that cause deadlocks or livelocks in S⁴R is presented to lay foundations for further analysis and control. The authors conclude that an S⁴R is live if there is no feasible solution to this new MIP test. Compared with the existing methods, the proposed one is more general and powerful. Experimental studies are used to illustrate it.