Full Text

Turn on search term navigation

Emad Abouel Nasr 1, 2 and Abdulaziz M. El-Tamimi 1 and Abdulrahman Al-Ahmari 1 and Husam Kaid 1

Academic Editor:Yan-Jun Liu

1, Industrial Engineering Department, College of Engineering, King Saud University, Riyadh 11421, Saudi Arabia
2, Mechanical Engineering Department, Helwan University, Cairo 11792, Egypt

Received 13 January 2015; Revised 26 June 2015; Accepted 3 August 2015; 16 September 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Effectively designing and operating an automated manufacturing system can be of assistance to manufacturers to adapt the variety in the market in order to maintain and confirm competitiveness. Different types of parts in AMS enter the system at discrete points of time and are produced concurrently; these parts have to share some common resources, such as robots, machine tools, buffers, automated guided vehicles, and fixtures. The deadlocks can occur in an AMS during its operation by shared resources competition, which are highly unwanted phenomena that often cause low use of some expensive and critical resources and long downtime and can lead to calamitous results in automated manufacturing systems. Therefore, it is required to develop a successful AMS control policy to prevent deadlocks occurrence in AMS.

There are several mathematical tools to solve deadlock problems in AMSs including automata, graph theory, and Petri nets. Recently, Petri nets have been known as one of the most robust mathematical tools for modelling, analyzing, and controlling deadlocks in resource allocation systems including AMS [1]. To overcome the deadlocks in AMS, there are methods which have been derived from a Petri net tool either to forbid the deadlock occurrences by preventing some necessary condition or to detect and resolve a deadlock when it occurs. In general, these methods can be classified into three strategies: deadlock detection and recovery, deadlock avoidance, and deadlock prevention [1, 2].

The researchers proposed three criteria for designing and evaluating a supervisor for a manufacturing system to be controlled. These criteria include behavioral permissiveness, which leads to increase in the resources utilization of system, structural complexity that leads to design supervisor with a few number of monitors to decrease the software and hardware costs, and computational complexity that means a deadlock control policy can be implemented in huge systems [1]. Therefore, the objectives of many researchers are to develop deadlock prevention policies which can provide liveness-enforcing supervisors with maximal permissiveness, a structural complexity, and computational complexity [1].

From previous studies, there are mainly two techniques of analysis for deadlock prevention in AMSs using Petri net: structural analysis [3, 4] and reachability graph analysis [5-7]. Oftentimes structural analysis is applied for structural objects of Petri nets, such as resource transition circuits and siphons. In this case, control steps are simple, and each empty minimal siphon requires a monitor to be added to prevent itself from being not emptied, but the disadvantages of this technique are the fact that the resulting controlled system can be suboptimal and linearly the number of control places is dependent on the size of a net [8].

The reachability graph analysis suffers from a state explosion problem because it requires listing of all or a part of reachable markings. The reachability graph of a Petri net has been classified into two zones: live zone (LZ) and deadlock zone (DZ). In DZ, there is first-met bad markings (FBMs) which are extracted from it; the FBMs are representing the very first entry from LZ to DZ. In this case, a control place is designed and added to forbid the FBM from being reached. This process requires iterations to forbid all FBMs and single out each FBM. The process is terminated if the resulting net is a live [9]. There are several methods and algorithms used for deadlocks prevention; some of them are siphon control methods, a theory of region, and iterative methods [4, 6, 9-11].

Most of the researchers have used structural analysis and reachability graph analysis to design deadlocks prevention policies for different scales of AMSs under three criteria that are maximal permissiveness, structural complexity, and computational complexity. The comparison between these policies has been done according to the three aforementioned criteria. It is taken for granted in the literature that a maximally permissive supervisor in the logical level usually leads to the better time performance in an AMS such as productivity and resource utilization, which looks intuitive, as an optimal supervisor will permit more permissive behavior. However, there is a shortage in the quantitative evaluation of time performance of these policies in terms of maximal permissiveness and productivity. Simulation is a powerful tool for performance analysis of complex manufacturing systems.

The contribution of this paper is using a simulation tool based on existing deadlock prevention policies and different types of Petri net models to explore whether a permissive liveness-enforcing Petri net supervisor can provide better time performance (maximal permissiveness).

The work of simulation is implemented in the following steps. (1) Assign the time to the controlled Petri net models, which leads to timed Petri nets. (2) Build the Petri net model using MATLAB software (Petri Net Toolbox (PN Toolbox)). (3) Run and simulate the model to obtain the system time performance. (4) Finally, the simulation results will be analyzed to determine which existing deadlock prevention policies are convenient for different types of manufacturing systems. Different control methods (siphon control methods and iterative methods) are used for deadlocks prevention. Moreover, this paper aims to evaluate the performance of the selected methods such as utilization of resources, plant throughput, the number of monitors, the number of arcs, and the number of reachable states. This paper focuses on the performance evaluation of automated manufacturing systems by using Petri nets under different deadlock prevention policies. The considered Petri net models belong to [figure omitted; refer to PDF] -nets [12] that are a general class of manufacturing-oriented net models in the literature. In an [figure omitted; refer to PDF] -net, there are a number of structural properties thanks to its definition [12].

Including this introductory section, the paper is organized as follows. Section 2 provides a literature review of previous researchers works related to deadlock prevention. The basics of Petri nets are discussed in Section 3. The deadlock prevention methods and policies are presented in Section 4. Sections 5 and 6 show the analysis of the selected methods for four different automated manufacturing systems. Finally, Section 7 presents the conclusion and future work.

2. Literature Review

Deadlock prevention policies have been widely achieved for AMS and led to a huge number of results [1, 11]. In this section, deadlock prevention strategies are reviewed by using Petri nets and developed based on different techniques such as structural analysis and reachability graph analysis.

2.1. Structural-Analysis Methods

Ezpeleta et al. [13] used a class of Petri nets, called System of Simple Sequential Processes with Resources (S³ PR) and proposed an algorithm for resource allocation in flexible manufacturing systems (FMSs). The proposed algorithm added new places to the net to impose certain restrictions that forbid the presence of unmarked siphons. The works of Huang et al. [14] and Huang et al. [15] present a new deadlock prevention policy for the class of Petri nets, where deadlocks are related to unmarked siphons. Two types of control places are added to the original model for flexible manufacturing system called ordinary control place and weighted control place to prevent siphons from being unmarked.

The study by Li and Zhou [11] presents a Petri net model which consists of 26 places, 20 transitions, and 18 strict minimal siphons. In [16], elementary siphons concept is introduced to design a liveness-enforcing Petri net supervisor for the same Petri net model, and six elementary siphons are obtained; therefore, only six monitors are added to control the 18 strict minimal siphons. Nevertheless, the proposed algorithm by Ezpeleta et al. [13] adds monitors for all 18 strict minimal siphons.

A new methodology is proposed by Huang [17] to synthesize supervisors for resource allocation in FMSs; the class of Petri net, namely, S³ PR, is considered, where deadlocks are related to unmarked minimal siphons; all minimal siphons should be controlled by adding control places. In this study, the number of control places is reduced by using the concept of the elementary siphon. Based on elementary siphons and [figure omitted; refer to PDF] -invariants concepts in Petri nets, a deadlock prevention algorithm is introduced by Li and Wei for a specific class of Petri nets which can properly model several FMSs [16], siphons in a Petri net model are classified into dependent and elementary siphons, and control places are added for all elementary siphons, so that the siphons are invariant-controlled. Therefore, the controllability of dependent siphons is guaranteed by adjusting the control requirements of its related elementary siphons. A novel deadlock prevention algorithm is presented by Chen et al. [1], and the concept of siphon extraction is used to compute unmarked siphons for the Petri net model. First, a siphon extraction algorithm obtains a maximal unmarked siphon, divides the places in it, and determines a necessary siphon from the divided places; this process is carried out for all unmarked siphons. Then, the proposed deadlock prevention algorithm designs a convenient monitor for each necessary siphon to be marked until the controlled Petri net model is a live.

Most of the deadlock control algorithms have been developed for reliable automated manufacturing systems (AMSs). Liu et al. [18] proposed a variety of deadlock control algorithms for AMSs with unreliable resources, monitors and recovery subnets are designed for strict minimal siphons (emptied siphon) and unreliable resources, respectively, and two types of arcs which are normal and inhibitor are used to connect monitors with recovery subnets. In order to obtain a supervisor with structural complexity, elementary siphons extracted from all strict minimal siphons are obviously controlled. The problems of structural complexity, behavioral permissiveness, and computational complexity are considered in the study of Wang et al. [19] to design liveness-enforcing supervisors for a class of Petri nets, namely, S³ PR, without [figure omitted; refer to PDF] -resources. They used two steps to obtain a supervisor for the model. In the first step, an algorithm is proposed to extract unmarked strict minimal siphons from a given unmarked siphon by using loop resource subsets. In the second step, a siphon-based deadlock prevention algorithm is introduced to provide a maximally permissive liveness-enforcing supervisor with small numbers and no weighted monitors.

2.2. Reachability Graph-Based Approaches

Viswanadham et al. [20] presented static resource allocation methods for eliminating deadlocks; in this study, a reachability graph of the Petri net (PN) model is used to reach static resource allocation method. A deadlock prevention algorithm is implemented for a small size manufacturing system consisting of a machine and an automated guided vehicle (AGV). The authors observed that the proposed algorithm can be applied effectively only for small size manufacturing systems. The forbidden state problem of Petri nets (PN) with uncontrollable transitions and liveness requirement is addressed by Ghaffari et al. [5]. An approach is presented to compute a maximally permissive Petri net controller that consists of two steps. In the first step, an ordinary Petri net is used to build the system model. In the second step, control places are designed and added to the original model by using a theory of regions method. The work of Uzam [7, 9] proposes and improves method based on a theory of regions to design an optimal Petri net supervisor. The size of the reachability graph of Petri net model is a major problem to apply the deadlock prevention policy to very large Petri net model. Therefore, they proposed a reduction algorithm to simplify very large Petri nets models in order to make necessary computation easily. Based on the theory of regions, Uzam and Zhou [6] developed an iterative deadlock prevention policy for FMS. In their study, the reachability graph of a Petri net model is divided into two parts: deadlock-free zone (live zone, LZ) and the deadlock zone (DZ). The live zone is developed since the maximal strongly connected component contains the initial marking. The deadlock zone contains markings from which the initial marking is unreachable. FBM is defined as a marking in the deadlock zone. The deadlocks can be eliminated by forbidding the firing of the enabled transitions at FBM. In their work, the presented approach has two problems. First, an optimal supervisor cannot be guaranteed in general even if such an optimal supervisor exists. Second, at each iteration full reachability graph computation is required to check whether the markings in the deadlock zone are reachable. This approach is easy to use and simple if the reachable graph of a system is small but cannot ensure the supervisor behavioral optimality. The redundant monitors in Petri net supervisor may exist when the supervisor is designed by an iterative siphon control approach. Therefore, Uzam et al. [21] introduced an approach to identify and eliminate the redundant monitors by computing the reachability graph of a controlled Petri net model. If the controlled Petri net model does not lose liveness when removing redundant monitors, then the redundant monitors can be eliminated from the supervisor. The reachability graph and liveness check are the major problems in designing liveness-enforcing supervisor. To overcome a full state enumeration, Li and Hu [22] proposed two approaches to eliminating control places from a Petri net supervisor. The first approach is based on the concept of implicit places [23, 24]. The implicity of a monitor is computed by solving a linear programming problem (LPP) that can be implemented in polynomial time. The second approach is extracted from the Mixed Integer Programming- (MIP-) based deadlock detection approach. If the optimal solution to an MIP problem does not lose optimality when removing control place, then the control place is implicit and may provide permissive behavior while liveness is guaranteed. Chen et al. [1] developed a novel and computationally effective approach to design optimal monitors and an iterative approach that can compute the reachability graph to get an optimal supervisor of the flexible manufacturing system, which is demonstrated by a set of control places. The vector covering approach is used to compute the minimal sets of FBMs and legal markings. Iteratively, an FBM is selected from the minimal set of FBMs, an integer linear programming problem (ILPP) is used to design a place invariant (PI) that prevents the FBM from being reached, and all minimal sets of legal markings are not forbidden. The process is terminated if all FBMs cannot be reached and the resulting net is a live. This study is improved in its computational efficiency in [25], and the objective function of the ILPP is maximizing the number of FBMs that are prohibited by the PI; in other words, a control place is designed such that as many FBMs as possible are forbidden and all minimal sets of legal markings are not prohibited. If the ILPP has no solution, it means that there is no maximally permissive Petri net supervisor for the Petri net model.

3. Basics of Petri Nets

Petri nets are a mathematical and graphical tool suitable for several systems. It is a major tool for studying and describing manufacturing system operations that are characterized as being asynchronous, concurrent, parallel, and distributed.

A Petri net or place/transition net can be defined as a four-tuple [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is a finite nonempty set of places, [figure omitted; refer to PDF] is a finite nonempty set of transitions, [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are disjoint, [figure omitted; refer to PDF] are called nodes with [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are represented by circle and bar, respectively. [figure omitted; refer to PDF] is called a flow relation or directed arcs of the net that can be represented by arcs with arrows from places (transitions) to transitions (places). [figure omitted; refer to PDF] is a mapping that assigns a weight to an arc: if [figure omitted; refer to PDF] ; otherwise, [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is called an ordinary net, if [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . Consider a node [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] is a preset of [figure omitted; refer to PDF] . Postset of [figure omitted; refer to PDF] is [figure omitted; refer to PDF] . A marking [figure omitted; refer to PDF] of [figure omitted; refer to PDF] is a mapping from [figure omitted; refer to PDF] . [figure omitted; refer to PDF] denotes the number of tokens in place [figure omitted; refer to PDF] . Usually, markings and vectors can be described using formal sum. Therefore, vector [figure omitted; refer to PDF] is denoted by [figure omitted; refer to PDF] . For example, a marking that puts two tokens in place [figure omitted; refer to PDF] , five tokens in place [figure omitted; refer to PDF] , and no tokens in other places in a net is denoted by [figure omitted; refer to PDF] . ( [figure omitted; refer to PDF] ) is a net system or marked net and is denoted by [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is an initial marking of [figure omitted; refer to PDF] . For a Petri net modeling [figure omitted; refer to PDF] represents the different raw parts that are to be synchronously processed in the system, and the state of resources, such as machines and robots. A net is self-loop free or pure if for all [figure omitted; refer to PDF] , [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Incidence matrix [ [figure omitted; refer to PDF] ] in a net [figure omitted; refer to PDF] is an integer matrix that consists of [figure omitted; refer to PDF] rows and [figure omitted; refer to PDF] columns with [figure omitted; refer to PDF] . The enabled rule for each [figure omitted; refer to PDF] at marking [figure omitted; refer to PDF] if [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . As a result, enabled rule is denoted by [figure omitted; refer to PDF] . When a transition [figure omitted; refer to PDF] fires, it removes [figure omitted; refer to PDF] tokens from each place [figure omitted; refer to PDF] and deposits [figure omitted; refer to PDF] tokens in each place [figure omitted; refer to PDF] . Therefore, it yields a new marking [figure omitted; refer to PDF] , denoted by [figure omitted; refer to PDF] [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is reachable from [figure omitted; refer to PDF] if there exists a fireable finite transition sequence [figure omitted; refer to PDF] , and markings [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] so that [figure omitted; refer to PDF] , which can be denoted by [figure omitted; refer to PDF] and satisfied the state equation [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is a mapping [figure omitted; refer to PDF] in [figure omitted; refer to PDF] to the number of occurrences of [figure omitted; refer to PDF] in [figure omitted; refer to PDF] , called a Parikh vector or a firing count vector. Obviously, [figure omitted; refer to PDF] is the set of all reachable markings of a net [figure omitted; refer to PDF] from initial marking [figure omitted; refer to PDF] and is denoted by [figure omitted; refer to PDF] . The reachable markings [figure omitted; refer to PDF] can be involved in the enumeration of all reachable markings of a net [figure omitted; refer to PDF] and graphically expressed by a reachability tree. The reachability tree is denoted by [figure omitted; refer to PDF] , which is a directed graph and consists of nodes and arcs, nodes are markings in the reachable markings [figure omitted; refer to PDF] , and arcs are labeled by the transitions of a net [figure omitted; refer to PDF] . For instance, an arc from [figure omitted; refer to PDF] to [figure omitted; refer to PDF] is labeled by [figure omitted; refer to PDF] if [figure omitted; refer to PDF] . A net [figure omitted; refer to PDF] with initial marking [figure omitted; refer to PDF] is to be [figure omitted; refer to PDF] -bounded if, for all [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . In other words, for each reachable marking " [figure omitted; refer to PDF] " from the initial marking [figure omitted; refer to PDF] , the number of tokens in each place " [figure omitted; refer to PDF] " never exceeds a finite number " [figure omitted; refer to PDF] " A net is called safe if all its places are safe, and the number of tokens in each place " [figure omitted; refer to PDF] " does not exceed one. In other words, a net is [figure omitted; refer to PDF] -safe if it is 1-bounded. A Petri net with [figure omitted; refer to PDF] is a live if all its transitions are a live at [figure omitted; refer to PDF] . A transition [figure omitted; refer to PDF] is a live if, for all [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , there is a firing sequence [figure omitted; refer to PDF] . A transition is dead at [figure omitted; refer to PDF] if [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . [figure omitted; refer to PDF] -vector (place vector) and [figure omitted; refer to PDF] -vector (transition vector) are column vectors. The former [figure omitted; refer to PDF] is catalogued by [figure omitted; refer to PDF] and called a [figure omitted; refer to PDF] -invariant or place invariant if [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . The latter [figure omitted; refer to PDF] is catalogued by [figure omitted; refer to PDF] and called a [figure omitted; refer to PDF] -invariant or transition invariant if [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the integers set. If each element of [figure omitted; refer to PDF] is nonnegative the [figure omitted; refer to PDF] -invariant [figure omitted; refer to PDF] is called a [figure omitted; refer to PDF] -semiflow or place semiflow. Suppose that [figure omitted; refer to PDF] is a place invariant of a Petri net with ( [figure omitted; refer to PDF] ) and [figure omitted; refer to PDF] is a reachable marking from the initial marking [figure omitted; refer to PDF] . Then, [figure omitted; refer to PDF] . Let [figure omitted; refer to PDF] be a support of place invariant [figure omitted; refer to PDF] and it can be classified into three parts. Firstly, [figure omitted; refer to PDF] is a positive support of place invariant [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Secondly, [figure omitted; refer to PDF] is a negative support of place invariant [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Finally, [figure omitted; refer to PDF] is a minimal place invariant if [figure omitted; refer to PDF] is not a superset of the support of any other one and its components are mutually prime. Let [figure omitted; refer to PDF] 's be the coefficients of place invariant [figure omitted; refer to PDF] if, for all [figure omitted; refer to PDF] , [figure omitted; refer to PDF] .

4. Deadlock Prevention Methods and Policies

4.1. Siphon Control Methods

This section presents two methods that are motivated by Ezpeleta et al. [13] and Li and Zhou [11]. These methods are called a strict minimal siphons control method and an elementary siphons control method, respectively.

4.1.1. Strict Minimal Siphons (SMSs) Control Method

A siphon in a Petri net is a set of places [figure omitted; refer to PDF] . The very important property of siphon is that, for a given marking, the siphon is unmarked.

Definition 1.

Let [figure omitted; refer to PDF] be a net. Any set [figure omitted; refer to PDF] , [figure omitted; refer to PDF] with [figure omitted; refer to PDF] is called a siphon. If a siphon does not properly contain another siphon is called a minimal siphon. A minimal siphon [figure omitted; refer to PDF] is called a strict if [figure omitted; refer to PDF] .

Siphons play a significant role in the liveness analysis of a Petri net, especially in ordinary ones. If a siphon [figure omitted; refer to PDF] in a net has no tokens, then no transitions in [figure omitted; refer to PDF] are enabled and all the transitions connected to [figure omitted; refer to PDF] cannot be fired; as a result, the transitions are dead leading to the loss of liveness of the Petri net. In [13], a monitor is added to each strict minimal siphon in order to achieve the liveness of the system. The proposed approach is simple and ensures a success. Nevertheless, it leads to a complex Petri net model than the originally model because the added places are equal to the strict minimal siphons in the target net model and the added arcs are larger than that of places added.

The SMS control based on complementary sets of siphons [figure omitted; refer to PDF] is used to design the control places. A complementary set of a siphon [figure omitted; refer to PDF] is a set of operation places which are the holders of the resources in [figure omitted; refer to PDF] but do not belong to [figure omitted; refer to PDF] . In addition, [figure omitted; refer to PDF] is the support of a place invariant, which means the operation places in [figure omitted; refer to PDF] will compete for the resources in [figure omitted; refer to PDF] with the operation places belonging to [figure omitted; refer to PDF] . [figure omitted; refer to PDF] will be unmarked when all tokens in [figure omitted; refer to PDF] flow into [figure omitted; refer to PDF] . The following notation will be used in the establishment of the control policy.

(1) [figure omitted; refer to PDF] denotes the set of strict minimal siphons which does not contain the support of any place semiflow (i.e., siphons that can be emptied).

(2) Given the fact that [figure omitted; refer to PDF] is a siphon we have [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the operation places and [figure omitted; refer to PDF] is the resource places. [figure omitted; refer to PDF] denotes the following set of state places: [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] , [figure omitted; refer to PDF] indicates the positive support of place invariant [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . For a given siphon [figure omitted; refer to PDF] , [figure omitted; refer to PDF] is the set of holders, corresponding to resources in [figure omitted; refer to PDF] that do not belong to [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is called [figure omitted; refer to PDF] 's complementary set.

(3) Given the fact that [figure omitted; refer to PDF] is a complementary set of [figure omitted; refer to PDF] , add a control place for [figure omitted; refer to PDF] and the initial marking of control place is [figure omitted; refer to PDF] .

Based on the concept of strict minimal siphon, the proposed deadlock prevention algorithm developed by Ezpeleta et al. [13] is stated as follows.

Algorithm 2 (SMS based policy).

Input . Petri net model ( [figure omitted; refer to PDF] ) of an AMS, where [figure omitted; refer to PDF] .

Step 1 . For a given Petri net ( [figure omitted; refer to PDF] ), compute all SMSs.

Step 2. For each siphon SMS, add a monitor [figure omitted; refer to PDF] such that

(i) the [figure omitted; refer to PDF] output arcs are connected to the source transitions leading to the sink transitions of [figure omitted; refer to PDF] and all arcs weights are ones;

(ii) the [figure omitted; refer to PDF] input arcs are connected from the stealing places of [figure omitted; refer to PDF] and all arcs weights are ones;

(iii): [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is an initial marking of a monitor.

Step 3 . Repeat Step 2 until all existing SMSs are covered.

Step 4 . Add all monitors into ( [figure omitted; refer to PDF] ) and the resulting net is denoted by ( [figure omitted; refer to PDF] ).

Step 5 . Output ( [figure omitted; refer to PDF] ).

Step 6 . End.

For instance, consider the AMS shown in Figure 1(a). Its Petri net model is shown in Figure 1(b). It consists of one robot R1 that can hold a part at a time, two machines M1 and M2, where each machine can process a part at a time, two loading buffers (I1 and I2), and unloading buffers (O1 and O2). Two parts types are considered in the system: PA and PB. PA moves to M1 and PB moves to M2. The robot R1 reaches the machine that finishes its operation first and grips and loads the part to the next machine 1 or machine 2. The Petri net model consists of 11 places and 8 transitions. The places have the following set partition: [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the input places, [figure omitted; refer to PDF] is the resources places, and [figure omitted; refer to PDF] is the operation places. It has 8 minimal siphons, 3 of which are strict minimal siphons and 20 reachable markings. The three SMSs are [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Table 1 shows the required monitors using Algorithm 2 for Figure 1(b). Figure 2 illustrates the controlled system of the Petri net model in Figure 1(b) after adding monitors by using Algorithm 2.

Table 1: Control places computations by Algorithm 2.

SMS	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
[figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] .	[figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] .	[figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] .	[figure omitted; refer to PDF] .	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2

[figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] .	[figure omitted; refer to PDF] , [figure omitted; refer to PDF] .	[figure omitted; refer to PDF] , [figure omitted; refer to PDF] .	[figure omitted; refer to PDF] .	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1

[figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] .	[figure omitted; refer to PDF] , [figure omitted; refer to PDF] .	[figure omitted; refer to PDF] , [figure omitted; refer to PDF] .	[figure omitted; refer to PDF] .	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1

Figure 1: (a) An AMS example and (b) Petri net model of an AMS.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

Figure 2: Controlled system of the Petri net in Figure 1(b) by Algorithm 2.

[figure omitted; refer to PDF]

4.1.2. Elementary Siphons Control Method

The strict minimal siphons (SMSs) are classified into elementary and dependent ones. Π is used to denote the set of strict minimal siphons while [figure omitted; refer to PDF] and [figure omitted; refer to PDF] denote the sets of elementary and dependent (redundant) ones, respectively. Otherwise, when a strict minimal one is mentioned, it can be called a siphon.

Definition 3.

Let an ordinary Petri net ( [figure omitted; refer to PDF] ) and [figure omitted; refer to PDF] is a siphon, [figure omitted; refer to PDF] . Place vector [figure omitted; refer to PDF] is said to be the characteristic place vector of [figure omitted; refer to PDF] if for all [figure omitted; refer to PDF] , [figure omitted; refer to PDF] ; otherwise, [figure omitted; refer to PDF] .

Definition 4.

Let [figure omitted; refer to PDF] be an ordinary Petri net with [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and we suppose that [figure omitted; refer to PDF] has [figure omitted; refer to PDF] SMS, [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] Let [figure omitted; refer to PDF] be the characteristic place (transition) vector of siphon [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . We define [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are said to be the characteristic place vector and transition vector matrices of the siphons of [figure omitted; refer to PDF] , respectively.

Proposition 5.

Let [figure omitted; refer to PDF] be an ordinary Petri net and let [figure omitted; refer to PDF] be the characteristic transition vector matrix of the siphons of it. The set of elementary siphons in [figure omitted; refer to PDF] can be defined as a rank of [figure omitted; refer to PDF] .

From Proposition 5, it can easily enumerate all elementary siphons in a Petri net system ( [figure omitted; refer to PDF] ) given all siphons. First, compute matrices [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Then independent linear vectors can be determined in [figure omitted; refer to PDF] . Finally, the siphons that correspond to these independent linear vectors are called the elementary siphons in the Petri net ( [figure omitted; refer to PDF] ). Li and Zhou [11] introduced some results and theorems as follows.

Theorem 6.

Let [figure omitted; refer to PDF] be a marked ordinary Petri net and [figure omitted; refer to PDF] be a siphon in [figure omitted; refer to PDF] . Monitor [figure omitted; refer to PDF] is added to [figure omitted; refer to PDF] , and the new net system can be denoted by [figure omitted; refer to PDF] , such that (a) [figure omitted; refer to PDF] is a place invariant of [figure omitted; refer to PDF] and (b) [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is said to be the control depth variable of siphon [figure omitted; refer to PDF] , which states the least number of tokens that siphon can hold. Evidently is greater than or equal to [figure omitted; refer to PDF] to fulfil purpose of control [figure omitted; refer to PDF] , and (c) for all [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the set of operation places of [figure omitted; refer to PDF] , such that [figure omitted; refer to PDF] can be called invariant-controlled.

Theorem 7.

Let [figure omitted; refer to PDF] be an ordinary Petri net and let [figure omitted; refer to PDF] be a generally dependent siphon on elementary siphons [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] that means [figure omitted; refer to PDF] . If [figure omitted; refer to PDF] ,..., and [figure omitted; refer to PDF] are invariant-controlled by adding monitors [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] , [figure omitted; refer to PDF] is called controlled. Based on the concept of elementary siphons, the proposed deadlock prevention algorithm developed by Li and Zhou [11] is stated as follows.

Algorithm 8 (elementary siphon-based policy).

Input . Petri net model ( [figure omitted; refer to PDF] ) of an AMS, where [figure omitted; refer to PDF] .

Step 1 . For a given Petri net ( [figure omitted; refer to PDF] ), compute all SMSs.

Step 2 . Compute the transition vector matrix [figure omitted; refer to PDF] of the SMS.

Step 3 . Compute the elementary siphons of Petri net [figure omitted; refer to PDF] . The remaining are the dependent siphons.

Step 4 . For each siphon elementary siphon, add a monitor [figure omitted; refer to PDF] such that

(i) the [figure omitted; refer to PDF] output arcs are connected to the source transitions leading to the sink transitions of [figure omitted; refer to PDF] and all arcs weights are ones;

(ii) the [figure omitted; refer to PDF] input arcs are connected from the stealing places of [figure omitted; refer to PDF] and all arcs weights are ones;

(iii): [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is an initial marking of a monitor and [figure omitted; refer to PDF] .

Step 5 . Repeat Step 4 until all elementary siphons are covered.

Step 6 . Adjust [figure omitted; refer to PDF] , such that each dependent siphon is controlled.

Step 7 . Add all monitors to ( [figure omitted; refer to PDF] ) and the resulting net is denoted by ( [figure omitted; refer to PDF] ).

Step 8 . Output ( [figure omitted; refer to PDF] ).

Step 9 . End.

For example, there are three SMSs in the Petri net model shown in Figure 1(b), which are [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . One can obtain that [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Hence, [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . The transition vector matrix [figure omitted; refer to PDF] for the Petri net model in Figure 1(b) is as follows. Obviously, the rank of [figure omitted; refer to PDF] is 2 since the first row [figure omitted; refer to PDF] can be linearly represented by the second and third rows, and we can see that [figure omitted; refer to PDF] . As a result, the siphons that correspond to the second and third rows [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are elementary siphons. Thus, [figure omitted; refer to PDF] is a dependent siphon: [figure omitted; refer to PDF] The dependent siphons and their elementary siphons, the initial marking relationships between dependent and elementary siphons, and the controllability of dependent siphons due to Theorem 7 are shown in Table 2. Table 3 shows the required monitors using Algorithm 8 for Figure 1(b). Figure 3 presents the controlled system of the Petri net model in Figure 1(b) after adding monitors by using Algorithm 8.

Table 2: Marking relationships between dependent and elementary siphons.

Dependent	[figure omitted; refer to PDF] relationship	Initial marking relationships, [figure omitted; refer to PDF]	Controlled
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF] 3 > (2 + 2) - (1 + 1), 3 > 2	Yes

Table 3: Required monitors using Algorithm 8.

Siphon	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1
[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1

Figure 3: Controlled system of the Petri net in Figure 1(b) by Algorithm 8.

[figure omitted; refer to PDF]

4.2. Iterative Methods

This section presents two techniques that are motivated and developed by [25]. These techniques are used to design a place invariant (PI) that can prohibit as many forbidden bad markings (FBMs) as possible. First, the vector covering method is used to find the minimal covering sets of legal markings and FBMs (see Chen et al. [1]). Then, solving the integer linear programming problem (ILPP) can obtain the coefficients of the place invariant and monitors. An iterative monitor design process is executed. At each iteration, a place invariant is designed to prohibit as many FBMs as possible. All FBMs that are prohibited by the place invariant are eliminated from the minimal covered set of FBMs. This process is terminated when all the minimal covered sets of FBMs are forbidden.

4.2.1. Maximal Number of Forbidding FBM Problem 1

The Maximal number of Forbidding FBM Problem 1 (MFFP1) is a technique used to design a monitor synthesis for FBMs. This technique used ILPP to obtain the coefficients of the place invariant that prohibit as many FBMs as possible. The MFFP1 is shown in the following mathematical model.

MFFP1 is [figure omitted; refer to PDF] where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are the minimal covering sets of legal markings and FBMs, respectively. The objective function [figure omitted; refer to PDF] is used to maximize the number of FBMs that are forbidden by place invariant. If [figure omitted; refer to PDF] , we have [figure omitted; refer to PDF] , for all [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] is used to denote [figure omitted; refer to PDF] ): that is to say, no FBMs in [figure omitted; refer to PDF] can be prohibited by place invariant. In (2), let [figure omitted; refer to PDF] be a place invariant, where [figure omitted; refer to PDF] 's ( [figure omitted; refer to PDF] ) are the coefficients of [figure omitted; refer to PDF] , [figure omitted; refer to PDF] is a positive integer variable, and [figure omitted; refer to PDF] are the number of tokens in minimal covering set of legal markings.

All legal markings should be kept after a monitor is added, implying that every marking [figure omitted; refer to PDF] cannot be forbidden from being reached, and coefficients [figure omitted; refer to PDF] 's ( [figure omitted; refer to PDF] ) should satisfy (2) that is called the reachability condition.

In (3), [figure omitted; refer to PDF] is a positive integer constant number that must be large enough, [figure omitted; refer to PDF] are the number of tokens in minimal covering set of FBMs, and [figure omitted; refer to PDF] 's ( [figure omitted; refer to PDF] ) are a set of [figure omitted; refer to PDF] variables. Moreover, in (3), [figure omitted; refer to PDF] implies that [figure omitted; refer to PDF] is prohibited by [figure omitted; refer to PDF] and [figure omitted; refer to PDF] implies that this constraint is redundant and [figure omitted; refer to PDF] cannot be prohibited by [figure omitted; refer to PDF] .

Based on the concept of MFFP1, the proposed deadlock prevention algorithm developed in [25] is stated as follows.

Algorithm 9 (MFFP1 based policy).

Input . Petri net model ( [figure omitted; refer to PDF] ) of an AMS, where [figure omitted; refer to PDF] .

Step 1 . For a given Petri net ( [figure omitted; refer to PDF] ), find the sets of FBMs [figure omitted; refer to PDF] and legal markings [figure omitted; refer to PDF] .

Step 2 . Find the minimal covered sets of FBMs [figure omitted; refer to PDF] and legal markings [figure omitted; refer to PDF] .

Step 3 . [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is used to indicate the set of monitors to be found. [figure omitted; refer to PDF]

Step 4 . While [figure omitted; refer to PDF] , do the following.

(i) Design MFFP1.

(ii) Solve MFFP1. Let [figure omitted; refer to PDF] 's ( [figure omitted; refer to PDF] ) and [figure omitted; refer to PDF] be the solution if [figure omitted; refer to PDF] .

: Otherwise, exit, as the solution does not exist.

(iii): Design a place invariant [figure omitted; refer to PDF] and a monitor [figure omitted; refer to PDF] .

(iv) [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is covered [figure omitted; refer to PDF]

: endwhile.

Step 5 . Add all monitors in [figure omitted; refer to PDF] to ( [figure omitted; refer to PDF] ) and the resulting net is denoted by ( [figure omitted; refer to PDF] ).

Step 6 . Output ( [figure omitted; refer to PDF] ).

Step 7 . End.

For the Petri net model shown in Figure 1(b), we have [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Algorithm 9 is considered. At the first iteration, let [figure omitted; refer to PDF] be the place invariant to be calculated. [figure omitted; refer to PDF] should satisfy (2) for the two legal markings in [figure omitted; refer to PDF] : that is, [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Therefore, we have the following two constraints: [figure omitted; refer to PDF] We introduce three variables [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ) to represent whether [figure omitted; refer to PDF] forbids [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , respectively. Therefore, we have the following three constraints: that is, [figure omitted; refer to PDF] Finally, MFFP1 is defined as follows.

MFFP1 is [figure omitted; refer to PDF] The optimal solution of the above MFFP1 is [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , and all the remaining variables are equal to zero. Then, a monitor [figure omitted; refer to PDF] is designed for [figure omitted; refer to PDF] . As a result, we have [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . FBM₁ and FBM₃ are prohibited by [figure omitted; refer to PDF] : that is, [figure omitted; refer to PDF] . Therefore, we have [figure omitted; refer to PDF] : that is, [figure omitted; refer to PDF] .

At the next iteration, let [figure omitted; refer to PDF] place invariant be calculated. The new MFFP1 can be easily obtained by eliminating constraints that related to FBM₁ and FBM₃ from the first MFFP1. Therefore, the new MFFP1 is stated as follows.

MFFP1 is [figure omitted; refer to PDF] The optimal solution of the above MFFP1 is [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] and all the remaining variables are equal to zero. Then, a monitor [figure omitted; refer to PDF] is designed for [figure omitted; refer to PDF] . As a result, we have [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Only FBM₂ is prohibited by [figure omitted; refer to PDF] : that is, [figure omitted; refer to PDF] . Therefore, we have [figure omitted; refer to PDF] : that is, [figure omitted; refer to PDF] .

Algorithm 9 is terminated. Totally, there are two monitors computed for this net. Adding the two monitors to the original Petri net model, the controlled system after addition is as shown in Figure 4. Table 4 shows the two required monitors by using Algorithm 9.

Table 4: Required monitors using Algorithm 9.

[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1

Figure 4: Controlled system of the Petri net in Figure 1(b) by Algorithm 9.

[figure omitted; refer to PDF]

4.2.2. Maximal Number of Forbidding FBM Problem 2

The Maximal number of Forbidding FBM Problem 1 has been modified to improve its efficiency and its number of variables and constraints are slightly reduced. The modified technique is called a Maximal number of Forbidding FBM Problem 2 (MFFP2). The MFFP1 is shown in the following mathematical model.

MFFP2 is [figure omitted; refer to PDF] The objective function is maximizing [figure omitted; refer to PDF] the number of FBMs that are prohibited by place invariant. If no solution has been obtained from MFFP2 for an FBM, then there are not any FBMs in [figure omitted; refer to PDF] that can be forbidden by that place invariant.

In (8), [figure omitted; refer to PDF] 's ( [figure omitted; refer to PDF] ) are the coefficients of [figure omitted; refer to PDF] , [figure omitted; refer to PDF] are the number of tokens in minimal covering set of legal markings, and [figure omitted; refer to PDF] are the number of tokens in selected [figure omitted; refer to PDF] . In (9), [figure omitted; refer to PDF] is a positive integer constant number that must be large enough, [figure omitted; refer to PDF] are the number of tokens in minimal covering set of FBMs, and [figure omitted; refer to PDF] 's ( [figure omitted; refer to PDF] ) are a set of [figure omitted; refer to PDF] variables. In (9), [figure omitted; refer to PDF] implies that [figure omitted; refer to PDF] is prohibited by [figure omitted; refer to PDF] and [figure omitted; refer to PDF] implies that this constraint is redundant and [figure omitted; refer to PDF] cannot be prohibited by [figure omitted; refer to PDF] .

Based on the concept of MFFP2, the proposed deadlock prevention algorithm developed in [25] is stated as follows.

Algorithm 10 (MFFP2 based policy).

Input . Petri net model ( [figure omitted; refer to PDF] ) of an AMS, where [figure omitted; refer to PDF] .

Step 1 . For a given Petri net ( [figure omitted; refer to PDF] ), find the sets of FBMs [figure omitted; refer to PDF] and legal markings [figure omitted; refer to PDF] .

Step 2 . Find the minimal covered sets of FBMs [figure omitted; refer to PDF] and legal markings [figure omitted; refer to PDF] .

Step 3 . [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is used to indicate the set of monitors to be found. [figure omitted; refer to PDF]

Step 4 . While [figure omitted; refer to PDF] , do the following.

(i) Design MFF2.

(ii) Solve MFFP2. Let [figure omitted; refer to PDF] 's ( [figure omitted; refer to PDF] ) and [figure omitted; refer to PDF] be the solution if [figure omitted; refer to PDF] . Otherwise, exit, as the solution does not exist.

(iii): Design a place invariant [figure omitted; refer to PDF] and a monitor [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is covered [figure omitted; refer to PDF]

: endwhile.

Step 5 . Add all monitors in [figure omitted; refer to PDF] to ( [figure omitted; refer to PDF] ) and the resulting net is denoted by ( [figure omitted; refer to PDF] ).

Step 6 . Output ( [figure omitted; refer to PDF] ).

Step 7 . End.

Consider the Petri net model shown in Figure 1(b) by Algorithm 10. At the first iteration, [figure omitted; refer to PDF] is chosen. Let [figure omitted; refer to PDF] be the place invariant to prohibit FBM₁ , whose coefficients are [figure omitted; refer to PDF] 's ( [figure omitted; refer to PDF] ). [figure omitted; refer to PDF] should satisfy (8) that is called the reachability condition and does not prohibit any marking in [figure omitted; refer to PDF] . Therefore, [figure omitted; refer to PDF] should satisfy two constraints: [figure omitted; refer to PDF] for the two legal markings [figure omitted; refer to PDF] and [figure omitted; refer to PDF] in [figure omitted; refer to PDF] , respectively. After simplifying the two constraints, we have [figure omitted; refer to PDF] Two variables are introduced [figure omitted; refer to PDF] and [figure omitted; refer to PDF] to represent whether [figure omitted; refer to PDF] forbids [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively. Therefore, we have the two constraints: that is, [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is a positive integer constant that must be big enough and [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ) implies that FBM₂ (FBM₃ ) is forbidden by [figure omitted; refer to PDF] and [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ) implies that FBM₂ (FBM₃ ) cannot be forbidden by [figure omitted; refer to PDF] . After simplifying the two constraints, we have [figure omitted; refer to PDF] Finally, from the above constrains MFFP2 for FBM₁ is stated as follows.

MFFP2 is [figure omitted; refer to PDF] The optimal solution of the above MFFP2 is [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , and all the remaining variables are equal to zero. Then, a monitor [figure omitted; refer to PDF] is designed for [figure omitted; refer to PDF] . As a result, we have [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . FBM₁ and FBM₂ are prohibited by [figure omitted; refer to PDF] : that is, [figure omitted; refer to PDF] . Therefore, we have [figure omitted; refer to PDF] : that is, [figure omitted; refer to PDF] . At the second iteration, the last FBM is considered, that is, FBM₃ . Let [figure omitted; refer to PDF] be the place invariant to prohibit FBM₃ . First, the coefficients of [figure omitted; refer to PDF] should fulfill the reachability conditions: that is, [figure omitted; refer to PDF] Since FBM₃ is the last marking in [figure omitted; refer to PDF] , no other FBMs in the set require to be prohibited by [figure omitted; refer to PDF] . By solving the above integer linear system, we have a solution with [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and all the remaining variables are equal to zero. Then, a monitor [figure omitted; refer to PDF] is designed for [figure omitted; refer to PDF] . As a result, we have [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Only FBM₃ is prohibited by [figure omitted; refer to PDF] : that is, [figure omitted; refer to PDF] . Therefore, we have [figure omitted; refer to PDF] : that is, [figure omitted; refer to PDF] .

Algorithm 10 is terminated. Totally, there are two monitors computed for this net. We add the two monitors to the original Petri net model. The controlled system after addition is as shown in Figure 5. Table 5 shows the two required monitors by using Algorithm 10.

Table 5: Required monitors using Algorithm 10.

[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1

Figure 5: Controlled system of the Petri net in Figure 1(b) by Algorithm 10.

[figure omitted; refer to PDF]

5. Case Studies

This section presents four case studies and the applications of the proposed applied algorithms.

(a) The production sequence of the first AMS case study is shown in Figure 6(a). It consists of two robots (R1 and R2; each one can hold a part at a time) and five machines (Ml, M2, M3, M4, and M5; each one can process one part at a time). There are three loading buffers I1-3 and three unloading buffers O1-3. Three types of parts are considered in the system: PA, PB, and PC. The model of Petri net for this case study is shown in Figure 6(b).

Figure 6: (a) Production sequence and (b) Petri net model of case study 1.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(b) The production sequence of the second AMS case study is shown in Figure 7(a) and several studies have been done in this case study (see Elzpeleta et al. [13] and Chen et al. [25]). The system consists of three robots (Rl, R2, and R3; each one can hold a part at a time) and four machines (Ml, M2, M3, and M4; each machine can process two parts at a time). There are three loading buffers I1-3 and three unloading buffers O1-3. Three types of parts are considered in the system: PA, PB, and PC. The model of Petri net for this case study is shown in Figure 7(b).

Figure 7: (a) Production sequence and (b) Petri net model of case study 2.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) Next, the production sequence of the third AMS case study is shown in Figure 8(a). The cell consists of two robots (R1 and R2; each one can hold a part at a time) and four machines (M1, M2, and M3; each machine can process a part at a time; M4 can process two products at a time) and, for loading and unloading the cell, two loading buffers (I1 and I2) and two unloading buffers (O1 and O2). Two types of parts are considered in the cell: PA and PB. The model of Petri net for this case study is illustrated in Figure 8(b).

Figure 8: (a) Production sequence and (b) Petri net model of case study 3.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(d) Finally, the production sequence of the fourth AMS case study is shown in Figure 9(a) and several studies have been achieved in this case study (see Uzam [9], Chen et al. [25], Piroddi et al. [26], and Piroddi et al. [27]). The system is composed of two robots (R1 and R2; each robot can hold a part at a time) and four machines (M1, M2, M3, and M4; each machine can process one part at a time). There are two loading buffers (I1 and I2) and two unloading buffers (O1 and O2). PA and PB are considered in the system. The model of Petri net for this case study is shown in Figure 9(b).

Figure 9: (a) Production sequence and (b) Petri net model of case study 4.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

The main parameters of all case studies are presented in Table 6 such as number of places, number of transitions, set partition, SMS, dependent siphons, elementary siphons, reachable markings, FBMs, legal markings, [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Table 7 illustrates the supervisor performance of applied algorithms for all case studies with respect to the numbers of monitors, arcs, and reachable states.

Table 6: Main parameters of all case studies.

Parameter	Case study
1	2	3	4
Number of places	26	26	20	19

Number of transitions	20	20	16	14

Set partition	[figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF]	[figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF]	[figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF]	[figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF]

SMS	11	18	12	5

Dependent siphons	6	9	7	2

Elementary siphons	5	9	5	3

Reachable markings	1492	26750	836	282

FBMs	388	4211	156	54

Legal markings	1072	21581	656	205

[figure omitted; refer to PDF]	9	34	7	8

[figure omitted; refer to PDF]	92	393	56	26

Table 7: Supervisor performance of applied algorithms for all case studies.

Case study	Parameter	Algorithm 2	Algorithm 8	Algorithm 9	Algorithm 10
1	Monitors number	11	5	3	3
Arcs number	66	23	14	31
Reachable states number	1072	1072	1072	1072

2	Monitors number	18	9	6	6
Arcs number	106	50	45	59
Reachable states number	6287	6287	21581	21581

3	Monitors number	12	5	4	4
Arcs number	61	25	21	21
Reachable states number	436	489	656	656

4	Monitors number	5	3	2	2
Arcs number	21	13	15	12
Reachable states number	182	205	205	205

From Table 7, Algorithms 9 and 10 obtain fewer numbers of monitors than Algorithms 2 and 8 for all case studies while Algorithm 9 provides less or equal number of arcs than the other algorithms in case studies 1, 2, and 3. In case study 4, Algorithm 10 obtains less number of arcs than the other algorithms. As for the reachable states, all algorithms provide the same number of reachable states in case study 1, which is 1072 while both Algorithms 2 and 8 have the same number of reachable states, which is 6287 in case study 2. Moreover, in case study 2, both Algorithms 9 and 10 provide the same number of reachable states, which is 21581. Moreover, in case study 3, both Algorithms 9 and 10 outperform Algorithms 2 and 8 in number of reachable states, which have 656 reachable states. Finally, in case study 4, Algorithms 8, 9, and 10 provide better reachable states than Algorithm 2, which is 205. The required monitors using applied algorithms for all case studied are shown in Tables 8, 9, 10, and 11.

Table 8: Required monitors using applied algorithms for case study 1.

Algorithm	[figure omitted; refer to PDF]	Siphon	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF] )
Algorithm 2	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₁ , t ₇ , t ₁₃	6
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₁ , t ₇ , t ₁₃ , t ₁₆	5
3	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₁ , t ₉ , t ₁₃	4
4	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₁ , t ₇ , t ₁₅	3
5	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₃ , t ₇ , t ₁₃	5
6	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₃ , t ₇ , t ₁₃ , t ₁₆	4
7	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₃ , t ₉ , t ₁₃	3
8	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₇ , t ₁₅	2
9	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₁ , t ₇ , t ₁₆	2
10	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₁	1
11	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₇ , t ₁₆	1

Algorithm 8	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₁ , t ₉ , t ₁₃	4
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₃ , t ₉ , t ₁₃	3
3	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₇ , t ₁₅	2
4	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₁	1
5	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	t ₇ , t ₁₆	1

Algorithm 9	1		[figure omitted; refer to PDF]	t ₃ , t ₉ , t ₁₃	3
2		[figure omitted; refer to PDF]	2t ₇ , t ₁₅ , t ₁₆	3
3		[figure omitted; refer to PDF]	t ₁	1

Algorithm 10	1		[figure omitted; refer to PDF]	t ₄ , 6t ₇ , t ₁₄ , 2t ₁₅ , 3t ₁₆	11
2		[figure omitted; refer to PDF]	11t ₁ , 2t ₃ , t ₇ , 2t ₉ , 6t ₁₃	20
3		[figure omitted; refer to PDF]	t ₄ , t ₉ , t ₁₃	3

Table 9: Required monitors using applied algorithms for case study 2.

Algorithm	[figure omitted; refer to PDF]	Siphon	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Algorithm 2	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	10
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	7
3	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
4	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
5	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	9
6	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	6
7	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	4
8	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	7
9	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	4
10	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
11	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	8
12	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
13	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	3
14	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
15	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
16	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	7
17	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	4
18	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2

Algorithm 8	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	10
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
3	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1
4	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
5	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	8
6	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
7	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1
8	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	4
9	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1

Algorithm 9	1		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	196
2		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	71
3		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	34
4		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
5		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
6		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2

Algorithm 10	1		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	196
2		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	71
3		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	34
4		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
5		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
6		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2

Table 10: Required monitors using applied algorithms for case study 3.

Algorithm	[figure omitted; refer to PDF]	Siphon	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Algorithm 2	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	6
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
3	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
4	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	4
5	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	3
6	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
7	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
8	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	3
9	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
10	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	4
11	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
12	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2

Algorithm 8	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	3
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
3	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
4	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
5	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2

Algorithm 9	1		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
2		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
3		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
4		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2

Algorithm 10	1		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
2		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
3		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
4		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2

Table 11: Required monitors using applied algorithms for case study 4.

Algorithm	[figure omitted; refer to PDF]	Siphon	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Algorithm 2	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	5
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
3	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	4
4	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	3
5	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1

Algorithm 8	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	2
2	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	3
3	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	1

Algorithm 9	1		[figure omitted; refer to PDF] , [figure omitted; refer to PDF]	[figure omitted; refer to PDF] , [figure omitted; refer to PDF]	14
2		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	9

Algorithm 10	1		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	3
2		[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	9

6. Computational Results and Analysis

This section presents that the computational results and analysis of the applied methods are conducted for four AMSs case studies. All cases have been modeled using MATLAB software. The simulation is done for 24 time units. After running and simulating the case studies, the results of MATLAB simulation in terms of the utilization resources and throughput can be summarized as follows. For case study 1, Figures 10 and 11 show the resources utilization and throughput of case study 1, respectively. From the figures, it can be found that all applied Algorithms 8, 9, and 10 obtain the same utilization for all resources, while Algorithm 2 obtains utilization better than Algorithms 8, 9, and 10 at M1, M2, M5, and R1, and same utilization at M4 and R2. For the throughput, Algorithm 2 obtains greater produced number of part A and part C than Algorithms 8, 9, and 10. Moreover, Algorithms 8, 9, and 10 provide the same throughput for all part types. For case study 2, Figures 12 and 13 show the resources utilization and throughput of the case study 2, respectively.

Figure 10: Utilization of resources for the Petri net model in case study 1.

[figure omitted; refer to PDF]

Figure 11: Throughput of the system for the Petri net model in case study 1.

[figure omitted; refer to PDF]

Figure 12: Utilization of resources for the Petri net model in case study 2.

[figure omitted; refer to PDF]

Figure 13: Throughput of the system for the Petri net model in case study 2.

[figure omitted; refer to PDF]

The figures indicate that both applied Algorithms 9 and 10 have the same utilization for all resources and have better results than Algorithms 2 and 8 at M1, M2, M4, R1, and R2. Algorithm 2 obtains utilization better than Algorithms 8, 9, and 10 at M3 and R3. For the throughput, Algorithm 2 obtains greater produced number of part C than Algorithms 8, 9, and 10, while Algorithms 9 and 10 have greater produced number of part A than Algorithms 2 and 8. Moreover, Algorithm 8 obtains a greater produced number of part B than Algorithms 2, 9, and 10. For case study 3, Figures 14 and 15 show the resources utilization and throughput of case study 3, respectively. The figures indicate that both applied Algorithms 9 and 10 have the same utilization of all resources and obtain better results than Algorithms 2 and 8 at M1, M3, and R2. Both Algorithms 2 and 8 obtain the same utilization for all resources and provide utilization better than Algorithms 9 and 10 at M2, M4, and R1. For the throughput, Algorithms 2 and 8 have greater produced number of part B than Algorithms 9 and 10, while Algorithms 9 and 10 obtain greater produced number of part A than Algorithms 2 and 8. Finally, for case study 4, Figures 16 and 17 show the resources utilization and throughput of case study 4, respectively. From the figures, it can be found that both applied Algorithms 9 and 10 obtain the same utilization of all resources and obtain better results than Algorithms 2 and 8 at M1, M2, R1, and R2. Both Algorithms 2 and 8 obtain the same utilization of all resources and obtain utilization better than Algorithms 9 and 10 at M3 and M4. For the throughput, Algorithms 9 and 10 obtain greater produced number of parts A and B than Algorithms 2 and 8.

Figure 14: Utilization of resources for the Petri net model in case study 3.

[figure omitted; refer to PDF]

Figure 15: Throughput of the system for the Petri net model in case study 3.

[figure omitted; refer to PDF]

Figure 16: Utilization of resources for the Petri net model in case study 4.

[figure omitted; refer to PDF]

Figure 17: Throughput of the system for the Petri net model in case study 4.

[figure omitted; refer to PDF]

Based on the above computational results for all case studies, it is shown that four applied deadlock prevention policies may not imply high resource utilization and plant productivity which has been shown theoretically in previous publications, since the utilization of any resource at case studies does not exceed 50% and there are several resources that have utilization less than 20%. Moreover, it is found that the resource utilization and plant productivity are different for case studies by using applied policies. The main reason of the occurrence of this difference is a conflict situation in places. When a control place enables more than one transition at the same time, only one transition can fire. For instance, in case study 1, the number of control places using Algorithm 2 are 11 and more than one transition is enabled at the same time; that is, several transitions can be fired. While Algorithm 10 reduces the control places into 3 places and enables more than one transition at the same time, few transitions can be fired compared with Algorithm 2. Therefore, the performance is different for different cases by using applied policies. However, we can introduce the comparison between applied policies based on the above computational results, from the viewpoint of behavior permissiveness. Both Algorithms 9 and 10 can provide better behavioral permissiveness than Algorithms 2 and 8 for small size systems (case studies 3 and 4). For the large systems size (case studies 1 and 2), Algorithm 2 leads to better behavioral permissiveness than the other algorithms. The supervisor performance of applied algorithms such as the number of monitors, arcs, and reachable states as averages values is summarized. Figures 18, 19, and 20 show the summarized supervisor performance of all algorithms. From the figures, both Algorithms 9 and 10 obtain a supervisor with structural complexity and computational complexity compared to Algorithms 2 and 8.

Figure 18: Average of monitors for all cases.

[figure omitted; refer to PDF]

Figure 19: Average of arcs for all cases.

[figure omitted; refer to PDF]

Figure 20: Average of reachable states for all cases.

[figure omitted; refer to PDF]

7. Conclusion and Future Work

This paper presents four applied deadlock prevention policies, two and two of which are iterative methods and siphon control methods, respectively. Four applied deadlock control methods are used to design a liveness-enforcing supervisor for four automated manufacturing system case studies. The controlled case studies are modeled and simulated using MATLAB software (Petri net toolbox) to analyze and evaluate the performance of selected methods such as utilization of resources and throughput; the computational results can be summarized as follows.

The applied deadlock prevention policies may not imply high resource utilization and plant productivity which has been shown theoretically in previous publications. Moreover, it is found that the resource utilization and plant productivity are different for case studies by using applied policies. The main reason for this difference is a conflict situation in places. When a control place enables more than one transition at the same time, only one transition can fire. For instance, in case study 1, the number of control places using Algorithm 2 are 11 and more than one transition is enabled at the same time; that is, several transitions can be fired. While Algorithm 10 reduces the control places into 3 places and enables more than one transition at the same time, few transitions can be fired compared with Algorithm 2. Therefore, the performance is different for different cases by using applied policies. However, for all automated manufacturing systems, with respect to structural complexity and computational complexity, the selected iterative methods can always lead to structurally complicated and computationally expensive liveness-enforcing net supervisors compared to the siphon control methods. From the aspect of behavioral permissiveness, the selected iterative methods can provide better behavioral permissiveness than siphon control methods for small size systems. For large systems size, strict minimal siphons control method leads to better behavioral permissiveness than the other methods.

Real-world AMSs can suffer from impacts of unreliable resources (resources with failures) under the supervisory control of deadlocks. Therefore, the need for new effective deadlock control policies based on Petri nets becomes increasingly more important. Thus, the future research direction involves designing new effective deadlock prevention policies for automated manufacturing systems with unreliable resources [8]. Then, a simulation will be used to measure the performance of these policies. Different and complex automated manufacturing systems are required and should be considered as a benchmark for these deadlock prevention policies under a variety of control specifications. Optimal deadlock-free scheduling with high time performance will also be interesting.

Acknowledgment

This work was funded by the National Plan for Science, Technology and Innovation (MARRIFAH), King Abdulaziz City for Science and Technology, Kingdom of Saudi Arabia, Award no. 12-ELE2506-02.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] Y. Chen, Z. Li, M. Khalgui, O. Mosbahi, "Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems," IEEE Transactions on Automation Science and Engineering , vol. 8, no. 2, pp. 374-393, 2011.

[2] R. A. Wysk, N. S. Yang, S. Joshi, "Detection of deadlocks in flexible manufacturing cells," IEEE Transactions on Robotics and Automation , vol. 7, no. 6, pp. 853-859, 1991.

[3] D. Y. Chao, "Direct minimal empty siphon computation using MIP," The International Journal of Advanced Manufacturing Technology , vol. 45, no. 3-4, pp. 397-405, 2009.

[4] D. Y. Chao, "Improvement of suboptimal siphon-and FBM-based control model of a well-known," IEEE Transactions on Automation Science and Engineering , vol. 8, no. 2, pp. 404-411, 2011.

[5] A. Ghaffari, N. Rezg, X. Xie, "Design of a live and maximally permissive Petri net controller using the theory of regions," IEEE Transactions on Robotics and Automation , vol. 19, no. 1, pp. 137-141, 2003.

[6] M. Uzam, M. Zhou, "Iterative synthesis of petri net based deadlock prevention policy for flexible manufacturing systems," in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (SMC '04), pp. 4260-4265, October 2004.

[7] M. Uzam, "The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems," The International Journal of Advanced Manufacturing Technology , vol. 23, no. 3-4, pp. 204-219, 2004.

[8] K. Lautenbach, "Linear algebraic calculation of deadlocks and traps," Concurrency and Nets , pp. 315-336, Springer, Berlin, Germany, 1987.

[9] M. Uzam, "An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions," The International Journal of Advanced Manufacturing Technology , vol. 19, no. 3, pp. 192-208, 2002.

[10] D. Y. Chao, "Fewer monitors and more efficient controllability for deadlock control in S³ PGR² (systems of simple sequential processes with general resource requirements)," The Computer Journal , vol. 53, no. 10, pp. 1783-1798, 2010.

[11] Z. Li, M. Zhou, "Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems," IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans , vol. 34, no. 1, pp. 38-51, 2004.

[12] Z. Li, G. Liu, H.-M. Hanisch, M. Zhou, "Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems," IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans , vol. 42, no. 1, pp. 178-191, 2012.

[13] J. Ezpeleta, J. M. Colom, J. Martinez, "A petri net based deadlock prevention policy for flexible manufacturing systems," IEEE Transactions on Robotics and Automation , vol. 11, no. 2, pp. 173-184, 1995.

[14] Y. S. Huang, M. D. Jeng, X. L. Xie, S. L. Chung, "A deadlock prevention policy for flexible manufacturing systems using siphons," in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '01), pp. 541-546, May 2001.

[15] Y. S. Huang, M. Jeng, X. Xie, D.-H. Chung, "Siphon-based deadlock prevention policy for flexible manufacturing systems," IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans , vol. 36, no. 6, pp. 1248-1256, 2006.

[16] Z. Li, N. Wei, "Deadlock control of flexible manufacturing systems via invariant-controlled elementary siphons of petri nets," The International Journal of Advanced Manufacturing Technology , vol. 33, no. 1-2, pp. 24-35, 2007.

[17] Y. S. Huang, "Design of deadlock prevention supervisors using Petri nets," The International Journal of Advanced Manufacturing Technology , vol. 35, no. 3-4, pp. 349-362, 2007.

[18] G. Y. Liu, Z. W. Li, K. Barkaoui, A. M. Al-Ahmari, "Robustness of deadlock control for a class of Petri nets with unreliable resources," Information Sciences , vol. 235, pp. 259-279, 2013.

[19] S. Wang, M. Zhou, W. Wu, "Design of a maximally permissive liveness-enforcing supervisor with reduced complexity for automated manufacturing systems," Asian Journal of Control , vol. 17, no. 1, pp. 190-201, 2014.

[20] N. Viswanadham, Y. Narahari, T. L. Johnson, "Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models," IEEE Transactions on Robotics & Automation , vol. 6, no. 6, pp. 713-723, 1990.

[21] M. Uzam, Z. Li, M. Zhou, "Identification and elimination of redundant control places in petri net based liveness enforcing supervisors of FMS," The International Journal of Advanced Manufacturing Technology , vol. 35, no. 1-2, pp. 150-168, 2007.

[22] Z. Li, H. Hu, "On systematic methods to remove redundant monitors from liveness-enforcing net supervisors," Computers & Industrial Engineering , vol. 56, no. 1, pp. 53-62, 2009.

[23] F. Garcia-Valles, J. Colom, "Implicit places in net systems," in Proceedings of the 8th International Workshop on Petri Nets and Performance Models, pp. 104-113, Zaragoza, Spain, 1999.

[24] L. Recalde, E. Teruel, M. Silva, "Improving the decision power of rank theorems," in Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Computational Cybernetics and Simulation, pp. 3768-3773, October 1997.

[25] Y. Chen, Z. Li, M. Zhou, "Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems," IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans , vol. 42, no. 3, pp. 615-629, 2012.

[26] L. Piroddi, R. Cordone, I. Fumagalli, "Selective siphon control for deadlock prevention in Petri nets," IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans , vol. 38, no. 6, pp. 1337-1348, 2008.

[27] L. Piroddi, R. Cordone, I. Fumagalli, "Combined siphon and marking generation for deadlock prevention in Petri nets," IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans , vol. 39, no. 3, pp. 650-661, 2009.

Word count: 14538

Show less

Copyright © 2015 Emad Abouel Nasr et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Translate

In automated manufacturing systems (AMSs), deadlocks problems can arise due to limited shared resources. Petri nets are an effective tool to prevent deadlocks in AMSs. In this paper, a simulation based on existing deadlock prevention policies and different Petri net models are considered to explore whether a permissive liveness-enforcing Petri net supervisor can provide better time performance. The work of simulation is implemented as follows. (1) Assign the time to the controlled Petri net models, which leads to timed Petri nets. (2) Build the Petri net model using MATLAB software. (3) Run and simulate the model, and simulation results are analyzed to determine which existing policies are suitable for different systems. Siphons and iterative methods are used for deadlocks prevention. Finally, the computational results show that the selected deadlock policies may not imply high resource utilization and plant productivity, which have been shown theoretically in previous publications. However, for all selected AMSs, the iterative methods always lead to structurally and computationally complex liveness-enforcing net supervisors compared to the siphons methods. Moreover, they can provide better behavioral permissiveness than siphons methods for small systems. For large systems, a strict minimal siphon method leads to better behavioral permissiveness than the other methods.

Details

Title

Comparison and Evaluation of Deadlock Prevention Methods for Different Size Automated Manufacturing Systems

Author

Emad Abouel Nasr; El-Tamimi, Abdulaziz M; Al-Ahmari, Abdulrahman; Kaid, Husam

Publication year

2015

Publication date

2015

Publisher

John Wiley & Sons, Inc.

ISSN

1024123X

e-ISSN

15635147

Source type

Scholarly Journal

Language of publication

English

DOI

https://doi.org/10.1155/2015/537893

ProQuest document ID

1716887332

Comparison and Evaluation of Deadlock Prevention Methods for Different Size Automated Manufacturing Systems

Jump to:

Full Text

Abstract

Details

Suggested sources