Liveness Analysis And Deadlock Control For Flexible Manufacturing Systems

As an indispensable component of contemporary advanced manufacturing systems, flexible manufacturing systems (FMSs) possess flexibility and agility that traditional manufactur-ing systems lack. Flexible manufacturing systems are computer-controlled systems that usually consist of computer numerically controlled machine tools, buffers, fixtures, robots, automated guided vehicles (AGVs), and other material-handling devices, some of which are recognized as their shared resources. From a methodological and formal viewpoint, an FMS belongs to resource allocation systems. The resources in an FMS can be dynamically configured and allocated according to changeable product specifications. By sharing the re-sources, multiple different raw workpieces are concurrently processed in an FMS to meet variable manufacturing need for high-mix-low-volume products. Due to the competition for limited resources among concurrently executed processes, deadlocks arising in an FMS can cause a series of disturbing issues. A variety of deadlock control methods are developed for deadlock problems in automated flexible manufacturing systems such as operating systems, multiprocessing, and distributed systems. Therefore, the analysis and control of deadlock in FMSs are imperative.Deadlock-freedom means that concurrent production processes in all FMSs will never stag-nate. Furthermore, liveness is undoubtedly one of the most important properties of FMSs. Inversely, nonliveness is usually undesirable in an FMS. Liveness implies deadlock-freedom, but not vice versa. Once a system is not live, some events may never be executed, often caus-ing local and global deadlocks. As for those systems closely related to the safety of life and critical infrastructures, once deadlocks in such a system occur, the losses of lives and prop-erties would be heavy. Nowadays, liveness checking is a hot but difficult issue, as there exists no efficient method to solve it in general. As a powerful mathematical tool, Petri nets are widely used to model, analyze, and control of discrete event systems (DESs), including flexible manufacturing systems, workflow management systems, and automated guided ve-hicles. Liveness of a Petri net model implies that every operation in a modeled system can become executable starting from any state, thereby ensuring the absence of global and local deadlocks.This dissertation focuses on liveness checking and deadlock control of flexible manufactur-ing systems by utilizing the net structures of related modeled Petri nets. The main results of this research are as follows.1. For a class of Petri nets, which is called a weighted S3PR (WS3PR), this research takes the full advantage of the net structure of a WS3PR. Accordingly, the relationship between the markings of resource places and their input and output arc weights is analyzed, which can be used to restrict the allocation of system resources. The concepts of α-transitions and β-transitions are proposed to reveal the numerical combinational relation among all the arc weights of input transitions and the marking of a resource place. By utilizing related properties of strongly connected components and trees, a simple and graphical method to check liveness given a marked WS3PR is presented.Finally, sufficient conditions to check liveness of WS3PR are established.2. A linear system of simple sequential processes with resources (LS3PR) is a subclass of S3PR. As an extension and application of the approach for checking liveness of WS3PR, this study proposes a resource configuration method for liveness of an LS3PR. The relationship between the markings of resource places and process idle places is analyzed and used to restrict the configuration of system resources. We take the full advantages of the net structure characteristics of an LS3PR and utilize related knowledge of resource subnets. Next, an algorithm used to compute the marking for each resource place in an LS3PR is developed by taking the full advantages of resource subnets. Finally, the computational complexity of the algorithm is proved to be polynomial.3. From a technical perspective, most of the control policies resolving deadlocks are devel-oped via the state space analysis or structural analysis of Petri nets. This research develops a deadlock prevention policy based on resources reallocation and supervisor reconfigura-tion. First, given a plant model, we reallocate the marking of each resource place to be one, obtaining a net model whose reachable states are much less than that of the original one. In this case, we find a controlled system for it by using the theory of regions. Next, the markings of the resource places in the controlled system are restored to their original ones. Without changing the structure of the obtained controlled system, we compute the markings of the monitors gradually, which can be realized by two algorithms proposed in this study. Finally, we decide a marking for each monitor such that it makes the controlled system live with nearly optimal permissive behavior. Two FMS examples are used to illustrate the application of the proposed method and show its superior efficiency.4. For a class of Petri nets called systems of simple sequential processes with resources (S3PR), the concepts of critical resource places and their related multi-way holder places are first proposed in this research. Next, by analyzing the structural properties of the critical re-source places and their related loop resource subsets, sufficient conditions for loop resource subsets to derive SMSs are established. Finally, based on the proposed results, all SMSs can be obtained from their related loop resource subsets in an S3PR net.Finally, conclusions and future research studies on the liveness analysis and deadlock control for FMSs are illustrated.