Disassembly sequence generation: A Petri net based heuristic approach

The generation of a set of optimal or near-optimal disassembly sequences is an important task associated with the study of disassembly planning. This task encapsulates actions at the required disassembly depth to reach maximum net revenue while satisfying economic constraints. The Petri net modelling, combined with heuristic search procedures developed in this study, offers an efficient procedure for disassembly sequence generation. The heuristic generates and searches a partial reachability graph to arrive at an optimal or near-optimal disassembly sequence based on the firing sequence of transitions of the Petri net model. The proposed methodology reduces the search space in two areas: (1) pruning the disassembly tree (DT) and, (2) selective tracking of the reachability graph. The efficacy of the proposed methodology is demonstrated by using two examples from the literature.     

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.     

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.     

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.     

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.     

Decomposition in automatic generation of Petri nets for manufacturing system control and scheduling

Despite the efforts in developing Petri net models for manufacturing control and scheduling, the generation of Petri net models cannot be automated for agile manufacturing control and scheduling without difficulties. The problems lie in the complexity of Petri net models. First of all, it is difficult to visualize the basic manufacturing process flow in a complex Petri net model even for a Petri net modelling expert. The second problem is related to the complexity of using Petri net models for manufacturing system scheduling. In this paper, a decomposition methodology in automatic generation of Petri nets for manufacturing system control and scheduling is developed. The decomposition methodology includes representing a manufacturing process with the Integrated Definition 3 (IDEF3) methodology, decomposing the manufacturing process based on the similarity of resources, transforming the IDEF3 model into a Petri net control model, and aggregating sub Petri net models. Specifically, a sequential cluster identification algorithm is developed to decompose a manufacturing system represented as an IDEF3 model. The methodology is illustrated with a flexible disassembly cell example. The computational experience shows that the methodology developed in this paper reduces the computational time complexity of the scheduling problem without significantly affecting the solution quality obtained by a simulated annealing scheduling algorithm. The advantages of the methodology developed in this paper include the combined benefits of simplicity of the IDEF3 representation of manufacturing processes and analytical and control properties of Petri net models. The IDEF3 representation of a manufacturing process enhances the manmachine interface.     

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.     

Deadlock prevention policy based on Petri nets and siphons

This paper presents a deadlock prevention method for a class of flexible manufacturing systems where deadlocks are caused by unmarked siphons in their Petri net models. This method is an iterative approach consisting of two main stages. At each iteration, a fast deadlock detection technique developed by mixed integer programming is used to find an unmarked maximal siphon. An algorithm is formalized that can efficiently obtain an unmarked minimal siphon from the maximal siphon. The first stage, called siphons control, of the proposed method is to add, for each unmarked minimal siphons, a control place to the original net with its output arcs to the sink transitions of the minimal siphon. The objective is to prevent a minimal siphon from being unmarked. The second stage, called augmented siphons control, is to add a control place to the modified net with its output arcs to the source transitions of the resultant net if the resource places are removed. The second stage is required since adding control places in the first stage may create new unmarked siphons. In addition, the second stage assures that there are no new unmarked siphons generated. The relation of the proposed method and the liveness and reversibility of the controlled net have been obtained. Finally, manufacturing examples are presented to illustrate the method and to allow comparison with earlier methods.     

A Petri-net-based state-transition model for an optimal operator cyclic walking pattern development in GT cells

An approach for developing the optimal operator scheduling solution for a group technology (GT) production problem is studied. A state-transition model is developed to analyse and gain insight into the operator-machine interaction of the problem. Operator cyclic walking patterns are then denned. A Petri net model has succeeded in determining the optimal cyclic walking pattern. The computational efforts needed for the Petri net model are compared with those for an integer programming model. The results show large savings in computational effort by using the Petri net model. In addition, the extendability of the Petri net model for various system aspects is addressed     

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.     

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.     

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.     

A note on: On controlling the controllable lead time component in the integrated inventory models

This paper develops an analytical approach to quantifying manufacturing system flexibility (MSF). Measures of flexibility, namely, producibility, processivity, transferability and introducibility are developed based on a state-transition formalism, the reachability graph. The uncertainty in system operating conditions is specified in terms of certain disturbing factors, external and internal to the system, which impinge on system performance. The contribution of each factor to the value of a given type of flexibility is estimated using the analytic hierarchy process (AHP). The individual flexibility measures are thus combined to give a measure of MSF under a given operating environment. A Petri net model is used to construct the reachability graphs used in flexibility measurement. Uses of the proposed measures at the design and operational analysis stages of FMS are presented     

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.     

Hybrid metaheuristic techniques for optimising sugarcane rail operations

Mixed integer programming and parallel-machine job shop scheduling are used to solve the sugarcane rail transport scheduling problem. Constructive heuristics and metaheuristics were developed to produce a more efficient scheduling system and so reduce operating costs. The solutions were tested on small and large size problems. High-quality solutions and improved CPU time are the result of developing new hybrid techniques which consist of different ways of integrating simulated annealing and Tabu search techniques.     

Formal design and analysis of a hybrid supervisory control structure for Virtual Production Systems

Virtual Production Systems (VPSs) is a dynamic paradigm for production resources structure, which was proposed to cope with changing and uncertain manufacturing environment. However, the high performance of VPSs relies on a high-quality control in practice. Motivated by both local quick responses and global optimization, a supervisory control structure based on autonomous and coordination mechanisms is proposed for VPSs in this paper. This hybrid supervisory control structure is formally designed and analysed with timed automata on the platform of an integrated tool named UPPAAL. First, the Discrete Events Dynamic Systems (DEDS) model of VPSs is established. Then autonomous and coordinated supervisory controllers are further designed under the guidance of heuristic scheduling rules, such that the desired characteristics of both performance (production flow and time) and activity (overflow-, conflict- and deadlock-free) can be ensured. Finally, system analysis, including deadlock-free analysis, calculation and simulation of time-optimal scheduling, is made through verification. A case study is made to illustrate that control and scheduling can be well integrated into this hybrid supervisory control structure in practice.     

Performance evaluation of tandem and conventional AGV systems using generalized stochastic Petri nets

This paper investigates the different policies and concepts followed in the traffic management of automated guided vehicle (AGV) systems, and develops the controls for automatically eliminating potential vehicle conflicts in an AGV system. The planning of the AGV system is performed in such a way that there are no conflicts or deadlocks for the vehicles using stochastic Petri nets (SPNs). The major effort is devoted to determining the benefits of the tandem AGV control in comparison with the conventional AGV control method. SPNs have been used to model the different designs of flexible manufacturing systems (FMSs) and with different policies for the movement of material, vehicle path control, inventory planning and tool control. The SPN model is solved and the performance of the system can be evaluated. In this study, the effort is directed to model an FMS with two different types of AGV traffic management methods, namely the conventional and tandem AGV control. A SPN program is used which takes the FMS Petri net model as the input and evaluates the different properties of the Petri net. Finally the performance measures are obtained, which helps in evaluating and comparing the two different AGV traffic management methods.     

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.