Deadlock avoidance for manufacturing multipart re-entrant flow lines using a matrix-based discrete event controller

Abstract

A deadlock avoidance supervisory controller for Discrete Event (DE) Systems is implemented. The DE controller uses a novel rule-based matrix dispatching formulation (US patent received). This matrix formulation makes it easy to write down the DE controller from standard manufacturing tools such as the bill of materials or the assembly tree. It is shown that the DE controller's matrix form equations plus the Petri Net (PN) marking transition equation provide a complete dynamical description of DE systems. We provide circular wait analysis (CW) for deadlock-free dispatching rules for Multipart Re-entrant Flow line (MRF) regular systems, and provide a regularity test for these systems in PN and matrix notations. We analyse the so-called critical siphons, and certain critical subsystems to develop a DE controller that guaranties deadlock-free dispatching by limiting the work-in-progress in the critical subsystems associated with each CW. This least-restrictive dispatching policy avoids deadlock. The deadlock-free dispatching rules are implemented by the DE controller on a three-robot, two-machine re-entrant flow line, the Intelligent Material Handling cell at the Automation and Robotics Research Institute of UTA. Technical information given includes the development of the deadlock-free controller in LabVIEW.