This paper describes the development of a Java based simulator which has the capability to perform distributed simulation of colored stochastic Petri nets. The design specifics are presented, along with initial results using a single processor. This simulator is built based on algorithms which were developed to combine the race condition of stochastic Petri nets and the additional modeling convenience of colored Petri nets. Distributed simulation capabilities are being added to these tools, using inexpensive workstations connected solely by low cost LAN equipment. The new simulation software supports even more computing platforms than previous work, utilizing Sun Microsystems' Java to achieve processor and operating system portability. Future work is discussed, including development of new automatic partitioning and synchronization methods, which should yield significant improvement when simulating large colored Petri net models.

This paper formulates a methodology to evaluate the performance of various stochastic Petri net models including colored stochastic Petri net models. The results include an example of the performance evaluation of a stochastic Petri net. This formulation utilizes simulation to generate an approximation of the reachability graph of a Petri net, then applies moment generating function analysis to this approximate reachability graph. The approximation of the reachability graph is constructed from paths taken by a simulator as it executes the Petri net. This partial reachability graph is then combined with the firing rates of the original Petri net to form a state machine Petri net which can then be analyzed via moment generating functions. This analysis involves computing a system transfer function for the time elapsed between two specified markings of the state machine. This paper demonstrates by a small example the ability to identify a transfer function that approximates the behavior of a system represented by a Petri net.

Combines Petri nets and digraphs to implement control policies avoiding deadlocks in flexible manufacturing systems. We translate some deadlock characterizations into Petri net markings. Hence we deduce inequality constraints on the token distribution to avoid deadlocks. By using control places we define place invariants to respect these constraints.

This paper presents Petri net models of buffers and a methodology by which buffers can be included in a system without introducing deadlocks or overflows. The context is automated manufacturing. The buffers and models are classified as random order or order preserved (first-in-first-out or last-in-first-out), single-input-single-output or multiple-input-multiple-output, part type and/or space distinguishable or indistinguishable, and bounded or safe. Theoretical results for the development of Petri net models which include buffer modules are developed. This theory provides the conditions under which the system properties of boundedness, liveness, and reversibility are preserved. The results are illustrated through two manufacturing system examples: a multiple machine and multiple buffer production line and an automatic storage and retrieval system in the context of flexible manufacturing.

This paper proposes a general approach to synthesize a class of Petri nets that model shared-resource automated manufacturing systems. The approach imposes minimal restrictions on the interactions among subsystems initially so that the modeler is given significant freedom. To modularize the synthesis procedure, a shared-resource system is formulated from the processes. i.e., the subsystems, that control the system resources and the interactions among the processes. For modeling the processes. Resource control nets are defined as the basic generic modules. Then, the system model is built by merging these modules through their common transitions and common transition subnets, which denote the interactions among the processes. The merged net is proven to be conservative and thus bounded. An algorithm is also developed to check two sufficient conditions for structural liveness of the net. This algorithm examines only the net's structure, and appears to be more efficient than state enumeration techniques such as the reachability graph method.>

The primary motivation for this research is to show how Petri nets may be efficiently used within the framework of supervisory control. In particular, the paper discusses how integer programming techniques for Petri net models may be used to validate supervisors for the control of discrete event systems. We consider a class of place/transition nets, called elementary composed state machines. The reachability problem for this class can be solved by a modification of classical incidence matrix analysis. In fact it is possible to derive a set of linear inequalities that exactly defines the set of reachable markings. Finally, we show how important properties of discrete event systems, such as the absence of blocking states or controllability, may be analyzed by integer programming techniques.>

Petri net modeling combined with heuristic search provides a new scheduling method for flexible manufacturing systems. The method formulates a scheduling problem with a Petri net model. Then, it generates and searches a partial reachability graph to find an optimal or near optimal feasible schedule in terms of the firing sequence of the transitions of the Petri net model. The method can handle features such as routing flexibility, shared resources, lot sizes and concurrency. By following the generated schedule, potential deadlocks in the Petri net model and the system can be avoided. Hence the analytical overhead to guarantee the liveness of the model and the system is eliminated. Some heuristic functions for efficient search are explored and the experimental results are presented.>

In industrial applications, the quantity of error recovery codes far exceeds that required for supervisory control. Declarative programming techniques can be integrated with the traditional procedural control to reduce the efforts in developing error recovery codes and to provide flexibility for future modifications as new error types are encountered. A flexible control system that employs reasoning for both control and error recovery should distribute its functions among hierarchical levels. A symbolic level for task level control and error recovery reasoning is composed of a system model, an assembly plan and a reasoning system. A device level includes all the devices and modular control programs. A robotic assembly of a gear plate is presented as an example application of the intelligent error recovery system. The results from two implemented versions of the example application show that incremental revisions to such a system can be made easily and cost effectively, but the system requires a relatively large initial declarative programming investment.>

Research results in both bottom-up and top-down synthesis techniques for Petri net modeling are reviewed. These methods can be adopted for representing parallel and distributed application environments such as automated manufacturing systems. Bottom-up techniques, consisting of the merging of places and sharing of simple elementary paths, have the advantage of ease of system description since the modeled subsystems usually have real-life correspondences. Nevertheless, with current bottom-up techniques, the synthesized system may not exhibit the same control properties as the subsystems. Top-down methods, including refinement of transitions and refinement of places, have the advantage of viewing the system globally, which may generate more structured designs. However, it is difficult to apply these methods to the environments with highly shared resources. Examples in the context of automated manufacturing systems are given to demonstrate application of these techniques. Petri net reduction techniques and their relationship to synthesis methods are discussed.>

The authors describe the resource sharing interaction between subprocesses, which frequently appear in automated manufacturing systems, using the deviation bound. The results are used for synthesizing Petri nets in which liveness and boundedness are guaranteed. A shared resource net that can be considered a basic formulation for handling shared resource problems is introduced. A weighted deviation bound is introduced and used to characterize concurrency in generalized Petri nets.>

A method for scheduling of flexible manufacturing systems by merging Petri net modeling and heuristic search is presented. The method uses the Petri net model to generate and search a partial reachability graph, and presents an optimal or near-optimal schedule in terms of a firing sequence of transitions of the Petri net model of the system. This method can easily handle routing flexibility and shared resources. Taking this approach also relieves the analytical burden since it becomes less urgent to analyze the large net to guarantee freedom from deadlock, or liveliness once an optimal schedule is developed. Some heuristic functions to guide the search are explored, and preliminary results and the search algorithm are presented.>

Beginning with a bounded (safe), live, or reversible Petri net as a first-level net model for a system, Petri nets are synthesized by first refining operation places through basic design modules in top-down modular ways, then adding nonshared resource places stepwise, and finally adding shared resource places step by step in a bottom-up manner. Refinement theory is extended to include reversibility of Petri nets. Parallel and sequential mutual exclusions are used to model shared resources. Design of the first-level Petri nets is discussed, and two basic kinds of Petri nets, choice-free and choice-synchronization, are given to cope with different types of manufacturing systems. The major advantages of the method are that the modeling details can be introduced in incremental ways such that complexity can be handled, and the important properties of the resulting Petri net are guaranteed so that costly mathematical analysis for boundedness, liveness, and reversibility can be avoided. A manufacturing system consisting of four machines, one assembly cell, two shared robots, and two buffers is used to illustrate the design methodology.>

A moment generating function approach for performance analysis of extended stochastic Petri nets (ESPN) is proposed. In ESPN, firing delays of transitions can be either deterministic or stochastic with an extended distribution. Transfer functions for transitions are first defined based on moment generating functions of all transitions and then used to evaluate system performance. Three fundamental structures that can be reduced into a single transition are discussed. Two examples are given to illustrate the proposed approach for system performance evaluation. The advantages and limitations of such an approach are discussed, and future research directions are indicated.>

A theoretical basis for Petri net synthesis methods is provided that can be used to model systems with shared resources, and to make the resulting nets bounded, live, and reversible. Two resource-sharing concepts, parallel mutual exclusion (PME) and sequential mutual exclusion (SME), are formulated in the context of the Petri net theory. A PME models a resource shared by distinct independent processes, and an SME is a sequential composition of PMEs, modeling a resource shared by sequentially related processes. The conditions under which a net containing such structures remains bounded, live, and reversible are derived.>

The diagnostic step of the error recovery process in manufacturing systems is discussed, and an algorithm for constructing and pruning a failure propagation tree is formalized. The methodology of building of failure propagation tree is proposed. This methodology is based on a hierarchical process plan, a precondition-postcondition model of manufacturing operations, and a classification of the failure reasons. The hierarchical operation model embodies the process plan, and the functional and structural classifications for each failure reason of every operation in the model. Based on the hierarchical operation model, the final failure propagation tree is generated or expanded by linking the operations in the model. The expansion process is accomplished by iteratively applying the expansion rule and priority rule to the operations in the hierarchical operation model.>

The authors present transformation methods for generalized Petri nets by introducing and using the concept of a live and bounded circuit (LB-circuit), based on fusing common paths. An LB-circuit is a generalized version of a simple elementary circuit. The authors briefly review generalized Petri nets, including their formal definitions and properties, and define an arc ratio, a remainder, and an LB-circuit. A partially overlapping relation is introduced. Using these concepts, four lemmas and three theorems which are the theoretical background for the transformation methods are presented. Reduction methods are described with examples. Synthesis methods are illustrated for a simple automated manufacturing system, a machining/assembly process with three robots and two workstations.>

The authors focus on the diagnostic step of the error recovery process in manufacturing systems and develop theories for evaluating the diagnosability of failure knowledge in manufacturing systems. The theories are based on the action-error-feature data set, described previously by the authors (1989). The definition of one-error diagnosability and the necessary and sufficient conditions for multiple-error diagnosability are given. A simple matrix operation, called covering analysis, for testing the conditions is also presented. The methodology provides a qualitative measure for the embedded diagnostic knowledge in terms of the ability to diagnose the number of multiple simultaneous errors in the system. This provides the diagnosability of the model and the feasibility of the computation, because the covering analysis is simple and at most two analyses are required to determine multiple-fault diagnosability. A discussion of the results obtained and simple examples to illustrate those results are presented.>

Two concepts are formulated: parallel and sequential mutual exclusion (SME) in the context of Petri net theory. The conditions under which a net containing such structures is bounded, live, and reversible are derived, and they are used to construct the Petri net models for a practical manufacturing system. The sufficient conditions for a Petri net to be live and reversible include that the number of initial tokens in each place be less than or equal to the token capacity of an SME and that the net without this SME be live and reversible.>

The authors describe an approach using machine learning for developing heuristics to be used in diagnosis for automated error recovery in manufacturing systems. This approach can automatically generate diagnostic heuristics for error hypotheses. The approach is based on the integration of set covering and explanation-based learning. In this way, the diagnostic heuristics can be automatically generated and the competing errors can be narrowed down, if not identified. In addition, the set covering concept is potentially useful for diagnostic problems, since it provides a solution to the problem of multiple simultaneous errors. The set covering theory and the theoretical development based on the approach for diagnosing the error and for automatically generating diagnostic heuristics are given. The authors also propose an approach for future research to extract discriminating knowledge for the competing errors when set covering is incapable of identifying the error. A discussion of results thus far obtained, accompanied by simple examples to illustrate those results, is presented.>

The authors propose an approach to systematic synthesis of Petri net models for manufacturing systems. It is based on top-down, modular, and decomposition philosophies which make the stepwise refinement of the Petri-net models possible. Using the proposed method, it is possible to obtain a Petri net model which is guaranteed to have the most important properties in the context of manufacturing: safeness, liveness, and reversibility. A formal problem statement is presented first. Then, the previous research on synthesis approaches is reviewed. Next, several modules are defined which, when combined according to a proposed algorithm, lead to the derived model. It is proven that the algorithm yields the safeness, liveness, and reversibility properties. An example of piston-rod assembly is used to demonstrate the proposed method.>

The concept of Petri net controllers is extended to include automatic error recovery and adaptive design. In the Petri net controller considered, a place that represents an operation or a state of a machine is attached to two functions and a constant so that it can represent a system working with both normal states and abnormal states. In addition, it is possible to detect an error with the controller using watchdog timers. Four basic Petri net augmentation methods for error recovery are investigated: input conditioning, alternate path, feedback error recovery, and forward error recovery. The authors demonstrate that when these methods are used to augment the Petri net controller, some important properties of the controller are guaranteed to be preserved. These properties include boundedness or safety, liveness, reversibility and the essentially decision-free property. An example of augmentations for error recovery for a piston insertion cell with two robots is given.>

A colored Petri net (CPN) model of a cell controller capable of real-time control and monitoring of multiple workstations is described. The need to incorporate the ideas of both computer integrated manufacturing (CIM) and flexible manufacturing systems (FMS) is discussed, and the controller is based on these concepts. The CPN for the cell controller is presented and described. The controller in this case controls two workstations: the Cincinnati Milacron 5VC machining center and a robotic assembly workstation using an Adept robot. An analysis of the net is performed, and relevant portions are presented. A data structure for implementing this type of a CPN is given. The code for the controller is divided into application-dependent and -independent code. An execution algorithm is provided. The conclusions emphasize the advantages of CPNs in modeling and analysis for discrete-event control of manufacturing systems.>

An application-independent manufacturing workstation controller is described for a general purpose computer which uses Petri nets to describe the sequencing informaiton. Several additions are made to Petri nets to allow the modeling of hierarchical systems, conflict decisions, and system actions. An application is composed of a description of the Petri net model of the system using a declarative language, and action-causing procedures written in the 'C' programming language. The Petri net determines when an action is to be done. An application is documented for a machining workstation centered around a Cincinnati Milacron SVC Machining Center.

This paper details the functions of a generic manufacturing workstation controller in the context of a computer integrated manufacturing (CIM) system. For each of these functions the required software and hardware performance characteristics are assessed. A brief overview of CIM is presented followed by a discussion of manufacturing workstations. The functions presented and described are task decomposition, inventory management, monitoring and control, reporting and communications. The performance attributes are presented using a qualitative scale. In software they include several characteristics of the operating system, application development potential, and communications support. The hardware attributes are discussed in terms of modularity of architecture, computing speed, memory requirements, I/O, interrupt structure, network support, remote unit support and environmental features. The results are concisely presented on two qualitative assessment matrices which match functions with performance attributes. Details supporting these assessments are presented in the text.

A methodology is presented which makes use of both theory-based and data-based information to structure and calibrate low-order dynamic models for lake ecosystem analysis. A brief historical review explores the inductive and deductive aspects of past modeling efforts and describes the motivation for this research. A methodology, summarized in a flowchart, is discussed in terms of data analysis, conceptualization, development of a mathematical model, calibration, and three feedback stages for validity checks. This approach has been applied to the study of nutrient cycling in the south basin of Lake George, NY. The results of several iterations of the methodology are given and discussed in terms of statistical validity and agreement with biological theory. The final model is a set of difference equations containing two state variables and three external variables, and shows a good fit to the existing data. This is one of the first lake ecosystem studies to make extensive use of data in order to develop model relationships and estimate parameters.

A two-tiered dynamic model for allocating residential housing growth both among townships in a metropolitan area and among zones within a township is developed. A metropolitan-level model having data aggregated up to the township level is proposed to explain the effects of metropolitan-level controls (such as employment location and accessibility) and township controls (such as the presence of land-use regulations) on residential growth in each township. A township-level model is proposed to accept growth forecasts generated by the metropolitan model and spatially and temporally allocate this growth within a given township. A case-study metropolitan area and one township within it are chosen and a data base is developed, using published and raw data sources. Multiple linear regression analysis is used to calibrate and validate these models. Metropolitan-model results indicate good model fit (R2 = 0.835, overall model F value = 15.9) with accessibility to employment being the dominant explanatory independent variable with a strong positive correlation (partial R2 = 0.71) to the rate of housing growth. Other independent variables in the model include the property tax rate in the analysis zone (negative correlation), housing value (weak positive correlation), and land-use controls (weak negative correlation). These results support a theory of metropolitan growth that says accessibility to employment weighted by available land for development, availability of existing residential development, and low tax rates promote residential growth. A significant factor is that the presence or absence of land-use controls does not meaningfully affect growth.

Mathematical models are formulated to help planners, elected officials, and citizens in small cities estimate the socioeconomic and fiscal impacts of residential development. The city of Cohoes, NY, serves as a case study. The need for this work is established by reviewing the city's history from its period of growth as a mill town in the nineteenth century to its decline and attempt at reversal in the twentieth century. The community development process is briefly discussed. Two levels of models are developed: static and dynamic. The static models, which describe a new steady state in the city, are less expensive to implement but sacrifice flexibility and accuracy. The dynamic models, programmed in an interactive mode on the computer, are more expensive but provide a wider range of data at greater accuracy. The models contain three sectors, a residential sector which describes the changes in population and housing, a commercial sector which describes the changes in the retail economy, and the public sector which accounts for municipal costs, revenues, and tax rates. The inputs are the type and amount of development proposed. Typical outputs are population by age group, the tax revenues derived from the new development, and changes in the property tax rate. The models are calibrated with data from the city, state, and federal governments. Both static and dynamic model results indicate that new private-sector residential development on vacant city lands returns a net surplus of funds to the municipal government and school district.