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

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

An optimal-elementary-siphons-based iterative deadlock prevention policy for flexible manufacturing systems

Petri nets have been proved to be a tool with prominent capabilities to describe discrete event systems, such as flexible manufacturing systems (FMS), thanks to their excellent properties over other models. Characterization in terms of special structural elements in a Petri net called siphons has been a major approach for the investigation of deadlock-freeness in context of FMS. Utilizing the optimal elementary siphons and the modified mixed integer programming (MIP) algorithm proposed in this paper, one can detect and solve deadlock problems arising in FMS in an iterative mode with tractable computational complexity. Moreover, the MIP approach can be exploited to implement the flexibility enhancement in the resultant net system so that the obtained system is less restricted. In contrast to the conventional typical policies, this approach evolves without explicitly enumerating all the strict minimal siphons. Its legitimacy and feasibility are proved and validated through an experimental study.     

Efficient deadlock prevention policy in automated manufacturing systems using exhausted resources

To design supervisors enforcing liveness of automated manufacturing systems (AMS), an efficient deadlock prevention policy based on the exhausted resources is proposed. This policy exploits a special structure of Petri nets in the sense that the liveness of a specific system can be guaranteed if no shared resource can be emptied. In contrast to the typical conventional policies, the explicit enumeration of either the reachable states or the siphons can be avoided. Experimental results verify the efficient implementation of the proposed policy.     

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.     

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.     

Technical note—reducing mip iterations for deadlock prevention of flexible manufacturing systems

We propose adding monitors to each basic siphon and find conditions for a compound siphon to be already controlled. This (1) relieves the problem of siphon enumeration, which grows exponentially, and (2) reduces the number of subsequent time-consuming mixed integer programming (MIP) iterations.     

柔性制造系统一种次优化的死锁控制设计

为解决柔性制造系统中的死锁问题,以受控系统的许可行为作为指标,根据Petri网基本信标理论,提出了一种次优化的活性控制器设计方法.根据基本信标和从属信标的可控性关系,通过调整控制库所的初始标志,获得了具有较多许可行为的活性Petri网控制器.与文献中其他方法相比,所提的控制策略具有更好的许可性.     

A resource decoupling approach for deadlock prevention in FMS

Many deadlock prevention approaches have been suggested in the literature for Petri net models of flexible manufacturing systems, based on siphon enumeration and control. With medium and large problem dimensions, such methods often require both an excessive computational load and extremely large control sub-nets, making them unfeasible or impractical. In this work, a simple approach is proposed for the design of sub-optimal but compact controllers. The approach is based on the anticipated allocation of a sub-set of resources that decouples the deadlock prevention problem in two much smaller and simpler problems, each devoted to the deadlock prevention for a sub-set of resources only. The application of the two designed control sub-nets to the original Petri net together with resource anticipation ensures deadlock prevention. A heuristic algorithm is also provided for the selection of a suitable resource partition, in order to maximize the control quality and performance. Several illustrative benchmark examples are provided.     

An iterative approach to system setup problems in flexible manufacturing systems

System setup problems in flexible manufacturing systems deal with short-term planning problems such as part type selection, machine grouping, operation assignment, tooling, fixture and pallet allocation, and routing. In this article, we consider three of the subproblems: part type selection, machine grouping, and loading. We suggest a heuristic approach to solve the subproblems consistently with the objective of maximizing the expected production rate. The proposed procedure includes routines to generate all possible machine grouping alternatives for a given set of machines, to obtain optimal target workloads for each grouping alternative, and to allocate operations and tools to machine groups. These routines are executed iteratively until a good solution to the system setup problem is obtained. Computational experience is reported.     

Real-time scheduling with deadlock avoidance in flexible manufacturing systems

The dynamic nature of manufacturing makes rescheduling essential in today's complex production environment, particularly in flexible and re-configurable systems. Research on optimising schedules, which includes deadlock avoidance, is rather limited. Furthermore, the deadlock problem is mostly ignored in research on rescheduling. A rescheduling algorithm, that uses time petri-nets and the minimal siphons concept, was developed to deal with sources of disturbance such as machine breakdowns in real-time. The algorithm guarantees a deadlock-free new schedule. The existence of alternative routes, availability of material handling facilities and the limitation of buffer capacities were taken into consideration. The developed algorithm modifies only the affected portion of the original schedule, rather than rescheduling all jobs, in order to limit changes to the original schedule and reduce the impact on the response time.The effect of flexible routing, machine breakdowns, machine downtime, routing criterion and the use of the dispatching rule on the performance of manufacturing systems was studied. The systems performance was measured by the average flow time, the makespan and the average machine utilisation. The results indicate that utilising the system routing flexibility in real-time rescheduling, while avoiding deadlocks, improves system performance. Moreover, routing the interrupted operation to an alternative machine, based on the minimum expected completion time rather than the least utilised machine criterion, resulted in better performance.     

A distributed architecture for automated manufacturing systems

The concept of distributed architectures for automated manufacturing systems is presented here. A modular architecture for a logical cell-controller is proposed where shopfloor level modules are incorporated in the cell control system so as to allow active co-operation for distributed decision making and control. Two examples illustrating distributed formulations for specific planning and control are presented. These examples demonstrate the feasibility and potential for distributed architectures for automated manufacturing. This work has been supported by a grant from the Institute of Manufacturing Research, Wayne State University, USA.     

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.     

Object-oriented Petri nets for modelling and analysis of automated manufacturing systems

This paper presents an Object-oriented Petri Net (OPN) approach to model and analyse the dynamic behaviours of an Automated Manufacturing System (AMS). Both the basic and the complete OPN models are introduced to represent the generic and specific dynamic behaviours of an AMS, respectively. Based on the basic OPN model, we need to construct the Object Communication Net (OCNet) for each physical object, and then employ the theory of invariants to perform the deadlock analysis. For an analysed non-deadlock basic OPN model, the complete OPN model for a specific AMS may be effectively derived from it by only including those related system constraints (e.g. part routing, resource capacity), since the basic OPN class library is reusable. A conflict analysis approach is then introduced to identify all the conflicting events involved in the complete OPN model, so that the most suitable control/decision strategy for resolving each conflict event may be suggested. Consequently, a rule-based control software may be implemented directly from the specification of the validated complete OPN model by following a number of transformation rules.     

Machine cell formation for cellular manufacturing systems using an ant colony system approach

The aim of a cellular manufacturing system is to group parts that have similar processing needs into part families and machines that meet these needs into machine cells. This paper addresses the problem of grouping machines with the objective of minimizing the total cell load variation and the total intercellular moves. The parameters considered include demands for number of parts, routing sequences, processing time, machine capacities, and machine workload status. For grouping the machines, an ant colony system (ACS) approach is proposed. The computational procedure of the approach is explained with a numerical illustration. Large problems with up to 40 machines and 100 part types are tested and analyzed. The results of ACS are compared with the results obtained from a genetic algorithm (GA), and it is observed that its performance is better than that of GA.     

On a deadlock prevention policy for a class of Petri nets S3PMR

In Yan et al. (J Inf Sci Eng 25(1): 167–183, 2009), a deadlock prevention policy is proposed for a subclass of Petri nets, S³PMR, that can well model a large class of flexible manufacturing systems (FMS) where deadlocks are caused by unmarked siphons in their Petri net models. To validate the effectiveness and efficiency of the proposed approach, two examples were demonstrated in Yan et al. (J Inf Sci Eng 25(1): 167–183, 2009). This paper shows that there is a problem with one of the control places computed for one of the examples. In Yan et al. (J Inf Sci Eng 25(1): 167–183, 2009), for another example, two different deadlock prevention supervisors were proposed. It is also shown in this paper that, for these two supervisors, it is possible to obtain two subsets of control places. Thus, the structures of the two supervisors are further simplified with the same permissive system behaviours.     

Object-oriented approach of MCTPN for modelling Flexible manufacturing systems

Manufacturing industry is facing a stricter challenge than ever before owing to the rapid change in market requirements. Flexible manufacturing systems (FMSs) have a much greater capability than traditional fixed-type production systems for coping with the rapid change. In this paper, a modified coloured-timed Petri net (MCTPN) is developed to model the dynamic activities in an FMS. The MCTPN provides an object-oriented and modular method of modelling manufacturing activities. It includes colour, time, modular and communication attributes. The features of object-oriented modelling allow the FMS to be modelled with the properties of classes, objects, and container trees. Since the system activities can be encapsulated and modularised by the proposed MCTPN, the manufacturing systems can be easily constructed and investigated by the system developers. It makes the concept of software IC possible for modelling complex FMSs. Once all of the MCTPN objects are well defined, the developers need to consider only the interfaces and operations relating to the MCTPN objects. In order to demonstrate the capability of the proposed MCTPN, the FMS in the Manufacturing Automation Technology Research Center (MATRC) of the National Taiwan University will be stimulated and justified by using the proposed MCTPN along with the G2 expert system.     

A model management systems approach to manufacturing systems design

Manufacturing systems design involves the solution of a complex series of interrelated problems. This complexity will increase in the future as manufacturing practices change to meet increased global competition. Research within manufacturing systems design has mainly been focused on finding improved models for solving particular problems, or extending existing modeling techniques. This has resulted in numerous modeling tools being available to support manufacturing systems design. However, little research work has been carried out into consolidating the existing theories and models. As a result, a large body of this work has not been applied in industry.Model management has evolved as a research area which investigates methods for storing, modifying, and manipulating models. This article describes a prototype model management system for manufacturing systems design. The objective here is not to develop another decision support system for manufacturing design, but to illustrate, through the development of a prototype system, a number of key ideas of how concepts from the area of model management systems can be used to support manufacturing systems design. The prototype model management system utilizes the structured modeling framework and uses an extended version of the structured modeling language. An important aspect of the prototype model management system is the incorporation of the model development task, thus allowing the system to be easily updated and adapted. The prototype system was evaluated using a range of queueing network models for manufacturing systems design.     

Simple blocking prevention for bay type path-based automated material handling systems

This paper proposes a simple blocking prevention method for a path-based automated material handling system (AMHS) such as a semiconductor fabrication line. Here, blocking means the situation in which a vehicle stands and waits without doing anything because the vehicle in front of it is in the process of loading or unloading. Since a typical bay type path-based AMHS has a single path in each bay and no sidetracks, the blocking issue is inevitable in a large complex system with many vehicles. The proposed method is based on the swapping of load assignments between retrieval vehicles on the same path. Our simulation study on an example semiconductor line shows that the proposed method improves the AMHS productivity under various vehicle dispatching rules.     

A methodology for the implementation of automated measuring stations in flexible manufacturing systems

This paper presents a methodology for the inclusion of an automated measuring station in an existing flexible manufacturing system (FMS) by treating the measuring station as a workstation integrated into the FMS. This approach causes minimal distortion of the FMS work functions and does not depend on the control algorithms implemented on the system. A case study based on an FMS located at the Aeronautical Centre is presented. The FMS used in the case study is called CFF-ETSIA. This system contains the main elements needed in a FMS: two computer numerical control machine tools for machining and two industrial robots for handling and manipulating. The measuring station in the case study is implemented with one of the robots used to perform the necessary actions of measurement and manipulation.