engleski

Matrix Approach To Deadlock Avoidance Of Dispatching In Multi-Class Finite Buffer Reentrant Flow Lines

For finite-buffer manufacturing systems, deadlock is the major stability issue, not bounded-buffer stability. For a very general class of finite-buffer multi-class reentrant flow lines, necessary and sufficient conditions are given here for the absence of deadlock in terms of circular wait relations. The result is a multi-class last buffer first serve (LBFS) dispatching policy for finite buffer flow lines. The notion of so-called "critical siphons", as well as the novel notion of "critical traps" are introduced in this paper. Petri net (PN) techniques are used in the analysis. Since PN suffer from problems of computational complexity, it is shown that a judicious ordering of the place vector allows one to identify within the PN incidence matrix certain submatrices including the bill of materials (BOM) and resource requirements matrices. In terms of these submatrices, computationally efficient matrix techniques are given for implementing a multi-class dispatching policy that is guaranteed not only to avoid deadlock, but allows one to obtain efficient utilization of the resources in multi-class reentrant flow lines.

discrete event systems; deadlock avoidance; matrix approach

nije evidentirano