Event Circuit Structures for Deadlock Avoidance in Flexible Manufacturing Systems

Deadlock avoidance of flexible manufacturing systems (FMSs) has received increasing attention from both academic and industrial communities. There have been a large number of different types of deadlock avoidance policies discussed in the literature. However, how to avoid deadlocks in an efficient way is still one of the major obstacles, especially for large systems. In this paper, we propose a new Petri net structure, i.e., event circuit structures (
$ESs$
), based technique to overcome this difficulty. First, we provide details of
$ESs$
and develop an algorithm to calculate
$ESs$
in the systems of sequential systems with shared resources (
$S^{4}Rs$
). Second, we analyze the liveness of
$S^{4}Rs$
using undermarked
$ESs$
. A necessary and sufficient condition between undermarked
$ESs$
and deadlocks of
$S^{4}Rs$
is established. Third, we describe how undermarked
$ESs$
can be applied to avoid deadlocks for
$S^{4}Rs$
. Only structure information is needed during this procedure, thereby improving the efficiency and convenience of deadlock avoidance. Several examples are presented to illustrate our approach. Note to Practitioners—Deadlock avoidance of flexible manufacturing systems (FMSs) is extremely important in real-world manufacturing scenarios. A large body of deadlock avoidance policies are presented in the existing literature. Through an effective deadlock avoidance policy, all deadlocks can be prevented from happening in advance, so as to avoid the reallocation of resources and the re-execution of deadlocked processes. This shortens the production cycle of systems and improves the utilization of resources. However, most existing approaches suffer from formidable computational difficulty since they necessarily rely on the whole reachability graph to avoid deadlocks. In this paper, we present event circuit structures (
$ESs$
) as a new technique for deadlock avoidance. We show that undermarked
$ESs$
can be used to avoid deadlocks by using only key structure information instead of complicated state information. Thus, it not only can greatly improve the efficiency of predicting deadlock markings for FMSs, but also reduce operating costs as much as possible while ensuring stable operation of FMSs.