Real-time scheduling of batch systems using Petri nets and linear logic

This paper presents an approach to model, design and verify scenarios of real-time systems used in the scheduling and global coordination of batch systems. The initial requirements of a system specified with sequence diagrams are translated into a single p-time Petri net model representing the global behavior of the system. For the Petri net fragments involved in conflicts, symbolic production and consumption dates assigned to tokens are calculated based on the sequent calculus of linear logic. These dates are then used for off-line conflict resolution within a token player algorithm used for scenario verification of real-time specifications and which can be seen as a simulation tool for UML interaction diagrams.     

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.     

Combining flow control techniques with Petri nets methodologies for real-time control of FMS

This paper focuses on the combination of the flow control techniques with Petri net methodologies. The flow control techniques are improved in order to handle multiple routing. A general and unified Petri net formalism is introduced. The integration of the flow control techniques with an interpreter based on this new Petri net formalism is discussed. Results for simulation of a very flexible manufacturing system are provided.     

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.     

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.     

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     

基于Petri网的柔性制造系统混惑检测与控制*

已有的混惑检测算法,需要多次遍历Petri网中的所有变迁寻找混惑,比较耗时,不适合应用在复杂的柔性制造系统中。对此提出一种新的混惑检测思路,根据混惑的基本结构特征,首先排除了一些从结构上就不可能出现混惑的库所和变迁,然后在最有可能出现混惑的库所和变迁中去寻找混惑,从而降低了检测混惑的时间复杂度。文章还采用抑止弧对系统中出现的混惑进行了一定的消解控制,最后通过一个柔性制造系统实例对所提出的混惑检测及控制策略进行了验证。     

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.     

Modeling and control of workstation level information flow in FMS using modified Petri nets

A flexible manufacturing system (FMS) has a traditional structure of three levels: cell, workstation, and equipment. The workstation level plays an important role in the overall performance of the FMS. This paper focuses on modeling and control of the FMS workstation level information flow. In order to have a unified workstation level system structure, front-end interfaces are introduced as a standard communication medium between the workstation level and the equipment level. A detailed information flow analysis is then carried out on the workstation level. For modeling purposes, a modified Petri net is proposed with its increased modeling capability over an ordinary Petri net. It associates data structures with places and programs with transitions. Finally, the modified Petri net is used to model and control the FMS workstation level information flow. The designed control system has been implemented in a real manufacturing factory with satisfactory performance.     

Deadlock-free scheduling for flexible manufacturing systems using Petri nets and heuristic search

Deadlock-free control and scheduling are two different problems for flexible manufacturing systems (FMSs). They are significant for improving the behaviors of the systems. Based on the Petri net models of FMSs, this paper embeds deadlock control policies into heuristic search algorithm, and proposes a deadlock-free scheduling algorithm to minimize makespan for FMSs. Scheduling is performed as heuristic search in the reachability graph of the Petri net. The searching process is guided by a heuristic function based on firing count vectors of state equation for the Petri net. By using the one-step look-ahead method in the optimal deadlock control policy, the safety of a state is checked. Experimental results are provided to show effectiveness of the proposed heuristic search approach in deadlock-free scheduling for FMSs.     

Automatic generation of ladder diagram with control Petri Net

This paper presents a design method to generate a ladder diagram (LD) automatically with the control Petri Net (CPN) for control of discrete event system. This method describes the specification of a practical system with the CPN that associates operations with places and conditions with transitions. Based on the firing regulation of transition, the relationship of places, conditions, and events are formulated with Boolean functions. These functions can be easily converted into LD and implemented on a programmable logic controller (PLC). An application example in a liquid mixture system shows that the proposed method is effective and has the advantages of ease of understanding, modification, and maintenance.     

Process modeling and analysis of manufacturing supply chain networks using object-oriented Petri nets

This paper presents a systematic methodology for modeling and analysis of manufacturing supply chain business processes. The proposed approach first employs Computer Integrated Manufacturing Open System Architecture (CIMOSA) behavior rules to model the business process routing structures of manufacturing supply chain networks. Object-oriented predicate/transition nets (OPTNs) are then developed for the modular modeling and analysis of process models. Based on the structure of OPTNs, a procedure to obtain the system's P-invariants through objects’ P-invariants is suggested. From the P-invariants obtained, system structural properties such as deadlock and overflow can be analyzed. By using Petri net unfolding techniques and by extracting the process model of each object from the entire process model, the sequencing analysis for operations in supply chain processes becomes possible. Several manufacturing supply chain examples are used to illustrate the effectiveness of the proposed method.     

Hybrid heuristic search approach for deadlock-free scheduling of flexible manufacturing systems using Petri nets

Based on the Petri net models of flexible manufacturing systems (FMSs), this paper focuses on deadlock-free scheduling problem with the objective of minimizing the makespan. Two hybrid heuristic search algorithms for solving such scheduling problems of FMSs are proposed. To avoid deadlocks, the deadlock control policy is embedded into heuristic search strategies. The proposed algorithms combine the heuristic best-first strategy with the controlled backtracking strategy based on the execution of the Petri nets. The scheduling problem is transformed into a heuristic search problem in the reachability graph of the Petri net, and a schedule is a transition sequence from the initial marking to the final marking in the reachability graph. By using the one-step look-ahead method in the deadlock control policy, the safety of a state in the reachability graph is checked, and hence, deadlock is avoided. Experimental results are provided and indicate the effectiveness of the proposed hybrid heuristic search algorithms in solving deadlock-free scheduling problems of FMSs. Especially, the comparison against previous work shows that both new algorithms are promising in terms of solution quality and computing times.     

The real-time supervisory control of an experimental manufacturing system based on a hybrid method

In this paper, the real-time supervisory control of an experimental manufacturing system is reported based on a recently proposed hybrid (mixed PN/automaton) approach. Assuming that an uncontrolled bounded Petri net (PN) model of a (plant) discrete event system (DES) and a set of forbidden state specifications are given, the proposed approach computes a maximally permissive and nonblocking closed-loop hybrid model. The method is straightforward logically, graphically and technologically. This paper particularly shows the applicability of a hybrid (mixed PN/automaton) approach to low-level real-time DES control. To do this, programmable logic controller (PLC) based real-time control of an experimental manufacturing system is considered.     

间歇式化工系统的Petri网优化调度与控制方法

为了解决复杂间歇式化工系统的优化调度和控制问题,提出了一种基于Petri网的优化调度与控制方法:首先,根据加工工艺,建立加工过程的赋时Petri网模型;其次,根据间歇式化工生产对象的拓扑结构,在该赋时Petri网模型中引入阀门系统的网结构,从而获得系统的受控Petri网模型;最后,利用可达图来计算加工时间最短的控制策略,借助网结构信息,得到了控制策略的阀门控制矩阵,并用一个示例演示验证了本文方法.     

Modeling and scheduling of ratio-driven FMS using unfolding time Petri nets

In this paper, we focus on the analysis of a cyclic schedule for the determination of the optimal cycle time and minimization of the Work in Process (WIP for short). Especially, this paper deals with product ratio-driven FMS cyclic scheduling problem with each other products and ratios using Timed Petri nets unfolding (TPN for short). TPN slicing and unfolding are applied to analyze this FMS model. We can divide original system into subsystem using TPN slices and change iterated cycle module into acyclic module without any loss of other behavior properties.     

Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming

In this article we deal with deadlock prevention problems for S⁴PR, a class of generalised Petri nets, which can well model a large class of flexible manufacturing systems where deadlocks are caused by insufficiently marked siphons. We present a deadlock prevention methodology that is an iterative approach consisting of two stages. The first one is called siphon control, which is to add for each insufficiently marked minimal siphon a control place to the original net. Its objective is to prevent a minimal siphon from being insufficiently marked. The second one, called control-induced siphon control, is to add a control place to the augmented net with its output arcs connecting to the source transitions, which assures that there are no new insufficiently marked siphons generated. At each iteration, a mixed integer programming approach is adopted for generalised Petri nets to obtain an insufficiently marked minimal siphon from the maximal deadly siphon. This way complete siphon enumeration is avoided that is much more time-consuming for a sizeable plant model than the proposed method. The relation of the proposed method and the liveness and reversibility of the controlled net is obtained. Examples are presented to demonstrate the presented method.     

Robust control reconfiguration of resource allocation systems with Petri nets and integer programming

Supervisory control reconfiguration can handle the uncertainties including resource failures and task changes in discrete event systems. It was not addressed to exploit the robustness of closed-loop systems to accommodate some uncertainties in the prior studies. Such exploitation can cost-efficiently achieve reconfigurability and flexibility for real systems. This paper presents a robust reconfiguration method based on Petri nets (PNs) and integer programming for supervisory control of resource allocation systems (RASs) subject to varying resource allocation relationships. An allocation relationship is seen as a control specification while the execution processes requiring resources as an uncontrolled plant. First, a robust reconfiguration mechanism is proposed. It includes updating the P$P$-invariant-based supervisor and evolving the state of the closed-loop system. The latter adapts to the control specification changes by the self-regulation of the closed-loop system’s state. Next, two novel integer programming models for control reconfiguration are proposed, called a reconfiguration model with acceptability and reconfiguration one with specification correction. Since both models integrate the firability condition of transitions, no additional efforts are required for the state reachability analysis. Finally, a hospital emergency service system is used as an example to illustrate them.