Petri net based process scheduling: A model of the control system of flexible manufacturing systems

In this paper, we propose a class of algorithms for the sub-optimal solution of a particular class of problems of process scheduling, particularly focusing on a case study in the area of flexible manufacturing systems (FMSs). The general class of problems we face in our approach is characterized as follows: there is a set of concurrent processes, each formed by a number of temporally related tasks (segments). Tasks are executable by alternate resource sets, different both in performance and costs. Processes and tasks are characterized by release times, due dates, and deadlines. Time constraints are also present in the availability of each resource in resource sets. It has been proven that such a problem does not admit an algorithm for an optimal solution in polynomial time. Our proposed algorithm finds a sub-optimal schedule according to a set of optimization criteria, based on task and process times (earliness, tardiness), and/or time independent costs of resources. Our approach to process scheduling is based on Timed Coloured Petri Nets. We describe the structure of the coordination and scheduling algorithms, concentrating on (i) the general-purpose component, and (ii) the application-dependent component. In particular, the paper focuses on the following issues: (i) theautomatic synthesis of Petri net models of the coordination subsystem, starting from the problem knowledge base; (ii) the dynamic behavior of the coordination subsystem, whose kernel is a High Level Petri net executor, a coordination process based on an original, general purpose algorithm; (iii) the structure of the real-time scheduling subsystem, based on particular heuristic sub-optimal multi-criteria algorithms. Furthermore, the paper defines the interaction mechanisms between the coordination and scheduling subsystems. Our approach clearly distinguishes the mechanism of the net execution from the decision support system. Two conceptually distinct levels, which correspond to two different, interacting implementation modules in the prototype CASE tool, have been defined: theexecutor and thescheduler levels. One of the outstanding differences between these levels is that the executor is conceived as a fast, efficient coordination process, without special-purpose problem-solving capabilities in case of conflicts. The scheduler, on the other hand, is the adaptive, distributed component, whose behavior may heavily depend on the problem class. If the scheduler fails, the executor is, in any case, able to proceed with a general-purpose conflict resolution strategy. Experimental results on the real-time performance of the kernel of the implemented system are finally shown in the paper. The approach described in this paper is at the basis of a joint project with industrial partners for the development of a CASE tool for the simulation of blast furnaces.     

Integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems

This paper presents some results of integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems. The intention of this research is to use predicate transition nets as a specification method and to use first order temporal logic as a verification method so that their strengths — the easy comprehension of predicate transition nets and the reasoning power of first order temporal logic can be combined. In this paper, a theoretical relationship between the computation models of these two formalisms is presented; an algorithm for systematically translating a predicate transition net into a corresponding temporal logic system is outlined; and a special temporal refutation proof technique is proposed and illustrated in verifying various concurrent properties of the predicate transition net specification of the five dining philosophers problem.     

Robust design of flexible manufacturing systems using, colored Petri net and genetic algorithm

A method is presented for the robust design of flexible manufacturing systems (FMS) that undergo the forecasted product plan variations. The resource allocation and the operation schedule of a FMS are modeled as a colored Petri net and an associated transition firing sequence. The robust design of the colored Petri net model is formulated as a multi-objective optimization problem that simultaneously minimizes the production costs under multiple production plans (batch sizes for all jobs), and the reconfiguration cost due to production plan changes. A genetic algorithm, coupled with the shortest imminent operation time (SIO) dispatching rule, is used to simultaneously find the near-optimal resource allocation and the event-driven schedule of a colored Petri net. The resulting Petri net is then compared with the Petri nets optimized for a particular production plan in order to address the effectiveness of the robustness optimization. The simulation results suggest that the proposed robustness optimization scheme should be considered when the products are moderately different in their job specifications so that optimizing for a particular production plan creates inevitably bottlenecks in product flow and/or deadlock under other production plans.     

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     

Time matrix controller design of flexible manufacturing systems

A matrix framework that based on the Petri nets theory (PNs) and the standard industrial engineering (IE) techniques were adopted into this paper. In this paper, the operational times are modeled and introduced into the matrix system model to activate the matrix system functioning. Different types of time include parts input, for operations and processing, for resources arriving, and time for finished goods or products output are developed for designing manufacturing systems. Therefore, different time matrices Ts (i.e., T_u, T_v, T_r, T_y) are constructed in this paper. Those time matrices are the key factors for integrating the manufacturing systems to approach the real time manufacturing world. Here, the key procedure for developing those time matrices is to develop and integrate the manufacturing matrix framework with the techniques of max/plus algebra. The result of this paper is to introduce and establish time into the matrix manufacturing system to approach the real world production situation. System simulation is also provided in this paper to demonstrate the integration between matrix formulation and time matrices.     

Expert systems: An application in flexible manufacturing

Flexible manufacturing systems (FMS) are needed to provide manufacturing operations with the capability to adjust, in real time, to changes in the manufacturing environment. Realization of the goals of flexible manufacturing is governed by the ability of the FMS to maintain adequate information on the factory to assist in generating scenarios from product planning to operations and performance. This leads to a view where the factory is represented as an integrated information system. To facilitate the analysis of information requirements and the design of information systems for flexible manufacturing, an expert support system (ESS) which can be used to model and study the various structures is described. This ESS uses the information cell model to build these information structures. Petri net representations of these structures and their interactions are then constructed. The ESS may now be used to exercise these models and study their performance using time and cost measures.     

Real-time feedback scheduling of flexible manufacturing systems

A genetic manufacturing environment is considered. The emphasis is on small-lot, discrete, and asynchronous type of manufacturing systems rather than high volume and continuous type. Two classes of scheduling policies are proposed to render the machine stable. The policies are of feedback type. The decision is made in real-time and on-line.     

Modeling and formal verification of embedded systems based on a Petri net representation

In this paper we concentrate on aspects related to modeling and formal verification of embedded systems. First, we define a formal model of computation for embedded systems based on Petri nets that can capture important features of such systems and allows their representation at different levels of granularity. Our modeling formalism has a well-defined semantics so that it supports a precise representation of the system, the use of formal methods to verify its correctness, and the automation of different tasks along the design process. Second, we propose an approach to the problem of formal verification of embedded systems represented in our modeling formalism. We make use of model checking to prove whether certain properties, expressed as temporal logic formulas, hold with respect to the system model. We introduce a systematic procedure to translate our model into timed automata so that it is possible to use available model checking tools. We propose two strategies for improving the verification efficiency, the first by applying correctness-preserving transformations and the second by exploring the degree of parallelism characteristic to the system. Some examples, including a realistic industrial case, demonstrate the efficiency of our approach on practical applications.     

Reconfigurable manufacturing systems: Key to future manufacturing

Presented in this article is a review of manufacturing techniques and introduction of reconfigurable manufacturing systems; a new paradigm in manufacturing which is designed for rapid adjustment of production capacity and functionality, in response to new market conditions. A definition of reconfigurable manufacturing systems is outlined and an overview of available manufacturing techniques, their key drivers and enablers, and their impacts, achievements and limitations is presented. A historical review of manufacturing from the point-of-view of the major developments in the market, technology and sciences issues affecting manufacturing is provided. The new requirements for manufacturing are discussed and characteristics of reconfigurable manufacturing systems and their key role in future manufacturing are explained. The paper is concluded with a brief review of specific technologies and research issues related to RMSs.     

Collaborative reconfiguration mechanism for holonic manufacturing systems

Although holonic manufacturing systems (HMS) are recognized as a paradigm to cope with the changes in manufacturing environment based on a flexible architecture, development of reconfiguration mechanism is required to realize the advantages of HMS. Finding a solution from scratch to deal with changes in HMS is not an appropriate approach as it may lead to chaos at the shop floor. The objective of this paper is to propose a viable design methodology to achieve effective reconfiguration in HMS based on the cooperation of holons. We formulate and study a holarchy reconfiguration problem and define an impact function to characterize the impact of resource failures on different holons in a holarchy. A collaborative reconfiguration algorithm based on the impact function is proposed to effectively reconfigure the systems to achieve minimal cost solutions.     

Formal methods integration for the specification of dependable distributed systems

This paper describes a real-world case study in the specification and analysis of dependable distributed systems. The case study is an automated transport system with safety requirements. In order to manage the complexity of the problem of specifying the dynamic behavior of the whole system, a compositional approach is used, based on the integration of the trace logic of the Communicating Sequential Processes (CSP) theory, and stochastic Petri nets (SPNs). It is argued that the integration of different formal methods is a useful approach in the definition of practical engineering methodologies for the specification, design and analysis of complex dependable distributed systems.     

Holarchy formation and optimization in holonic manufacturing systems with contract net

Holonic manufacturing systems (HMS) is based on the notion of holon, an autonomous, cooperative and intelligent entity to provide a econfigurable, flexible and decentralized manufacturing environment to respond to changing needs and opportunities. A set of holons that cooperate to achieve a goal forms a holarchy. How to design a mechanism to form a holarchy to achieve a goal while minimizing the overall cost is a challenge. The objectives of this paper are to propose models and develop collaborative algorithms to guide the holons to form a holarchy to coherently move toward the desired goal state ultimately. We adopt contract net protocol (CNP) to model mutual selection of holons in forming a holarchy. We formulate a holarchy optimization problem to minimize the cost subject to the feasibility constraints. To analyze the feasibility of a holarchy, a Petri net (PN) model is proposed. As classical PN models do not take into account the cost involved in firing transitions, we augment the PN model with cost functions in the problem formulation. Due to the distributed architecture of HMS, the internal structure of each potential holarchy that acts as bidder in CNP is not available to the manager. A key issue is to determine the feasibility of a holarchy without constructing the whole PN model of the given hierarchy. We study the feasible conditions for a holarchy and propose a collaborative algorithm to analyze the feasibility and award contracts to holons without constructing the whole model of a holarchy.     

Model and control holonic manufacturing systems based on fusion of contract nets and Petri nets

Holonic manufacturing systems (HMS) can be modeled as multi-agent systems to which contract net protocol can be effectively and robustly applied. However, the lack of analysis capability of contract nets makes it difficult to avoid undesirable states such as deadlocks in HMS. This paper presents a framework to model and control HMS based on fusion of Petri net and multi-agent system theory. The main results include: (1) a multi-agent model and a collaboration process to form commitment graphs in HMS based on contract net protocol, (2) a procedure to convert commitment graph to collaborative Petri net (CPN), and (3) feasible conditions and collaborative algorithms to award contracts in HMS based on CPNs.     

A component framework for system modeling based on high-level replacement systems

The aim of this paper is to present a generic component framework for system modeling that satisfies main requirements for component-based development in software engineering. In this sense, we have defined a framework that can be used, by providing an adequate instantiation, in connection with a large class of semi-formal and formal modeling techniques. Moreover, the framework is also flexible with respect to the connection of components, providing a compositional semantics of components. This means more precisely that the semantics of a system can be inferred from the semantics of its components. In contrast to other component concepts for data type specification techniques, our component framework is based on a generic notion of transformations. In particular, refinements and transformations are used to express intradependencies, between the export interface and the body of a component, and interdependencies, between the import and the export interfaces of different components. The generic component framework generalizes module concepts for different kinds of Petri nets and graph transformation systems proposed in the literature, and seems to be also suitable for visual modeling techniques, including parts of the UML, if these techniques provide a suitable refinement or transformation concept. In this paper the generic approach is instantiated in two steps. First to high-level replacement systems generalizing the transformation concept of graph transformations. In a second step it is further instantiated to low-level and high-level Petri nets. To show applicability we present sample components from a case study in the domain of production automation as proposed in a priority program of the German Research Council (DFG).     

Discrete event diagnosis using labeled Petri nets. An application to manufacturing systems

In this paper an approach to on-line diagnosis of discrete event systems based on labeled Petri nets is presented. The approach is based on the notion of basis markings and justifications and it can be applied both to bounded and unbounded Petri nets whose unobservable subnet is acyclic. Moreover it is shown that, in the case of bounded Petri nets, the most burdensome part of the procedure may be moved off-line, computing a particular graph called Basis Reachability Graph.Finally, the effectiveness of the proposed procedure is analyzed applying a MATLAB diagnosis toolbox we developed to a manufacturing example taken from the literature.     

A three-level knowledge-based system for the generation of live and safe Petri nets for manufacturing systems

New generation manufacturing systems are involved in a transformation process which aims for more reliable production processes and with a lower response time to the demand of the market. This work presents an application of artificial intelligence planning techniques for the automatic generation of the control program for a manufacturing system expressed as a safe and live Petri net. The advantage of the system presented here is straightforward: it allows for a fast generation of sound results free of human errors, reducing the cost and duration of the development phase of control programs.     

基于变迁覆盖的制造系统死锁控制策略

基于系统Petri网模型,研究柔性制造系统的死锁控制问题.论文利用变迁覆盖为系统设计活性控制器.变迁覆盖是由一组极大完备资源变迁回路组成的集合,其变迁集覆盖了Petri网中所有极大完备资源变迁回路的变迁集.验证变迁覆盖的有效性,然后仅对有效变迁覆盖中的极大完备资源变迁回路添加控制位置,就得到系统的活性受控Petri网.这种受控Petri网包含的控制位置个数少,从而结构相对简单.最后通过一个例子说明了所提出的死锁控制策略的构成与特点.     

An Efficient Method for Computing Exact State Space of Petri Nets With Stopwatches

In this paper, we address the issue of the formal verification of real-time systems in the context of a preemptive scheduling policy. We propose an algorithm which computes the state-space of the system, modeled as a time Petri net with stopwatches, exactly and efficiently, by the use of Difference Bounds Matrices (DBM) whenever possible and automatically switching to more time and memory consuming general (convex) polyhedra only when required. We propose a necessary and sufficient condition for the need of general polyhedra. We give experimental results comparing our implementation of the method to a full DBM over-approximation and to an exact computation with only general polyhedra.