Search

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]

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]

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]

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

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 robotic cluster tool involves many activities whose time is subject to some disturbance, thus leading to the activity time variation. It results in wafer sojourn time fluctuation in a process module, which may in turn violate wafer residency time constraints. Some wafer fabrication requires a revisiting process. With wafer revisiting, the effect of activity time variation on wafer sojourn time fluctuation is so complicated that no analysis was reported to the best knowledge of the authors. It is vitally important to accurately analyze it. To do so, this paper adopts a Petri net model to describe the dynamical behavior of cluster tools. With this model, a real-time control policy is proposed to offset the effect of the activity time variation on wafer sojourn time fluctuation as much as possible. Then, the wafer sojourn time delay is analyzed and algorithms are developed to calculate its exact upper bound. With the proposed method, one can check if a given schedule is feasible under bounded activity time variation. Some practical examples are given to show the application of the proposed approach. [ABSTRACT FROM PUBLISHER]

In wafer fabrication, a robotic cluster tool is required to be closed down in order for engineers to perform its on-demand and preventive maintenance and switch between different wafer lots. They often deal with a close-down process subject to wafer residency time constraints, i.e., a wafer must exit from a processing chamber before its quality degradation within a certain time limit. To obtain higher yield, it is very important to optimize a close-down process for a cluster tool. Yet the existing literature pays no or little attention to this issue. By focusing on a time-constrained single-arm cluster tool, this paper intends: 1) to build its Petri net model to analyze its schedulability and 2) to develop computationally efficient algorithms to find an optimal and feasible schedule for its closing-down process under different workloads at its steps. Industrial examples are used to illustrate the application of the proposed method. [ABSTRACT FROM PUBLISHER]

A hybrid multirobot cluster tool is composed of both single and dual-arm robotic cluster tools. Since the behavior of different individual tools is different, it is very challenging to coordinate their activities in such a tool and to schedule it optimally. To find a one-wafer cyclic schedule to reach the shortest cycle time for a treelike hybrid multirobot cluster tool whose bottleneck tool is process-bound, this paper extends resource-oriented Petri nets to model it such that a schedule can be parameterized by its robots’ waiting time. Based on the model, this paper then establishes the conditions under which there is a one-wafer cyclic schedule such that the shortest cycle time can be obtained. An efficient algorithm is also given to test the existence of such a schedule and to find it if existing. At last, examples are used to illustrate the proposed approaches. [ABSTRACT FROM AUTHOR]

Scheduling a multicluster tool with wafer residency time constraints is highly challenging yet important in ensuring high productivity of wafer fabrication. This paper presents a method to find an optimal one-wafer cyclic schedule for it. A Petri net is developed to model the dynamic behavior of the tool. By this model, a schedule of the system is analytically expressed as a function of robots’ waiting time. Based on this model, this paper presents the necessary and sufficient conditions under which a feasible one-wafer cyclic schedule exists. Then, it gives efficient algorithms to find such a schedule that is optimal. These algorithms require determining the robots’ waiting time via simple calculation and thus are efficient. Examples are given to show the application and effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In semiconductor manufacturing, there are wafer fabrication processes with wafer revisiting. Some of them must meet wafer residency time constraints. Taking atomic layer deposition (ALD) as a typical wafer revisiting process, this paper studies the challenging scheduling problem of single-arm cluster tools for the ALD process with wafer residency time constraints. It is found that there are only several scheduling strategies that are applicable to this problem and one needs to apply each of them to decide whether a feasible schedule can be found or not. This work, for each applicable strategy, performs the schedulability analysis and derives the schedulability conditions for such tools for the first time. It proposes scheduling algorithms to obtain an optimal schedule efficiently if such conditions are met. It finally gives illustrative examples to show the application of the proposed concepts and approach. [ABSTRACT FROM PUBLISHER]

With the interaction of discrete-event and continuous processes, it is challenging to schedule crude oil operations in a refinery. This paper studies the optimization problem of finding a detailed schedule to realize a given refining schedule. This is a multiobjective optimization problem with a combinatorial nature. Since the original problem cannot be directly solved by using heuristics and meta-heuristics, the problem is transformed into an assignment problem of charging tanks and distillers. Based on such a transformation, by analyzing the properties of the problem, this paper develops a chromosome that can describe a feasible schedule such that meta-heuristics can be applied. Then, it innovatively adopts an improved nondominated sorting genetic algorithm to solve the problem for the first time. An industrial case study is used to test the proposed solution method. The results show that the method makes a significant performance improvement and is applicable to real-life refinery scheduling problems. [ABSTRACT FROM PUBLISHER]

This work proposes a novel structure in Petri nets, namely data inhibitor arcs, and their application to the optimal supervisory control of Petri nets. A data inhibitor arc is an arc from a place to a transition labeled with a set of integers. A transition is disabled by a data inhibitor arc if the number of tokens in the place is in the set of integers labeled on it. Its formal definitions and properties are given. Then, we propose a method to design an optimal Petri net supervisor with data inhibitor arcs to prevent a system from reaching illegal markings with respect to control specifications. Two techniques are developed to reduce the supervisor structure by compressing the number of control places. Finally, a number of examples are used to illustrate the proposed approaches and experimental results show that they can obtain optimal Petri net supervisors for the net models that cannot be optimally controlled by pure net supervisors. A significant result is that the proposed approach can always lead to an optimal supervisor with only one control place for bounded Petri nets on the premise that such a supervisor exists. [ABSTRACT FROM PUBLISHER]

This work studies the scheduling problem of a single-arm multicluster tool with a linear topology and process-bound bottleneck individual tool. The objective is to find a one-wafer cyclic schedule such that the lower bound of cycle time is reached by optimally configuring spaces in buffering modules that link individual cluster tools. A Petri net (PN) model is developed to describe the dynamic behavior of the system by extending resource-oriented PNs such that a schedule can be parameterized by robots’ waiting time. Based on this model, conditions are presented under which a one-wafer cyclic schedule with the lower bound of cycle time can be found. With the derived conditions, an algorithm is developed to find such a schedule and optimally configure buffer spaces. The algorithm requires only simple calculation to set the robots’ waiting time and buffer size. Illustrative examples are presented to demonstrate the proposed method. [ABSTRACT FROM PUBLISHER]

With a combinatorial nature and hybrid characteristics, it is very challenging to schedule crude oil operations in a refinery and, up to now, there is no software tool for practical use in this field. To solve this problem, based on the two-level architecture in our previous work, for cases where crude oil mixing is required, this paper investigates the refining scheduling problem at the upper level. Based on the schedulability conditions, a three-stage approach is proposed. First, a linear programming model is developed to maximize productivity. Second, another linear programming model is built and solved to optimally obtain the mixed crude oil types and their amounts, and assign them into the distillers. Finally, this paper simply sequences and merges the oil parcels obtained at the second stage to form a desired schedule. Because the proposed approach mainly solves two linear programming problems, it is very efficient. An industrial case study is presented to illustrate the proposed approach. [ABSTRACT FROM PUBLISHER]

This paper addresses the scheduling problem of single-arm cluster tools with both wafer residency time constraints and activity time variation in semiconductor manufacturing. Based on a Petri net model developed in our previous work, polynomial algorithms are proposed to obtain the exact upper bound of the wafer sojourn time delay for the first time. With the obtained results, one can check the feasibility of a given schedule or find a feasible and optimal one if it exists. Illustrative examples are given to show the applications of the proposed method. [ABSTRACT FROM PUBLISHER]

Some wafer fabrication processes require a wafer to visit some processing modules in a cluster tool multiple times, leading to a wafer revisiting process. They may pose wafer residency time constraints, i.e., a wafer can stay in a module for a limited time after it is processed. Although techniques exist for scheduling cluster tools with either wafer residency time constraints or wafer revisiting, it is much more challenging to schedule tools with both of them. Considering that atomic layer deposition is a typical wafer revisiting process, this paper intends to schedule a dual-arm cluster tool dealing with it. Based on the analysis of such a tool’s properties, a novel scheduling strategy called modified 1-wafer cyclic scheduling is derived. With this strategy, necessary and sufficient schedulability conditions are presented. If schedulable, highly efficient scheduling algorithms are developed to obtain a feasible and optimal schedule together with a way to implement the obtained one. Illustrative examples are given to show the application of the proposed approach. [ABSTRACT FROM PUBLISHER]

A multi-cluster tool is composed of a number of individual cluster tools linked by buffering modules (BMs). The capacity of a BM can be one or two. Aiming at finding an optimal one-wafer cyclic schedule, this paper explores the effect of two-space BMs on the performance of a multi-cluster tool. A Petri net (PN) model is developed to model it by extending resource-oriented PNs. The dynamic behavior of robot waiting and tasks, process modules, and buffers is well described by the model. This paper shows that there is always a one-wafer cyclic schedule that reaches the lower bound of the cycle time of a process-bound tool. Furthermore, a closed-form algorithm is revealed to find such a schedule for the first time for such multi-cluster tools. Illustrative examples are given to show the application and power of the proposed method. [ABSTRACT FROM AUTHOR]

Due to the different behavior of single-arm and dual-arm cluster tools, it is challenging to schedule a hybrid multi-cluster tool containing both of them. This paper aims to find an optimal one-wafer cyclic schedule for such a multi-cluster tool. It is assumed that the bottleneck individual cluster tool in it is process-bound, thereby making it process-dominant. To do so, this paper models a hybrid multi-cluster tool with Petri nets. With this model, it derives the conditions under which individual cluster tools can operate in a paced way. Based on these conditions, this paper shows that for any process-dominant hybrid multi-cluster tool there is always a one-wafer cyclic schedule. Then, it develops the algorithms to find the minimal cycle time and the optimal one-wafer cyclic schedule. It is computationally efficient and easy-to-implement in practice. Examples are given to show the application and effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]