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

Abstract

bFor finite-buffer manufacturing systems, the major stability issue is deadlock, rather than bounded-buffer-length stability. The paper introduces the concept of system deadlock, defined rigorously in Petri net terms, and 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 necessary 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 the percent utilization of resources. The result is a generalized kanban dispatching strategy, which is more general than the standard multi-class last buffer first serve (LBFS) dispatching strategies for finite buffer flowlines 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.