Analysis of deadlocks and circular waits using a matrix model for discrete event systems

A new matrix rule-based model of discrete-part discrete event systems is given that, together with the well-known Petri net marking transition equation, yields a complete matrix-based dynamical description of these systems. In this application to deadlock analysis, the exact relations between circular blockings and deadlocks are given for a large class of reentrant flow lines. Explicit matrix equations are given for online dynamic deadlock analysis in terms of circular blockings, and certain `critical siphons´ and `critical subsystems´. This allows efficient dispatching with deadlock avoidance using a generalized kanban scheme. For the class of flow lines considered, the existence of matrix formulae shows that deadlock analysis is not NP-complete, but of polynomial complexity