An Optimal Transition-Based Recovery Policy for Controlling Deadlock Within Flexible Manufacturing Systems Using Graph Technique

Abstract

Weighted Petri nets are common tools for modeling and validating discrete event systems involving resource allocation, such as flexible manufacturing systems (FMSs). A subclass of weighted Petri nets called a system of sequential systems with shared resources (S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> R) has the power for modeling complex FMSs where the execution of an operation may require multiple resource types and multiple units of some resource types. Deadlock resolution is a crucial issue for the operation of an FMS. A direct and efficient policy is developed in this paper for detecting deadlock markings by extracting a weighted resource flow graph (WRFG) from an S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> R and recovering them by synthesizing a recovery-transition-based controller. This study contributes to the field with five folds: (1) with S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> R, an efficient integrated policy is put forward for robust supervisor synthesis; (2) it enhances an algorithm for extracting the WRFG from an S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> R to reveal the shared resource competitions by different processes; (3) to detect partial deadlock markings, a technique for finding weighted circular wait graphs (WCWGs) in WRFG is presented; (4) with WCWGs, an algorithm is designed for the design of recovery-transition-based controller such that the resulting controlled system becomes deadlock-free; and (5) it presents a comprehensive analysis to demonstrate the proposed method by using the Integrated Net Analyzer (INA). With the proposed policy, it is not necessary to generate a reachability graph, making the method efficient. Finally, the performance of the proposed policy is illustrated by some commonly used examples.