This work addresses the problem of deadlock control in flexible assembly systems (FASs) with multiple resource requirements and parts loaded separately into the system. We use generalized Petri nets to model, analyze, and control these FASs. Two kinds of structural objects in the Petri net model, namely A-circuits and closed$\Omega $-structures, can characterize deadlocks. Then a necessary and sufficient condition is derived for the liveness of FAS based on these two objects. By using integer linear programs, we compute all the problematic closed$\Omega $-structures and A-circuits that are related to deadlocks. A specific design of the monitor is developed for each of these objects so as to prevent it from causing deadlock. By composing all these monitors, a deadlock prevention controller is proposed for a subclass of FASs under consideration. Importantly, this work generalizes the liveness condition of ordinary Petri net models to broader non-ordinary ones. Finally, an example can illustrate the usefulness and correctness of the proposed concepts and methods. Note to Practitioners—In the context of FAS, deadlocks are caused by two patterns: “resource circuit-wait” and “event circuit-wait”. The former indicates a circuit-wait relation among shared resources and has been studied extensively in the past decades, while the latter results from the assembly of different parts and has not received much attention. The analysis regarding event circuit-wait is the key to solving a deadlock problem in FAS. To date, there are a limited number of studies addressing the deadlock control problem for FASs with multiple resource requirements. Given such a complex FAS, based on its Petri net model, this paper 1) characterizes the above two circuit-wait patterns by structural objects, 2) presents a sufficient and necessary liveness condition, and 3) develops an effective deadlock prevention controller for a class of FASs under consideration. The proposed deadlock controller can well solve the deadlocks in concerned FAS applications, like automotive industry, semiconductor manufacturing, and so on. Especially, unlike some existing methods, our controller can be applied to the cases where parts of the same product are permitted to load separately into the system.

Resource failures can be encountered in a practical automated manufacturing system (AMS), and thus, its robust supervisory control is an important issue to be addressed. This work uses Petri nets to model AMS with multiunit and unit-type resource acquisitions and releases. Such a system contains multiple unreliable resources. It is known that perfect activity circuits (PACs) are important structural objects in Petri nets. We define a new one called the maximally extended PAC (MPAC) that can be used to characterize deadlocks as PAC does. The number of MPACs is much smaller than that of PACs. The stalled production of a part of an AMS is caused by the occurrence of a blocking marking (BM) state, where a resource circuit-wait pattern is formulated with respect to MPAC. We use an integer linear program (ILP) to compute a problematic MPAC, and a monitor is designed to prevent all BM states caused by it. Then, a robust controller is synthesized in an iterative manner. Such a controller can be used to guarantee the continuous production of all part types even if some resources fail. Finally, the effectiveness and efficiency of the proposed method are demonstrated via experiments and comparative analysis.

The supervisor simplification problem for automated manufacturing systems (AMSs) has been receiving increasing attention in recent years. This article uses a well-known class of Petri nets, namely, systems of sequential systems with shared resources (S4Rs) to model general AMSs. We aim to simplify the liveness-enforcing supervisor for S4R by using the concept of transition cover (TC). Deadlocks in S4R can be characterized by a kind of special structural object called perfect activity circuits (PACs). First, a set of special PACs are defined as a TC and its effectness is also verified. Then, by adding a monitor with a control variable to each PAC in an effective TC (ETC), we establish a liveness-enforcing supervisor for S4R. The control variables are determined by solving an integer linear programming problem so as to increase the supervisor’s permissiveness as much as possible. Under the proposed control methodology, it is analyzed that the upper bound of the number of monitors equates to that of transitions in S4R. Especially for the system with a few transitions, since not many monitors are added, the proposed supervisor has relatively small-scaled structures or a small number of control places. In addition, we present algorithms to get an ETC from any nonlive S4R. Based on this ETC, we can design one liveness-enforcing supervisor of small size for the underlying S4R. Finally, some examples are used to illustrate the proposed approach.

It is inevitable that resource failures occur in real production processes, and sometimes many different types of unreliable resource failures may occur. Once there are resource failures, the stagnation states of production caused by these failures, called as failure blockings (FBs), tend to appear. Hence, both deadlocks and FBs can arise to reduce production efficiency sharply. Designing robust control policies for such an automated system is thus very important. Our work focuses on a novel robust Petri net controller of flexible manufacturing systems with multitype and multiunit of unreliable resources. First, under the assumption that all resources are reliable, these systems are modeled by a class of Petri nets called systems of simple sequential processes with resources (S3PRs). For each operation place that is a holder of an unreliable resource, the corresponding repair place and related transitions are added to the net and an S3PR with unreliable resources (S3PRu) is developed. For an S3PRu, the formal definition of FBs is then proposed. Such an FB is characterized by a maximal perfect resource-transition circuit (MPC). Next, the concept of a critical set of MPCs is introduced. For any two adjacent MPCs in such a critical set, one input transition of the former and one output transition of the latter are connected by passing through resource places. A$\xi $-resource is a one-unit resource shared by two or more MPCs that do not contain each other. For an S3PRu without$\xi $-resources and critical sets of MPCs, a control place corresponding to an MPC is added to the net with its output arcs to the input transitions of the MPC. However, for an S3PRu with$\xi $-resources or critical sets of MPCs, the output arcs of each control place are added to the source transitions of the original net. Thus, a novel robust controller of an S3PRu is synthesized. Such a robust controller can guarantee that as long as at least one unit of each type of unreliable resources can work normally, all kinds of parts can be processed to complete smoothly their tasks through any one of their process routes. Finally, three examples are provided to illustrate the efficiency of the proposed robust controller.

This article focuses on the problem of deadlock for sequential automated manufacturing systems (AMSs) that allow for the general resource allocation and flexible routings. A class of Petri nets, systems of sequential systems with shared resources (S4PR), are used to model these considered AMSs. Our previous work has showed that deadlocks in S4PR are characterized by saturated perfect activity-circuit (PA-circuit). In this article, we divide all saturable PA-circuits into two categories: 1) dependent and 2) independent. An algorithm is proposed to compute all independent saturable PA-circuits. We prove that by adding a monitor for each independent PA-circuit to ensure that it is not saturated, all dependent PA-circuits cannot be saturated either and deadlocks in S4PR are successfully prevented. The presented method simplifies the structure of the deadlock controller without imposing tight constraints on the system. Finally, the proposed controller is illustrated by some examples.

This article addresses the scheduling problem of deadlock-prone flexible manufacturing systems subject to no-wait constraints for the first time, and develops a new scheduling algorithm based on the place-timed Petri net (PN) model and heuristic search. The considered problem can be solved by two procedures: 1) timetabling and 2) sequencing. The timetabling is to translate a given job sequence into a feasible schedule that satisfies the deadlock-free and no-wait constraints. A novel timetabling algorithm based on the controlled PN model is then proposed for solving it. The goal of sequencing is to find a job sequence so that the makespan of the corresponding schedule is the minimum. To this end, a hybrid heuristic search (HHS) is developed by combining the A* algorithm and dynamic window. Two new heuristic functions are designed to guide the search, and the dynamic window is used to limit the searched space. The performance of HHS with different heuristic functions and deadlock controllers is evaluated by ten instances. The computational results demonstrate that through the proposed approach, optimal or suboptimal feasible schedules can be obtained within a reasonable time.

This paper focuses on the liveness analysis and deadlock control for automated manufacturing systems (AMSs) with multiple resource requirements. Such an AMS is modeled by a class of generalized Petri nets called systems of simple sequential processes with multiple resources (S3PMR). It is shown that a deadlock of the considered AMSs can be characterized by the saturation of a structural object in S3PMR, called perfect resource transition-circuit (PRT-circuit). As a consequence, an S3PMR is live if and only if no PRT-circuit is saturated at any reachable marking. To ensure the system liveness, one has to prevent all PRT-circuits from being saturated at all reachable markings. To develop a structurally simple Petri net deadlock controller, we present the concept of an effective transition cover, which is a special subset of PRT-circuits that may be saturated. Then by designing a control place with a proper control variable for each PRT-circuit in an effective transition cover, we obtain a deadlock controller for the system. The needed control variables are determined by an integer linear program. Since the number of PRT-circuits in an effective transition cover is much less than that of all PRT-circuits that need to control, our controller is of small structural size. For an AMS with saturable PRTcircuits, there exists at least a transition cover. An algorithm is presented for checking the effectiveness of transition covers, and transforming noneffective transition covers into effective ones. Finally, some examples are used to illustrate the proposed method.

Recently, the problem of robust control for automated manufacturing systems (AMSs) with unreliable resources receives increasing attentions. Almost all the existing related works are only concerned with the failure-prone AMSs in which each part stage utilizes only one unit of resources. While, in real-world AMS, it is often necessary to use multiple units of different resources to complete a part. This paper focuses on the robust control of such complex AMSs with a type of unreliable resources. General Petri nets are used to model all the behavior of such AMSs. By adding a control place to the Petri net models for each considered siphon, we develop robust deadlock controllers for the considered AMS. Such a robust controller ensures that the parts of all types can be processed continuously through any of its processing routes, even if one of the unreliable resources fails. Finally, some examples are used to illustrate the proposed method.

This paper presents a liveness analysis method for sequential automated manufacturing systems (AMSs), which can be modeled by a class of Petri nets named systems of sequential systems with shared resources (S4PR). We show that deadlocks in S4PR can be characterized by the saturation of its structural object named a perfect activity circuit (PA-circuits). Thus, S4PR is live if and only if no PA-circuits in it is saturated at all reachable states. A PA-circuits of an S4PR may not be saturated at any state; hence, we propose an integer linear program (ILP) to determine whether a PA-circuits can be saturated or not. Then an algorithm is proposed to compute the set of PA-circuits that may be saturated. This presented method nontrivially generalizes deadlock characterization and liveness condition of ordinary Petri nets to a broader class of nonordinary ones.

So far, the majority of deadlock control policies for automated manufacturing systems (AMSs) are based on the assumption that no resource fails; while for AMSs with unreliable resources, the main concerns are deadlock avoidance problems. This paper focuses on the robust deadlock prevention problem for AMSs with a type of unreliable resources, and assumes that at most one of unreliable resources fails at a time. Petri net is introduced to model the considered AMS. Deadlock can be characterized in terms of maximal perfect resource transition-circuits (MPRT-circuits). To develop robust Petri net deadlock controllers with small structures for the system, a new concept of strong transition covers is presented, which is a special kind of transition covers. By designing a control place with a proper control variable to each MPRT-circuit in the strong transition cover, a 1-robust Petri net controller is obtained, whereas the control variables can be determined by an integer linear programming. Such a 1-robust controller ensures that the system can process all types of parts infinitely even if one of unreliable resources fails. Since the number of MPRT-circuits in a strong transition cover is much less than that of all MPRT-circuits, our Petri net controller is of small structural size. Each AMS with a type of unreliable resources has at least a transition cover. An algorithm is presented for checking the strongness of transition covers, and transforming weak transition covers into strong ones. Finally, some examples are given to illustrate the effectiveness of the proposed method.