Manufacturing Controller Design and Deadlock Avoidance Using a Matrix Model for Discrete Event Systems

The use of shared resources is a major problem occurring in discrete event (DE) systems, including manufacturing systems, computer systems, communication systems, highway/vehicle systems, and others. The issues involve problems of assignment of resources when the same resources are simultaneously requested by more than one job. Failure to suitably assign, or dispatch, resources in such situations can have serious deleterious effects on system performance, resulting in extreme cases in system deadlock [7]. Computer operating systems engineers and industrial engineers have used the concepts of circular wait (CW) and circular blocking in analysis of such phenomena [41, 24]. Various concepts in Petri nets (PN) are extremely useful for dealing with deadlock and a great deal of research has been done from the PN point of view (see references, especially [11, 14, 19]). The PN approaches are often based on the notion of the siphon, which indeed is called a “deadlock” in some works [26]. Unfortunately, it is known that many problems in scheduling, dispatching, and deadlock analysis are NP-hard [12], so that significant increases in computing power do not significantly improve computational ability. Neither PN nor CW approaches have addressed this issue.