Brief paperDeadlock characterization and control of flexible assembly systems with Petri nets☆
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 assemble 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, where and. 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 and be two A-chains. If and are said to be compatible, and 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, as shown in Fig. 1 (b), has 6144 reachable states, where there are 5228 safe states. In Example 2, it has been shown that. By Definition 11, the Petri net controller 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)
- et al.
A robust deadlock prevention control for automated manufacturing systems with unreliable resources
Information Sciences
(2016) - et al.
Robust deadlock control for automated manufacturing systems with an unreliable resource
Information Sciences
(2016) - et al.
Design of supervisors to avoid deadlock in flexible assembly systems
International Journal of Flexible Manufacturing Systems
(2002) - et al.
Deadlock control methods in automated manufacturing systems
IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans
(2004) - 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) - et al.
Efficient optimal deadlock control of flexible manufacturing systems
IET Control Theory & Applications
(2016) - et al.
A petri net-based discrete event control of automated manufacturing systems with assembly operations
IEEE Transactions on Control Systems Technology
(2015) - et al.
Deadlock prevention policy based on Petri nets and siphons
International Journal of Productions Research
(2001) Deadlock avoidance for production systems with flexible routing
IEEE Transactions on Robotics and Automation
(1999)
Cited by (34)
Deadlock control and hybrid social spider scheduling algorithm for two-stage assembly permutation flowshop with limited buffers
2024, Expert Systems with ApplicationsHybrid particle swarm optimization algorithm for scheduling flexible assembly systems with blocking and deadlock constraints
2021, Engineering Applications of Artificial IntelligenceCitation 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 SystemsCitation 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, AutomaticaCitation 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
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.