A structured approach to deadlock detection, avoidance and resolution in flexible manufacturing systems

Abstract

Production scheduling models that determine part mix ratios and detailed schedules do not usually account for deadlocks that can be caused by part flow. Deadlocks must be prevented for operational control (especially in automated systems). The major thrust of this paper is in developing a structured model for deadlock detection, avoidance and resolution caused by part flow in manufacturing systems. A system status graph can be constructed for the parts currently in the system. Deadlock detection amounts to determining deadlocks in the system status graph. On the other hand, deadlock avoidance amounts to restricting parts movement so that deadlocks are completely avoided in the future. While deadlock detection is a one-step look ahead procedure, deadlock avoidance is a complete look ahead procedure. Deadlock resolution or recovery amounts to judiciously using a limited queue to recover from deadlocks. Deadlock detection and avoidance are absolutely crucial to uninterrupted operation of automated manufacturing systems. A model based in graph theory has been formulated to detect and avoid deadlocks in automated manufacturing systems.