| A system deadlock is a situation in which machines in a manufacturing system have been allocated various parts, and because of a conflict in part flow direction, continuous part flow is inhibited when using a direct address type of material handling device such as a robot or a transfer cart. In the implementation of flexible manufacturing systems, deadlocking is usually avoided by installing a large amount of in-process storage, which may sacrifice the system performance. Deadlock avoidance is classified as an NP-complete problem; therefore, a solution procedure that relies on exhaustive enumeration of all deameration of all deadlock possibilities is inefficient for control of a manufacturing system in terms of computation time and memory.;In this research, an analytical detection procedure for system deadlocks is developed. The detection procedure applies a string multiplication algorithm to specifically and exclusively identify closed circuits in a graph which represents the part flow in a manufacturing system. A closed circuit in the graph indicates a deadlock possibility. Manufacturing control is maintained using a detection and recovery method which is suitable for manufacturing systems with a special in-process storage station. Once identified, a deadlock can be corrected by sending an interlocked part to the special buffer. In a manufacturing system without any in-process storage, deadlock becomes unrecoverable, and must be avoided. An avoidance control method, which uses the detection procedure to identify deadlock possibilities in advance, is also illustrated to control a manufacturing system so that deadlocking is prevented. A simulation study demonstrates that the detection and recovery and avoidance methods are appropriate control strategies for manufacturing systems conducting short period machining process like stamping. On the contrary, in a manufacturing system that runs metal removal operations which require long machining time (cutting or grinding), installing a large amount of in-process storage to avoid deadlocking remains a proper control policy. The two methods developed in this dissertation provide additional control alternatives for the design of flexible manufacturing systems. |
