Petri nets and genetic algorithms for complex manufacturing systems scheduling

In this paper we propose the GAPN (genetic algorithms and Petri nets) approach, which combines the modelling power of Petri nets with the optimisation capability of genetic algorithms (GAs) for manufacturing systems scheduling. This approach uses both Petri nets to formulate the scheduling problem and GAs for scheduling. Its primary advantage is its ability to model a wide variety of manufacturing systems with no modifications either in the net structure or in the chromosomal representation. In this paper we tested the performance on both classical scheduling problems and on a real life setting of a manufacturer of car seat covers. In particular, such a manufacturing system involves features such as complex project-like routings, assembly operations, and workstations with unrelated parallel machines. The implementation of the algorithm at the company is also discussed. Experiments show the validity of the proposed approach.     

基于随机Petri网的铜带拉弯矫直机可用度分析

为了合理确定铜带拉弯矫直机的校验周期,提高其生产效率,确保其矫直精度,根据某铜板带公司拉弯矫直机9个月的维修数据,对拉弯矫直机的失效模式进行随机Petri网建模,将系统失效模式转换成相应的随机Petri网;基于马尔科夫过程对随机Petri网进行瞬态概率求解,并得到该拉弯矫直机失效模式的稳态概率;利用或门对应的随机Petri网模型分析,计算不同校验周期下拉弯矫直机的可用度.综合考虑设备可用度和经济效益,确定了合理的校验周期,为拉弯矫直机的长周期运行提供了依据.     

Modelling reconfigurable manufacturing systems with coloured timed Petri nets

Reconfigurable manufacturing systems (RMSs) have been acknowledged as a promising means of providing manufacturing companies with the required production capacities and capabilities. This is accomplished through reconfiguring system elements over time for a diverse set of individualised products often required in small quantities and with short delivery lead times. Recognising the importance of dynamic modelling and visualisation in decision-making support in RMSs and the limitations of current research, we propose in this paper to model RMSs with Petri net (PN) techniques with focus on the process of reconfiguring system elements while considering constraints and system performance. In view of the modelling challenges, including variety handling, production variation accommodation, machine selection, and constraint satisfaction, we develop a new formalism of coloured timed PNs. In conjunction with coloured tokens and timing in coloured and timed PNs, we also define a reconfiguration mechanism to meet modelling challenges. An application case from an electronics company producing mobile phone vibration motors is presented. Also reported are system analysis and application results, which show how the proposed formalism can be used in the reconfiguration decision making process.     

Scheduling of flexible manufacturing systems based on Petri nets and hybrid heuristic search

This paper proposes and evaluates a hybrid search strategy and its application to flexible manufacturing system (FMS) scheduling in a Petri net framework. Petri nets can concisely model multiple lot sizes for each job, the strict precedence constraint, multiple kinds of resources, and concurrent activities. To cope with the complexities for FMS scheduling, this paper presents a hybrid heuristic search strategy, which combines the heuristic A* strategy with the DF strategy based on the execution of the Petri nets. The search scheme can invoke quicker termination conditions, and the quality of the search result is controllable. To demonstrate this, the scheduling results are derived and evaluated through a simple FMS with multiple lot sizes for each job. The algorithm is also applied to a set of randomly generated more complex FMSs with such characteristics as limited buffer sizes, multiple resources, and alternative routings.     

Integrated analytical models for flexible manufacturing systems

Product form queueing networks (pfqn) and generalized stochastic Petri nets (gspn) have emerged as the principal performance modelling tools for flexible manufacturing systems (fms). In this paper, we present integratedpfqn-gspn models, which combine the computational efficiency ofpfqn and representational power ofgspn by employing the principle of flow-equivalence. We show thatfms that include nonproduct form characteristics such as dynamic routing and synchronization can be evaluated efficiently and accurately using the integrated models.     

Performance modelling of a fault-tolerant real-time multiprocessor using stochastic Petri nets

The fault-tolerant multiprocessor (ftmp) is a bus-based multiprocessor architecture with real-time and fault-tolerance features and is used in critical aerospace applications. A preliminary performance evaluation is of crucial importance in the design of such systems. In this paper, we review stochastic Petri nets (spn) and developspn-based performance models forftmp. These performance models enable efficient computation of important performance measures such as processing power, bus contention, bus utilization, and waiting times.     

Scheduling manufacturing systems with blocking: a Petri net approach

This paper introduces a Petri net-based approach for scheduling manufacturing systems with blocking. The modelling of the job routings and the resource and blocking constraints is carried out with the Petri net formalism due to their capability of representing dynamic, concurrent discrete-event dynamic systems. In addition Petri nets can detect deadlocks typically found in systems with blocking constraints. The scheduling task is performed with an algorithm that combines the classical A* search with an aggressive node-pruning strategy. Tests were conducted on a variety of manufacturing systems that included classical job shop, flexible job shop and flexible manufacturing scheduling problems. The optimisation criterion was makespan. The experiments show that the algorithm performed well in all types of problems both in terms of solution quality and computing times.     

Supply chain configuration with co-ordinated product,process and logistics decisions: an approach based on Petri nets

Supply chain configuration lends itself to be an effective means to deal with product differentiation and customisation throughout a supply chain network. It essentially entails the instantiation of a generic supply chain network to specific supply chains in accordance with diverse customer requirements. The lynchpin of supply chain configuration lies in the co-ordination of product, process and logistics decisions in relation to a variety of customer orders. This paper aims to provide modelling support to supply chain configuration. The ultimate goal is to assist companies to form appropriate supply chains with the most added-value to customer order fulfillment. A formalism based on coloured Petri nets is developed for configuring supply chains. System models are built upon the coloured Petri nets and used to incorporate product and process concerns into the supply chain configuration process. An industrial case study is reported to illustrate the potential of the coloured Petri net modelling formalism and the built system models for supply chain configuration.     

Modelling and simulation of a bottling plant using hybrid Petri nets

In this paper we use First–Order Hybrid Petri nets (FOHPN), an hybrid model that combines fluid and discrete event dynamics, to model the concurrent activities of manufacturing systems. In particular we consider an existing mineral water bottling plant and we show how the FOHPN model is extremely suited to describe the high-throughput production lines, that are one of the main components in the considered plant. Some variations with respect to the previous definition of the FOHPN model are also introduced here to better describe the behavior of the conveyor lines. Finally, we show that, thanks to the fluid approximation of some discrete-event dynamics, the considered plant may also be efficiently simulated using FOHPN. This also enabled us to identify, among the most commonly used configurations of the plant, which are the optimal working conditions in terms of maximal throughput and net profit.     

Modeling of system reliability Petri nets with aging tokens

The paper addresses the dynamic modeling of degrading and repairable complex systems. Emphasis is placed on the convenience of modeling for the end user, with special attention being paid to the modeling part of a problem, which is considered to be decoupled from the choice of solution algorithms. Depending on the nature of the problem, these solution algorithms can include discrete event simulation or numerical solution of the differential equations that govern underlying stochastic processes. Such modularity allows a focus on the needs of system reliability modeling and tailoring of the modeling formalism accordingly. To this end, several salient features are chosen from the multitude of existing extensions of Petri nets, and a new concept of aging tokens (tokens with memory) is introduced. The resulting framework provides for flexible and transparent graphical modeling with excellent representational power that is particularly suited for system reliability modeling with non-exponentially distributed firing times. The new framework is compared with existing Petri-net approaches and other system reliability modeling techniques such as reliability block diagrams and fault trees. The relative differences are emphasized and illustrated with several examples, including modeling of load sharing, imperfect repair of pooled items, multiphase missions, and damage-tolerant maintenance. Finally, a simple implementation of the framework using discrete event simulation is described.     

Optimal manufacturing policy in a reverse logistic system with dependent stochastic returns and limited capacities

The stochastic models of systems with reverse logistics usually assume that the quantity of products returned is independent of sales. This hypothesis is obviously not true and can lead to suboptimal production policies. In this paper a new sales-dependent returns model is described. In this model, the returns depend on the useful life of the products sold and on the probability of an end-of-life product being returned. A Markov decision problem is formulated in order to obtain the optimal manufacturing policy. A numerical example is provided to illustrate the use of the defined model. An approximated Markov decision model is defined where the optimal policy is easily obtained. The optimal policies of the original and the approximated models are compared.     

Hybrid Petri net and digraph approach for deadlock prevention in automated manufacturing systems

This paper proposes a hybrid approach to deadlock prevention in automated manufacturing systems that combines Petri nets (PNs) and digraphs, so taking advantage of the strong points of both techniques. The approach uses digraphs to make the detection of deadlock conditions easier and then translates the obtained information in empty siphons of the PN modelling the same system. The proposed methodology allows the implementation of new PN‐based deadlock prevention control policies. A case study and the simulation results show the benefits of the new control strategies.     

Transient inter-production scheduling based on Petri nets and constraint programming

In this article, we focus on the transient inter-production scheduling problem between two cyclic productions in the framework of flexible manufacturing systems. This problem is first formulated as a reachability problem in timed Petri nets (TPN), then solved using a methodology based on constraint programming. Our work is based on the controlled executions proposed by Chretienne to model the sequence of transition firing dates. Our methodology is based on a preliminary resolution of the state equation between initial and final states in the underlying non-TPN. Then, we choose a duration T _max corresponding to the maximal duration time of the scheduling. For each solution S of the state equation, we build a controlled execution from the sequence of firings in S. After the propagation of firing date constraints and reachability constraints in the TPN, we use constraint programming to enumerate the set of feasible controlled executions.     

Deadlock modeling and control of semiconductor track systems using resource-oriented Petri nets

This paper addresses the deadlock avoidance problem in track systems in semiconductor fabrication. For the system without buffer space in it, the existing deadlock avoidance policies tend to be too conservative. Routing flexibility provides a chance to develop better ones, but makes their computation more complex. This paper models a track system using coloured resource-oriented Petri net (CROPN). Based on the model, a sufficient condition for deadlock-free operation and the corresponding control law are presented. This proposed policy is shown computationally efficient and less conservative than existing methods. An example is presented to demonstrate its application.     

Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets

This paper addresses the problem of real-time deadlock-free scheduling for a semiconductor track system. The system is required to process wafers continuously, cassette by cassette. The process is not necessarily a repeated one. In addition, the system is deadlock-prone and its modules are failure-prone. Thus, real-time scheduling approaches are required to achieve high-performance. The problem can be solved in a hierarchical way. A deadlock avoidance policy is developed for the system as a lower-layer controller. With the support of the deadlock avoidance policy, heuristic rules are proposed to schedule the system in real-time. An effective modeling tool, colored–timed resource-oriented Petri net, is presented. It is shown that with this model we can schedule a system to achieve satisfactory results in real-time. This method is tolerant to module failures.     

Think globally act locally approach for the synthesis of a liveness-enforcing supervisor of FMSs based on Petri nets

This paper, by using Petri nets (PNs), reports a general approach, called a think globally, act locally (TGAL) method, to compute liveness-enforcing supervisors (LES) for flexible manufacturing systems (FMSs) prone to deadlocks. A place called global sink/source place (GP) is introduced provisionally help us to decide a set of monitors such that deadlock states can be removed. The TGAL method proceeds with liveness enforcement by an iterative way in which a complete state enumeration is computed at each step. The resulting LES is generally maximally permissive or suboptimal, without solving intractable integer linear programming (ILP) problems. Given a system, a sufficient condition is developed to decide whether the TGAL method can find maximally permissive, that is, optimal supervisors. Several typical FMSs popularly studied in the literature are used as the examples to demonstrate the proposed method.     

Active robustness of a milk manufacturing workshop with time constraints

This paper deals with the active robustness of a milk manufacturing workshop including time interval constraints. Such systems have robustness properties towards time disturbances. The robustness property can be a static property, but using a dynamic control strategy may increase the robustness value. Controlled P-time Petri nets are used as a modelling tool. Some definitions and a series of lemmas are cited in order to build a theory dealing with robustness problems. In order to avoid the death of marks at the synchronisation transitions of the P-time Petri net model, a robust control strategy facing time disturbances is presented. The proposed approach tries to reject the disturbance as soon as it is observed. Furthermore, this approach is used by an algorithm computing an active robustness margin at a given node. It is illustrated step by step on an example of a milk manufacturing workshop. A comparison with the bound provided for the passive robustness is made.     

On deadlock control for a class of generalised Petri net models of flexible manufacturing systems

This paper develops a deadlock prevention policy for a class of Petri nets that can model flexible manufacturing systems with assembly and disassembly operations. Siphons in a plant Petri net model are divided into elementary and dependent siphons according to the linear dependency of their characteristic T-vectors. The proposed approach is to make every siphon satisfy the controlled-siphon property (the cs-property), i.e., at any reachable marking, any siphon is max-marked, so that no deadlock states can be reached. The satisfiability of the cs-property is achieved by explicitly adding a monitor for each elementary siphon. The max-controllability of a dependent siphon is ensured by properly supervising its elementary siphons. More permissive behaviour of the non-blocking supervisor is obtained through the rearrangement of the output arcs of the monitors. Compared with existing policies reported in the literature, the advantage of the present method is that a small number of monitors are added and the iterative computing process is accordingly avoided. Finally, the application of the proposed method to an FMS example is presented.     

Constructing the closed-form solution of control-related states real-time information for insufficient k-th order systems with one non-sharing resource to realize dynamic modeling large TNCS systems of petri nets

Since the contribution from the closed-form solution (CFS) of the number of control-related states (CRSs) of the variant k-th order system can enumerate the number of each type of CRS in real time, we can apply this real-time information to enhance the capability for dynamic modeling of such systems. For example, allocating a non-sharing waiting dummy resource (known as a deadlock thread-holder [DTH]) in each forbidden substate at that location will increase the maximum number of reachable states that can be derived using a CFS in real time. We can thus avoid the occurrence of deadlock without implementing an additional controller. To extend this capability to model a k-th order system with one non-sharing circle subnet allocated at the top position of the left-hand process (denoted as a top non-sharing circle subnet [TNCS] k-th order system) by Petri net (PN), which is the fundamental manufacturing model for different products sharing common parts, this paper extends the existing research on CFS for PNs to an insufficient k-th order system, which is the essential element for a TNCS system with one non-sharing resource. The proposed deadlock avoidance algorithm can be employed to realize the allocation of dynamic non-sharing processes.