Deadlock avoidance for free choice Multi-Reentrant Flow Lines: Critical Siphons & Critical Subsystems

This paper has two contributions. First, we present an analysis of deadlock avoidance for a generalized case of multi reentrant flow line systems (MRF) called the free choice multi reentrant flow line systems (FMRF). In FMRF, some tasks have multiple resource choices; hence routing decisions have to be made and current results in deadlock avoidance do not hold. This analysis is based on the so-called circular waits (CW) of the resources in the system. For FMRF, the well known notions of critical siphons and critical subsystems must be generalized and we redefine these objects for such systems. Our second contribution provides a matrix formulation that efficiently computes the objects required for deadlock avoidance. A MAXWIP dispatching policy is formulated for deadlock avoidance in FMRF systems. According to this policy, deadlock in FMRF is avoided by limiting the work in progress (WIP) in the critical subsystems of each CW. A main contribution of this paper is a matrix formulation for direct and efficient computation of Petri net objects.