An improved time line search algorithm for manufacturing decision-making

The coloured Petri net formalism has been recently used to analyse and optimise manufacturing systems making use of the state space (SS) analysis. This approach has great potential for scheduling and production planning purposes when it is properly implemented. In this article, an improved version of the algorithm known as the time line search for optimising the makespan of manufacturing models is presented. The algorithm has been developed for the use in a compact SS of coloured Petri net models in order to analyse the highest possible number of manufacturing configurations for the improvement of the makespan of a production system. The proposed algorithm can be used for the developing of decision support tools in manufacturing or operational decision-making.     

A CTPN‐based scheduler for a flexible manufacturing cell

Abstract

This paper first presents hierarchical scheduling and control architecture for a flexible manufacturing cell (FMC) that is currently set up at the Mechanical Industrial Research Laboratories of the Industrial Technology Research Institute at Hsinchu, Taiwan. With this architecture, we focus on the scheduling problem of the FMC and present a scheduling mechanism based on a colored timed Petri net (CTPN) model. The CTPN model has three functions in the proposed mechanism: the first one is to formally describe pallet flows and resource constraints in the FMC by the event‐condition relation; the second one is to analyze conflict points among the pallet flows; the third one is to evaluate the used dispatching rules concerned with the selection of machine routings, the selection of work‐in‐process pallets in inter‐medium buffers and the assignment of the commonly used material‐handling device. Using the CTPN‐based scheduler, an appropriate combination of dispatching rules for each given batch can be selected to fit given criteria, e.g. minimum batch completion time, maximum resource utilization or minimum tardiness, etc. Moreover, real‐time status of the FMC can be represented in the mechanism for obtaining the on‐line scheduling effect.     

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.     

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.     

Modelling and simulation of automated manufacturing systems for evaluation of complex schedules

Automated manufacturing systems have been studied widely in terms of scheduling. As technology evolves, the behaviour of tools in automated manufacturing systems has become complicated. Therefore, mathematical approaches to the analysis of complex schedules no longer reflect reality. In this paper, we propose a systematic way of conducting simulation experiments to evaluate the complex operating schedules of automated manufacturing systems. A simulation model is based on a timed Petri net to take advantage of its mathematical strength. Since a Petri net cannot itself have token firing rules, we introduce additional states called operational states. Operational states are not directly related to a Petri net, and are only used for decision making. In addition, a decision function that is responsible for the conflict resolution of a Petri net model and an operational state transition function are introduced. The parallel simulation concept is also suggested by dividing a Petri net into several independent decision sub-nets. A multi-cluster tool system for semiconductor manufacturing is analysed as an application.     

Scheduling and optimization of mixed-processing with multi-variety wafers in dual-armed cluster tools

ABSTRACT

To improve the efficiency of wafer fabrication, this work addresses the scheduling and control problems of mixed-processing with multiple wafer types in cluster tools. Then, based on a developed Petri net (PN) model, it presents a general model for cluster tools with multiple wafer types and the conventional swap strategy. By analyzing the coordination mechanism between wafers processing and robot tasks, necessary and sufficient conditions are established to check the schedulability of the system that is operated by using the conventional swap strategy. If the system is not schedulable checked by such schedulability conditions, a constraint-guided heuristic algorithm and a conflicts-avoiding algorithm are developed to obtain a reasonable schedule. Finally, illustrative examples are presented to show the applications of the proposed method.     

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.     

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.     

Automatic Petri Net Simulation Model Generation for a Continuous Flow Transfer Line with Unreliable Machines

A production line is studied with several machines in series. The machines are separated with finite buffers. They can break down and have to be repaired. Production is assumed to be continuous, i.e. no individual products can be identified. Analytical models for the performance evaluation of such a system are scarce. Analytical results for the throughput can be obtained only under very restrictive assumptions. The performance study of longer transfer lines requires either approximation or simulation. A Petri net model is developed for an n‐machine ‐buffer system. The rules to design the Petri net transitions are given. The automatic generation of a discrete‐event simulation model from the Petri net model is explained. Finally, some potential applications of the Petri net are illustrated. These applications include the simulation of transfer lines with complex stochastic behaviour, the optimization of buffer size and allocation and the evaluation of approximation models for long transfer lines. Using the simulation model described in this paper, quality and reliability engineers can simulate the performance of a given continuous flow transfer line and evaluate the effect of performance‐increasing measures such as the insertion of extra buffer space or the use of more reliable machines. Copyright © 2004 John Wiley & Sons, Ltd.     

Optimisation of block erection scheduling based on a Petri net and discrete PSO

The shipyard block erection system (SBES) is a typical discrete-event dynamic system. To model multiprocessing paths and a concurrent assembly procedure, a timed Petri net (TPN) is proposed. The definition of a Petri net is extended to accord with the real-world SBES organisation. The basic TPN modules are presented to model the corresponding variable structures in the SBES, and then the scheduling model of the whole SBES is easily constructed. A modified discrete particle swarm optimisation (PSO) based on the reachability analysis of Petri nets is developed for scheduling of the SBES. In the proposed algorithm, particles are coded by welding transitions and selecting places of the TPN model, and then the collaboration and competition of particle individuals is simulated by crossover and mutation operators in a genetic algorithm. Numerical simulation suggests that the proposed TPN–PSO scheduler can provide an improvement over the conventional scheduling method. Finally, a case study of the optimisation of a back block erection process is provided to illustrate the effectiveness of the method.     

双管道原油运输系统的着色赋时可控Petri网建模

针对双管道原油运输（高低凝固点原油）系统,利用着色赋时可控Petri网进行建模,分析多个关键约束,特别是高凝固点原油运输管道的约束。利用模块化建模方法,分层建模,结构严谨,描述系统行为完整,可作为观察系统物流信息和短期生产调度制定的辅助工具。     

System Failure Analysis Through Counters of Petri Net Models

Petri nets are a powerful technique widely used in the modeling and analysis of complex manufacturing systems and processes. Due to their capability in modeling the dynamics of the systems, Petri nets have been combined with fault tree analysis techniques to determine the average rate of occurrence of system failures. Current methods in combining Petri nets with fault trees for system failure analysis compute the average rate of occurrence of system failures by tracking the markings of the Petri net models. The limitations of these methods are that tracking the markings of a Petri net represented by a reachability tree can be very complicated as the size of the system grows. Therefore, these methods offer less flexibility in analyzing sequential failures in the system. To overcome the limitations of the current methods in applying Petri nets for system failure assessment, this paper expands and extends the concept of counters used in Petri net simulation to perform the failure and reliability analysis of complex systems. The presented method allows the system failures to be modeled using general Petri nets with inhibitor arcs and loops, which employs fewer variables than existing marking‐based methods and substantially accelerates the computations. It can be applied to real system failure analysis where basic events can have different failure rates. Copyright © 2003 John Wiley & Sons, Ltd.     

Petri-net based applications for supply chain management: an overview

Supply networks are discrete event dynamic systems consisting of suppliers, manufacturers, distributors, and customers. It is a difficult and challenging task to model such a complex system. Recently, characterised as being capable of model parallelism and synchronisation, Petri nets (PNs) have attracted great attention for modelling and studying a supply network. Since each type of Petri net has its unique properties to model specific applications, this paper reviews and classifies Petri net applications for supply chain management (SCM). According to the decision problems facing SCM, we have the Petri net applications classified into three areas: competitive strategy, firm focused tactics, and operational efficiency. Categorising the Petri net applications will provide a guideline to industry practitioners and research academics to choose the appropriate Petri net for the problem. In addition, the paper attempts to offer future directions in applying the Petri net to SCM including: (1) modelling with uncertainty elements; (2) addressing the scalability issue of Petri nets; (3) integrating Petri nets with other tools; and (4) extending Petri nets to emerging applications.     

Maximally permissive deadlock prevention via an invariant controlled method

Recently, researchers have proposed a novel and computationally efficient method to design optimal control places and an iteration approach that computes the reachability graph once to obtain a maximally permissive, if any, liveness-enforcing supervisor of flexible manufacturing systems (FMS). The approach solves the set of integer linear inequalities to compute control places. If, given a Petri net model, no solution exists, the optimal control place does not exist for the Petri net model. We discover that a solution always exists for systems of simple sequential processes with resources (S³PR), but not for the case of FMS modelled by generalised Petri nets (GPN). We propose a theory to prove that there are no good states that will be forbidden by the control policy for S³PR, in which live and dead states cannot have the same weighted sum of tokens in the complimentary set of a siphon. For a system of simple sequential processes with general resource requirements (S³PGR²) modelled by GPN, we find the reason why the integer linear programming (ILP) may not have solutions, which is consistent with the fact that optimal supervisor synthesis for GPN remains unknown. We show that live and dead states may have the same weighted sum of tokens in the complimentary set of a siphon in a GPN. These theoretical results are verified by case studies.     

A heuristic algorithm to minimise the control places of a Petri net for the control of shared machines

This paper proposes a design methodology of a controller based on a Petri net for the shared machines of manufacturing systems. A conflict occurs when several manufacturing systems require the same shared machines at the same time. In this case, we have two issues; the scheduling of jobs on shared machines and the construction of a control procedure for scheduling. The scheduling of production on machines has been extensively studied over the past years by researchers. In this paper, our concern is not the scheduling problem but the construction of a control procedure for the production schedule. We propose a design of a Petri net based controller for the shared machines of manufacturing systems such that the number of control places in the Petri net is minimised. The experimental results show that the proposed algorithm performs better than an upper bound in terms of optimality. Also, the proposed algorithm is computationally more efficient than the optimal algorithm. Finally, we present the application of the proposed algorithm to a realistic batch process system shown in the literature.     

Use of Petri Nets to Model the Maintenance of Wind Turbines

With large expansion plans for the offshore wind turbine industry, there has never been a greater need for effective operations and maintenance. The two main problems with the current operations and maintenance of an offshore wind turbine are the cost and availability. In this work, a simulation model has been produced of the maintenance process for a wind turbine with the aim of developing a procedure that can be used to optimise the process. This initial model considers three types of maintenance—periodic, conditional and corrective—and also considers the weather in order to determine the accessibility of the turbine. Petri nets have been designed to simulate each type of maintenance and weather conditions. It has been found that Petri nets are a very good method to model the maintenance process because of their dynamic modelling and adaptability and their ability to test optimisation techniques. Because of their versatility, Petri net models are developed for both system hardware and the maintenance processes, and these are combined in an efficient and concise manner. Copyright © 2014 John Wiley & Sons, Ltd.     

A Petri Net Approach to Remote Diagnosis for Failures of Cardiac Pacemakers

This paper describes the application of Petri nets to remote diagnosis for failures of cardiac pacemakers. The operations, structures and basic control methods of the different types of cardiac pacemakers are first described. A combined synchronous pacemaker is modeled into a Petri net in this study. Twelve checkpoints are added into the modeled Petri net so as to construct a Petri net for failure diagnosis. A remote mode for failure diagnosis of implanted pacemakers is also designed by the Petri net approach. A low‐power transmitter transmits a checking‐code with 12 digits from the implanted pacemaker to the outside of the patient's body manually or automatically. By observing the markings of the checking code, the working status and the health condition of the pacemaker are clear at a glance. Applications of the Petri net method for failure diagnosis and control optimization are discussed. Copyright © 2004 John Wiley & Sons, Ltd.     

考虑资源成本的Petri网在FMS调度中的应用

本文针对目前基于petri网的调度方法中调度目标单一的缺点，通过在petri网的结构中引入资源成本元素的方法，使得在调度计划产生的过程中可以同时考虑时间和资源成本优化，为企业作出更为科学合理的生产决策提供依据．最后通过一个实例来验证了提出的算法。     

FAILURE ANALYSIS FOR AN AIRBAG INFLATOR BY PETRI NETS

Petri nets are useful for modelling a variety of asynchronous and concurrent systems, such as automated manufacturing, computer fault tolerant systems, and communication networks. This study employs an airbag inflator system as an example to demonstrate a Petri net approach to failure analysis. This paper uses Petri nets to study minimum cut sets finding, marking transfer, and dynamic behaviour of system failure. For Petri net models incorporating sensors, fault detection and higher-level fault avoidance is dealt with. Compared with fault trees that present only static logic relations between events, Petri nets indeed offer more capabilities in the scope of failure analysis. © 1997 John Wiley & Sons, Ltd.     

A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles

To achieve a significant improvement in the overall performance of a flexible manufacturing system, the scheduling process must consider the interdependencies that exist between the machining and transport systems. However, most works have addressed the scheduling problem as two independent decision making problems, assuming sufficient capacity in the transport system. In this paper, we study the simultaneous scheduling (SS) problem of machines and automated guided vehicles using a timed coloured Petri net (TCPN) approach under two performance objectives; makespan and exit time of the last job. The modelling approach allows the evaluation of all the feasible vehicle assignments as opposed to the traditional dispatching rules and demonstrates the benefits of vehicle-controlled assignments over machine-controlled for certain production scenarios. In contrast with the hierarchical decomposition technique of existing approaches, TCPN is capable of describing the dynamics and evaluating the performance of the SS problem in a single model. Based on TCPN modelling, SS is performed using a hybrid heuristic search algorithm to find optimal or near-optimal schedules by searching through the reachability graph of the TCPN with heuristic functions. Large-sized instances are solved in relatively short computation times, which were a priori unsolvable with conventional search algorithms. The algorithm’s performance is evaluated on a benchmark of 82 test problems. Experimental results indicate that the proposed algorithm performs better than the conventional ones and compares favourably with other approaches.