Deadlock-free scheduling in flexible manufacturing systems using Petri nets

This paper addresses the deadlock-free scheduling problem in Flexible Manufacturing Systems. An efficient deadlock-free scheduling algorithm was developed, using timed Petri nets, for a class of FMSs called Systems of Sequential Systems with Shared Resources (S 4 R). The algorithm generates a partial reachability graph to find the optimal or near-optimal deadlock-free schedule in terms of the firing sequence of the transitions of the Petri net model. The objective is to minimize the mean flow time (MFT). An efficient truncation technique, based on the siphon concept, has been developed and used to generate the minimum necessary portion of the reachability graph to be searched. It has been shown experimentally that the developed siphon truncation technique enhances the ability to develop deadlock-free schedules of systems with a high number of deadlocks, which cannot be achieved using standard Petri net scheduling approaches. It may be necessary, in some cases, to relax the optimality condition for large FMSs in order to make the search effort reasonable. Hence, a User Control Factor (UCF) was defined and used in the scheduling algorithm. The objective of using the UCF is to achieve an acceptable trade-off between the solution quality and the search effort. Its effect on the MFT and the CPU time has been investigated. Randomly generated examples are used for illustration and comparison. Although the effect of UCF did not affect the mean flow time, it was shown that increasing it reduces the search effort (CPU time) significantly.     

Deadlock-free genetic scheduling for flexible manufacturing systems using Petri nets and deadlock controllers

In this paper, a new deadlock-free scheduling method based on genetic algorithm and Petri net models of flexible manufacturing systems is proposed. The optimisation criterion is to minimise the makespan. In the proposed genetic scheduling algorithm, a candidate schedule is represented by a chromosome that consists of two sections: route selection and operation sequence. With the support of a deadlock controller, a repairing algorithm is proposed to check the feasibility of each chromosome and fix infeasible chromosomes to feasible ones. A feasible chromosome can be easily decoded to a deadlock-free schedule, which is a sequence of transitions without deadlocks. Different kinds of crossover and mutation operations are performed on two sections of the chromosome, respectively, to improve the performance of the presented algorithm. Computational results show that the proposed algorithm can get better schedules. Furthermore, the proposed scheduling method provides a new approach to evaluate the performance of different deadlock controllers.     

Modelling and simulation of manufacturing systems with first-order hybrid Petri nets

First-order hybrid Petri nets are models that consist of continuous places holding fluid, discrete places containing a non-negative integer number of tokens, and transitions, either discrete or continuous. In the first part of the paper, we provide a framework to describe the overall hybrid net behaviour that combines both time-driven and event-driven dynamics. The resulting model is a linear discrete-time, time-varying state variable model that can be directly used by an efficient simulation tool. In the second part of the paper, we focus on manufacturing systems. Manufacturing systems are discrete-event dynamic systems whose number of reachable states is typically very large, hence approximating fluid models have often been used in this context. We describe the net models of the elementary components of a flexible manufacturing system (machines and buffers) and we show in a final example how these modules can be put together in a bottom-up fashion.     

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.     

Adaptive production scheduling of virtual production systems using object-oriented Petri nets with changeable structure

Virtual Production Systems (VPSs) are logically constructed by organizing production resources belonging to one or more physical manufacturing systems. VPSs can enhance the agility of manufacturing systems. However, an effective scheduling approach is required to cope with disturbance and changes to these systems. An adaptive production scheduling method is proposed. Object-oriented Petri nets with changeable structure (OPNs-CS) formulate the scheduling problem of VPSs. To resolve resource constraints in a VPS, the OPNs-CS is modified by introducing limited token available time and by revising the enabling and firing rules. The artificial intelligent heuristic search (A*) algorithm is modified and applied to generate the optimal or near optimal schedule. When a VPS encounters any disturbance, an estimate of the effects of the disturbance can be estimated by simulation on the OPNs-CS model. If the scheduling target (completion time) is not affected, rescheduling is not required. Whenever there is a change to the VPS, the TOPNs-CS model is updated to refresh VPS schedule. A case study is presented to demonstrate the procedures for applying the proposed scheduling approach. The given case study shows that the proposed approach is capable of scheduling a VPS dynamically in response to disturbances and changes are involved.     

Industrial systems maintenance modelling using Petri nets

This article presents a new algorithm that we have developed to find the minimal cut-sets of a coherent fault tree. The model presented is based on Petri nets. We also show that for a large fault tree, we are faced with the complexity problem. We suggest the use of place fusion as well as a methodology that can allow us to overcome this difficulty.     

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.     

Nested coloured timed Petri nets for production configuration of product families

Production configuration is as an effective technique to deal with product variety while maintaining production stability and efficiency. It involves a diverse set of process elements (e.g., machines, operations), a high variety of component parts and assemblies and many constraints arising from product and process variety. Production configuration entails the selection and subsequent arrangement of process elements into complete production processes and the final evaluation of configured multiple alternatives. To better understand production configuration and its implementation, we study the underlying logic for configuring production processes using a dynamic modelling and visualisation approach. This is accomplished by developing a new formalism of nested coloured timed Petri nets (PNs). In view of the inherent modelling difficulties, in the formalism three types of nets–process nets, assembly nets and manufacturing nets–together with a nested net system are defined. Using an industrial example of vibration motors, we show how the proposed formalism can be applied to specify production processes at different levels of abstraction to achieve production configuration.     

Temporized coloured Petri nets with changeable structure (CPN-CS) for performance modelling of dynamic production systems

One of the difficulties in modelling dynamic production systems is the representation of changes to the system along time. Coloured Petri nets with changeable structure (CPN-CS) are capable of modelling systems subject to change. However, this is restricted to functionality modelling of the system. In this paper, we extend CPN-CSs into temporized CPN-CS (TCPN-CS). The extension is carried out by associating relevant modelling elements with time parameters and modifying the mechanism for structure change of the CPN-CS model. TCPN-CS makes it possible to model a dynamic production system considering both functionality and performance. A case study is provided to show that TCPN-CS is effective for modelling dynamic production systems.     

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.     

Modelling and simulation of energy consumption of ceramic production chains with mixed flows using hybrid Petri nets

Ceramic production chain consisting of discrete flow and continuous flow energy-intensive processes consumes substantial amounts of energy. This study aims to evaluate energy consumption performance and energy-saving potentials of the ceramic production chain. According to the energy consumption characteristics of manufacturing processes and process interaction constraints in a ceramic production chain, an approach integrating the first-order hybrid Petri net (FOHPN) model, an objective linear programming model and a sensitivity analysis is proposed. The FOHPN model will simulate the energy consumption patterns of the ceramic production chain. Meanwhile, multi-objective linear programming model and sensitivity analysis will suggest the optimal specific energy consumption (SEC) of the production chain and identify the influences of input parameters (i.e. production rate of a process) on the SEC in the optimal production scheme. Finally, a real case study from bathroom ceramic plant validates the approach. It provides a tool for modelling and simulation of energy consumption of ceramic production chains with mixed flows and helps operators to perform energy-saving actions in the ceramic enterprise.     

Reliability analysis of discrete event dynamic systems with Petri nets

This paper deals with dynamic reliability of embedded systems. It presents a method for deriving feared scenarios (which might lead the system to a critical situation) in Petri nets. A classical way to obtain scenarios in Petri nets is to generate the reachability graph. However, for complex systems, it leads to the state space explosion. To avoid this problem, in our approach, Petri net reachability is translated into provability of linear logic sequents. Linear logic bases are introduced and used to formally define scenarios and minimality of scenarios. These definitions allow the method to produce only pertinent scenarios. The steps of the method are described and illustrated through a landing-gear system example.     

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.     

Celeritas: a coloured Petri net approach to simulation and control of flexible manufacturing systems

In many areas of computerization today, the capabilities of hardware systems far exceed the sophistication of software systems needed for optimum control. This research is an attempt to advance software control capabilities of flexible manufacturing systems (FMSs). To this end, an FMS controller architecture, called Celeritas, has been designed and a software system conforming to this architecture has been designed and implemented. Celeritas is a generic, data-configurable FMS controller designed using the coloured Petri nets (CP-nets) modelling paradigm augmented with decision support software to provide both FMS simulation and control. Formalisms of the CP-net paradigm provide straightforward representation of both the inherent concurrency and resource conflicts present in such a complex system. Augmentations provide user-defined routines for real-time interfaces to this information which is utilized to provide resource arbitration services among jobs competing for scarce resources and overall job scheduling.     

Towards self-adaptive production systems: Modular generic simulation models for continuous replanning and reconfiguration

Changing factors within markets, such as continually shortening product life cycles, increasing competition due to shorter development and order processing times, manufacturing in intercompany networks and the individualization of customer needs, create new requirements that manufacturing organizations are expected to fulfil. To be successful, manufacturing organizations and business processes have to be transformable to cope with these environmental changes. That is why the creation and implementation of self-adaptive production systems represent one vision of the near future. A first step to self-adaptive production systems is the transition from a non-recurring, static planning and operation cycle to a continuous replanning and reconfiguration of work systems, supported by new planning methods and tools. Starting with a definition of self-adaptive production systems, the requirements for planning support systems for a continuous reconfiguration and replanning are derived. The paper also presents a solution for an integrated planning tool based on object-oriented, generic simulation models. The architecture and planning procedure are described in detail. The paper finally shows the first test results of the implemented prototype.     

Maintenance integration in manufacturing systems by using stochastic Petri nets

Research into both increased performance and improvements in dependability of production systems involves maintenance integration, which allows one to protect their availability and their durability. In the case of large manufacturing systems, maintenance integration is essential from conception, and so it involves a particular development concerned with both model complexity and computing time. A modular modelling approach, based on a cellular decomposition of the system, using stochastic Petri nets and Markov chains has been adopted to implement various maintenance strategies in complex production workshops, with the aim of studying their influence on the system dependability and performance.     

Assembly/disassembly task planning and simulation using expert Petri nets

Automatic assembly/disassembly planning is recognized as an important tool for reducing the manufacturing costs in concurrent product and process development. This paper developed a knowledge-based expert Petri net model by incorporating expert system techniques in artificial intelligence into ordinary Petri nets for an analytical framework of understanding, representing and reasoning the assembly/disassembly tasks. Substantial extensions have been made to ordinary Petri nets by adding control places, time constraints, and place and transition knowledge annotations. The proposed expert Petri net model can be considered as the hybrid of expert systems and ordinary Petri nets. Through these extensions, the capacities of modelling and representation of ordinary Petri net models are largely enhanced, and thus the expert Petri net models are more powerful than ordinary Petri nets. Such intelligent Petri net models can combine the abilities of modelling, planning, and performance evaluation for assembly/disassembly tasks in an integrated and intuitive way, and can therefore be applied to either linear/non-linear, static/dynamic, or on-line/off-line assembly/disassembly tasks at both high and low levels. The developed assembly/disassembly planning system can generate the best strategies and plans for assembly/disassembly. The research findings are exemplified with a real assembly to show the effectiveness of the method.     

Modelling of semiconductor wafer fabrication systems by extended object-oriented Petri nets

In this paper, extended object-oriented Petri nets (EOPNs) are proposed for the effective modelling of semiconductor wafer fabrication systems (SWFSs). To cope with their complexity in terms of the re-entrant process route and the mixed production mode, a special type of transition called main-bus gate is introduced, which may lead each kind of product to undergo every re-entrant processing stage. In addition, the hierarchical approach is also applied to cope with the complexity. An etching area that processes 0.25?µm logic IC products is taken as an illustration to present the detailed modelling procedures by EOPNs, and the resulting model validates that the EOPNs may cope well with complex SWFSs modelling.