Requests network model for deadlock detection and avoidance in automated manufacturing systems

Abstract

A modern competitive environment requires rapid and effective responses to varying production demands with shorter life cycles. A feasible solution to cope with such unpredictable situations is to introduce an automated manufacturing system characterized by high flexibility, autonomy and cooperation. Much research has been done on negotiation-based scheduling and control under the distributed control architecture due to its operational flexibility and scalability. Despite many advantages, the probability of the system stalling at a deadlock state is high. Specifically, it is difficult to detect impending part flow deadlocks within the system. A system request network model is defined here to analyse various deadlock situations. Request cycles are then identified by a virtual part flow control mechanism. No request cycle in the system request network represents ‘no system deadlock’. For any request cycle, a deadlock analysis is performed. If any request cycle exists that represents either a part flow deadlock or an impending part flow deadlock, then the system will be deadlocked. The proposed model can analyse all types of impending part flow deadlocks. Furthermore, it is more efficient through the reduction of search space, is applicable to various configurations and is less restrictive in dynamic shop floor control.

Acknowledgements

This work was supported by Grant 2001-1-31500-1 from the Basic Research Program of the Korea Science & Engineering Foundation and the BK21 Projects in 2003. The authors would like to express their gratitude for the support.