Synthesis of liveness enforcing supervisor for automated manufacturing systems using insufficiently marked siphons

A liveness enforcing supervisor synthesis technique is presented for Petri net modeling automated manufacturing systems. The insufficiently marked siphons are deployed to characterize the deadlock situations in an incidence matrix based way, which makes possible the study of the modeled systems from both structural and algebraic perspectives. The approach generates at each step a generalized mutual exclusion constraint which contains only markings for which liveness can be enforced. To avoid the explicit enumeration of all the set of strict minimal siphons, a set of mathematical programming formulations are established to implement the derivation of insufficiently marked siphons from the PT-transformation of the plant system. Further, a generalized elementary siphon control approach is involved such that the final supervisor can be structurally simplified. Several examples are used to illustrate these results.     

On structural minimality of optimal supervisors for flexible manufacturing systems

This paper develops a place invariant based deadlock prevention method to obtain an optimal, i.e., maximally permissive, liveness-enforcing Petri net supervisor with a minimal supervisory structure that means the minimal number of control places. Maximal permissiveness can be achieved by designing place invariants that make all legal markings reachable while all first-met bad markings unreachable. An integer linear programming problem is formulated to compute all place invariants and its objective function minimizes the number of place invariants, aiming to yield a minimal supervisory structure. Importantly, we develop a technique to greatly improve the efficiency of the proposed method by reducing the number of constraints and variables in the integer linear programming problem under consideration. A number of examples from the literature are used to illustrate the proposed approaches.     

Autonomy-subnet based structural synthesis and liveness guarantying policy of Petri net model of flexible manufacturing system

In this paper, an autonomous subnet based structural methodology forbottom-up synthesis of Petri Nets for Flexible Manufacturing Systems is proposed.Furthermore, the theoretical analysis of the model constructed by the method is carried byintensively using model's structural information, such as invariants, siphons, etc.. As aresult, the analysis leads us to draw the general conclusion that the model obtained isconservativeness and thus bound, and characterize its liveness in terms of zero-markingminimal siphons. It is based on model's structural information that distinguishes ourmethod from others. in line of this thought, a liveness guarantying policy for the obtainedmodel is proposed. Some control subnets are merged into the original model according tothe proposed synthesis rules in this paper to ensure that no minimal siphons are emptiedin any state, therefore the liveness is guaranteed. As a result, a live, conservative andrevertible Petri Nets is obtained. A practical example is also presented to     

A survey of flexible manufacturing systems

In this report, the different flexible manufacturing systems used for machining and assembling in the following countries are reviewed: the United States, Japan, the Federal Republic of Germany, the German Democratic Republic, Italy, Great Britain, Sweden, Norway, France, Czechoslovakia and Hungary.Three categories of systems discussed are (1) flexible modules and units, (2) flexible transfer lines, and (3) “unaligned” flexible systems. Within each category are several sub-groups, divided up mainly according to the conveyor system and operating mode. This classification shows the effective French position in this field.     

Design of liveness-enforcing supervisors with simpler structures for deadlock-free operations in flexible manufacturing systems using necessary siphons

Siphons can be used to characterize deadlock states and solve deadlock problems in Petri nets that model flexible manufacturing systems. This paper presents an iterative siphon-based control (ISC) deadlock prevention policy for Petri nets via the combination of mixed integer programming (MIP) and the concept of necessary siphons (NSs). At each iteration in this ISC policy, a maximal deadly marked siphon that is closely related to deadlocks in a Petri net can be conveniently found by an MIP-based deadlock detection method. Then the places in it are classified and an NS is derived from the classified places. For each NS found, depending on its complementary set, the proposed policy adds a proper control place (CP) to make it marked (max-controlled). Moreover, during the ISC procedure, a test for redundant NSs is carried out under a certain condition in order to avoid the addition of the corresponding CPs. The siphon control process proceeds iteratively until the controlled system is live. Compared with the existing approaches, the proposed policy usually leads to a structurally simple liveness-enforcing supervisor by adding as few CPs as possible and achieves better control results. Some examples are introduced to illustrate the proposed approach.     

A framework for synthesis of communicating decentralised supervisors for discrete-event systems

We propose a framework to study communication among decentralised supervisors for a (distributed) discrete-event system (DES), where system specifications lack co-observability. Using agent-wise labeling maps (ALMs), the framework explores the observation and control structures of an already designed centralised supervisor in a distributed manner, and represent them as polynomial equations over a finite field. Communication is naturally required to re-evaluate the equations, which depend on distributed information, correctly, and is formalised and implemented using communication events. The framework generalises the authors’ previous work on extended finite-state machines (EFSMs) by formalising system representation and communication events, proving the correctness of proposed communication policies, and algorithmic simplification of polynomial equations. This provides a systematic procedure for the synthesis of decentralised supervisors and formalisation, computation and implementation of the communication.     

A methodology for economic justification of flexible manufacturing systems

This paper develops a model for the economic justification of flexible manufacturing systems. The proposed model considers the intangible and tangible benefits resulting from the implementation of advanced computer controlled manufacturing systems. The model's structure consists of a top down approach which identifies and measures the desirability of the firm's global (strategic) as well as local (tactical) objectives.     

Path-clearing policies for flexible manufacturing systems

In practical manufacturing settings it is often possible to obtain, in real-time, information about the operation of several machines in a flexible manufacturing system (FMS) that can be quite useful in scheduling part flows. The authors introduce some scheduling policies that can effectively utilize such information and they provide sufficient conditions for the stability of two such policies     

Tool-provisioning strategies for flexible manufacturing systems

The difficulties encountered in managing the tool flow in flexible manufacturing systems for the manufacture of prismatic parts indicate the requirement to handle operational issues such as tool assignment. The choice of operational strategy and its relationship to machine specification, work and tool loading, scheduling and specific mode of tool management may significantly enhance machine utilization and work throughput. In this paper, strategies are presented aimed at improving system efficiency and minimizing tooling costs by considering tool provision as work-orientated, where the tooling is changed to suit the production task, or tool-orientated, where resident tools dictate the work flow, or a combination of the two. This paper draws on evidence from current industrial practice and recent developments.     

A decision support algorithm for flexible manufacturing systems control

An application of a modification of Petri nets to mathematical modeling of discrete production processes utilized for a simulation of the flexible manufacturing systems is presented and an algorithm for the support of decision making in the control process of such systems based on the system model analysis is created. The algorithm makes the choice of a suitable control strategy possible in such a way that it automatically generates all potentially possible control strategies, automatically chooses the really possible ones and gives to an operator the chance to choose the most suitable realizable control strategy from the technological point of view.     

基于Petri网的柔性制造系统无死锁遗传调度算法

对以最小化加工时间为目标的柔性制造系统无死锁调度问题, 提出了一种遗传调度算法. 算法考虑到同类工件具有预先确定的相同加工路径, 而各工序的处理时间与工件有关. 用Petri网对工序和资源分配进行逻辑建模,利用遗传算法, 采用工序自然编码方式, 基于系统的最佳避免死锁Petri网控制器, 检测染色体的可行性, 修复不可行染色体使其对应的调度满足资源约束和无死锁控制约束, 从而保证算法所利用的所有染色体都对应系统的可行调度. 仿真结果表明了算法的可行性和有效性.     

Optimal deadlock avoidance Petri net supervisors for automated manufacturing systems

Deadlock avoidance problems are investigated for automated manufacturing systems with flexible routings. Based on the Petri net models of the systems, this paper proposes, for the first time, the concept of perfect maximal resourcetransition circuits and their saturated states. The concept facilities the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reach their saturated states. For a large class of manufacturing systems, which do not contain center resources, the optimal deadlock avoidance Petri net supervisors are presented. For an general manufacturing system, a method is proposed for reducing the system Petri net model so that the reduced model does not contain center resources and, hence, has optimal deadlock avoidance Petri net supervisor. The controlled reduced Petri net model can then be used as the liveness supervisor of the system.     

Optimal deadlock avoidance Petri net supervisors for automated manufacturing systems

Deadlock avoidance problems are investigated for automated manufacturing systems with flexible routings. Based on the Petri net models of the systems, this paper proposes, for the first time, the concept of perfect maximal resource-transition circuits and their saturated states. The concept facilitates the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reaching their saturated states. For a large class of manufacturing systems, which do not contain center resources, the optimal deadlock avoidance Petri net supervisors are presented. For a general manufacturing system, a method is proposed for reducing the system Petri net model so that the reduced model does not contain center resources and, hence, has optimal deadlock avoidance Petri net supervisor. The controlled reduced Petri net model can then be used as the liveness supervisor of the system.     

Exploiting symmetry in the synthesis of supervisors for discreteevent systems

We investigate a method to exploit the symmetry inherent to many discrete-event systems in order to reduce the computational complexity of the supervisory control problem (SCP). We characterize symmetry using notions of group theory and derive conditions under which there exists a quotient (reduced) automaton representation for a language with, in general, a much smaller state space than the original minimal (in number of states) automaton representation for the language. We then propose an algorithm to synthesize a solution to the SCP which is similar to the classical one, but performed on reduced automata. Special attention is given to the particular case of systems whose models contain similar components. The approach is illustrated by an example of control of a small production line     

Phase change fixturing for flexible manufacturing systems

Fixturing is fundamental to many manufacturing operations, hence, if computer integrated flexible manufacturing systems are to be truly flexible, then the fixturing must also be flexible. That is, it must be capable of accomodating parts of different geometries and sizes. This paper reports on an innovative class of flexible fixtures which utilizes materials that undergo a phase change between solid and liquid states. When in the liquid state, the fixturing medium can accommodate a wide variety of different part geometries, while in the solid state the part is held fixed. A mathematical model is developed which governs the holding ability of a particular class of these fixtures and some results of parametric computer studies are then presented.     

Stable scheduling policies for flexible manufacturing systems

In this brief note we provide a new analysis of the transient behavior of the clear-a-fraction policy of Perkins and Kumar (1989). In addition, we show that a new “clear-average-oldest-buffer” policy and a “random part selection” policy (of which “first-come-first-served” is a special case) are stable. Finally, we introduce a stable and efficient “stream modifier” that can be used to obtain network level stability results     

Automated formal verification for flexible manufacturing systems

We present an effective approach to perform formal verification of properties of interest of production systems whose behavior is modeled through Stateflow diagrams. The approach hinges on a semantics of Stateflow diagrams given in terms of formulae of a metric temporal logic. The semantics has been implemented in a fully automated tool through which users can define a wide range of properties of interest and then check if they hold for the system. We illustrate the approach and the use of the tool through a realistic case study. The verification technique allowed us to uncover a previously undetected error in the design of the system.     

Functions required for advanced flexible manufacturing systems

This paper describes the concept and functions of multilevel supervisory systems aimed at a more efficient operation of advanced flexible manufacturing systems. A supervisory system consists of a control system, an adaptation system, a process monitoring system and a machine failure diagnosis system. Thus supervisory system assure the control of machining accuracy, the detection of human errors and tool breakage, and the identification of machine failures. This paper presents some successful results of the implementation of these subsystems.     

Robots in flexible manufacturing systems

The use of computer controlled manufacturing systems incorporating robots and flexible control is of paramount interest today. A number of economists have noted that strength in high technology industries such as aircraft, missiles, communications, electronic and computers, in contrast to older industries, gives the economy of any country strong long-term growth prospects.During the past two decades, the concept of a flexible, programmable automation device, which has come to be known as an “industrial robot”, has become a reality. A variety of these automation modules have been developed, offering a wide range of capabilities and application possibilities. Robots currently help weld, cast, form, assemble, machine, transfer, inspect, load and unload parts into and out of a number of differing machines and processes.The first part of this paper analyzes the significance of FMS in industries today. The second part of the paper attempts to evaluate some of the areas of savings as a result of using robots.     

Design of T-liveness enforcing supervisors in Petri nets

This paper presents a procedure for the design of supervisors that enforce the transitions in a given set T to be live. T-liveness enforcement corresponds to full liveness enforcement when T equals the total set of transitions. Rather than assuming a given initial marking, this procedure generates at every iteration a convex set of admissible initial markings. In the case of full liveness enforcement and under certain conditions also in the case of T-liveness enforcement, the convex set of each iteration includes the set of markings for which liveness/T-liveness can be enforced. When the procedure terminates, and if it terminates, the final convex set contains only markings for which T-liveness can be enforced. Then, the supervisor keeping the Petri net (PN) marking in this convex set can be easily designed using the place invariant based approach. This paper focuses on the fully controllable and observable PNs. Several extensions of the procedure, including to partially controllable and observable PNs, are outlined.