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.     

Robotic disassembly sequence planning using enhanced discrete bees algorithm in remanufacturing

Increasing attention is being paid to remanufacturing due to environmental protection and resource saving. Disassembly, as an essential step of remanufacturing, is always manually finished which is time-consuming while robotic disassembly can improve disassembly efficiency. Before the execution of disassembly, generating optimal disassembly sequence plays a vital role in improving disassembly efficiency. In this paper, to minimise the total disassembly time, an enhanced discrete Bees algorithm (EDBA) is proposed to solve robotic disassembly sequence planning (RDSP) problem. Firstly, the modified feasible solution generation (MFSG) method is used to build the disassembly model. After that, the evaluation criterions for RDSP are proposed to describe the total disassembly time of a disassembly sequence. Then, with the help of mutation operator, EDBA is proposed to determine the optimal disassembly sequence of RDSP. Finally, case studies based on two gear pumps are used to verify the effectiveness of the proposed method. The performance of EDBA is analysed under different parameters and compared with existing optimisation algorithms used in disassembly sequence planning (DSP). The result shows the proposed method is more suitable for robotic disassembly than the traditional method and EDBA generates better quality of solutions compared with the other optimisation algorithms.     

Modelling an automated storage and retrieval system using Petri nets

We investigated the feasibility of using stochastic Petri nets (SPNs) to describe the behaviours of automated storage/retrieval systems as well as to evaluate the performance of different control policies of such systems. SPNs have been studied in the past 2 decades, and have become a powerful tool in modelling concurrent and distributed systems that exhibit synchronization and contention of shared resources. It appeared that some important characteristics of AS/RS could be well modelled with SPNs. The SPN is a graph-based tool suitable for modelling systems (manufacturing, computer, biological, etc.). It can be used to model a system at different levels of abstraction. In this study, the efficiency, control rules, bay assignment, and many other performance issues associated with AS/RS have been studied in detail using SPN models. SPNs are shown to be equivalent to the stochastic processes in which embedded Markov chains can be recognized. In addition, a stochastic Petri net package, SPNP, was adopted to solve the reachability trees from which an embedded Markov chain was generated. Finally, the performance of those systems of our interest was evaluated. The unique features and flexibility of SPNs are presented. Furthermore, the SPN models for different control algorithms of an AS/RS are discussed with examples.     

Modelling and analysis of wafer fabrication scheduling via generalized stochastic Petri net and simulated annealing

Some of the important characteristics of the semiconductor wafer fabrication factories are re-entrant process flows, a dynamic and uncertain environment, stringent production control requirements, etc. that pose a major challenge to the scheduling decisions in integrated circuit wafer fabrication process. Keeping in view the high capital investment and quick response to the market changes, it is essential for the integrated circuit fabrication process to exercise effective control on its production operations so that production resources can be employed in a flexible and efficient manner. The present research has focussed on the development of a generalized stochastic Petri net model that faithfully captures dynamic behaviours such as re-entrant processing, machine failures, loading and unloading, etc., pertaining to wafer fabrication. A simulated annealing-based scheduling strategy using mean cycle time and tardiness as performance measures was also developed to obtain an efficient and robust schedule for a known hard problem. Analysis of variance was applied to examine the interaction effects of various scheduling rules and to identify the main as well as the interaction effects of dispatching rules, dispatching rules and set-up rules, and set-up rules and batching rules. Paired t-tests were applied to assess the performance of rule combinations for lot and batch scheduling. The proposed simulated annealing-based solution methodology was tested on a well-known data set adopted from the literature and its performance reveals that simulated annealing-based scheduling rules work better than existing rules in terms of the two performance measures mean cycle time and tardiness.     

Deadlock avoidance in an automated guidance vehicle system using a coloured Petri net model

This paper addresses the problem of deadlock control in automated guided vehicle (AGV) systems for automated manufacturing systems with unidirectinal guided paths. First, a Petri net (PN) model was developed for the problem. Then, by using the PN model developed, the condition for deadlock-free operation in AGV system and a control law are presented. To avoid deadlocks in AGV systems by this law, one needs only to observe the state of the system and check the number of free spaces available in some of the circuits. It is estimated that the proposed control law is simple enough to be used in the real-time control of contemporary system configuration. Three examples are used to show the application and efficiency of the proposed control law.     

Setup planning using Hopfield net and simulated annealing

This paper reports a new approach to setup planning of prismatic parts using Hopfield neural net coupled with simulated annealing. The approach deals with setup planning in two stages, i.e.: (1) sequence all the features of a workpiece according to geometric and technological constraints; and (2) identify setups from the sequenced features. In the first stage, the task of feature sequencing is converted to a constraint optimization problem (COP) which is similar to the travelling salesman problem (TSP). The setup time due to setup and tool changes is incorporated into the 'distance' between features, while the precedence and critical tolerance relationships between features are treated as constraints. The Hopfield neural net approach for TSP, i.e. energy function, is adopted to model the COP mathematically where the constraints are attached as additional penalty functions. Simulated annealing is then used to search for the minimum energy state of the net while avoiding the local minima. The feature sequence obtained aims at minimizing the number of setups and tool changes while ensuring little or no violation of feature precedence relationship, thus keeping critical tolerance violation to a minimum. In the second stage, setups are generated from the sequenced features using a vector intersection approach based on common tool approach directions. A case study is presented to demonstrate the effectiveness of this approach. A comparison study between this approach and an existing integer programming setup planning system is also given which indicates the superior efficiency of the proposed approach when dealing with problems with large number of features.     

e-Commerce and supply chains: Modelling of dynamics through fuzzy enhanced high level petri net

Although information plays a major role in effective functioning of supply chain networks (SCNs), studies that deal specifically with the dynamics of supply chains are few. This problem is relatively new since fast communications and the means to employ it for effective management of supply chains did not exist till recently. In order to provide a vehicle for dynamic modelling and analysis of supply chain operations in vague and uncertain environments, we propose a fuzzy enhanced high level petri net (FEHLPN) model. The proposed model captures the capability of petri nets for graphical and analytical representation of dynamic SCNs with the management of uncertain information provided by fuzzy logic. The dynamics associated with two production planning and control policies are modelled, viz. make-to-stock and assemble-to-order in vague and ambiguous situations in electronic commerce environment. A fuzzy set and fuzzy truth-values are attached to an uncertain fuzzy token to model imprecision and uncertainty. The proposed FEHLPN incorporates essential aspects of rule-based systems, such as conservation of facts, refraction, and closed-world assumption.     

拆卸序列规划中子装配体的识别与生成

子装配体识别是解决大规模拆卸序列规划"组合爆炸"问题的有效方法之一.为了准确有效地识别与生成子装配体,在装配体零部件间接触关系、联接关系和向位妨碍关系及其相应图模型、矩阵的基础上,提出了一种基于图模型和判断矩阵的拆卸序列规划子装配体的识别算法.该算法利用图模型对子装配体集合做加法,利用判断矩阵对子装配体集合做减法,首先依据子装配体识别准则对图模型检索生成潜在子装配体集合,然后依据矩阵判断公式从集合中排除不符合连续性原则、稳定性原则和可行性原则的子装配体,并筛选理想个数的符合重量标准、同质标准和价值标准的最终子装配体集合.以减速器实例验证方法的可行性和有效性.     

Modelling imperfect maintenance and the reliability of complex systems using superposed renewal processes

In problems of maintenance optimization, it is convenient to assume that repairs are equivalent to replacements and that systems or objects are, therefore, brought back into an as good as new state after each repair. Standard results in renewal theory may then be applied for determining optimal maintenance policies. In practice, there are many situations in which this assumption cannot be made. The quintessential problem with imperfect maintenance is how to model it. In many cases it is very difficult to assess by how much a partial repair will improve the condition of a system or object and it is equally difficult to assess how such a repair influences the rate of deterioration. In this paper, a superposition of renewal process is used to model the effect of imperfect maintenance. It constitutes a different modelling approach than the more common use of a virtual age process.     

A Petri Net based approach to determine the disassembly strategy of a product

In order to protect the environment and regain value added to products, a process known as disassembly has come into the limelight. This process is to be applied to reuse abandoned goods and materials. Manufacturers are being forced to establish disassembly plants and to develop their products' designs so as to maintain the government's dictate to dispose off their products in an environmentally responsible manner. This research presents a cost-based heuristic analysis for a circuit board assembly. Various components of the product and their assembly relationships are represented by a Petri Net diagram. Firing the transitions of the disassembly Petri Net is integrated with cost-based indices to develop an effective disassembly strategy. The methodology discussed here simplifies the decisionmaking process involved in disassembly planning. A comprehensive disassembly process planning system is proposed here and is exemplified by a case study of circuit board assembly.     

Economic evaluation of disassembly processes in remanufacturing systems

A model to deal with the disassembly processes in remanufacturing systems is presented with focus being on evaluating their economic consequences. More specifically, the model assists decisions such as to which degree and for the sake of which components should the returned items be disassembled. Consequently, using the economic values of recoverable items, the inventory holding costs of these items are obtained. This information is further used to determine the inventory control policy. To access such economic values, the above average cost approach is compared with the net present value method. The latter is often considered a more?‘correct’?way in remanufacturing systems from the viewpoint of inventory control. The results from the economic evaluation model are intended to aid companies in systematically evaluating current as well as projected remanufacturing systems.     

基于规则对象Petri网的柔性制造系统建模

针对FMS建模中存在的问题，通过分析FMS的组成和活动特点，提出了规则对象Petri网的建模方法。该方法集中了Petri网和面向对象技术的优点，并融系统决策规则子模型中。利用规则对象Petri网，建立了FMS的资源对象模型、动态行为模型和调度决策模型，为设计、分析和调度控制提供了有效的工具。     

医疗信息系统工作流的Petri网建模与化简分析

应用 Petri网建模与工作流技术,构建了基于医疗信息整合(IHE)规范的医疗信息系统工作流的Petri网模型,并对一个医疗信息系统工作流实例,给出了基于Petri网化简分析方法的模型化简与性质验证,表明该模型能够对医疗信息工作流进行有效的分析和验证,从而为医疗信息系统集成设计及其工作流分析提供了理论基础.     

Expert Enhanced Coloured Stochastic Petri Net and its application in assembly/disassembly

This article comprises of an Expert Enhanced Coloured Stochastic Petri Net (rule base system, or RBS) for modelling and analysing assembly/disassembly systems. RBSs are an Enhanced High-level Petri net extended with Close-World-Assumption (CWA). Traditional Petri nets can be used to model RBSs containing explicitly described knowledge. The main focus was is to facilitate and analyse the process planning activities of assembly/disassembly. The advantages of the new modelling approach were: (1) consideration of the non-desirable events, (2) occurrence of assembly/disassembly tasks with regard to colour of the tokens and utilization of probability concept to determine feasible steps, (3) establishing a relationship among components by means of arc labels, and (4) deeper insight into the assembly/disassembly process using high- and low-level petri nets.     

Dynamic disassembly planning for remanufacturing of multiple types of products

With the increased need for remanufacturing of end-of-life products, achieving economic efficiency in remanufacturing is urgently needed. The purpose of this study was to devise a cost-minimisation plan for disassembly and remanufacturing of end-of-life products returned by consumers. A returned end-of-life product is disassembled into remanufacturable parts, which are supposed to be used for new products after being remanufactured. Each end-of-life product is disassembled into parts at variable levels and through variable sequences as needed, taking into account not only disassembly but also manufacturing, remanufacturing, and holding inventory of remanufacturable parts. This study proposes a mixed integer linear programming (MILP) model for derivation of the optimal disassembly plan for each returned product, under deterministically known demand and return flows. For the purposes of an illustrative example, the proposed model was applied to the formulation of an optimal disassembly and remanufacturing plan of ‘fuser assembly’ of laser printers. The solution reveals that variable-level disassembly of products saves a significant remanufacturing cost compared with full disassembly.     

Petri net models of flexible and automated manufacturing systems: a survey

Petri nets (PNs) have recently emerged as a promising approach for modelling flexible and automated manufacturing systems. PNs are a graphical and mathematical modelling technique that is useful for modelling concurrent, asynchronous, distributed, parallel, nondeterministic, and stochastic systems, as attested by a steady stream of papers which appeared throughout the 1980s. Since 1989, there has been an explosion of interest in using PNs to model, simulate, and analyse manufacturing systems. We present an overview of PN theory. We then present a schema for categorizing PN models of manufacturing systems, followed by a survey of PN models of flow lines, automatic transfer lines, job shops, flexible manufacturing systems, and assembly systems. This discussion represents the most comprehensive survey of applications of PNs to manufacturing through 1994. Finally, we present a summary and some conclusions.     

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.     

基于Petri网的可信连接架构的安全属性分析

为确保可信连接架构(TCA)自身的安全可靠,研究了其安全属性量化问题,分析了其双向用户身份认证和平台认证过程中存在的安全威胁.利用随机Petri网对带有攻击行为的TCA可信网络连接过程进行了建模,该模型用于描述攻击行为和TCA的双向认证过程.以该模型为基础构造了马尔科夫链,通过计算马尔科夫模型的稳定状态概率对TCA的稳定状态机密性和完整性等安全属性进行定量分析.最后给出了一个具体数值评估结果的实例.此研究给出的方法有理论和实用意义.     

Conflict detection of automated guided vehicles: a Petri net approach

This research project investigates and develops techniques for automatically detecting potential vehicle conflicts in an automated guided vehicle (AGV) system. Three activities are involved: (1) construction of a set of formal definitions of Petri nets for modelling AGV systems; (2) development of procedures for detection of vehicle routeing conflicts; (3) development of a simulation program of the procedure. In this paper the first two activities are discussed in detail, and examples are provided.     

Performance evaluation of an auction-based manufacturing system using coloured Petri nets

The next generation of manufacturing systems is assumed to be intelligent enough to make decisions and automatically adjust to variations in production demand, shop-floor breakdowns etc. Auction-based manufacturing is a control strategy in which various intelligent entities in the manufacturing system bid themselves, accept bids and make selections among the bids available based on a heuristic. This paper deals with the simulation modelling and performance evaluation of a push-type auction (negotiation) based manufacturing system embedded in a pulltype production system using coloured Petri nets. Three different models of an auction-based manufacturing system have been discussed. This methodology helps in developing systems for real-time control, anticipation of deadlocks, and evaluation of various performance metrics like machine utilization, automated guided vehicle (AGV) utilization, waiting times, work in process (WIP) etc. Various decision-making rules were identified for the real-time control of auction-based manufacturing systems.