The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems

In a flexible manufacturing system (FMS) with multiple products, deadlocks can arise due to limited shared resources, such as machines, robots, buffers, fixtures etc. The development of efficient deadlock prevention policies, which can optimise the use of system resources, while preventing deadlocks from occurring, has long been an important issue to be addressed. In [1], an optimal deadlock prevention policy was proposed, based on the use of reachability graph (RG) analysis of the Petri net model (PNM) of a given FMS and the synthesis of a set of new net elements, namely places with initial marking and related arcs, to be added to the PNM, using the theory of regions. The policy proposed in [1] is optimal in the sense that it allows the maximal use of resources in the system according to the production requirements. For very big PNMs, the reachability graph of the PNMs becomes very large and the necessary computations to obtain an optimal deadlock prevention policy become more difficult. In this paper, we propose the use of the Petri net reduction approach to simplify very big PNMs so as to make necessary calculations easily in order to obtain an optimal deadlock prevention policy for FMSs. An example is provided for illustration.     

Application of Petri nets for deadlock analysis and avoidance in flexible manufacturing systems

Unreasonable dispatching resources to jobs in flexible manufacturing system (FMS) may result in a deadlock situation. This serious situation is studied and avoided through Petri net (PN) analysis techniques in this paper. Firstly, a production Petri net (PPN) model for a given FMS is developed. Based on a certain set of resources in PPN, the concepts of a deadlock state and a potential deadlock state are introduced. Then, we present a deadlock avoidance method that consists of two parts. One is the construction of a deadlock state equation that describes the intrinsic relationship between resources assignation and a deadlock state in PPN. This equation is a necessary and sufficient condition for the occurrence of a deadlock situation. The other is the construction of a restrictive PN controller for each deadlock state equation. This restrictive PN controller can control the resources dispatching by excluding some enabled transitions from firing, consequently avoiding the deadlock. This method is minimally restrictive and allows the maximal use of resources not only for normal FMS, but also for special FMS with cyclic deadlock structure chain (i.e., a pathological type of circular waiting structure). Finally, two applications are given to illustrate the validity of this method. The results show that this method can be efficiently implemented in practical FMS.     

Estimation of Optimum Genetic Control Parameters for Job Shop Scheduling

Genetic algorithms (GA) have demonstrated considerable success in providing good solutions to many non-polynomial hard optimization problems. GAs are applied for identifying efficient solutions for a set of numerical optimization problems. Job shop scheduling (JSS) has earned a reputation for being difficult to solve. Many workers have used various values of genetic parameters. This paper attempts to tune the control parameters for efficiency, that are used to acceleate the genetic algorithm (applied to JSS) to converge on an optimal solution. The genetic parameters, namely, number of generations, probability of crossover, probability of mutation, are optimized relating to the size of problems. The results are validated in job shop scheduling problems. The results indicate that by using an appropriate range of parameters, the genetic algorithm is able to find an optimal solution faster. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: Dr S. G. Ponnambalam, Department of Production Engineering, Regional Engineering College, Tiruchirapalli, 620 015, India. E-mail: pons&commat;rect.ernet.in     

平面包络环面蜗杆基于坐标测量的高精度制造方法

用坐标测量的方法实现了平面包络环面蜗杆齿形偏差的测量，提出了由齿形偏差的测量结果诊断蜗杆加工时机床工具的调整误差，并根据诊断结果修正机床工具的调整参数，从而提高蜗杆制造精度的方法，加工测量的试验表明本文方法十分有效。     

Optimal Shape Design of an Extrusion Die Using Polynomial Networks and Genetic Algorithms

Designing the optimal shape for an extrusion die to produce a high-quality extrusion product is often required by industry. Design from experience is unsatisfactory for achieving the flexibility and precision requirements in die design. In this paper, a design method has been developed for the optimum shape design of extrusion die. The extrusion process was modelled and analysed by using the finite-element method to obtain the extrusion force and effective strain for different die shapes. A polynomial network was applied to identify the force and strain models in terms of the geometric parameters of the extrusion die. An improved genetic algorithm was used to optimise the identified model for optimal shape with minimum force and strain. It has been verified that the modelling error is extremely small. The designer can quickly and accurately access the optimal shape of an extrusion die through this new approach. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: Dr Y.-C. Hsu, Department of Mechanical Manufacturing Engineering, National Huwei Institute of Technology, 64 Wun-Hua Road, Huwei, Yunlin, Taiwan. E-mail: jasonych&commat;sunws.nhit.edt.tw     

Deadlock prevention and avoidance in FMS: A Petri net based approach

The use of structure theory of Petri nets to develop efficient deadlock prevention and deadlock avoidance methods for flexible manufacturing systems (FMSs) modelled by S⁴R nets is demonstrated. Major synchronisation patterns, such as generalised parallel and sequential mutual exclusion, frequently observed in FMS contexts can be represented by this class. The liveness property of a given S⁴R net (deadlock-freeness in the context of FMSs) is characterised in terms of structural Petri net elements called siphons. An efficient method for controlling minimal siphons of a given S⁴R net is developed where local control places are added to the net. A sufficient condition for liveness of the augmented net is provided. This constitutes a deadlock prevention approach. When the net liveness condition is not satisfied, an on-line controller, using a dynamic resource allocation policy, is developed for the augmented net. The performance of the proposed approaches is illustrated using several examples.     

Form Feature and Tolerance Transfer from a 3D Model to a Set-up Planning System

Currently, most CAD systems, even the feature-based design systems which were developed for CAPP, cannot provide exact information about an object (e.g. dimensions and tolerances). Some feature-based design systems can provide product data directly or indirectly; however, most CAPP systems still do not have an interface with CAD systems. The product data required by CAPP systems usually has a specific format which is unique to the system. In a CAPP system, it is essential for set-up planning to ensure the precision of the machining processes. Therefore, it is necessary to develop an interface with CAD models, so that the part data file can be obtained directly from the CAD representation. This paper proposes an approach for integrating the set-up planning system with a feature-based CAD system. By using an object-oriented approach – Product Data Translator (PDT), the computer-automated extraction of geometry and complete tolerance information was achieved; and the automated generation of the tool approach direction was developed. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: H.-C. Zhang, Department of Industrial Engineering, Texas Tech University, Lubbock, TX 79409&ndash;3061, USA. E-mail: hzhang&commat;coe.ttu.edu     

Identification and elimination of redundant control places in petri net based liveness enforcing supervisors of FMS

In the past two decades, a number of Petri-net-based approaches were proposed for deadlock prevention in flexible manufacturing systems (FMS). An FMS is modeled as a Petri net, and then the controller or the liveness enforcing supervisor (LES) is computed as a Petri net. A live Petri net (LPN) guarantees deadlock-free operations of the modeled FMS. An LES consists of a number of control places (CPs) and their related arcs. To-date most of the attention has been paid to make the underlying Petri net models live without questioning whether or not all of the computed CPs are necessary. It is often the case that the number of CPs determined by these approaches is not minimal. Reducing it in order to reduce the complexity of the controlled system is an important issue that was not tackled before. To address this problem, this paper proposes a redundancy test for an LES of an FMS. The proposed approach takes an LPN model, controlled by n CPs, as input and in the existence of any redundant CPs it produces redundant and necessary CPs. The proposed approach is applicable to any LPN consisting of a Petri net model (PNM), controlled by means of a set of CPs.     

Addressing Surface Error Problems Found when Using Multiple Axis Milling for the Manufacture of Turbine Impellers

This paper addresses the phenomenon of circular dots, which often occur on the component surface as a result of 5-axis machining. These dots occur typically at the interface of two or more patches owing to the cutter fouling adjoining surfaces whilst machining is being undertaken on a particular patch. The action described above forms a half-dot in the adjoining surface. This is made into a full dot, when, during the machin-ing of the second surface, the first surface is fouled. This paper is concerned with an industrial case study, namely the machining of a hydraulic transmission turbine impeller blade. The work does not eradicate the dot problem; however, it reduces the occurrence. To achieve a component completely free from the dot problem it was necessary to amend the milling strategy to minimise the motion of the A and B axes. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: Professor D. K. Harrison, Department of Engineering, Caledonian University, City Campus, Cowcaddens Road, Glasgow, G4 0BA, UK. E-mail: dha2&commat;gcal.ac.uk     

Error Analysis of a Serial–Parallel Type Machine Tool

In order to evaluate the accuracy of a serial–parallel type machine tool, an error analysis is presented. Two different methods are adopted to derive the error model, namely the linkage kinematic analysis and the differential vector method, by which the effects of strut manufacturing tolerance and actuating error on the tool position and pose are investigated. The computational results show the influences of the actuating error and the strut length error on the machine tool inaccuracies. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: Professor Kuang-Chao Fan, Department of Mechanical Engineering, National Taiwan University, Taipei, Taiwan. E-mail: fan&commat;ccms.ntu.edu.tw     

Development of an Integrated Laser-Based Reverse Engineering and Machining System

Reverse engineering technology plays an important role in a variety of manufacturing applications. It significantly reduces the production lead time and the costs of the part duplication processes. This paper evaluates the feasibility of using reverse engineering and concurrent engineering methods with data obtained from state-of-the-art laser scanning to remanufacture complex geometrical parts. Two aircraft structural components were evaluated in this study: a forward latch fitting of a C 141 and a leading edge rib of an F-15. The first phase of this project, accuracy characterisation of a reverse engineering system, demonstrated that laser scanning and CAD model reconstruction can duplicate aircraft structural components accurately and efficiently, within a tolerance of ±0.127 mm (0.005 in). The second phase of this project, development of a concurrent engineering system, showed that an integrated reverse engineering and CAM machining system can make the entire remanufacturing process more automatic and efficient, further reducing part turnaround time. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: Dr J. Chow, Department of Industrial Engineering, Florida International University, Miami, FL 33196, USA. E-mail: chow&commat;eng.fiu.edu     

Connection Method for Dynamic Modelling and Simulation of Parallel Kinematic Mechanism (PKM) Machines

The design of a PKM (parallel kinematic mechanism) machine usually concentrates on a kinematic analysis but its dynamic control behaviour is not paid equal attention, so there is a need to model a PKM machine dynamically. This paper presents a connection method for dynamic modeling of a PKM machine by introducing active and passive matrices. Using computer algebra, this method makes the dynamic modeling processes available, even though the kinematic constraint Eq. cannot be solved as analytical solutions. The modeling is used succesfully for a planar PKM machine, called PAMELA (parallel mechanism with linear actuators). Using dynamic modeling and simulation, we can anticipate the dynamic behaviour of the PAMELA machine and develop a suitable algorithm for the motion control. This enables a better dynamic configuration of the PAMELA machine to be obtained. As a consequence, it speeds up the design process and reduces the development cost before a physical machine is built. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: Dr Q. Huang, Department of Manufacturing Systems, The Royal Institute of Technology, 100 44 Stockholm, Sweden. E-mail: qhu&commat;cadcam.kth.se     

A Generic Part Orientation System Based on Volumetric Error in Rapid Prototyping

The paper presents the development of a generic part orientation system for rapid prototyping by considering the issue of volumetric error encountered in parts during the layer by layer building process in a rapid prototyping (RP) system. An algorithm is developed that slices the part with horizontal planes and computes the volumetric error in the part at different orientations by rotation about user-specified axes. The system recommends the best orientation based on the least amount of volumetric error in the part. The system has been tested using several examples of simple and complex parts. The generic part orientation system is believed to be first of its kind based on a volumetric error approach and will be useful for RP users in creating RP parts with a higher level of accuracy and surface finish, and also for intelligent process planning in rapid prototyping. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: Assoc. Prof. S. H. Masood, CAD/CAM/CAE Group, Industrial Research Institute Swinburne, Swinburne University of Technology, Hawthorn, Melbourne, 3122 Australia. E-mail: smasood&commat;swin.edu.au     

Investigation of 3D Non-Random Porous Structures by Fused Deposition Modelling

The development of 3D non-random porous structures for biomedical applications has been of interest for many years. Processing of these 3D non-random porous structures using the fused deposition modelling (FDM) process is presented in this paper. The FDM built structures were evaluated to determine their suitability for use in the area of tissue engineering. The influence of process parameters on the porosity, pore diameter and compressive strength of the porous structures was investigated. The FDM process was found to be able to provide good control and reproducibility of the desired degree of porosity and 3D microstructure. This technology also offers flexibility and ease of varying the microstructure to meet specific structural and functional requirements for tissue engineering. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: Dr C. K. Chua, School of Mechanical and Production Engineering, Nanyang Technological University, Nanyang Avenue, 639798, 2263, Singapore. E-mail: mckchua&commat;ntu.edu.sg     

On the Dry Machining of Steel Surfaces Using Superhard Tools

Coolant for cutting and grinding not only increases the production costs, but also damages the environment and health of the employees. Therefore, attention should be directed towards machining processes, where the use of coolant can be reduced significantly or even stopped. Analysis of the cutting processes and the tool materials throws light on the area where wet, moist, or dry machining are applicable. Dry machining with CBN tools, so called hard turning, performed on hardened steels has produced very favourable results, which are applicable in industry. The characteristics of the surface integrity with dry machining are more favourable than with grinding and the operation costs are reduced. In hard turning, the compressive residual stress field developed, in contrast to the tensile stresses developed in grinding, increases the fatigue life of the machined components. RID=" ID=" <E5>Correspondence and offprint requests to</E5>: Professor A. G. Mamalis, Manufacturing Technology Division, Department of Mechanical Engineering, National University of Athens, 42, 28th October Avenue, 106 82 Athens, Greece. E-mail: mamalis&commat;central.ntua.gr     

S3PMR网的一种死锁预防优化策略

针对Petri网的S3PMR中的死锁预防问题,提出一种优化的控制器设计方法.当控制器的优化性不能保证时,要对所添加的控制器进行结构分析,提出了一个输出弧位置最优化的死锁预防控制算法.将S3PMR中的严格极小信标分为基本信标和从属信标,对每一个基本信标添加一个控制库所,使其P-不变式可控,且不会产生新的可被清空信标,对从属信标的控制则通过调整基本信标的控制深度变量来实现.从而用少量的控制库所得到结构更简单、许可行为更多的活性Petri网控制器.     

Modeling and analysis for a kind of flexible manufacturing system involving time factors

Time control and management are important in flexible manufacturing systems (FMS). The time to finish the machining unit is uncertain because of the uncertainties of the workpieces, so the whole time to finish the FMS is also variable. In order to reduce the time to finish for the whole FMS to improve efficiency, the modeling and analysis method for this timing kind of FMS based on standard Petri net is proposed. The modeling method is a mapping from the machining units to the component of a Petri net, and the timing factors are represented by a timing function on the place set. With the Petri net model obtained and its reachability graph, the timing factors influencing the implementation of the FMS are analysed and presented. In addition, the method is obtained to find the best state line for the implementation of the FMS.     

自动制造系统中的迭代式死锁预防策略

为解决自动制造系统中的死锁问题,提出一种将混合整数规划算法和Petri网相结合的迭代式预防策略。在该策略中,混合整数规划算法中的0／1变量用来表示Petri网模型中的库所和变迁是否与一个最大的可被清空的信标相关。由于从一个最大的可被清空的信标中可以容易地计算出一个严格极小信标,就可以在不遍历所有的严格极小信标的情况下,直接求得一组基本信标,从而大大地降低了策略的时间算法复杂度。同时,控制该组基本信标可以确保目标系统具有简单的控制器结构和尽可能多的许可行为。实验结果表明了该控制策略的有效性和高效性。     

On a maximally permissive deadlock prevention policy for automated manufacturing systems by using resource-oriented Petri nets

It is theoretically and practically significant to synthesize a maximally permissive (optimal) controller to prevent deadlocks in an automated manufacturing system (AMS). With an AMS being modeled with Petri nets, by the existing methods, integer linear programming (ILP) problems are usually formulated and solved to obtain optimal policies by forbidding illegal markings at the same time no legal marking is excluded. Without an efficient technique for solving an ILP, such a method is usually computationally prohibitive. A resource-oriented Petri net (ROPN) is employed to model a class of AMS for resolving the deadlock control problem with maximal permissiveness in this paper. Efficient methods are developed to figure out the key structures in an ROPN model for deadlock prevention. Based on the structural properties of ROPN models, this work explores several types of illegal markings that can be prohibited optimally by structural analysis. For these markings, a deadlock prevention policy can be derived in an algebraic way without solving a notorious ILP problem. For the other markings, linear programming (LP), instead of ILP, approaches are developed to forbid them optimally. Thus, a maximally permissive controller can be developed while the computational cost is reduced greatly. The proposed methods are verified by typical examples in the literature.     

Matrix Controller Design and Deadlock Analysis of Automated Manufacturing Systems. Part 1. Designing the Matrix-Based Controller

A system theory approach is used to design rule-based discrete-event controllers for the sequencing of jobs in manufacturing systems. The controller is described in terms of matrix equations that are easy to implement on a personal computer. Industrial engineering (IE) techniques and the concepts of Petri nets (PN) are included. A standard bill of materials (BOM) is used in the first design step to make a "task sequencing matrix". Then a resource requirement matrix is constructed to add non-shared resources and shared resources (e.g. pallets, transport robots, and material handling machines). Non-shared resources are controlled using inner decision loops. However, shared resources require outer decision loops for dispatching and routeing that resolve conflicts, taking into account the specified performance measures to be optimised (e.g. percentage of idle time, throughput, etc.). Failures are simply represented as disturbance inputs, allowing design for failure recovery. The rule-based controller design algorithm is a step-by-step procedure with repeatability and guaranteed conflict/deadlock resolution. It shows that the closed-loop system, once designed, is equivalent to a Petri net (PN); this gives, as a by-product, an algorithm for PN design. Furthermore, the matrix formulation allows a rigorous analysis of deadlocks in terms of circular wait and blocking, and the resources available.