An Efficient Deadlock Recovery Policy For Flexible Manufacturing Systems Modeled With Petri Nets

Flexible manufacturing system(FMS)is a typical automated processing system to produce different kinds of raw parts by using a number of limited and shared resources such as machines,robots,and automatic guided vehicles.The competition for resources in different production processes may lead to deadlocks.Deadlocks are highly undesirable situations resulting in the whole system or a part of it blocked and some production processes are discontinuous.The long downtime and low utilization of resources are all profitless in a system.Therefore,deadlocks must be analyzed and controlled effectively in these systems.Petri nets are very suitable mathematical tools,especially for modeling and analyzing the behaviors of FMSs.In many previous studies,most strategies for analyzing and recovering deadlock problems are based on Petri net models.This thesis proposes a transition-based deadlock recovery policy,aiming to solve the deadlock problems in FMSs modeled with Petri nets.Different from the traditional deadlock control policies that add control places to a net model,this work employs some additional recovery transitions to recover all the deadlock markings to be legal ones.As a result,a live net system can be obtained with all reachable markings.In order to obtain less number of recovery transitions,the paper presents a method of iterative intersection to compute all recovery transitions.The main results are as follows:1.The main idea of the proposed control policy is to recover all deadlock markings to some legal ones by adding a set of recovery transitions to a Petri net model.According to the analysis of a reachability graph,all the reachable markings are obtained including the legal markings and deadlock markings.For a given net system,the number of deadlock markings is fixed and the number of legal markings is relatively large.In addition,as the complexity of the model structure increases,the number of reachable marking will increase exponentially.The purpose of deadlock control is to recover all deadlock markings in the system to some legal markings.Undoubtedly,the consideration of all legal markings increases the computational costs,which is particularly significant especially in some complex net models.Accordingly,the minimal covering set of legal markings is presented to reduce the number of considered legal markings.If all markings in the minimal covering set of legal markings can be reached,all legal markings can also be reached.Based on the vector covering method,the deadlock recovery policy is converted into recovering all deadlocks to some markings in the minimal covering set of legal markings instead of all legal markings.2.By using the previous analysis and the enable condition of transition firing,there exists a set of recovery transitions for each deadlock and any transition in the set can recover the corresponding deadlock marking to a legal one.Therefore,the deadlock markings have path to the initial marking.In order to obtain less additional transitions to recover all deadlocks,we provide an iterative intersection approach.First,a vector intersection approach is presented to compute a recovery transition to recover both two deadlock markings in a system.Then,an iterative method is developed to find a small number of recovery transitions to recover all deadlocks.At each iteration step,a recovery transition is obtained to recover more than one deadlock markings synchronously.Compared with the results from some extensive experimental studies,the presented deadlock recovery approach not only obtains the minimal number of recovery transitions but also further optimizes the time efficiency.Finally,several widely used examples are provided to demonstrate the presented approach.Experimental results show that the reported deadlock recovery technique is effective and efficient.