An Efficient Method of Deadlock Detection and Recovery for Flexible Manufacturing Systems by Resource Flow Graphs

Autor:	Yao Lu, YuFeng Chen, Zhiwu Li, Naiqi Wu
Rok vydání:	2022
Předmět:	For loop Loop (graph theory) Theoretical computer science Control and Systems Engineering Computer science Reachability Control flow graph Directed graph Electrical and Electronic Engineering Petri net Deadlock Deadlock prevention algorithms
Zdroj:	IEEE Transactions on Automation Science and Engineering. 19:1707-1718
ISSN:	1558-3783 1545-5955
Popis:	Deadlocks are a highly undesirable situation in flexible manufacturing systems (FMSs). This article presents a direct and novel method to detect such markings by constructing the resource flow graph of a Petri net that models an FMS and to recover such markings by adding a set of recovery transitions. First, an algorithm is developed to build a new kind of directed graph called the resource flow graph of a Petri net. Resource flow graphs can well represent the competition for shared resources by different processes. Second, based on the resource flow graph, loop graphs can be found. Furthermore, partial deadlock markings can be easily detected due to their relationship with loop graphs. Then, we propose an algorithm to design a set of recovery transitions for loop graphs that are enabled at partial deadlock markings. The proposed approach can detect partial deadlock markings without generating a complete reachability graph of a Petri net and the resulting net is deadlock-free with all reachable markings by adding the obtained recovery transitions. Finally, some widely used examples are provided to demonstrate the proposed approach.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::9ff3ca8c8709eace312152402fa32ae0 https://doi.org/10.1109/tase.2021.3114498 Zobrazit plný text záznamu