This paper presents a visual feedback available robotic gait training system for motor recovery of hemiplegic stroke survivors. The system is composed of a treadmill consisting of two split belts, a pelvic support manipulator assisting patient's pelvic movement, and a visual interface feedbacking patient's gait phase. The split-belt treadmill allow patient to walk in different velocities between sound side and affected side legs, and detect patient's gait phase by current value of DC motor. The pelvic support manipulator provides three active actuations to assist patient's leg swinging during walk training. The virtual walking scenario gives visual feedback for patient while providing patient's gait phase calculated from motor current of the treadmill. One subject with simulated stroke participated in this study. Experiment results indicate gait phase of the virtual model can well track that of patient's walking, verify the feasibility of the proposed system to improve gait recovery during rehabilitation.

In this paper, a feature extraction method called kernel Fisher's emotion pattern (KFEP) based on the kernel Fisher's discriminant analysis and spectral powers of multiple EEG rhythms is proposed for emotion recognition. An emotion-induction paradigm is designed for emotional EEG data collection, where a set of pictures selected from the International Affective Picture System (IAPS) are used as the emotion induction stimuli. Experimental results indicate that the KFEP feature performs better than the commonly used spectral power features. Our proposed KFEP achieves high classification accuracies of valence (78.49%) and arousal (81.93%).

Timed Petri net (TPN) has been utilized as a visual formalism for the modeling of complex discrete event dynamic systems. It illuminates the features on describing properties of causality and concurrency. Moreover, it is well-known that synchronized timed Petri net (STPN) allows us to present all of the concurrent states in complex TPN. In this paper, we propose a new methodology to design, analyze and implement an urban traffic network control system by using STPN. The applications of STPN to eight-phase, six-phase and two-phase traffic lights are illustrated. The advantage of the proposed approach is the clear presentation of traffic lights' behaviors in terms of conditions and events that cause the phases alternations. Moreover, the reach ability and reversibility properties of the control STPN will be obtained.

Deadlock prevention policies are used to solve the deadlock problems of flexible manufacturing systems. Theory of regions is the efficient method for obtaining optimal (i.e. maximally permissive) controllers. All legal and live maximal behavior can be preserved by using marking/transition-separation instances (MTSIs) or event-state-separation-problem (ESSP) methods. However, solving all sets of inequalities is very time-consuming. Moreover, the number of linear programming problems (LPPs) of all legal markings is also exponential with net size. In this paper, a novel methodology is proposed to reduce the number of MTSIs/ESSPs and LPPs. Preciously, one new concept called critical ones of crucial marking/transition-separation instances (COCMTSI) is developed and used in this deadlock prevention policy that allows designers to employ few MTSIs to deal with deadlocks.

Deadlock prevention policies are used to solve the deadlock problems of FMSs. The theory of regions is recognized as the unique method for obtaining maximally permissive (i.e., optimal) controllers in the existing literature. In this paper, the selective siphons and critical markings method [17] is merged in the new deadlock prevention policy. First of all, reachability graph is still needed. Second, CMTSIs are identified. Further, selective siphons and critical markings method is used to check if all dead/quasi-dead markings of CMTSIs are covered by these selective siphons. Furthermore, choose anyone CMTSI that belongs to a same selective siphon to be processed. Finally, controllers are therefore obtained. Experimental results indicate that the computational cost can be reduced again. Besides, it is the most efficient policy to obtain maximal permissive behavior of Petri net models.

Based on the characteristics of electric vehicles (EV), this paper proposes a conceptual framework utilizing the Controller Area Network (CAN) bus technology, OBD-II connector and the existing telematics service systems to construct a novel telematics gateway for EV. Vehicle gateway interface has been applied to telematics service systems for many years but not to EV. The proposed framework of telematics gateway establishes a three layers' architecture, namely, the physical layer, data link layer, and application layer. The telematics gateway needs to resolve two issues: One is to simplify the framework of EV gateway interface and the other is to ensure the application scenarios for power saving and location based service (LBS). Using the framework of telematics gateway, the entire service network can meet different application scenarios for EV.

A novel approach for probabilistic timed structure that is based on combining the formalisms of timed automata and probabilistic automata representation of the system is proposed. This paper presents an algorithm that combines probability measure and clock variables constructed model. Hence, their real-valued clocks can measure the passage of time and transitions can be probabilistic such that it can be expressed as a discrete probability distribution on the set of target states. The usage of clock variables and the specification of state space are illustrated with real value time applications. The transitions between states are probabilistic by events which describe either the occurrence of faults or normal working conditions. Additionally, the passage of discrete time and transitions can be probabilistic by mean of the theory of expectation sets to obtain a unified measure reasoning strategy. Finally, an example where a probabilistic time model is used to measure a robot of a system is also presented.

Petri nets have been recognized as one of the most powerful tools for modeling FMSs. The reason is that PNs are suited well to represent FMS characteristics such as present relations, concurrence, conflict and synchronization. On the other hand, it is well known that the marking/transition-separation instances (MTSIs) method with the theory of regions has been recognized as the best (i.e. maximally permissive) policy in deadlock problems. However, its major shortcoming is the state explosion and redundant inequalities problem since the reachability graph of a plant model has to be generated when one wants to find all MTSIs. For improving these drawbacks, this paper uses the reduction method and proposes a novel concept of the crucial marking/transition-separation instances (CMTSI) which is the key of MTSIs based on Petri nets and the theory of regions. According to our experimental results, our deadlock prevention policy is more efficient in existing literatures based on the theory of regions.

With level-set formulation, new contours can emerge during the evolution of contours. A defect inspection system that utilizes the evolution of zero-level contours for segmenting postsawing wafer is proposed in this study. The system utilizes a regional formulation, which improves the level-set segmentation in images with intensity inhomogeneity. An automatic threshold is used to set the initial contour to a contour near the die region. Fewer iterations are thus required to evolve the zero-level set to segment the wafer. Without the needs for filtering in advance, the inspection can be performed directly on the segmented results. The proposed approach outperforms other postsawing inspection methods in terms of accuracy.

Statechart has been utilized as a visual formalism for the modeling of complex systems. It illuminates the features on describing properties of causality, concurrency and synchronization. In this paper, we try to describe a behavioral logical operations language by using Statecharts. The logical operation is a date structure that is used to represent by a Boolean function. This paper used them to analyze the models which are modeled by using Statecharts. Their formalism provides a clear means for presenting control logic. Finally, an example of traffic light controller system is examined successfully.

The theory of regions has been recognized as the best control policy for obtaining a maximally permissive controller in existing literature. All legal and live maximal behavior of the Petri nets model can be held by using the marking/transition-separation instance (MTSI) method. It has been established that the requirement of all sets of MTSIs is a problem in conventional studies stems from time consuming. However, the new crucial marking/transition-separation instance (CMTSIs) allows designers to employ few MTSIs to deal with system deadlocks. The advantage of the proposed policy is that the computational cost can be reduced due to few MTSIs involved in. The paper unveils a maximally permissive controller with the efficient computation can be obtained by our control policy. Experimental results, by varying the markings of given net structures, indicate that the CMTSI method is the most efficient policy among the close related approaches in existing literature.

With level set formulation, new contours can system that utilizes the evolution of zero-level contours for segmenting post-sawing wafer is proposed in this study. The system also utilizes a regional formulation, which improves the level set segmentation in images with intensity inhomogeneity. With a proper configuration, the initial contour can be given in arbitrary positions in the background. Hence, a small fixed initial contour is applied to evolve the zero-level set to automatically segment the wafer. Without necessity of applying any filtering in advance, the inspection can be performed directly on the segmented results. The experimental results demonstrate the effectiveness of the proposed approach.

Wafer defect inspection is an important process that is performed before die packaging. Conventional wafer inspections are usually performed using human visual judgment. A large number of people visually inspect wafers and hand-mark the defective regions. This requires considerable personnel resources and misjudgment may be introduced due to human fatigue. In order to overcome these shortcomings, this study develops an automatic inspection system that can recognize defective LED dies. An artificial neural network is adopted in the inspection. Actual data obtained from a semiconductor manufacturing company in Taiwan were used in the experiments. The results show that the proposed approach successfully identified the defective dies on LED wafers. Personnel costs and misjudgment due to human fatigue can be reduced using the proposed approach.

People have the need to use a novel consumer clock device for home automation, personal security and convenience. This paper presents the design and implementation of the innovative system. The system architecture which is controlled by micro-controller unit (MCU) includes main alarm clock module, lucky module and security module. In the main alarm clock module, we create a novel hourglass clock model and intelligent alarm clock features based on grey relational analysis. In the lucky module, we design a unique structure of live round according to the medical theory of psychology and hashing function for randomization. In the live round, it includes the fortune of love, career, family, and health. It adopts funny and encouraged voice to transmit messages. The system also provides the function of security using infrared sensors and third-generation (3G) mobile phone unit. The system has been successful and gets the award in Taiwan.

This paper presents an efficient method to obtain a maximally permissive deadlock prevention policy for a flexible manufacturing system based on theory of regions. The theory of regions policy can provides an optimal deadlock prevention controller which is based on the reachability graph. However, its disadvantage is the state explosion problem since all marking/transition-separation instances (MTSIs) have to be identified. For improving the shortcoming, this paper proposes a new concept of the crucial marking/transition-separation instances (CMTSIs). Experimental results indicate that the proposed control policy in this paper is more efficient than the closely related approaches in the literature.

A system for the automatic inspection of LED wafer defects is proposed to detect defective dies in a four-element (aluminum gallium indium phosphide, AlGaInP) wafer. There are over 80000 dies on an LED wafer. Defective dies are typically visually identified with the aid of a scanning electron microscope. This process involves dozens of operators or engineers visually checking the wafers and hand marking the defective dies. However, wafers may not be fully and thoughtfully checked, and different observers usually find different results. These shortcomings lead to significant labor and production costs. Therefore, a solution that consists of two Hopfield neural networks, of which one is used to identify the LED die regions and the other is used to cluster the die into three groups, is proposed to facilitate the detection of defective dies in wafer images. The experimental results show that the proposed method successfully detects defective dies in a four-element wafer.

This paper presents an approach using Petri nets for designing diagnosable discrete event systems such as complex automatic temperature control (ATC) system. The concept is based on diagnosability analysis and enhancement. In this paper, we interpret and formulate the diagnosability problem as a binary integer linear programming problem that may have a feasible solution. If the system is predicted to be non-diagnosable, the approach tries to add sensors to enhance its diagnosablity, i.e., to make the system diagnosable.

This paper addresses the deadlock problems in flexible manufacturing systems (FMS) by using a Petri net siphon control method and the theory of regions. The proposed policy consists of two stages. The first one, called siphons control, is to add, for every siphon that we identify, a monitor to the original net model such that it is optimally invariant controlled. In the second stage, the theory of regions is utilized to derive the net supervisors such that deadlocks can be prevented. The first-stage work significantly lowers the computational cost compared with the approach where the theory of regions is used alone. An FMS example is presented to illustrate the technique. By varying the markings of given net structures, this paper shows its computational advantages.

This paper presents an approach using Petri nets for designing diagnosable discrete event systems such as complex semiconductor manufacturing machines. The concept is based on diagnosability analysis and enhancement. In this paper, we interpret and formulate the diagnosability problem as a binary integer linear programming problem that may have a feasible solution. If the system is predicted to be non-diagnosable, the approach tries to add sensors to enhance its diagnosablity, i.e., to make the system diagnosable. The idea is to separate any two undifferentiated event cycles by changing their labels as a result of adding sensors. Our approach is under the assumption that the costs of sensors are not considered. This assumption is well justified in semiconductor manufacturing. We use a realworld Metal-Organic Vapor Phase Epitaxy (MOVPE) system to illustrate that our proposed approach is practically useful.

The six papers and one correspondence in this special section focus on the engineering applications of Petri nets.

This paper deals with vehicle-scheduling problem (VSP) in an automatic material-handling environment in 300-mm semiconductor wafer manufacturing. We adopt Petri nets (PNs) modeling techniques to model the complicated coupling dynamics among transport jobs and overhead hoist transport (OHT) vehicles in a 300-mm OHT loop. The congestion phenomenon among OHT vehicles is captured. With help of the PN models, we formulate the OHT VSP as an integer programming problem whose objective is to schedule OHT vehicles to transport jobs such that average job completion time is minimized. Instead of solving for the optimal solution, we develop a solution methodology to generate a feasible schedule efficiently. A Lagrangian relaxation step is first taken to decompose the PN-based, integer programming problem into individual job-scheduling subproblems. To reduce computation efforts in solving each subproblem optimally, we develop an approximation method to solve each job subproblem by utilizing a reduced PN model of the job. Lagrangian multipliers are then optimized by a surrogate subgradient method. A heuristic algorithm is developed to adjust the dual solution to a feasible schedule. Numerical results demonstrate that our solution methodology can generate good schedules within a reasonable amount of computation time for realistic problems. Compared to a popular vehicle-dispatching rule, our approach can achieve in average 32% improvements on the average delivery time in our realistic test cases.

This paper presents an iterative systematic methodology for enhancing diagnosability of discrete event systems by adding sensors. The methodology consists of the following steps. First, Petri nets are used to model the target system. Then, an algorithm of polynomial complexity is adopted to analyze a sufficient condition of diagnosability of the modeled system. Here, diagnosability is defined in the context of the discrete event systems theory, which was first introduced by Sampath [9], If the system is found to be possibly non-diagnosable, T-components of the Petri net model are computed to find a location in the system for adding a sensor. The objective is to distinguish multiple T-components with the same observable event sequences. The diagnosability-checking algorithm is used again to see if the system with the newly added sensor is diagnosable. The process is repeated until either the system is diagnosable or diagnosability of the system cannot be enhanced. Examples are given in the paper to illustrate our approach.

A siphon-based algorithm for deadlock prevention of a type of Petri nets called$hboxS^3hboxPMR$, which is a subclass of$hboxS^3hboxPGR^2$, is presented in this correspondence. The proposed method is an iterative approach by adding two kinds of control places called ordinary control (OC) places and weighted control (WC) places to the original model to prevent siphons from being unmarked. An OC place with ordinary arcs, which optimally prevent a siphon from becoming unmarked, is employed whenever it is possible, and otherwise, the WC places that adopt a conservative policy of controlling the release of parts into the system are used. Furthermore, this algorithm is not only for the subclass Petri nets but also for$hboxS^3hboxPR$,$hboxES^3hboxPR$,$hboxS^2hboxLSPR$, and$hboxS^3hboxPGR^2$nets. The authors prove the liveness and reversibility of the controlled net, and hence establish the correctness of the deadlock prevention policy. Finally, numerical experiments indicate that the proposed policy appears to be more permissive than closely related approaches in the literature.

A significant effort in recent computer-integrated manufacturing (CIM) development was carried out by SEMATECH who had laid out and created an open framework for the integration of manufacturing execution system applications running in semiconductor industries at the factory operation level. This paper presents the feasibility to incorporate basic manufacturing applications at the factory engineering level, which include product design, process planning, and material requirement planning, into the SEMATECH CIM framework to form a generic framework across both factory operation level and factory engineering level. The CIM framework established in this paper was aimed to provide a reusable integrated system framework that clearly specifies the functional interface boundaries and standard information model of the required components, in general, manufacturing systems at both factory operation and factory engineering levels. Standard unified modeling language (UML) diagrams and Petri nets have been utilized to model and analyze the specifications and dynamic behaviors of this generic CIM framework. The goal is to build a framework by creating a common, modular, flexible, and integrated object model that unifies an advanced object-oriented architecture concept and heterogeneous manufacturing application development in an open and multisupplier CIM system environment.

Semiconductor wafer defect inspection is an important process before die packaging. The defective regions are usually identified through visual judgment with the aid of a scanning electron microscope. Dozens of people visually check wafers and hand-mark their defective regions. By this means, potential misjudgment may be introduced due to human fatigue. In addition, the process can incur significant personnel costs. Prior work has proposed automated post-sawing wafer defect inspection that is based on supervised neural networks. Since it requires learned patterns specific to each application, its disadvantage is the lack of product flexibility. Self-Organizing Neural Networks (SONNs) have been proven to have the capabilities of unsupervised auto-clustering. In this paper, automated wafer inspection based on a self-organizing neural network is proposed. Based on real-world data, experimental results show that the proposed method successfully identifies the defective regions on wafers with good performances.

The surface mounting technology (SMT) assembly procedures consist of calibrating the printed circuit board (PCB); vacuuming components form the feeder stations; compensating the orientation of the vacuumed surface mountable component (SMC); placing SMC chips on PCB. To increase the throughput of the assemblies, the synchronous vacuuming of SMC components is designed. Evaluating the cycle times of SMT assemblies requires the modeling of the specified times of image processing, vacuuming and releasing components and the route dependent robot movement times. In this paper, the route oriented Petri nets (ROPN) is newly proposed to solve the SMT assembly problems in flexible routes. Based on the ROPN modeling capabilities, the flexible component mounting routes and the synchronous vacuuming procedures can be modeled actually. Finally, two actual testing PCB board data were evaluated and the results had been compared with the actual cycle times to verify the proposed approaches.

Diagnosability of discrete event systems was previously defined in terms of finite state machines by Sampath et al. Two algorithms of polynomial complexity in the number of states were proposed later for checking their diagnosability. In this paper, we present an algorithm of polynomial complexity in the number of nodes for computing a sufficient condition of diagnosability of discrete event systems modeled by Petri nets. In other words, our algorithm is more efficient than previous ones since no state enumeration is necessary. This gives us an advantage to solve large real-world problems. Our algorithm is formulated as a linear programming problem, which is well-known to be of polynomial complexity in the worst case. Examples are given in the paper to illustrate our approach.

In the above paper by Zuberek, conflict-free Petri nets with deterministic timing are used for modeling cluster tools. Performance analysis of the models is based on P-invariants. This comment tries to clarify some statements in the paper and points out a more efficient performance-analysis approach based on linear programming, which is of polynomial time complexity.

Instead of making decisions with fast but local dispatching functions, the increasing computing power and up-to-moment information provisioning have made possible real-time vehicle scheduling in an automated material handling environment in 300mm semiconductor manufacturing. To our best knowledge, this paper is the first work to adopt the scheduling approach to solve the 300mm vehicle transportation problems. We adopt Petri nets to model the coupling dynamics among transport jobs and OHT vehicles in an intrabay loop. The congestion phenomenon among OHT vehicles is captured. The OHT scheduling problem is then formulated into an integer programming problem whose goal is to efficiently allocate OHT vehicles to jobs such that average job delivery time is minimized. A solution methodology that combines Lagrangian relaxation and the surrogate subgradient methods [13] is developed. To reduce computational efforts in solving each subproblem optimally, an approximation method is developed to solve for subproblems. A heuristic algorithm is developed to adjust the dual solution to a feasible schedule. Numerical results demonstrate that our solution methodology can generate good schedules within a reasonable amount of computation time for realistic problems. Compared to a popular vehicle dispatching rule, our approach can achieve 25.6% improvements on the average delivery time in our realistic test cases.

This paper presents a new class of "well-behaved" Petri nets called extended resource control net (ERCN*) merged nets that generalize the class of ERCN merged nets proposed in a previous paper by Xie and Jeng. ERCN merged nets can model parallel and synchronized processes in semiconductor manufacturing such as lot split and lot merging, which occurs frequently in a research and development (R&D) semiconductor fab (semiconductor plant) for engineering purposes. However, processing cycles for each resource type must include the initial state of the resource type. In other words, no local processing cycles are allowed. This makes the modeling of degraded behavior in semiconductor manufacturing such as rework, failure, and maintenance difficult. In the current work, this constraint is relaxed under the "extended free-choice (EFC)" or "asymmetric choice (AC)" condition. Specifically, for each operation place with degrading outgoing arcs, the FC or AC condition is satisfied. In addition, degraded behavior is modeled as blocks within ERCNs. We show that conditions for liveness and reversibility of an ERCN* merged net correspond to the absence of unmarked siphons. The "well-behaved" conditions can be transformed into inequalities of the initial marking. Examples are shown to illustrate the proposed methodology.

A typical semiconductor wafer fabrication involves hundreds of complex manufacturing steps on capital-intensive equipment. In the persistent pursuit of near perfect hundred percents of production yield and equipment utilization, automation systems have been designed implemented to provide the functions of: direct equipment control, automated material transportation, and real-time lot dispatching. This paper presents an overview of typical semiconductor fab automation systems, of which two key systems are presented: (1) manufacturing executions systems (MES) that formulates manufacturing methods and procedures, and (2) cell controller that serves as the automation link between the upper MES and the lower equipment. At the end of the paper, lot operation of the lower equipment. At the end of the paper, lot operation of one manufacturing step is detailed to highlight the interaction between MES and cell controller within a fully automated semiconductor fab.

This paper presents a new class of "well-behaved" Petrinets called ERCN merged nets that generalize the class of ERCN merged nets proposed in (X.L. Xie and M.D. Jeng, 1999). ERCN merged nets can model parallel and synchronized processes in semiconductor manufacturing such as lot split and merging. However, processing cycles for each resource type must include the initial state of the resource type. In other words, no local processing cycles are allowed. This makes the modeling of degraded behavior in semiconductor manufacturing such as rework, failure, and maintenance, difficult. In the current work, this constraint is relaxed under the "extended free-choice (EFC)" or "asymmetric choice (AC)" condition. Specifically, for each operation place with degrading outgoing arcs, the FC or AC condition is satisfied. In additions, degraded behavior is modeled as blocks within ERCNs. We show that conditions for liveness and reversibility of an unmarked siphons. The "well-behaved" conditions can be transforms into inequalities of the initial marking. Examples are shown to illustrate the proposed methodology.

Failure diagnosis in the context of DES was first formulated by Sampath et al. Where the notion of diagnosability and the associated diagnoser are proposed. Ushio et al. extended Sampath's study to systems modeled by Petri nets. This paper further assumes some of the transitions in a Petri net model are observable in the sense that its occurrence can be observed. The main contribution of this study shows how diagnosers and verifiers for systems modeled by Petri net are constructed accordingly. As shown by examples, the additional information from observed transitions adds diagnosability to the system.

Statecharts have been proposed as a visual formalism for the behavioral of complex systems. The dynamical behavior of an elevation is a example to illustrate the operation of statechart systems because it shares with many other discrete event systems (DESs) the features of: simple actions, aggregating complexity of state descriptions, and great variety of possible control strategies and resulting trajectories. This paper applies the statechart terminologies to cope with the difficult situation of elevator system problems. In this paper, we present the modeling, control and implementation of an elevator system. A statechart-based for an elevator controller design and implementation is proposed. The intended advantage of the proposed controller is that using statechart terminologies, we can describe the system's behavior over time, including the dynamics of activities, and the conditions and events that cause states to change and other occurrences to take place. Moreover, A statechart-based approach is adopted to model the operation flows in the elevator system, and from the hierarchical tree of the elevator system, we can construct its statecharts model.

Generic equipment control, which allows control of multiple types of equipment simultaneously, is made possible under the premise that individual equipment operational scenario can be normalized. Scenario normalization for In-Line Steppers (ILS) in a photolithographic cell is complicated due to the necessity of integrating the track and stepper. To the best of our knowledge, scenario normalization for ILS and has not been addressed before in the literature. To establish the foundation of photolithographic cell control, this paper addresses the scenario normalization procedure for ILS and its implementation. To do so, we use the sequence diagram that highlights the operation details at the equipment level to model the operational scenarios of the stepper and track. Then, the overall operational scenarios are checked against the normalized operational flow to derive normalization rules, expressed in terms of "triggering rules" before being implemented in an event triggering programming platform as a coordinator between the equipment control system and the ILS. The design of an ILS coordinator for a real-world photolithographic cell controller is presented in detail.

Huang et al. (2001) proposed a deadlock prevention policy based on Petri net siphons for flexible manufacturing systems (FMS). The current paper presents an analysis to show that in terms of control, the proposed policy appears to be more permissive than previous siphon-based approaches. Specifically, two siphon-based methods are compared with this approach. One is Ezpeleta et al.'s (1995) work for S/sup 3/PR nets and the other is Huang et al.'s (2001) work called a two-stage policy due to its two stages of preventing deadlocks. All these three rely on the addition of control places to the original net model to prevent siphons from being unmarked. The differences lie in the exact locations and sequences of adding the control places. Our analysis starts with the development of several theoretical results followed an experimental study. Through reachability analysis, all of the experiments indicate that the proposed policy appears to be more permissive than the other two. In addition, the two-stage policy appears to be more permissive than Ezpeleta et al.'s approach.

This paper presents a methodology and its software implementation that converts UML models to Petri nets for modeling semiconductor manufacturing systems. Three widely adopted techniques of UML, the class diagram, the sequence diagram, and the state diagram, are selected as the front-end models for the user. The sequence diagram is extended with the power of describing concurrency, synchronization, choice, and confluence. The system model as specified by the user using the class, extended sequence and state diagrams is automatically converted to Petri nets for system analysis or simulation using the proposed software tool. The proposed methodology differs from prior work in that (1) the sequence diagram is extended; (2) low-level and unmodified Petri nets are used, which are equipped with more analysis techniques; and (3) to model a system, the user does not have to directly construct Petri nets. The proposed methodology has been tested for semiconductor manufacturing modeling.

This paper presents a new class of Petri nets, called process nets with resources (PNRs), for modeling manufacturing systems where only parts can interact with resources, and resources alone cannot interact with one another. PNRs properly include S/sup 3/PR, augmented marked graphs, and some subclasses of resource control net (RCN) merged nets and ERCN merged nets. As a result, PNRs can model far more complex manufacturing process flows and resource sharing than these nets. To construct a PNR, we first build a process net to specify the process flow for each part type. A process net is a consistent, conservative, strongly connected, and live Petri net that satisfies three conditions, including strong reversibility. Then resource places denoting the availability of resource types are added to the process nets. We generalize strong reversibility for PNRs in order to check a sufficient condition for reversibility of PNRs. It is shown that strong reversibility and reversibility of a PNR depends on the siphons. Liveness of a PNR can be verified by checking the potential firing ability of all transitions of each isolated process net, which is, informally speaking, a process net with all resources allocated to it. A manufacturing example is given to show the applicability of PNRs.

We present a new deadlock prevention algorithm for a class Petri nets. A new class of net that is extended from S/sup 3/PR, called ES/sup 3/PR, where deadlocks are related to unmarked siphons. This method is an iterative approach by adding two kinds of control places, called the ordinary control place and weighted control place, to the original model to prevent siphons from being unmarked. We obtained the relation of the algorithm, liveness and reversibility of the controlled net. Finally, a flexible manufacturing example is presented for illustrating the method.

Degraded behavior, such as reworks, failures, and maintenance, of a semiconductor manufacturing system (SMS) is not negligible in practice. When modeled by Petri nets, degraded behavior may be represented as initially-unmarked elementary circuits, interpreted as local processing cycles. Most existing "well-behaved" net classes for manufacturing have problems with describing such cycles and thus may have difficulties in modeling SMSs. We extend the class of nets in Jeng and DiCesare (1995) into the class of RCN* merged nets that model SMSs with such cycles. To model an SMS, we first describe the behavior of each resource type using a state-machine module, called RCN. Any RCN can be constructed as a connection of acyclic sub-nets called blocks, where one of them denotes the normal behavior of the resource type and the others denote its degraded behavior. Next, an RCN* merged net for the entire system is built by fusing all modules, conforming to three constraints, along their common transition sub-nets, which represent their synchronization. In the analysis of RCN* merged nets, we prove that their liveness and reversibility depend on the absence of unmarked siphons, which are structural objects that mixed integer programming can check rapidly. Examples are given to illustrate the proposed approach.

Degraded behavior, such as reworks, failures, and maintenance, of a semiconductor manufacturing system (SMS) is not negligible in practice. When modeled by Petri nets, degraded behavior may be represented as initially unmarked elementary circuits, interpreted as local processing cycles. We extend the class of nets we presented previously (1997) into the class of RCN* merged nets that model SMSs with such cycles. To model an SMS, we first describe the behavior of each resource type using a state-machine module, called RCN. Any RCN can be constructed as a connection of acyclic subnets called blocks, where one of them denotes the normal behavior of the resource type and the others denote its degraded behavior. Next, an RCN* merged net for the entire system is built by fusing all modules, conforming to three constraints, along their common transition subnets, which represent their synchronization. In the analysis of RCN* merged nets, we prove that their liveness and reversibility depend on the absence of unmarked siphons, which are structural objects that mixed integer programming can check rapidly. Examples are given to illustrate the proposed approach.

Presents a class of Petri nets called process nets with resources (PNRs) for modeling manufacturing systems where only parts can interact with resources, and resources alone cannot interact with one another. PNRs properly includes S/sup 3/PR, augmented marked graphs, and, sub-classes of RCN merged nets and ERCN merged nets where firing a transition may only generate parallel processes for parts but not for resources. As a result, PNRs can model far more complex manufacturing process flows and resource sharing than these nets. To construct a PNR, we first build a process net to specify the process flow for each part type. A process net is a consistent, conservative, strongly-connected, and live Petri net and satisfies three conditions. Then resource places denoting the availability of resource types are added to the process nets such that for each resource place, the input and output transitions of the resource place generate a transition sub-net. For qualitative analysis, we show that reversibility of a PNR is assured if and only if there exists no unmarked siphon. Liveness of a PNR can be verified by checking the potential firability of each isolated process net, which is a process net with all resources allocated to it. For certain sub-classes of process nets, conditions for potential liveness are obtained.

Equipment Managers (EMs) play a major role in a Manufacturing Execution System (MES). They serve as the communication bridge between the components of an MES and the equipment. The purpose of this paper is to propose a novel methodology for developing analytical and simulation models for the EM such that the validity and performance of the EM can be evaluated. Domain knowledge and requirements are collected from a real semiconductor packaging factory. By using IDEFO and state diagrams, a static functional model and a dynamic state model of the EM are built. Next, these two models are translated into a Petri net model. This allows qualitative and quantitative analyses of the system. The EM net model is then expanded into the MES net model. Therefore, the performance of an EM in the MES environment can be evaluated. These evaluation results are good references for design and decision making.

A subclass of generalized stochastic Petri nets (GSPNs) with priorities, called Markovian timed Petri nets, are proposed to model semiconductor manufacturing systems that consider process priorities, routing priorities, resource re-entrance, and nonpreemptive operations. Uniformization technique is used to establish both lower and upper bounds of the performance of interest. These bounds are computable using linear programming. Numerical experiments have been conducted to evaluate the accuracy of the bounds using models adapted from real-world systems. The experiments show that the upper bounds are very close to the simulation results. Thus, performance measures can be accurately estimated using these bounds.

This paper generalizes the modular approach proposed by Jeng and DiCesare (1995) for modeling manufacturing systems with shared resources. First, the-dynamic behavior of each resource is modeled separately using extended resource control nets (ERCNs). An important feature of ERCNs is their capability to express explicitly assembly operations and parallel processes, which is not possible with resource control nets. Interactions among the resources are then modeled through merging of common transitions and common transition subnets. This paper provides conditions, expressed in terms of siphons, under which reversibility and liveness of the integrated model are obtained. Relations between siphons, circular structure and circular-wait are formally established.

An augmented reachability tree (ART) is proposed to extend the capability of the classical reachability tree (RT) for analyzing qualitative properties, such as liveness, of a class of unbounded generalized Petri nets, called 1-place-unbounded nets, where there is at most one unbounded place for each net. The idea is based on the computation of the minimal marking of each node in the tree. An algorithm for obtaining the minimal marking is shown. Examples are given to illustrate the technique. In addition to liveness, the proposed method can verify other properties such as reversibility and feasible firing sequences. Furthermore, properties verifiable by RT are also verifiable by ART.

This paper uses siphons to analyze the class of Petri nets constructed by a modular approach by Jeng and DiCesare (1995) for modeling manufacturing systems with shared resources. A resource point of view is taken. First the behavior of each resource is modeled using resource control nets, strongly connected state machines with one place being marked initially. Interactions among the resources are modeled through merging of common transition subnets. This paper provides conditions, expressed in terms of siphons, under which reversibility and liveness of the integrated model are obtained. Relations between siphons and circular-wait are formally established. Superiority of the siphon-based analysis over a previous analysis using circular wait is shown.

We use Petri nets to model and evaluate the performance of the thin film area in a real-word IC wafer fabrication system. The major products of the system are 0.44 /spl mu/m and 0.38 /spl mu/m 4MB DRAMs. By using a modular approach, the system model is constructed. Several generic net modules are developed. After the system model is obtained, we use the simulation technique to evaluate its performance. The result shows that the error between an actual and simulated machine utilization is mostly less than 6%. As a result, the performance model is validated. The validated model has been adopted to predict the maximal throughput and bottleneck machines.

Heuristic search based on Petri nets is a partial reachability graph expansion technique. The paper proposes a modified best-first algorithm and applies it to a flexible manufacturing system with assembly. A heuristic function based on the Petri net structure and dynamics is presented. It performs well especially for nets called generalized symmetric and asymmetric nets. The heuristic function consists of two parts. The first part estimates the total remaining operation time for all jobs considering system dynamics. The second part approximates the maximal total remaining operation time of each job. We begin with the first part to search the reachability tree of a timed Petri net toward an optimal or near-optimal path until a depth-bound is reached. After the depth-bound, the second part is applied. We also propose a one-level backtracking procedure to avoid deadlocks and a pruning procedure to reduce the number of explored states. Experimental results of 1500 randomly generated test cases show that this work outperforms prior work.

The etching area of a real-world IC wafer fabrication system located in Taiwan's Hsinchu Science-Based Industrial Park can be modeled using Petri net modules. In this paper, the system model, where a single global buffer is assumed, is analyzed for important qualitative properties in manufacturing: boundedness, liveness, and a property slightly weaker than reversibility called almost reversibility. It is proven that the system net is bounded. The net is live and almost reversible if the number of global buffer rooms is not smaller than the maximal number of wafers processed in the etching area (or WIP). This condition is satisfied in the target system since (1) the global buffer rooms are flexible, and (2) the usual WIP in the area is about half the monthly system throughput. This results in a simple deadlock prevention policy for the target area.

It is difficult to conduct performance evaluation of shared-resource manufacturing systems because of the complex behaviour. We propose a method for evaluating the performance of prioritized processes with shared resources modeling a class of semiconductor manufacturing systems. Markovian timed Petri nets are first used to represent systems with process priorities, routing priorities, resource re-entrance and nonpreemptive operations. Uniformization technique is then used to established both lower and upper bounds of the performance of interest. These bounds are computable using linear programming.

A class of extended Petri nets is proposed for modeling semiconductor fabrication systems, where it is assumed that wafers are stored in the same buffer when they are waiting for either rework or a subsequent operation. An extended net is synthesized by merging net modules that are especially useful for semiconductor fabrication. For qualitative analysis, the synthesized extended net is first reduced to an ordinary net. It is shown that the reduced net is bounded. The reduced net is proven to be live and almost reversible if and only if there are no empty siphons. Almost reversibility is slightly weaker than reversibility in-that the former guarantees all in-process parts can be completed but the system may not be reset in terms of periodic maintenance. Using Chu and Xie's (1997) mixed integer programming approach, the existence of empty siphons can efficiently be checked.

This paper generalizes the modular approach proposed by Jeng and DiCesare (1995) for modelling manufacturing systems with shared resources. First the dynamic behaviour of each resource is modelled separately using extended resource control nets. An important feature of ERCN is their capability to express explicitly assembly operations and parallel processes, which is not possible with resource control nets. Interactions among the resources are then modelled through merging of common transitions and common transition subnets. This paper provides conditions, expressed in terms of siphons, under which reversibility and liveness of the integrated model are obtained. Relations between siphons, circular structure and circular-wait are formally established.

This paper enhances a Petri net synthesis theory with the capability to deal with reversibility, which is an important property related to the concept of error recovery in manufacturing. The theory has been proposed to synthesize a class of Petri nets for modeling shared-resource automated manufacturing systems. The class of nets has been shown to be conservative (bounded) and possess structural liveness under two sufficient conditions. The conditions can be checked structurally by an algorithm without enumerating the states. A bounded and live net means that the modeled system cannot have capacity overflows and deadlocks, two types of unwanted behaviors in manufacturing. In this paper it is further proven that under these two sufficient conditions, the class of nets possesses reversibility. Thus the liveness-checking algorithm can be used to check reversibility without modification.

A theory that synthesizes Petri nets for modeling flexible manufacturing systems is presented. The theory adopts a bottom-up or modular-composition approach to construct net models. Each module is modeled as a resource control net (RCN), which represents a subsystem that controls a resource type in a flexible manufacturing system. Interactions among the modules are described as the common transition and transition subnets. The net obtained by merging the modules with two minimal restrictions is shown to be conservative and thus bounded. An algorithm is developed to detect two sufficient conditions for structural liveness of the net. The algorithm examines only the net's structure and the initial marking, and appears to be more efficient than state enumeration techniques such as the reachability tree method. In this paper, the sufficient conditions for liveness are shown to be related to some structural objects called siphons. To demonstrate the applicability of the theory, a flexible manufacturing system of a moderate size is modeled and analyzed using the proposed theory.

This paper presents an application of neural networks for solving the job-shop scheduling problem with the consideration of lot sizes (i.e. job batch sizes), which are important since jobs are often processed in batches. The energy-based neural network that have been proposed to solve this problem usually take a long time to converge to solutions. The authors previously (1994) proposed a new neural model which needs no special convergence procedure and can find optimal or near-optimal solutions of the problem at a much faster speed. However, in this model as well as other energy-based models, the number of neurons are proportional to the lot sizes of the jobs. This may complicate the implementation. In this paper, we extend our model to solve this problem. In this extended model, the number of neurons are fixed for different lot sizes. These results are quite good in terms of quality and speed. Furthermore, in this new model, mn(n+7) number of neurons are needed to solve an n-job m-machine problem with an arbitrary lot size for each job.

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.>

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.>