Comparing digraph and Petri net approaches to deadlock avoidance in FMS

Area of Science:

• Manufacturing Systems Engineering
• Operations Research
• Computer Science

Background:

• Flexible manufacturing systems (FMSs) are adaptable production facilities prone to deadlock situations.
• Deadlocks occur due to circular resource waits among jobs.
• Existing deadlock avoidance policies often rely on formal models like Petri nets (PNs) and digraphs.

Purpose of the Study:

• To demonstrate the strong connections between graph-theoretic and PN models for FMS deadlock control.
• To propose a unified framework integrating these two modeling approaches.
• To establish a direct correspondence between PN structural elements and digraph components related to deadlocks.

Main Methods:

• Utilizing Petri nets (PNs) to model FMS operations, capturing system details.
• Employing digraphs for a synthetic representation of job-resource interactions.
• Developing a unitary framework to link PN and digraph models for deadlock analysis.

Main Results:

• A direct correspondence is established between empty siphons in PNs and maximal-weight zero-outdegree strong components in digraphs for deadlock characterization.
• The study shows that deadlock avoidance policies derived from digraphs can be effectively implemented using controlled PNs.

Conclusions:

• A unified framework enhances the understanding and management of deadlocks in FMSs by integrating graph-theoretic and PN approaches.
• This integrated approach facilitates the implementation of robust deadlock avoidance strategies in flexible manufacturing systems.