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.     

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.     

A deadlock prevention policy for a class of Petri net models of flexible manufacturing systems

This paper focuses on the problem of deadlocks in automated flexible manufacturing systems (FMS). Based on Petri nets, a deadlock prevention policy is proposed for a special class of Petri nets, S³PR. We embed the deadlock avoidance policy (DAP) of conjunctive/disjunctive resources upstream neighbourhood (C/D RUN) into the deadlock prevention policy (DPP), and allocate the underlying (sequential) resources reasonably to guarantee the absence of deadlock states and processes. First, siphons in a net model are distinguished by elementary and dependent ones. From the set of elementary siphons, a set of linear inequality constraints expressed by the state vector can be formalised. After being modified by the proposed policy, a set of generalised mutual exclusion constraints (GMEC) expressed by the marking vector can be found. Then monitors based on the GMEC are added to the plant model such that the elementary siphons in the S³PR net are all invariant-controlled and no emptiable siphon is generated due to the addition of the monitors. This novel deadlock prevention policy can usually lead to a more permissive supervisor by adding a smaller number of monitors and arcs than the existing methods for the design of liveness-enforcing Petri net supervisors. Two manufacturing examples are utilised to illustrate the proposed method and compared with the existing ones.     

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.     

Solving siphons with the minimal cardinality in Petri nets and its applications to deadlock control

Siphons can be used to characterise deadlock states and solve deadlock problems in Petri nets that model flexible manufacturing systems. By modifying the objective function and adding new constraints to the mixed-integer programming (MIP) method proposed by Park and Reveliotis, this paper presents a revised MIP (RMIP) to directly solve siphons, called smart siphons, with the minimal cardinality as well as the minimal number of resource places. Accordingly, an iterative siphon-based control (ISC) method adds a proper control place (CP) to make each smart siphon max-controlled until the controlled system is live. Since any siphon that has more resource places can be composed of those containing less resource places, a small number of CPs are required during the iterative control process due to the solved smart siphons containing the minimal number of resource places. Compared with the existing methods in the literature, the proposed ISC method using the RMIP avoids computing a maximal deadly marked siphon from which a minimal siphon is then derived, adds a small number of proper CPs, and leads to a liveness-enforcing supervisor with a simple structure. Finally, a case study demonstrates the effectiveness of the proposed ISC method.     

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.     

Two-step approach to robust deadlock control in automated manufacturing systems with multiple resource failures

ABSTRACT

In an automated manufacturing system (AMS), resource failures are inevitable, which renders the existing deadlock control policies for AMSs without considering resource failures ineffective. For the AMSs with multiple unreliable resources, in this paper, a method is developed for robust deadlock resolution using the framework of Petri nets (PNs). The considered AMSs are modeled with PN models called system of simple sequential process with resources (S³PR). An unreliable S³PR (U-S³PR) is obtained by adding recovery subnets that model the resource failures and recovery procedures of the places where resource failures may happen. Based on the model, a two-step approach is developed to design a robust controller. At Step 1, we use a siphon-based deadlock control method to analyze the behavior with resource failures and propose an incomplete robust deadlock controller for a U-S³PR. At Step 2, a reachability-graph-analysis-based method is utilized to consummate the robust deadlock controller. Then, a robust liveness-enforcing supervisor is derived to make an unreliable S³PR live even if multiple types of resources break down. Finally, the proposed method is illustrated by using an example.     

Biogeography-based optimisation for flexible manufacturing system scheduling problem

Biogeography-based optimisation (BBO) algorithm is a new evolutionary optimisation algorithm based on geographic distribution of biological organisms. With probabilistic operators, this algorithm is able to share more information from good solutions to poor ones. BBO prevents the good solutions to be demolished during the evolution. This feature leads to find the better solutions in a short time rather than other metaheuristics. This paper provides a mathematical model which integrates machine loading, part routing, sequencing and scheduling decision in flexible manufacturing systems (FMS). Moreover, it tackles the scheduling problem when various constraints are imposed on the system. Since this problem is considered to be NP-hard, BBO algorithm is developed to find the optimum /near optimum solution based on various constraints. In the proposed algorithm, different types of mutation operators are employed to enhance the diversity among the population. The proposed BBO has been applied to the instances with different size and degrees of complexity of problem adopted from the FMS literature. The experimental results demonstrate the effectiveness of the proposed algorithm to find optimum /near optimum solutions within reasonable time. Therefore, BBO algorithm can be used as a useful solution for optimisation in various industrial applications within a reasonable computation time.     

Guidelines for implementing robust supervisors in flexible manufacturing systems

Over the past several years, researchers have developed numerous control policies that assure deadlock-free operation for flexible manufacturing systems. Using this research base as a foundation, we have developed several supervisory policies that assure robust operation in the face of resource failure. Along with deadlock-free operation, these policies guarantee that failure of unreliable resources does not block production of part types not requiring failed resources. In our previous work, we developed two types of robust policies, those that ‘absorb’ all parts requiring failed resources into the buffer space of failure-dependent resources (resources that support only parts requiring failed resources), and those that ‘distribute’ parts requiring failed resources among the buffer space of shared resources (resources shared by parts requiring and parts not requiring failed resources). These two types of robust controllers assure different levels of robust system operation and impose very different operating dynamics on the system, thus affecting system performance in different ways. In this research, we use extensive simulation and experimentation on a highly complex and configurable system to develop guidelines for choosing the best robust supervisor based on manufacturing system characteristics and performance objectives. We validate these guidelines using seven randomly generated complex systems and find a better than 88% agreement.     

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.     

遗传算法的双目标柔性作业车间调度研究

研究了FMS环境下先进制造车间路径柔性的优化调度问题.同时考虑现代生产准时制的要求,建立了柔性作业车间调度问题的双目标数学优化模型,并给出了求解模型的遗传算法的具体实现过程;针对模型的特殊性,提出了染色体两层编码结构,将AOV网络图应用到解码和适应度函数的计算中,通过一个调度实例进行验证,给出了相应的选择、交叉、变异操作设计方案.     

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.     

Deadlock prevention technique using additional transitions for Petri nets

ABSTRACT

Siphon control has been utilized as a general methodology for systems of simple sequential process with resource (S³PR) deadlock systems. Although siphon control imposes additional control places on S³PR systems, it cannot guarantee that the maximum permissiveness is achieved. To solve the problem of deadlock prevention for S³PR, a new policy to design a deadlock-free supervisor with the maximally permissive system is proposed using additional transitions. Additionally, this approach can solve the problem of deadlock prevention for systems of sequential systems with shared resources (S4PR) system models.     

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.     

Markovian models for deadlock analysis in automated manufacturing systems

Deadlocks constitute a major issue in the desing and operation of discrete event systems. In automated manufacturing systems, deadlocks assume even greater importance in view of the automated operation. In this paper, we show that Markov chains with absorbing states provide a natural model of manufacturing systems with deadlocks. With illustrative examples, we show that performance indices such as mean time to deadlock and mean number of finished parts before deadlock can be efficiently computed in the modelling framework of Markov chains with absorbing states. We also show that the distribution of time to deadlock can be computed by conducting a transient analysis of the Markov chain model.     

Performance-based dynamic scheduling model for flexible manufacturing systems

A performance-based dynamic scheduling model for random flexible manufacturing systems (FMSs) is presented. The model is built on the mathematical background of supervisory control theory of discrete event systems. The dynamic FMS scheduling is based on the optimization of desired performance measures. A control theory-based system representation is coupled with a goal programming-based multi-criteria dynamic scheduling algorithm. An effectiveness function, representing a performance index, is formulated to enumerate the possible outputs of future schedules. Short-term job scheduling and dispatching decisions are made based on the values obtained by optimizing the effectiveness function. Preventive actions are taken to reduce the difference between actual and desired target values. To analyse the real-time performance of the proposed model, a software environment that included various Visual Basic Application® modules, simulation package Arena®, and Microsoft Access® database was developed. The experimentation was conducted (a) to determine the optimum look-ahead horizons for the proposed model and (b) to compare the model with conventional scheduling decision rules. The results showed that the proposed model outperformed well-known priority rules for most of the common performance measures.     

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 genetic scheduling methodology for virtual cellular manufacturing systems: an industrial application

Effective solutions to the cell formation and the production scheduling problems are vital in the design of virtual cellular manufacturing systems (VCMSs). This paper presents a new mathematical model and a scheduling algorithm based on the techniques of genetic algorithms for solving such problems. The objectives are: (1) to minimize the total materials and components travelling distance incurred in manufacturing the products, and (2) to minimize the sum of the tardiness of all products. The proposed algorithm differs from the canonical genetic algorithms in that the populations of candidate solutions consist of individuals of different age groups, and that each individual's birth and survival rates are governed by predefined aging patterns. The condition governing the birth and survival rates is developed to ensure a stable search process. In addition, Markov Chain analysis is used to investigate the convergence properties of the genetic search process theoretically. The results obtained indicate that if the individual representing the best candidate solution obtained is maintained throughout the search process, the genetic search process converges to the global optimal solution exponentially.

The proposed methodology is applied to design the manufacturing system of a company in China producing component parts for internal combustion engines. The performance of the proposed age-based genetic algorithm is compared with that of the conventional genetic algorithm based on this industrial case. The results show that the methodology proposed in this paper provides a simple, effective and efficient method for solving the manufacturing cell formation and production scheduling problems for VCMSs.     

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.