Matrix approach to deadlock-free dispatching in multi-class finite buffer flowlines

bFor finite-buffer manufacturing systems, the major stability issue is "dea dlock," rather than "bounded-buffer-length stability." The paper introduces the concept of "system deadlock," defined rigorously in Petri net terms, a nd system operation with uninterrupted part-flow is characterized in terms of the absence of this condition. Fur a large class of finite-buffer multi- class re-entrant flowline systems, an analysis of "circular waits" yields n ecessary and sufficient conditions for the occurrence of "system deadlock." This allows the formulation of a maximally permissive one-step-look-ahead deadlock-avoidance control policy for dispatching jobs, while maximizing th e percent utilization of resources. The result is a generalized kanban disp atching strategy, which is more general than the standard multi-class last buffer first serve (LBFS) dispatching strategies for finite buffer flowline s that typically under-utilize the resources. The problem of computational complexity associated with Petri net (PN) applications is overcome by using certain sub-matrices of the PN incidence matrix. Computationally efficient matrix techniques are given for implementing the deadlock-free dispatching policy.