As a computer-integrated manufacturing system, cluster tools are widely used for semiconductor manufacturing. To tackle their scheduling problems with parallel processing chambers, existing studies assume that the parallel processing chambers at each step are identical. However, due to machine aging, some differences could appear among them in reality. This work represents the first one to report the scheduling problems of cluster tools with non-identical parallel processing chambers. By focusing on time-constrained single and dual-armed cluster tools with non-identical parallel processing chambers, it derives the sufficient conditions under which a system is schedulable. Based on them, it develops two algorithms to obtain the feasible and optimal schedules. It also develops two linear programming models to find the feasible and optimal ones if the sufficient conditions are violated. The experimental results based on 5400 random instances show that the proposed scheduling method can be readily used to generate schedules for both time-constrained single and dual-armed cluster tools.

Cluster tools are extensively used for processing wafers in semiconductor manufacturing. To enhance the throughput of cluster tools, concurrent processing of multiple types of wafers has become a popular approach. In practice, due to mass customization and the shrinking of chips’ feature sizes, the lot size of wafers tends to become smaller, leading to more frequent transient and non-cyclic periods. Therefore, the scheduling problem of single-armed cluster tools that concurrently process two types of wafers from start-up to close-down period should be urgently addressed. To do so, a mixed integer programming (MIP) model is established to optimize the release sequence of wafer types and robot task sequence so that the total completion time of the two wafer types can be minimized. Since solving the MIP model for large-sized instances is hard, a two-combined backward sequence (2-CBS) is further proposed. Experimental results show that the 2-CBS can save a significant amount of computing time and increase the total completion time by only 1.09% on average. However, by quickly determining the completion time of each wafer lot, the throughput of cluster tools could be enhanced to some extent, as the idle time caused by the arrival delay of overhead hoist transports can be reduced. Note to Practitioners—When considering the concurrent processing of multiple wafer types, almost all existing studies focus on cyclic scheduling and thus fail to address the growing importance of non-cyclic scenarios. To fill this gap, the present work develops an MIP model to optimize the release sequence of wafer types and robot task sequence such that the total completion time of two wafer types can be minimized. Such a model is efficient for small-sized instances. Meanwhile, a 2-CBS strategy is developed for large-sized instances, which can be solved quickly and results in an increase in the total completion time by only 1.09%, demonstrating its effectiveness and applicability.

Cleaning operations are required to clear particles and residual chemical gases in processing chambers of cluster tools in semiconductor manufacturing. To clean the chambers, condition-based chamber cleaning operations considering the actual state of chambers have been developed in practice. For single-armed cluster tools with such operations and wafer residency time constraints, the scheduling problem has been tackled. However, for dual-armed ones, this problem remains open and it is difficult to solve since their scheduling strategies are different from and more complex than single clusters’. To address this challenging problem, this work presents an efficient scheduling strategy to find the schedules that meet wafer residency time constraints and maximize their productivity. Two examples are given to show the effectiveness of the developed strategies. Note to Practitioners—Dual-armed cluster tools are extensively employed in semiconductor manufacturing processes. For residency-time-constrained dual-armed cluster tools with condition-based chamber cleaning operations, this work derives efficient scheduling strategies and algorithms for different cleaning cases. They can be used to realize feasible schedules that meet the wafer residency time constraints and restore a cluster tool to its steady-state as soon as possible. Hence, this work is significant and promising in helping semiconductor manufacturers enhance their fab’s throughput.

Cluster tools (CTs) are extensively utilized in semiconductor manufacturing. To tackle the challenging scheduling problems of CTs that concurrently process two wafer types, studies have been previously conducted based on predetermined robot task sequences, resulting in suboptimality of throughput and low wafer residency time constraint (WRTC)-satisfaction ratio. With both WRTC and chamber cleaning operations taken into account for the first time, this work proposes a deterministic scheduling strategy by drawing on previous studies, as well as a novel and efficient mixed integer programming (MIP) model to determine the optimal release sequence of wafer types and robot task sequence. Compared to the existing deterministic scheduling strategies, computational experiments on large randomly generated instances show that the developed MIP model could improve throughput by 2.63% on average, and enhance the WRTC-satisfaction ratio by at least 108.33% demonstrating its effectiveness and significance.

In semiconductor manufacturing, chamber cleaning operations (CCOs) are performed from time to time to clear particles and chemical gases that remain in the processing chambers of cluster tools (CTs) to ensure wafer quality. For single-armed CTs with just one CCO that could be completed in one system cycle time, researchers have proposed several scheduling approaches. In practice, more than one CCO may be required concurrently, thus failing the existing ones under such cases. Furthermore, the duration of a cleaning operation may be larger than one system cycle time, which highly complicates the scheduling of such tools. This work addresses this challenge by proposing several scheduling approaches and algorithms for single-armed CTs with several CCOs, each of which exceeds the duration of one system cycle. Suggestions are given for engineers in semiconductor fabrication plants to take the most suitable scheduling approach and algorithm for enhancing the productivity of CTs given their specific scenarios. Finally, two illustrative examples are provided to showcase the power of the proposed concepts and techniques.

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.

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

Rescheduling is a necessary procedure for a flexible job shop when newly arrived priority jobs must be inserted into an existing schedule. Instability measures the amount of change made to the existing schedule and is an important metrics to evaluate the quality of rescheduling solutions. This paper focuses on a flexible job-shop rescheduling problem (FJRP) for new job insertion. First, it formulates FJRP for new job insertion arising from pump remanufacturing. This paper deals with bi-objective FJRPs to minimize: 1) instability and 2) one of the following indices: a) makespan; b) total flow time; c) machine workload; and d) total machine workload. Next, it discretizes a novel and simple metaheuristic, named Jaya, resulting in DJaya and improves it to solve FJRP. Two simple heuristics are employed to initialize high-quality solutions. Finally, it proposes five objective-oriented local search operators and four ensembles of them to improve the performance of DJaya. Finally, it performs experiments on seven real-life cases with different scales from pump remanufacturing and compares DJaya with some state-of-the-art algorithms. The results show that DJaya is effective and efficient for solving the concerned FJRPs.

This paper addresses a traffic signal scheduling (TSS) problem in a heterogeneous traffic network with signalized and non-signalized intersections. The objective is to minimize the total network-wise delay time of all vehicles within a given finite-time window. First, a novel model is proposed to describe a heterogeneous traffic network with signalized and non-signalized intersections. Second, five meta-heuristics are implemented to solve the TSS problem. Based on the problem characteristics, three local search operators and their ensemble are proposed. Then, five meta-heuristics with such an ensemble are proposed to solve the TSS problem. Third, experiments are carried out based on the real traffic data in the Jurong area of Singapore. The performance of the ensemble of local search operators is verified. Ten algorithms, including five meta-heuristics with and without the ensemble, are evaluated by solving 18 cases with different scales. Finally, the algorithm with the best performance is compared against the currently used traffic signal control strategies. The comparisons and discussions show the competitiveness of the proposed model and meta-heuristics.

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.

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.

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.

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.

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.

A multi-cluster tool with both single and dual-arm individual cluster tools is called a hybrid multi-cluster tool. To operate it, one needs to coordinate different types of robots for accessing the shared buffering modules. Aiming at finding a one-wafer periodic schedule such that the lower bound of cycle time can be reached, this work studies its scheduling when its bottleneck individual tool is process-bound. With a timed Petri net model, the scheduling problem is reduced to determine the waiting time of robots. Then, the conditions are presented, under which a one-wafer periodic schedule exists such that the lower bound of cycle time can be reached. Based on them, an efficient algorithm is given to check whether such a one-wafer periodic schedule exists. If so, it is found via simple calculation. An example is given to show its effectiveness.

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.

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.