Search

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 PRT-circuits, 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. [ABSTRACT FROM AUTHOR]

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.Note to Practitioners—In the context of AMS, liveness is the most important property since it implies that there is no partial deadlock during the system evolution, and hence, all part types can be produced smoothly. We study the problem of liveness for AMS with the most general resource allocation and flexible routing, which can be modeled by S4PRs or disjunctive/conjunctive (D/C) resource allocation systems (RASs). Given such a complex AMS, based on its Petri net model, this paper presents a sufficient and necessary liveness condition by utilizing the structural properties, and develops an algorithm to identify all the structural objects that may lead the systems to deadlocks. This paper is significant in liveness-enforcing supervisor design for S4PR. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]