一种基于Petri网的顺序共享资源AMS＊s

Ｐｅｔｒｉ网控制器自动设计及控制程序自动生成方法的研究是自动制造系统ＡＭＳｓ和柔性制造系统ＦＭＳｓ领域研究的热点问题之一〔２～６〕。本文以ＡＭＳｓ计划和调度产生的生产序列ＰＳ和资源需求序列ＲＲＳ为基础，为顺序共资源ＡＭＳｓ设计了一种规格说明语言，以自动生成ＡＭＳｓＰｅｔｒｉ网模型的矩阵形式，并给出了转换步骤。由于引入了资源状态反馈，故生成的Ｐｅｔｒｉ网模型是无死锁的。最后，用一个实例说明了设计过程。     

A modular simulator for design,planning, and control of flexible manufacturing systems

Flexible manufacturing systems are designed to produce a variety of different part types with high machine utilisation, short lead times and little work-in-progress inventory. Simulation is an efficient tool to verify design concepts, to select machinery, to evaluate alternative configurations and to test system control strategies of an FMS. This paper discusses a general-purpose, user-oriented discrete simulator (the Modular FMS Simulator) which can be used for design as well as for operation and scheduling of FMSs. The package can be implemented in different hierarchical steps of FMS production planning. It is also a useful tool in validating the results of analytical models or heuristic procedures developed for FMS problems. This package contains features for the system hardware and the control hierarchy. The model can study multiple part families, various station types, different number of work-in-process buffers and carts and almost any system layout. It is also possible to analyse the performance of the system. The package contains a set of decision rules from which the user can make his choice.     

A Heuristic Search Approach Using Approximate Solutions to Petri Net State Equations for Scheduling Flexible Manufacturing Systems

This paper proposes a new heuristic search approach based on an analytic theory of the Petri net state equations for scheduling flexible manufacturing systems (FMSs) with the goal of minimizing makespan. The proposed method models an FMS using a timed Petri net and exploits approximate solutions of the net's state equation to predict the total cost (makespan) from the initial state through the current state to the goal. That is, the heuristic function considers global information provided by the state equation. This makes the method possible to obtain solutions better than those obtained using prior works (Lee and DiCesare, 1994a, 1994b) that consider only the current status or limited global information. In addition, to reduce memory requirement and thus to increase the efficiency of handling larger systems, the proposed scheduling algorithm contains a procedure to reduce the searched state space.     

Simulation for maintenance of an FMS: an integrated system of maintenance and decision-making

Flexible manufacturing systems (FMSs) are designed to produce a variety of different part types with high machine utilisation, so the maintenance technique is necessary and very important in an FMS. This paper discusses the maintenance problem in an FMS and its simulation, analyses the maintainability of a real FMS shop, and presents the architecture of an integrated system of maintenance and decision-making/scheduling for manufacturing shop control. The modelling and simulation of the maintenance activities in the shop are shown. The simulation program is written in SLAM II and the special subroutines are realised in Fortran. The interest is directed towards the use of the method of simulation for maintenance and decision-making in FMSs.     

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 graphical modeling of FMSs

Presented in the article is a method for constructing a graphical model of an FMS by using a new modeling tool called JR-net (Job Resource relation-net). JR-net is an object-oriented graphical tool for modeling automated manufacturing systems (AMSs), such as FMSs, FASs, and AS/RSs. As with the object-oriented modeling paradigm of Rumbaugh et al. (1991), the JR-net modeling framework supports the three stages of models: static layout model (object model); job flow model (functional model); and supervisory control model (dynamic model). In this article, the existing JR-net structure (Park 1992, Han et al., 1995) is extended further to make it a graphical tool for FMS modeling. Using the extended JR-net, a step-by-step procedure for constructing a graphical model of FMSs is presented. Also addressed are issues of classifying FMSs in terms of their generic functions and of utilizing the JR-net model of FMSs.     

Holonic Concept Based Methodology for Part Routeing on Flexible Manufacturing Systems

A flexible manufacturing system (FMS) is designed to achieve good productivity and low cost. The success of an FMS depends largely on effective production scheduling and control. However, it has been found that current manufacturing scheduling and control algorithms lack the flexibility to handle interruptions or resource breakdowns; hence, system performance drops dramatically and abruptly when interruptions occur. This research develops a computer-simulation-based framework of FMS scheduling and control system using the holonic concept. This framework can maintain stability and flexibility while accommodating system disturbance, increase throughput, reduce part flow-time and work-in-process inventory, and balance workload among identical workstations. The significance of this research is the investigation of an innovative approach to revolutionary advances of control technologies for advanced manufacturing systems, and to the revitalisation of control and scheduling algorithms used by existing FMSs. A case study has been provided to substantiate the effectiveness of this proposed framework.     

A pattern-directed approach to flexible manufacturing: A framework for intelligent scheduling, learning, and control

The planning, scheduling, and control of manufacturing systems can all be viewed as problem-solving activities. In flexible manufacturing systems (FMSs), the computer program carrying out these problem-solving activities must additionally be able to handle the shorter lead time, the flexibility of job routing, the multiprocessing environment, the dynamic changing states, and the versatility of machines. This article presents an artificial intelligence (AI) method to perform manufacturing problem solving. Since the method is driven by manufacturing scenarios represented by symbolic patterns, it is referred to as pattern-directed. The method is based on three AI techniques. The first is the pattern-directed inference technique to capture the dynamic nature of FMSs. The second is the nonlinear planning technique to construct schedules and assign resources. The third is the inductive learning method to generate the pattern-directed heuristics. This article focuses on solving the FMS scheduling problem.In addition, this article reports the computation results to evaluate the utility of various heuristic functions, to identify important design parameters, and to analyze the resulting computational performance in using the pattern-directed approach for manufacturing problem-solving tasks such as scheduling.     

FMS调度与控制的统一建模与集成设计

分析了FMS调度与控制统一建模与集成设计的必要性，从FMS运行过程的IDEF0功能建模入手，建立了基于模块化彩色赋时Petri网（CTPN）的FMS调度与控制的统一模型。该模型不仅可描述FMS的调度问题，而且能表达FMS的运行控制逻辑与仿真，从而为FMS控制系统的集成设计奠定了基础。为简化FMS控制系统的设计，提出了虚拟工作站的概念与方法，将FMS控制器的部分控制功能下放到低层的工作站控制层。基于上述CTPN统一模型，开发了FMS调度与控制的集成设计原理和方法。     

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.     

Scheduling FMS with alternative routings using Petri nets and near admissible heuristic search

This paper proposes and evaluates a near admissible heuristic search strategy and its application to a kind of flexible manufacturing system (FMS) scheduling in a Petri net framework. Petri nets can concisely model the strict precedence constraint, multiple kinds of resources, and concurrent activities. To cope with the complexities for scheduling of FMS with alternative routings, this paper proposes an admissible heuristic function based on the execution of P-timed Petri nets and presents an improved dynamic weighting A* strategy using the proposed heuristic function. The search scheme does not need to predict the depth of solution in advance and the quality of the search result is also controllable. Some numerical experiments are carried out to demonstrate usefulness of the algorithm.     

A fuzzy integrated decision-making support system for scheduling of FMS using simulation

In the complex environment of an automated manufacturing system, decision-making is one of the most important and difficult tasks of a manager in general or a scheduler in particular. Flexible Manufacturing Systems (FMSs) are highly automated and expensive systems. The high investment cost of a FMS justifies the use of computer simulation support. This paper investigates the operational problems of FMSs through simulation, and different combinations of scheduling rules are evaluated by a fuzzy integrated decision-making support system.     

基于扩展高级全局决策Petri网的FMS优化模型

柔性制造系统是一个复杂的离散事件动态系统。在扩展高级决策：Petri网的基础上，提出了一种具有全局结构的扩展高级全局决策：Petri网，对柔性制造系统进行建模的方法。以扩展高级全局决策Petri网与基于遗传的最小平衡算法结合为例，证实了扩展高级全局决策：Petri网与智能优化方法相结合，既提高了FMS优化调度的整体性能，又使调度具有较强的可观性。     

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.     

Scheduling tasks and vehicles in a flexible manufacturing system

Due to their increasing applicability in modern industry, flexible manufacturing systems (FMSs), their design, and their control have been studied extensively in the recent literature. One of the most important issues that has arisen in this context is the FMS scheduling problem. This article is concerned with a new model of an FMS system, motivated by the practical application that takes into account both machine and vehicle scheduling. For the case of a given machine schedule, a simple polynomial-time algorithm is presented that checks the feasibility of a vehicle schedule and constructs it whenever one exists. Then a dynamic programming approach to construct optimal machine and vehicle schedules is proposed. This technique results in a pseudopolynomialtime algorithm for a fixed number of machines.     

An FMS scheduling and control decision support system based on generalised stochastic Petri nets

This paper presents an FMS scheduling and control DSS (decision support system) using generalised stochastic Petri nets (GSPNs) for model representation and analysis. The function of the DSS is to assist the FMS operator to search for suitable control strategies that will achieve efficient performance. It can also be called upon in the event of unforeseen changes in production requirements, component failures, or other related contingencies. The GSPN modelling approach is employed because GSPNs can characterise random processing times, machine breakdown and repair rates. The GSPN employed in the proposed DSS also incorporates dispatching control at conflicting immediate transitions and can be used to determine various performance measures pertaining to scheduling and control. An application example of the DSS for the processing of two part types in a three-machine FMS is also described.     

Modeling FMS with decision Petri nets

Decision point extended timed Petri nets or decision Petri nets (DPN) are introduced as an extended modeling framework for FMS performance evaluation. The decision point extension allows the explicit modeling of the control of the flow of tokens in timed Petri nets and hence represents the control of the flow of material, resources, and information in FMS. Further, the concept of a bounded transition is proposed to conveniently model the blocking logic in an FMS with limited buffer capacities. The motivation to present these conventions is to develop a user-friendly graphic model to represent FMS designs for analysis by discrete event simulation. DPN affords concise models that can be conveniently developed and easily transformed into discrete event simulation models. With the help of a simple FMS example, which includes a number of part types, loading rules, dispatching rules, and probabilistic branching (at an inspection station), we illustrate the DPN model development. As an illustration of the ease with which it can be tranformed into a simulation model, we have developed a generalized simulator called ROBSIM and outline here its methodological basis. The proposed concepts should be of interest to users of discrete event simulation in FMS design or elsewhere to tap the potential of basic Petri net concepts for graphic representation and specification purposes. In particular, our work should encourage other researchers to develop extensions relevant to their own areas of interest.     

Experimental investigation of an FMS due-date scheduling problem: Evaluation of machine and AGV scheduling rules

Although extensive research has been conducted to solve design and operational problems of automated manufacturing systems, many of the problems still remain unsolved. This article investigates the scheduling problems of flexible manufacturing systems (FMSs). Specifically, the relative performances of machine and automated guided vehicle (AGV) scheduling rules are analyzed against various due-date criteria. First, the relevant literature is briefly reviewed, and then the rules are tested under different experimental conditions by using a simulation model of an FMS. The sensitivity to AGV workload, buffer capacity, and processing-time distribution is also investigated to assess the robustness of the scheduling rules.     

基于EHLGEP-N的柔性制造系统的建模

柔性制造系统（FMS）是复杂离散事件动态系统.利用EHLGEP-N模型,对FMS建模,引入了全局库所G,使模型有了智能优化的思想,既提高了FMS优化调度的整体性能,又使调度具有较强的可观性.     

基于 Petri网的柔性制造系统动态优化模型

为解决柔性制造系统的动态优化调度问题,在基于扩展高级全局决策Petri网的柔性制造系统优化模型的基础上,提出了实时一优化切换控制Petri网模型。该模型在柔性制造系统发生加工设备故障、急件插入等异常情况时,自动切换并运行全局优化调度算法,并在系统允许的时间范围内,再切换返回到原有系统状态,按照新的优化结果运行。最后,以实时一优化切换控制Petri网模型与基于遗传的最小平衡算法结合为例,证实了该模型是有效的。