Search

Provides society information that may include news, reviews or technical notes that should be of interest to practitioners and researchers. [ABSTRACT FROM AUTHOR]

Nowadays, high-throughput screening (HTS) systems are widely used in pharmaceutical industries and laboratories for the discovery of new drugs and biomedical substances. It is important to efficiently schedule them so as to reduce the cost. In the operation of an HTS system, a microplate may visit some resources more than once and complex time window constraints are imposed on some activities and activity sequences. Moreover, with the consistency requirement, a one-microplate cyclic schedule is necessary. Thus, its scheduling problem is very challenging. This article studies the scheduling problem of an HTS system for an enzymatic assay, a typical application of HTSs, from the perspective of control theory. The system is modeled by resource-oriented Petri nets (ROPNs). With the model, necessary and sufficient conditions under which a feasible cyclic schedule exists are established. Then, we determine how many microplates should be in the system for concurrent processing and the transition firing sequence to obtain the activity sequence for an optimal and feasible schedule. In this way, a feasible and optimal cyclic schedule can be found by very simple computations, which shows that polynomial algorithms for an optimal schedule exist, while the existing studies apply mathematical programming with exponential computation complexity. Also, its efficient implementation is given. [ABSTRACT FROM AUTHOR]

Given a discrete event system, it is said to be opaque if an intruder who can partially observe system behavior cannot infer that the system is necessarily in a predefined secret. A discrete event system is current-state opaque if an intruder is never able to verify whether the current state of the system is within the secret states. This article addresses the verification of current-state opacity of a discrete event system modeled with Petri nets, where the secret is defined as a set of states. The existing methods cannot deal with large-sized systems due to the curse of dimensionality. Multi-valued decision diagrams (MDDs) are widely accepted as an efficient and compact data structure for representing the extremely large reachability sets of Petri nets. We show that MDDs can be used in Petri nets with partial observable transitions and propose an approach for the verification of current-state opacity for bounded Petri nets. It is shown by experimental studies that the symbolic approach is practically more efficient than traditional techniques such as basis reachability graphs (BRGs). [ABSTRACT FROM AUTHOR]

The recent extension of a macroscopic fundamental diagram (MFD) into a bi-modal MFD (or 3D-MFD) provides the relationship among the total network circulating flows and the accumulations of private vehicles and public buses. 3D-MFD reveals the contribution of large occupancy vehicles such as buses in improving urban transportation efficiency. A lot of bi-modal traffic management techniques are introduced based on 3D-MFD to improve the urban traffic efficiency without using detailed origin-destination (OD) information. However, similar to MFD, 3D-MFD is also highly affected by the heterogeneity of a road network. In order to form 3D-MFDs with low scatter to be utilized for further bi-modal traffic management, this paper proposes a partition method to cluster road links into several homogeneous regions for a bi-modal urban network. It is comprised of three layers named as initial partition, merging, and boundary adjusting. At the initial partition layer, Seeded Region Growing (SRG) and the Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) are integrated to obtain a number of subregions. A modified Genetic Algorithm (GA) is developed to merge the subregions into larger regions at the merging layer. Then, boundary adjusting is performed by changing the region to which a boundary is clustered to optimize the result. Multi-sensor data collected from Shenzhen in China are utilized to verify the effectiveness of the proposed partition method. [ABSTRACT FROM AUTHOR]

For route choice during an outside emergency evacuation, evacuees make different route choice decisions due to their preference diversity. Furthermore, uncertainties of human behavior are inevitable, leading to a high complexity of macroscopic traffic flows and great impact on the evacuation efficiency. In this work, a simulation-based evacuation traffic planning is presented for homogenizing the network traffic flows. In the simulation, the evacuees are divided into two types: panicky and rational ones, and their route choice behavior is captured by two distinct models, respectively. The proportion of panicky evacuees is dynamically changed based on the traffic information level (TIL) and traffic states of downstream links at a decision point. Type-II fuzzy logic system (T2FLS) is used to model the uncertainties of evacuees’ subjective perception on route costs. Comprehensive numerical experiments are done to analyze the impact of TIL, behavior diversity, and the heterogeneity of macroscopic traffic flows on evacuation efficiency. Results show that the proposed evacuation traffic planning is beneficial for improving the evacuation efficiency, alleviating the proportion of panicky evacuees, and homogenizing traffic flows in a large-scale network. [ABSTRACT FROM AUTHOR]

Cluster tools play a significant role in the entire process of wafer fabrication. As the width of circuits in semiconductor chips shrinks down to less than 10nm, strict operational constraints are imposed on the operations of cluster tools in order to ensure the quality of processed wafers. Particularly, wafer residency time constraints and chamber cleaning requirements are commonly seen in etching, chemical vapor deposition, coating processes, etc. They make the scheduling problem of cluster tools more challenging. This work aims to provide a solution for dual-arm cluster tools with wafer residency time constraints and chamber cleaning requirements. To do so, it proposes a novel virtual wafer-based scheduling method. By this method, under a steady state, a PM processes either a real or virtual wafer at a time. When a PM processes a virtual one, its chamber can perform a cleaning operation. In this way, we can meet not only the strict residency time constraints for real wafers, but also innovatively meet chamber cleaning requirements. Based on such a novel scheduling method, an efficient binary integer programming model is established to optimize the throughput of cluster tools. Finally, experiments are performed to show the efficiency and effectiveness of the proposed method. Note to Practitioners—To ensure wafer quality in semiconductor manufacturing, engineers have to impose wafer residency time constraints and chamber cleaning requirements on the operations of cluster tools. In order to tackle their scheduling problem with these constraints, this work proposes a novel method based on the use of virtual wafers. Under a one-cyclic schedule obtained for time-constrained cluster tools without chamber cleaning requirements, virtual wafers are loaded into the tool such that when a PM processes a virtual wafer, a chamber cleaning operation can be performed in practice. The key to solve this scheduling problem is to find a wafer loading sequence with the highest performance in terms of cycle time. To do so, this work establishes an efficient binary integer programming model to search for such a solution. Since the obtained solution is a periodical wafer loading sequence based on a one-wafer cyclic schedule, it can be easily implemented. Therefore, this work has a high practical value to numerous semiconductor manufacturers. [ABSTRACT FROM AUTHOR]

Deadlocks are a highly undesirable situation in flexible manufacturing systems (FMSs). This article presents a direct and novel method to detect such markings by constructing the resource flow graph of a Petri net that models an FMS and to recover such markings by adding a set of recovery transitions. First, an algorithm is developed to build a new kind of directed graph called the resource flow graph of a Petri net. Resource flow graphs can well represent the competition for shared resources by different processes. Second, based on the resource flow graph, loop graphs can be found. Furthermore, partial deadlock markings can be easily detected due to their relationship with loop graphs. Then, we propose an algorithm to design a set of recovery transitions for loop graphs that are enabled at partial deadlock markings. The proposed approach can detect partial deadlock markings without generating a complete reachability graph of a Petri net and the resulting net is deadlock-free with all reachable markings by adding the obtained recovery transitions. Finally, some widely used examples are provided to demonstrate the proposed approach. Note to Practitioners—The occurrence of deadlocks in an FMS tends to cause unnecessary productivity costs and even catastrophic results. In the framework of Petri nets, reachability graph analysis can usually obtain a maximally permissive supervisor of a plant. However, it is rather inefficient since it suffers from the state explosion problem. In this particular research, we develop an off-line deadlock detection and recovery policy by setting a group of virtual events that are not present in a physical model. The proposed approach is computationally efficient since it does not require to generate a reachability graph. It guarantees that the resulted system is deadlock-free with its all original reachable markings. [ABSTRACT FROM AUTHOR]

With integer linear programming problems (ILPPs) being formulated and solved, the existing approaches design optimal Petri-net supervisors via nonpure net structures, including self-loops and data inhibitor arcs. Nonpure net structures are powerful for control of Petri-net-modeled discrete-event systems. However, in the existing work, the formulated ILPPs contain a large number of constraints, which is computationally inefficient. In this article, we propose approaches that formulate ILPPs with fewer constraints such that the computational efficiency is significantly improved. To do so, in formulating ILPPs for optimal Petri-net controllers by using self-loops and data inhibitor arcs, we remove the reachability conditions for legal markings. By doing so, an obtained solution may result in some legal markings unreachable. To solve this problem, a novel technique is developed to design an optimal controller by modifying the initial marking and structure of the obtained supervisor. It is shown that, by the reduced ILPPs, one can find the same feasible solutions as that obtained by the existing work. Finally, the proposed approaches are demonstrated by examples. [ABSTRACT FROM AUTHOR]

With the recent advancement of technologies, it is progressively easier to collect diverse types of genome-wide data. It is commonly expected that by analyzing these data in an integrated way, one can improve the understanding of a complex biological system. Current methods, however, are prone to overfitting heavy noise such that their applications are limited. High noise is one of the major challenges for multiomics data integration. This may be the main cause of overfitting and poor performance in generalization. A sample reweighting strategy is typically used to cope with this problem. In this article, we propose a robust multimodal data integration method, called SMSPL, which can simultaneously predict subtypes of cancers and identify potentially significant multiomics signatures. Especially, the proposed method leverages the linkages between different types of data to interactively recommend high-confidence samples, adopts a new soft weighting scheme to assign weights to the training samples of each type, and then iterates between weights recalculating and classifiers updating. Simulation and five real experiments substantiate the capability of the proposed method for classification and identification of significant multiomics signatures with heavy noise. We expect SMSPL to take a small step in the multiomics data integration and help researchers comprehensively understand the biological process. [ABSTRACT FROM AUTHOR]

Transportation services play an increasingly significant role for people’s daily lives and bring a lot of benefits to individuals and economic development. The randomness and volatility of traffic flows, however, constrains the effective provision of transportation services to a certain extent. Precise traffic flow forecasting becomes the key and primary task to realize the stability of intelligent transport systems and ensure efficient scheduling of traffic. This paper investigates the application of an ensemble approach based on deep belief networks for short-term traffic flow forecasting. Traffic flow data, collected from the real world, is decomposed into several Intrinsic Mode Functions (IMFs) and a residue with EEMD (Ensemble Empirical Mode Decomposition). Then, for each component, the essential feature subset is extracted by the mRMR (minimum Redundancy Maximum Relevance Feature Selection) method considering weather conditions and day properties. Furthermore, each component is trained by DBN (Deep belief networks) and their forecasting results are summed up as the output of the ensemble model at last. Results indicate that the proposed approach achieves significant performance improvement over the single DBN and other selected methods. [ABSTRACT FROM AUTHOR]

A kind of facilities for wafer fabrication, cluster tools (CTs) need to close down to an idle state from time to time because of periodical maintenance and switches from one type of lots to another, which is called a normal close-down process (NCDP). It is crucial to optimize such a transient process since it tends to occur more and more frequently due to customization. Also, process modules (PMs) in CTs are known to be failure-prone. Once a PM failure occurs, a tool needs to close down to an idle state as well, which is different from NCDP and is called a failure close-down process (FCDP). With wafer residency time constraints (WRTCs) being imposed, close-down process optimization for such a tool is challenging, since one needs to not only finish this process as soon as possible but also meet WRTCs during this transient process. In order to tackle this problem, this article first introduces steady state scheduling problems. Then, with a presented backward robot task sequence, a linear programming model is first proposed to optimize NCDP. To deal with the PM failures, efficient PM failure response policies are formulated for the cases in which a PM fails. Then, four linear programs are proposed to optimize an FCDP. Finally, industrial case studies are given to show the usefulness of the proposed approaches. [ABSTRACT FROM AUTHOR]

Nowadays, wafer fabrication in semiconductor manufacturing is highly dependent on cluster tools. A cluster tool is equipped with several process modules (PMs) and a wafer handling robot. When the tool is operating, generally each PM is processing a wafer, and the robot is responsible for delivering the wafers from one PM to another. Thus, when a wafer is completed in a PM, the robot may be busy for performing other tasks such that it cannot immediately unload the completed wafer in the PM, resulting in that the wafer has to stay there for some extra time. The processing time of a wafer together with its delay time for waiting for the robot’s arrival for unloading is defined as wafer residency time in a PM. However, a long wafer delay time may deteriorate its quality. Therefore, it is highly desired and important to reduce the wafer delay time at each step as much as possible. This work aims to tackle this important issue for single-arm cluster tools (SACTs). Specifically, by using a Petri net model, this work analyzes the steady-state operational behavior of an SACT under the backward and earliest starting strategies. It is found that there must exist wafer delay time at the steps in the upstream of the bottleneck step, and such wafer delay time can be reduced by properly adjusting the robot waiting time. Thus, three algorithms are developed to reduce the wafer delay time at each step as much as possible by properly assigning the robot idle time. Finally, the application of the proposed method is illustrated by using examples. Note to Practitioners—In a modern semiconductor fab, there are hundreds of cluster tools for wafer fabrication. To ensure wafer quality, it is important to reduce the wafer delay time in PMs of cluster tools after a wafer is processed since the high temperature, chemical gas, and particles in the PMs may damage the wafer. To do so, this work proposes three algorithms with polynomial complexity to assign the robot idle time as robot waiting time such that the wafer delay time in PMs can be reduced as much as possible. Furthermore, the obtained schedule by these algorithms is optimal in terms of the cycle time. Besides, the developed algorithms can be easily embedded into the controller of cluster tools by facility engineers. Therefore, this work has a practical value. [ABSTRACT FROM AUTHOR]

A maximally permissive (or optimal) supervisory control of an automated manufacturing system (AMS) modeled by Petri nets (PNs) can be usually implemented by imposing constraints in the form of a set of linear inequalities. To find such a set of linear constraints, in the existing work, an integer linear programming (ILP) problem is generally formulated and solved for some dominant markings obtained by reachability analysis and vector covering theory, which is computationally inefficient due to the combinatorial nature of solving ILPs to decide the coefficients of optimal linear constraints. This paper addresses the deadlock prevention problem for AMSs by developing efficient methods to reduce the computational overhead through the establishment of conditions on deciding the maximal permissiveness of linear constraints imposed on a system. By taking the advantage of structural properties of a PN model under consideration, we identify the most part of minimal covered illegal markings that can be optimally controlled via policies obtained by specific linear inequality constraints. Also, algorithms are developed to implement the proposed policies. The proposed approach can verify the optimality of a linear constraint efficiently without solving ILP problems. A linear programming method is developed to deal with the markings that cannot be processed by the proposed structural analysis. It is shown that for the considered class of PNs, called system of simple sequential processes with resources (S3PR), no mixed ILP problem needs to solve and the computational burden is dramatically reduced. Two examples are employed to demonstrate the efficiency of the developed method. [ABSTRACT FROM AUTHOR]

In LED semiconductor manufacturing, it is important to evaluate the wafer reflectance in order to validate the quality of wafers. In this work, a learning model based on ${K}$ -means clustering and neural networks is proposed to analyze the relationship between etching parameters and wafer reflectance under a complex etching environment. The implemented clustering algorithm is used to cluster historical data and reduce the effect caused by different processing environments. Then, for each obtained cluster, a neural network is developed to learn the relationship between etching parameters and wafer reflectance. Finally, a real case study from an LED semiconductor fab is conducted to show the application of the proposed method. Experiments show that the proposed method achieves much better performance in comparison with support vector machine for mapping the relationship between etching parameters and wafer reflectance. Also, by the proposed method, the average prediction accuracy of the wafer reflectance can be improved by up to 9.38%, and the mean square error is reduced by 21.64% compared with the methods without clustering. [ABSTRACT FROM AUTHOR]

In semiconductor manufacturing, a process module (PM) failure in cluster tools (CTs) happens from time to time. To effectively operate a CT, such a failure should be handled in a proper and timely manner. This issue becomes much more complicated because wafer residency time constraints (WRTCs) must be met to ensure the quality for some wafer fabrication processes. With such constraints, if a tool is operated under a periodic schedule and a PM fails, it is desired that the tool can still operate under a periodic schedule if it is possible. Nevertheless, the periodic schedule after a PM failure must be different from that before its failure since in this case the tool is degraded. Thus, there must be a transient process between them. It is a great challenge to operate a tool such that it can go through such a transient process with WRTCs being always satisfied. This paper aims to solve this problem by proposing PM failure response policies which can successfully transfer a CT to the feasible schedule after failure from the one before a failure. Then, efficient algorithms are developed to improve these response policies. The proposed policies are composed of simple control laws such that they can be realized in real time and online. Illustrative examples are presented to show their applications. [ABSTRACT FROM AUTHOR]

As a kind of robotic cells, cluster tools are widely used for semiconductor wafer fabrication processes since they provide a reconfigurable and efficient environment. With recent advances in new semiconductor materials, the circuit line width has continuously being shrunk down, which brings new challenges for manufacturers. They require that a wafer should be moved away from a processing chamber as soon as possible after its processing is finished. To ensure high-quality integrated circuits in a wafer, its post-processing residency time must be minimized. It is also highly desirable to maximize the throughput of robotic cluster tools. This article aims at scheduling such tools with multiple objectives subject to wafer residency time constraints. To do so, new algorithms are proposed to calculate robot waiting time delicately upon the analysis of particular events of robot waiting for dual-blade robotic tools and optimally schedule such tools. The numerical results of industrial examples show that the proposed algorithms can provide an effective method to find schedules for dual-blade cluster tools such that multiple objectives are optimized. [ABSTRACT FROM AUTHOR]

State space techniques are one of the main approaches deployed for the analysis of concurrent systems. However, state space construction is stalled by a common phenomenon called the state explosion problem which makes it a tough task or even impossible when the state space computation demands prohibitive cost (time and memory). We limit general resource allocation systems (RASs) to a certain class whose state space can be hierarchically constructed, yet it comprises various enough types of real-world discrete event systems, such as automated manufacturing systems. This paper focuses on a class of RASs modeled with Petri nets (PNs), where, through pure algebraic operations, a novel method to compute the state spaces is proposed, which is motivated by the superposition property. Given a PN model of a system and a target resource configuration, we first propose a special initial marking called the initial basis marking and compute the corresponding reachability graph. Then, we increase the capacity of the resource places in an incremental way and generate the reachability graphs by taking advantage of the PN structure and the previously computed reachability graph until the capacity function of resources reaches the target resource configuration. A complete enumeration of reachable states can be obtained by a recursive scheme. Experimental studies also demonstrate the efficiency of the proposed approach in terms of computational cost and its high-potential to cope with the state-explosion problem. [ABSTRACT FROM AUTHOR]

In wafer manufacturing, extensive research on the operations of cluster tools under the steady state has been reported. However, with the shrinking down of wafer lot size, such tools are frequently required to switch from handling one lot of wafers to another, resulting in more transient processes, including start-up and close-down ones. Also, wafer residency time constraint is critical for many wafer fabrication processes. To cope with the transient scheduling problem of time-constrained single-arm cluster tools with parallel chambers, based on a generalized backward strategy, this paper first builds timed Petri net models for these two transient processes. Then, two linear programs are derived for the first time to search a feasible schedule with a minimal makespan. Two industrial examples are given to demonstrate the effectiveness of the obtained results at last. [ABSTRACT FROM AUTHOR]

For a time-constrained single-robot-arm cluster tool with unfixed scheduling strategy, necessary and sufficient conditions under which a feasible cyclic schedule exists are presented in the literature. However, the results are obtained under the assumption that the activity time is deterministic. In practice, the activity time could be subject to fluctuation, leading to that an originally feasible schedule obtained based on such an assumption may be infeasible. Hence, it is critically important to reveal how the wafer residency time (WRT) varies with the variation of activity time. To solve this problem, this paper first proposes an operational strategy and a real-time control policy. Based on them, the exact upper bound of WRT delay resulted from the activity time variation (ATV) is presented, with which one can check if a given schedule is feasible. Finally, illustrative examples are given to demonstrate the application of the derived method. [ABSTRACT FROM AUTHOR]

Scheduling a cluster tool with wafer residency time constraints is challenging and important in wafer manufacturing. With a backward strategy, the scheduling problem of such single-robot-arm cluster tools is well-studied in the literature. It is much more challenging to schedule a more general case whose optimal scheduling strategy is not limited to the backward one. This work uses a timed Petri net (PN) to model the dynamic behavior of the system and presents a method to determine the optimal scheduling strategy for the system. Based on its PN model and the obtained strategy, it reveals that the key issue to schedule such a tool is to determine when and how long the robot should wait for. Based on this finding, this work establishes for the first time the necessary and sufficient conditions regarding the existence of an optimal and feasible one-wafer cyclic schedule for single-robot-arm cluster tools. It then formulates a computationally efficient linear program to find it if existing, and finally gives industrial examples to show the application and power of the proposed method. [ABSTRACT FROM AUTHOR]

Resource failures may happen in automated manufacturing systems (AMSs) because of different reasons in the real world, making most existing deadlock control policies unapplicable. This paper develops methods for the robust deadlock control of AMSs with unreliable resources based on Petri nets. The considered AMSs are modeled with generalized systems of simple sequential processes with resources (GS3PR). First, a method based on reachability graph partition technique is provided to analyze the robust legal markings and the forbidden ones in an unreliable GS3PR (U-GS3PR), in which resource failures and recovery procedures are modeled with recovery subnets. Then, the control problem for such a system is converted into a problem for controlling the forbidden states in a U-GS3PR and control places can be designed by solving the maximal number of forbidden markings problems. Since the robust legal reachability spaces computed may be nonconvex and such a system cannot be optimally controlled by the conjunctions of linear constraints, we propose an interval-inhibitor-arc-based robust deadlock control policy for a system with nonconvex legal reachability spaces by solving the maximal number of ${t_{q}}$ -critical marking/transition separation instances problems (MNTMPs(${t_{q}}$)). Finally, examples are presented to demonstrate the proposed methods. [ABSTRACT FROM AUTHOR]

Wafer revisiting and residency time constraints complicate the scheduling problem of cluster tools in semiconductor manufacturing. Random disturbance to the activity time in operating a tool further complicates such a scheduling problem. To solve this challenging problem, this paper proposes a robust real-time schedule which consists of a real-time controller (RTC) and an off-line schedule. The former is developed to offset the activity time disturbance such that the wafer sojourn time fluctuation in a process module is minimized. With the RTC, to find the off-line schedule, necessary and sufficient schedulability conditions under which a feasible schedule exists are derived and these conditions can be easily checked. Then, the off-line schedule can be efficiently found by the proposed algorithms based on nondisturbed activity time if a feasible schedule exists. With the obtained real-time schedule, it is shown that the productivity of the system is maximized. Finally, examples are used to illustrate the proposed approach. [ABSTRACT FROM AUTHOR]

This paper deals with the identification problem of faulty behavior in a discrete event system, assuming that the fault-free model of a system is given in terms of Petri nets, where the set of transitions is divided into two disjoint subsets: 1) observable and 2) unobservable ones. The observed system output is defined as a transition-marking sequence, i.e., each transition is followed by a marking. First, a nonlinear integer programming model that characterizes the faults modeled by fault transitions is built according to the abnormal behavior extracted from the observed sequence. Then, it is converted into an integer linear programming (ILP) problem and a faulty net that preserves the structure of the fault-free one is obtained by solving this ILP model. In addition, an algorithm is developed to ensure acyclicity of the resulting unobservable subnet whose transition set is composed of the unobservable transitions of the fault-free net and the identified fault transitions. [ABSTRACT FROM AUTHOR]

A traditional power transmission system (TPTS) is composed of many electrical substations (ESs) and transmission lines. When the latter meet faults, the output of the ESs may be interrupted. In this paper, a methodology is proposed to construct controlled systems with battery energy storage systems to avoid the output interruption during the fault detection and restoration for some important ESs. In a TPTS, an important ES can be controlled by a supervisor that can be thought of as a control agent. Moreover, the ES can be preconnected with other ESs. If a fault occurs in the input lines of the ES, the fault can be detected by its supervisor and restored by its preconnected ESs. Furthermore, the ES can contain a battery energy storage system to store electric power for its temporary output during the fault detection and restoration. Therefore, the output interruption of the ES can be successfully avoided. This work formally models the structures of TPTSs and their control systems by using Petri nets and then verifies the correctness of fault detection and restoration. Finally, a case study is presented. [ABSTRACT FROM AUTHOR]