Elsevier

Automatica

Volume 87, January 2018, Pages 358-364
Automatica

Brief paper
Deadlock characterization and control of flexible assembly systems with Petri nets

https://doi.org/10.1016/j.automatica.2017.09.001Get rights and content

Abstract

Efficient deadlock controllers are critical in the operation of automated manufacturing systems. This work focuses on a deadlock control problem for flexible assembly systems (FAS). Petri nets are used to model the systems. Through their liveness analysis, it characterizes two kinds of structural objects. Each object can lead to a siphon, and may cause the system to deadlock. Based on such objects, a necessary and sufficient condition about the liveness of Petri net models is obtained. In order to prevent each such object from causing FAS to deadlock, a Petri net controller is designed such that its induced siphon cannot be empty. The conjunction of all these controllers is proved to be capable of ensuring deadlock-free operation of a large class of FAS. The effectiveness of the proposed approach is shown via an FAS example.

Introduction

An automated manufacturing system (AMS) is a computer-controlled production system exhibiting a high degree of resource sharing. It consists of a set of resources and can concurrently process different types of parts. Its interacting parts and shared resources can lead to deadlock states under which the system remains indefinitely blocked and cannot terminate its task (Fanti & Zhou, 2004). Therefore, to avoid deadlock and effectively operate and schedule AMSs (Xing, Han, Zhou, & Wang, 2012), it is necessary to develop proper deadlock controllers.

Tremendous progress has been made in the structural analysis of deadlocks and developing deadlock control policies for AMSs (without assembly processes) (Fanti & Zhou, 2004). The existing policies mainly include two kinds, prevention and avoidance. The former establishes in advance offline control policies such that the resulting operation is deadlock-free Feng et al. (2017), Han et al. (2016), Huang et al. (2001), Liu et al. (2014), Wang et al. (2016), Wu et al. (2016), Xing et al. (1996), Xing et al. (2009), while the latter is online control policies that use feedback information on the current state and future process resource requirements, to keep the system away from deadlocks Fanti et al. (2002), Lawley (1999), Roszkowska (2004), Wu et al. (2008), Xing et al. (2009).

Many use Petri nets to describe AMSs and develop deadlock resolution methods (Fanti and Zhou (2004), Zhou and Fanti (2005)). They add a control place and related arcs to each strict minimal siphon such that no siphon can be emptied Huang et al. (2001), Liu et al. (2014), Wu et al. (2016), or to maximal perfect resource-transition circuits such that none of them can be saturated Feng et al. (2017), Wang et al. (2016), Xing et al. (2009). Two methods are proved to be equivalent (Xing, Zhou, Wang, & Tian, 2011).

In contrast, few have addressed the deadlock control problems in flexible assembly systems (FASs). Assembly is one of the most important manufacturing processes, consisting of putting together two or more parts, to produce a finished product. Thus the class of AMSs with no assembly operations is a proper subclass of FASs. Deadlocks in AMSs result from only the circular wait of resources. Different from AMSs, those in FASs result from not only the circular wait of resources, but also the parts waiting for the assembly with other parts. Thus deadlock control problem in FASs is more difficult than one in AMSs. Xing, Hu, and Wan (1999) studied the liveness enforcement problem for a class of FASs, and presented a controller to avoid deadlock in the system. For FASs whose processes had a tree structure, Fanti et al. (2002) developed an approach to deadlock avoidance by inhibiting or enabling the events involving resource allocation. Roszkowska (2004) dealt with deadlock supervisory control in compound processes, and for a subclass of realizable systems, a supervisor was designed to ensure a deadlock-free process. Wu et al. (2008) studied the deadlock problem for FAS with fork/join flow. Based on Petri net models, they presented a deadlock control policy. Hu and Zhou (2015) used a mathematical programming method to derive each deadlock in FAS in an iterative way, and synthesized a live controlled net.

The prior research on deadlock problem in FASs was mostly based on a deadlock avoidance idea. There is less work on deadlock prevention for FASs. This work focuses on it, and develops deadlock controllers. A Petri net is used to describe FAS dynamics and analyze its deadlock. Two kinds of structural objects are identified. The first characterizes resource circular wait, while the second one models the phenomenon where some parts are waiting for other parts to be assembled. It is proved that either can induce a siphon and cause the system deadlock when its induced siphon is empty. A necessary and sufficient liveness condition is then established. In order to prevent these objects from causing system deadlocks, a Petri net controller for each of them is designed, which consists of control places and the reverse of sub-Petri net models. It is proved that the combination of all these controllers can ensure deadlock-free operation of a large class of FAS.

Section 2 first introduces FASs and then develops their Petri net models. Section 3 analyzes their liveness. Section 4 develops Petri net controllers for FASs. Section 5 gives a practical example. Section 6 concludes this paper.

Section snippets

FASs and their Petri net models

In this section, we first introduce the considered FASs and then develop their Petri net models. For concepts and notations of Petri nets, a reader is referred to Xing et al. (2011), Zhou and Fanti (2005).

An FAS consists of a set of resources such as workstations, buffers, AGV systems, and robots. It can manufacture and assemblem different types of products. A product is obtained from some raw parts through a series of manufacturing and assembly activities, and a type of raw parts can only be

Structural analysis of APNs

This section analyzes the liveness and presents a necessary and sufficient liveness condition of APNs.

Definition 1

An activity path (A-path) is a processing sub-route of a partπ=p1t1pktk, wherepiPA andtiT,iZk. An A-path starts from an activity place and ends with a transition.

Definition 2

An A-chain is defined recursively as follows.

(1) An A-path is an A-chain; and

(2) Letπ1=p11t11p1lt1l andπ2=p21t21p2kt2k be two A-chains. If(r)t1l=(p21),π1 andπ2 are said to be compatible, andπ=π1π2=p11t11p1lt1lp21t21p2kt2k is

Deadlock controllers for APNs

By the liveness analysis in Section 3, we know that only two kinds of special structures in Petri net models of FASs under consideration can lead to deadlocks, i.e., A-circuits and closedΩ-structures. The system is live if and only if any siphon induced by A-circuits or closedΩ-structures in APN is not emptied at any reachable marking. To avoid deadlock, therefore, it is necessary to guarantee that all these siphons are not empty. Our control method is to add a Petri net controller to each

An illustrative example

Let us reconsider the three-part assembly system in Example 1. Its Petri net model(N,M0), as shown in Fig. 1 (b), has 6144 reachable states, where there are 5228 safe states. In Example 2, it has been shown that(N)={θ1,w1w6}. By Definition 11, the Petri net controller(C,MC) can be designed as shown in Table 1, where all arcs have weight 1. The controlled net has 4460 reachable states.

In order to show the effectiveness of our controller, we compare it with the two existing deadlock avoidance

Conclusion

Based on the Petri net model of an FAS, this work conducts its structural analysis and invents two new structural objects called A-circuits and closedΩ-structures. They can induce siphons whose empty status signifies deadlocks. For each object, a Petri net controller, consisting of a control place and the reverse of a sub-Petri net, is designed in order to prevent it from causing a deadlock. By combining all these sub-controllers, a Petri net controller for the whole system is obtained. It is

Keyi Xing received his Ph.D. degree in systems engineering from Xi’an Jiaotong University in 1994. Currently, he is a professor of Systems Engineering Institute and the State Key Laboratory for Manufacturing Systems Engineering at Xi’an Jiaotong University. His research interests include control and scheduling of automated manufacturing, discrete-event, and hybrid systems.

References (18)

  • WangF. et al.

    A robust deadlock prevention control for automated manufacturing systems with unreliable resources

    Information Sciences

    (2016)
  • WuY.C. et al.

    Robust deadlock control for automated manufacturing systems with an unreliable resource

    Information Sciences

    (2016)
  • FantiM.P. et al.

    Design of supervisors to avoid deadlock in flexible assembly systems

    International Journal of Flexible Manufacturing Systems

    (2002)
  • FantiM.P. et al.

    Deadlock control methods in automated manufacturing systems

    IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans

    (2004)
  • FengY.X. et al.

    Transition cover-based robust petri net controllers for automated manufacturing systems with a type of unreliable resources

    IEEE Transactions on Systems, Man, and Cybernetics. Systems

    (2017)
  • HanL.B. et al.

    Efficient optimal deadlock control of flexible manufacturing systems

    IET Control Theory & Applications

    (2016)
  • HuH. et al.

    A petri net-based discrete event control of automated manufacturing systems with assembly operations

    IEEE Transactions on Control Systems Technology

    (2015)
  • HuangY.S. et al.

    Deadlock prevention policy based on Petri nets and siphons

    International Journal of Productions Research

    (2001)
  • LawleyM.

    Deadlock avoidance for production systems with flexible routing

    IEEE Transactions on Robotics and Automation

    (1999)
There are more references available in the full text version of this article.

Cited by (34)

  • Hybrid particle swarm optimization algorithm for scheduling flexible assembly systems with blocking and deadlock constraints

    2021, Engineering Applications of Artificial Intelligence
    Citation Excerpt :

    As for deadlock states caused by assembly circular waiting, parts are waiting for other parts to be assembled while the other parts cannot be available. Readers can refer to Hu et al. (2013), Xing et al. (2018), and Luo et al. (2019) for more details on deadlocks in FASs. An example is given in the following to show deadlock situations.

  • Resilience dynamics modeling and control for a reconfigurable electronic assembly line under spatio-temporal disruptions

    2021, Journal of Manufacturing Systems
    Citation Excerpt :

    Forces in traditional dynamics analysis need to be generalized as influence relations between discrete units, and considerations of costs must be included for the control in manufacturing. Work on control theory in manufacturing has included the bond graph [3] and Petri net [4], while the control of performance under disruptions has been investigated via a resilience analytic framework [5,6]. Resilient control aims at keeping an acceptable level of operational normalcy in the present of disruptive events.

  • A distributed method to avoid higher-order deadlocks in multi-robot systems

    2020, Automatica
    Citation Excerpt :

    Deadlocks will stop robots from moving forward and even stagnate the whole system. Indeed, deadlocks are a great challenge to systems containing multiple subsystems with shared resources, such as automated manufacturing systems and multi-robot systems, and have been widely studied (Alonso-Mora, DeCastro, Raman, Rus, & Kress-Gazit, 2018; Chen, Moarref, & Kress-Gazit, 2018; Chen, Wu, & Zhou, 2016; Fanti, Mangini, Pedroncelli, & Ukovich, 2015; Hu, Su, Zhou, & Liu, 2016; Hu & Zhou, 2015; Jager & Nebel, 2001; Kalinovcic, Petrovic, Bogdan, & Bobanac, 2011; Lee & Lin, 1995; Li, Wu, & Zhou, 2012; Moorthy, Hock-Guan, Wing-Cheong, & Chung-Piaw, 2003; Reveliotis & Roszkowska, 2011; Uzam & Zhou, 2007; Xing, Wang, Zhou, Lei, & Luo, 2018; Zhou, Hu, Liu and Ding, 2017; Zhou, Hu, Liu, Lin, & Ding, 2018). Among the existing work, there are mainly three strategies to solve deadlocks: deadlock detection and resolution, deadlock prevention, and deadlock prediction and avoidance.

  • A Robust Control Approach to AMSs by Using the Implementation of Strong and Weak Robustness

    2023, IEEE Transactions on Systems, Man, and Cybernetics: Systems
View all citing articles on Scopus

Keyi Xing received his Ph.D. degree in systems engineering from Xi’an Jiaotong University in 1994. Currently, he is a professor of Systems Engineering Institute and the State Key Laboratory for Manufacturing Systems Engineering at Xi’an Jiaotong University. His research interests include control and scheduling of automated manufacturing, discrete-event, and hybrid systems.

Feng Wang received her B.S. degree in applied mathematics from Northwest University, Xi’an, China, M.S. degree in applied mathematics and Ph.D. degree in the Systems Engineering Institute from Xi’an Jiaotong University, Xi’an, China. She is now an associate professor of School of Mathematics and Statistics of Xi’an Jiaotong University. Her main research interest includes control and scheduling of automated manufacturing and discrete-event systems, and Petri nets.

Meng Chu Zhou received his B.S. degree in Control Engineering from Nanjing University of Science and Technology, Nanjing, China in 1983, M.S. degree in Automatic Control from Beijing Institute of Technology, Beijing, China in 1986, and Ph.D. degree in Computer and Systems Engineering from Rensselaer Polytechnic Institute, Troy, NY in 1990. He joined New Jersey Institute of Technology (NJIT), Newark, NJ in 1990, and is now a distinguished professor of Electrical and Computer Engineering. He is a Fellow IFAC, IEEE, and AAAS.

Hang Lei received her Ph.D. degree in Systems Engineering from Xi’an Jiaotong University in 2016. She is currently with Beijing Wellintech Co., Ltd. Her interests include control and scheduling of automated manufacturing systems, and Petri nets.

Jianchao Luo received his B.S. degree in electrical engineering and its automation from Chang’an University, Xi’an, in 2012, and Ph.D. degree in Control Science and Engineering in Xi’an Jiaotong University in 2016. He joined the Northwestern Polytechnical University, Xi’an, China, in 2017, and is now an assistant professor of Software Engineering. His interests include scheduling and control of manufacturing systems.

This work was supported in part by the National Natural Science Foundation of P.R. China under Grant 61573278. The material in this paper was not presented at any conference. This paper was recommended for publication in revised form by Associate Editor Bart De Schutter under the direction of Editor Christos G. Cassandras.

View full text