The growing demand for high-performance semiconductors has heightened the importance of optimizing cluster tool scheduling to improve manufacturing efficiency. Ensuring high wafer quality necessitates chamber cleaning to eliminate processing residues. Since cleaning requires chambers to remain idle, this complicates scheduling and renders conventional methods inefficient. The swap sequence, which exchanges the wafer in a chamber with the wafer held by the robot in increasing order of steps, is particularly affected. This has led to the development of extended sequences such as swap(z) and swap(a, z), incorporating partial loading that intentionally leaves chambers idle and push-and-wait operations where loading precedes unloading. However, these methods are fundamentally limited by their 1-wafer cyclic structure, in which the tool outputs only one wafer in a single repetition of the robot sequence. To overcome this limitation, we propose the swap(A, z) sequence, which generalizes swap(a, z) by integrating the robot operations within a K-wafer cyclic structure. We theoretically show that swap(A, z) eliminates inefficiencies inherent in 1-wafer cyclic sequences, particularly for configurations with up to eight parallel chambers. Experimental evaluations further demonstrate that our method consistently matches or outperforms existing sequences.

Reinforcement Learning (RL) has shown promising results in solving Job Scheduling Problems (JSPs), automatically deriving powerful dispatching rules from data without relying on expert knowledge. However, most RL-based methods train only a single decision-maker, which limits exploration capability and leaves significant room for performance improvement. Moreover, designing reward functions for different JSP variants remains a challenging and labor-intensive task. To address these limitations, we introduce a novel and generic learning framework that optimizes multiple policies sharing a common objective and a single neural network, while enabling each policy to learn specialized and diverse strategies. The model optimization process is fully guided by a self-labeling manner, eliminating the need for reward functions. In addition, we develop a training scheme that adaptively controls the imitation intensity to reflect the quality of self-labels. Experimental results show that our method effectively addresses the aforementioned challenges and significantly outperforms state-of-the-art RL methods across six JSP variants. Furthermore, our approach also demonstrates strong performance on other combinatorial optimization problems, highlighting its versatility beyond JSPs.

Cluster tools, which are extensively used in semiconductor and display manufacturing, offer the capability to perform multiple processing steps within a single tool. Many companies have recently been reducing wafer lot sizes due to diversified customer demands and circuit width reduction, resulting in more frequent transient and non-cyclic periods. We therefore present a novel mixed integer programming (MIP) model that can handle these non-cyclic scheduling problems of cluster tools. Our model is specifically designed to efficiently handle various wafer flows, accommodating both single-and dual-armed robots, while ensuring a shorter computation time, compared to the previous formulations. We first model cluster tools with a timed Petri net (TPN) and develop several precedence relations between transitions by analyzing the characteristics of the scheduling problems. These precedence relations are incorporated into a TPN by introducing additional places and arcs. This modification helps reduce the overall number of decision variables involved in the scheduling problem. We then develop an MIP model which specifies the precedence relations between transitions, as opposed to the position-based decision variables used in the previous studies. The proposed MIP model is capable of handling various flow scenarios encountered in cluster tools, including serial, parallel, concurrent, and re-entrant flows with time window constraints.Note to Practitioners—In response to the diverse demands of customers, the use of larger wafer sizes, and the need for smaller circuit widths, operating cluster tools in a cyclic manner has become increasingly challenging. Cyclic scheduling, where the robot repeats a fixed sequence while assuming identical wafers, is no longer viable in such scenarios. Unfortunately, previous research on cluster tool scheduling has predominantly focused on cyclic scheduling, failing to address the growing importance of non-cyclic scenarios. To address this gap, we propose an innovative and efficient mixed integer programming (MIP) model capable of handling non-cyclic scheduling problems in cluster tools. Our model accommodates various flow types, including serial, parallel, concurrent, and re-entrant flows. Through comparative analysis, we demonstrate that our proposed model outperforms the well-known MIP model that relies on position-based decision variables. We believe that our proposed model holds practical value as it exhibits relatively short computation times. Additionally, widely-used commercial solvers, such as CPLEX or Google OR Tools, can seamlessly implement the model, making it easily accessible and applicable in real-world scenarios.

The semiconductor manufacturing system operates in lot units comprising wafers with identical recipes. Production predominantly occurs within a cluster tool, encompassing multiple single-wafer processing chambers and a wafer-handling robot. Recently, the increasing popularity of small lot sizes has been driven by the diversification of customer demand and larger wafer diameters. Thus, cluster tools frequently encounter lot switching periods, where lots with different recipes are processed consecutively. Existing research on cluster tool scheduling primarily relies on conventional backward and swap sequences optimized for cyclic robot operations. This approach persists even during lot switching period scheduling, which represents non-cyclic scenarios. However, it remains unclear whether these conventional robot task sequences remain optimal or ensure consistent performance during lot switching periods. Therefore, we introduce a theoretical analysis of the performance of the conventional robot sequences, such as backward and swap sequences, in lot switching periods for the first time. We examine various dominant relations, establishing the conditions under which the conventional sequences provide an optimal schedule. We also show worst-case performance bounds. Finally, given the limited performance of the conventional swap sequence during lot switching periods for dual-armed robots, we propose a new form of the robot task sequence and demonstrate its effectiveness.

Recent advances in AI/ML have significantly increased the demand for various semiconductor products. To meet the growing demand and improve productivity, semiconductor companies now produce multiple wafer types simultaneously and, in some cases, even transport them in a single cassette. These changes in manufacturing practices have increased the complexity of cluster tool scheduling, making efficient scheduling algorithms a key focus for both researchers and manufacturers. In this paper, we propose a deep reinforcement learning (DRL)-based scheduling approach that effectively addresses the challenges of scheduling multiple wafer types in cluster tools. The proposed model considers both input sequencing and robot move sequencing to handle various wafer types across different cluster tool configurations. It is structured around an encoder–decoder framework: the encoder captures wafer recipes (i.e., processing times and flow), and the decoder uses dynamic scheduling information to determine the robot’s next actions while avoiding deadlock situations. Through extensive experiments that consider multiple cluster tool structures and wafer types, our model consistently outperforms conventional robot move sequences and metaheuristic methods, without relying on cyclic assumptions. These results demonstrate that our approach can derive efficient robot sequences without requiring expert knowledge or extensive manual analysis, across single-arm, dual-arm, serial-parallel flow, concurrent flow, and skip flow configurations, while also considering purge operations within cluster tools. As such, our model is highly adaptable and can be effectively applied to a wide range of cluster tool scheduling problems. We provide benchmark datasets to support further research and practical applications: https://github.com/yeoneee/ClusterToolSchedulingRL.git.

We address the scheduling problem of single-armed cluster tools that concurrently process two wafer types without assuming cyclic scheduling. These cluster tools, consisting of multiple processing modules and a transport robot, are commonly used in semiconductor manufacturing processes, such as etching, deposition, and lithography. To optimize the tool’s throughput, we propose a reinforcement learning approach for determining both the robot task sequence and the release sequence of wafer types. By incorporating an adaptive search, our method intelligently explores future states to gather crucial information, enabling the selection of the best action. Extensive experiments demonstrate that our proposed method outperforms the well-known optimal robot task sequence for cyclic scheduling in single-armed cluster tools with concurrent processing. These findings underscore the effectiveness and superiority of our approach in optimizing the throughput of single-armed cluster tools, without relying on cyclic scheduling assumptions.Note to Practitioners—Single-armed cluster tools, comprising multiple processing modules and a transport robot, are commonly employed in semiconductor manufacturing processes. In recent times, there has been a trend towards concurrent processing of multiple wafer types within the fab, aimed at improving the PMs’ utilization. The concurrent backward sequence (CBS) has emerged as an efficient approach for such scenarios, assuming cyclic scheduling. However, the CBS relies on a cycle plan that specifies the number of wafers from each wafer type to be produced and their release sequence in a cycle. While the CBS provides an optimal schedule that maximizes the throughput of the tool in some cases under the cyclic scheduling assumption, its performance has not been guaranteed for other general cases. We propose a highly efficient reinforcement learning approach for the scheduling problem including the robot task sequence and release sequence of wafer types in a single-armed cluster tool. Our method outperforms the CBS, demonstrating its superior performance. By implementing our proposed approach, we believe that practitioners can effectively maximize the throughput of single-armed cluster tools and significantly enhance the fab productivity.

We propose an advanced real-time dispatcher for minimizing the makespan of job shop scheduling problems (JSSPs), which are NP-hard combinatorial problems. The proposed dispatcher can be applied to large-sized unseen problems without additional learning. Several studies recently proposed a scalable dispatching agent using a graph neural network (GNN) and reinforcement learning (RL). However, we observe that they have not considered suitable Markov decision process (MDP) and GNN structure to solve JSSPs. Therefore, we incorporate scheduling theory and properties to define the state, action, and GNN model. We especially define the action set and state transition so that active schedules can be exclusively generated, define node features in a dynamic manner, and use a neighbor type-aware Graph Attention Network (GAT) model with length-agnostic neighbor sets. We also investigate the use of imitation learning (IL) to learn the dispatcher instead of the RL. We evaluate the effectiveness of our dispatcher on benchmark instances and dynamic environments. Note to Practitioners—This work aims to develop an advanced real-time dispatcher using GNN. It can handle dynamic scheduling environments. The focus is on JSSPs without constraints, commonly seen in real manufacturing systems. To improve the GNN-based dispatchers proposed by recent studies, we refine the dispatcher using a novel state, action, and a GNN structure. Our dispatcher demonstrates state-of-the-art performance compared to other real-time dispatchers on JSSP benchmark instances and several customized instances, which consist of up to 20 machines and 300 jobs. Additionally, we assess the dispatcher’s performance in dynamic JSSP environments, including dynamic job arrival, machine breakdown, and stochastic processing time. Note that, to apply the proposed dispatcher for real-world fields, you have to prepare only the information about predefined machine orders and currently remaining processing times for each job. Also, you do not need a simulator if you are going to utilize a trained dispatcher. In the future, extended study is needed to apply it to sequence-dependent setup constraints, due-related objectives, etc.

In recent years, the industrial sectors, particularly in the manufacturing of steel, chemicals, automotive parts, and semiconductors, have been focusing on reducing energy usage in order to improve energy efficiency and maintain competitiveness in the global market. This study addresses an energy-conscious scheduling problem of identical parallel machines by considering the peak energy consumption limits. We provide an optimal schedule that minimizes the total energy consumption by developing novel integer programming (IP) models by reducing the number of decision variables and constraints from the previous model and a branch and bound (B&B) algorithm with three dominance properties and three lower bounds. The proposed B&B algorithm performs better than the existing IP and improved IP models. We then introduce a modified simulated annealing (MSA) algorithm, which accounts for the energy consumption rates for generating neighboring solutions, to solve large-sized instances.Note to Practitioners—In this work, we address parallel machine scheduling by taking into account the peak energy consumption limits imposed by various manufacturing companies. We present new mathematical programming models for the problem, demonstrating that these models provide optimal solutions faster than the previous one. Additionally, we enhance these models by developing a branch and bound (B&B) algorithm that yields optimal solutions even faster. Finally, we present a heuristic algorithm to handle large-sized instances.

This paper tackles the dynamic crane scheduling problem in a steel coil warehouse, involving tasks such as coil storage, retrieval, and shuffling. Tasks arrive dynamically with precedence relations, while multiple cranes share a track, necessitating collision avoidance. We aim to minimize the average task waiting time by allocating tasks to cranes and optimizing their execution sequence. Unlike prior research focusing on static scenarios or rule-based heuristics, we introduce a real-time, reinforcement learning-based algorithm. We propose a policy network based on graph neural networks to effectively handle precedence relations and global information. Experimental results demonstrate its superiority over traditional heuristics, such as dispatching rules in dynamic scenarios.

Flexible manufacturing systems (FMSs), which can easily adapt to changes in job types, have been widely used in manufacturing areas. Scheduling of FMSs is a variant of a flexible job shop with transport robots and no buffer, and it is extremely hard as it involves determining the job processing sequence on machines and the sequence of robot tasks, with various jobs with different processing flows and the risk of deadlocks. Due to these characteristics, many existing studies have focused on developing heuristic algorithms. However, an optimal solution is still crucial to minimize FMSs makespan. Therefore, we propose a mixed integer programming (MIP) and a branch and bound (B&B) algorithm with a timed Petri net (TPN) to achieve optimal scheduling of FMSs. FMSs are first modeled with a TPN, and tight lower bounds are proposed based on bottleneck machines and sophisticated ready times. In addition, the search space is effectively reduced by the transition index marking (TIM)-based dominance rule and various deadlock prevention conditions based on the TPN. The experimental results show that our proposed B&B algorithm outperforms mathematical formulation and previous algorithms in various FMS instancesNote to Practitioners—Flexible manufacturing systems (FMSs) can often be found in various manufacturing areas composed of machines, material-handling robots, and controlling computers. With the increase in customer demand for diverse products manufactured in small quantities, the importance of FMSs has grown even more prominent in the manufacturing sector. In this paper, we develop a mixed integer programming (MIP) and a branch and bound (B&B) algorithm for optimal scheduling of FMSs with a timed Petri net (TPN). The proposed B&B can handle various FMS layouts by modeling with a TPN, regardless of the number of product routes, machines, and robots. Three lower bounds and dominance rules are proposed, and they have the great advantage of reduced computational time and search spaces. Our proposed method can also be implemented as a rolling horizon approach when jobs arrive in batches. Additionally, the algorithm can be adapted for use in other types of manufacturing systems, such as cluster tools, robotic cells, and track systems, which can be modeled using TPNs.

Robotized manufacturing systems consisting of several processing machines and a robot for transporting jobs between the machines have been widely used in mechanical and electronic manufacturing industries. The sequence of robot tasks in such a robotized manufacturing system affects its productivity significantly, which also has the large impact on the overall production line consisting of multiple robotized manufacturing systems. This article addresses the scheduling problem in a single-gripper robotic cell, one of a robotized manufacturing systems. The objective is to minimize the makespan. To achieve this, a novel reinforcement learning method is proposed, which combines a look-ahead search (LAS) to improve decisionmaking using more accurate estimated makespan. Experimental results demonstrate the superior performance of the proposed method compared to existing approaches. Moreover, the method is applicable in dynamic environments with uncertain processing times.

The performance of a swap sequence is analyzed by assuming cyclic scheduling in dual-armed cluster tools with processing time variations. A dual-armed cluster tool consists of multiple processing modules (PMs), one material handling robot that can hold two wafers at the same time, and loadlocks where wafer cassettes are loaded or unloaded. The swap sequence in a dual-armed cluster tool is widely used in practice and known to be optimal with deterministic processing times when the bottleneck PM’s workload is larger than the robot workload. However, in practice, processing times on a PM can have a small variation, which leads to a different processing time of each wafer on the PM. Hence, when the processing time variation is introduced, the performance of the swap sequence needs to be analyzed. This paper first defines a fundamental cycle and analyzes its cycle time. It then proposes optimality conditions of the swap sequence and performs numerical experiments to show the effectiveness of the sequence. Note to Practitioners—A dual-armed cluster tool used for semiconductor manufacturing processes is usually operated with a swap sequence because it is simple, easy to control, and proven to be optimal with deterministic processing times. However, studies on the performance of the swap sequence are still limited with processing times varying in PMs which often occur in practice. Hence, this study shows the effectiveness of the swap sequence with the processing time variations by analyzing cycle times, optimality conditions, and performing numerical experiments.

A dual-gripper robotic cell consists of multiple processing machines and one material handling robot, which can perform an unloading or a loading task one at a time but can hold two parts at the same time. We address a scheduling problem of the robotic cell that determines a robot task sequence when two part types are processed in a different set of machines and all machines have variable processing times within a given interval. The objective is to minimize the makespan. This study proposes a learning-based method, i.e., a reinforcement learning (RL) approach, for the first time, to address a dual-gripper robotic cell scheduling problem. The problem is modeled with a Petri net, a graphical and mathematical modeling tool, which is used as an environment in RL. The states, actions, and rewards are defined by using flow shop scheduling properties, features from a Petri net, and knowledge from previous studies of scheduling robotized tools. Then, the RL approach is compared to the first-in-first-out (FIFO) rule, which is generally used in practice, a swap sequence, which is widely used for cyclic scheduling of dual-gripper robotic cells, and a lower bound. The extensive experiments show that the proposed method performs better than FIFO and the swap sequence; moreover, the gap between the makespan of the proposed method and the lower bound is not large.Note to Practitioners—We address a scheduling problem of dual-gripper robotic cells with two-part types when all machines have processing time variations. We propose an RL approach to obtain an efficient robot task sequence in order to minimize makespan. The proposed method is performed offline, and a robot task sequence is then obtained instantaneously. The proposed method performs better than the FIFO rule used in practice and the swap sequence used for cyclic scheduling of robotic cells. It can be easily extended for scheduling other configurations of robotic cells.

A robotic mobile fulfillment system (RMFS) performs the order fulfillment process by bringing inventory to workers at pick-pack-and-ship warehouses. In the RMFS, robots lift and carry shelving units, called inventory pods, from storage locations to picking stations where workers pick items off the pods and put them into shipping cartons. The robots then return the pods to the storage area and transport other pods. In this article, we consider an item assignment problem in the RMFS in order to maximize the sum of similarity values of items in each pod. We especially focus on a reoptimization heuristic to address the situation where the similarity values are altered so that a good assignment solution can be obtained quickly with the changed similarity values. A constructive heuristic algorithm for the item assignment problem is developed, and then, a reoptimization heuristic is proposed based on the constructive heuristic algorithm. Then, computational results for several instances of the problem with 10-500 items are presented. We further analyze the case for which an item type can be placed into two pods. Note to Practitioners-This article proposes an efficient heuristic algorithm for assigning items to pods in a robotic mobile fulfillment system (RMFS) so that items ordered together frequently are put into the same pod. Computational results with 10-500 items show that the gaps from upper bounds are very small on average. For cases where the similarity values between items change or their estimation is not accurate due to the fluctuations in demand, a reoptimization heuristic algorithm that alters the original assignment is developed. The experimental results show that the reoptimization algorithm is robust when perturbation levels are approximately 40%-50% of the original similarity values with much less computation times. We believe that this research work can be very helpful for operating the RMFS efficiently.

This article analyzes the backward sequence for single-armed cluster tools with processing time variations. The backward sequence is popularly used to operate a single-armed cluster tool in practice, but its performance has not been analyzed when processing time variations are introduced. To address the problem, we first define a fundamental cycle and derive a formula for cycle time analysis considering processing time variations. We then develop conditions for which the backward sequence is optimal for a certain cycle or all cycles. We also analyze the upper bound of the average cycle time with the backward sequence. Finally, the performance of the backward sequence with processing time variations is investigated experimentally.Note to Practitioners—The backward sequence, which is widely used for scheduling single-armed cluster tools, is analyzed with processing time variations in processing modules (PMs). The backward sequence is proven to be optimal in many cases with deterministic processing times. However, in reality, the wafer processing time in a PM is not deterministic and varies within a given time range. With regard to this issue, we analyze the performance of the backward sequence with processing time variations. This study can be very helpful for not only tool engineers but also for researchers who are interested in scheduling automated manufacturing systems.

Cluster tools, which consist of processing modules (PMs) and a transport robot, are used for wafer fabrication processes in semiconductor manufacturing fabs. Once processing of a wafer lot containing several wafers is completed in a tool, an overhead hoist transport (OHT) unloads the lot and transports it to another tool. Since it is not easy to estimate when a wafer lot is completed, an OHT is required to wait for the wafer lot to be completed near the tool, or tools become idle due to the late delivery of wafer lots. To reduce the resulting idle time, a closed-form expression of the lot completion time is derived, especially, for a dual-armed cluster tool consisting of parallel PMs, to reflect real applications. We even consider lot switching operations where two consecutive wafer lots are processed with an overlap in analyzing the completion time. We finally show that the formulas derived can be used when there are small processing time variations experimentally. Note to Practitioners-For a dual-armed cluster tool with parallel processing modules (PMs), a closed-form expression on the lot completion time is derived. For this, we also consider lot switching operations, where the previous and next lots are temporarily processed together in a tool. With the formulas, we can send overhead hoist transports (OHTs) just-in-time to tools to unload or load wafer lots in tools, which can significantly reduce the idle time of tools and OHTs. In addition, the formulas can be used to design the number of PMs for wafer lots and assign wafer lots to tools to reduce their flow time. We believe that more efficient planning and scheduling in semiconductor manufacturing can be achieved by utilizing our results.

This paper analyzes the completion time of automated manufacturing systems, especially a dual-armed cluster tool, equipped with parallel processing modules (PMs). Cluster tools, which consist of multiple PMs, a transport robot, and loadlocks where wafer lots are loaded and unloaded, perform semiconductor manufacturing processes, such as lithography, etching, deposition, and testing. Wafer lots are transported by overhead hoist transports (OHTs) between tools or stockers where wafer lots are stored. To reduce the idle time of OHTs or cluster tools, it is essential to estimate the time when all wafers of a lot finish processing in a tool. Hence, we derive closed-form expressions for the completion time of wafer lots, especially in dual-armed cluster tools with parallel PMs to reflect real circumstances of fabs. We finally show that the formulas derived can be used even when there are small processing time variations with numerical experiments.

As wafer circuit widths shrink down, wafer fabrication processes require stringent quality control. Therefore, fabs recently tend to clean a chamber after processing each wafer, in order to remove chemical residuals within the chamber. Such chamber cleaning, called purge operation, increases scheduling complexity in robotized cluster tools. In this paper, we examine scheduling problems of single-armed cluster tools with purge operations for series-parallel chambers. By extending the wellknown backward sequence, we propose a backward(z) sequence that allows partial loading for parallel chambers, where vector z specifies how many chambers zi of each process step i are kept empty for cleaning. We then propose a way of finding optimal vector z* and identify when backward(z*) achieves the minimum cycle time among all possible sequences. We present experimental results on the accuracy of backward(z*).

We examine a robot task sequencing problem for a flexible assembly system which consists of multiple 3D printers, two post-processing machines, multiple assembly machines, an inspection machine, and one material handling robot. The flexible assembly systems, which have been built in many large cities in Korea, are designed to produce customized products for start-up companies and individuals. In this paper, we develop a robot task sequence in order to operate the system efficiently. We consider cyclic scheduling, a process for a system in which the robot repeats a specified sequence in a cycle to produce identical items. The system behavior is then modeled with a timed event graph (TEG) and the optimality of the robot task sequence is proved by analyzing the workloads of resources and the circuit ratios of the TEG.

We analyze the completion time of wafer lots in single-armed cluster tools with parallel processing modules (PMs) by considering the lot switching operation. To effectively assign wafer lots and dispatch overhead hoist transports (OHTs) to manufacturing tools, it is crucial to obtain the completion time of wafer lots. However, estimating the completion time is not straightforward, due to the concurrent processing of two consecutive wafer lots during lot switching operation, which often increases wafer sojourn times in PMs. In this paper, we derive closed-form expressions of the completion time of wafer lots in single-armed cluster tools with parallel PMs. We assume that the robot unloads wafers in the order of their loading sequence. We then experimentally show that the formulas derived can be used even when processing time variation exists or another robot task sequence, which is of first-in first-out (FIFO), is assumed.

Cluster tools have been extensively used for many semiconductor manufacturing processes such as lithograph, etching, deposition, and testing. Most previous studies on cluster tool scheduling have focused on steady cycles in which cluster tools repeat identical work cycles. However, the proportion of noncyclic transient operation cycles such as start-up cycles and close-down cycles becomes larger as the lot size tends to be smaller. We examine optimal transient scheduling for a single-armed cluster tool, in which there are parallel chambers and a process chamber is a bottleneck, while minimizing the makespan of a lot. To do this, we first identify fundamental properties of noncyclic transient cycles in a tool by analyzing resource workloads. We then propose a simple robot task sequence, a generalized backward sequence, which performs backward operations incrementally for start-up cycles and decrementally for close-down cycles. We also develop workload-based conditions for which the generalized backward sequence has the minimum makespan for single-armed cluster tools with parallel chambers. Finally, we develop a linear programming model to find the minimum makespan of the generalized backward sequence for the cases in which the conditions are not met and show its effectiveness. Note to Practitioners-Scheduling transient cycles such as start-up, close-down, and lot-switching cycles is an important issue for cluster tools due to frequent lot switchings, cleaning, and machine breakdown. In this paper, we propose a generalized backward sequence to schedule a wafer lot from the start-up cycle to the close-down cycle in a single-armed cluster tool with parallel chambers. The workload-based analysis is used for computing a lower bound on the makespan of a lot. We prove that the generalized backward sequence has an optimal makespan in most practical cases. Process engineers can adjust the workloads of process steps to improve the tool productivity based on our results. Even though the optimality conditions are not satisfied, we show that the generalized backward sequence still provides a reasonable makespan experimentally.

We consider a scheduling problem of a robotized cluster tool for semiconductor manufacturing, which should control wafer delays within a chamber so as not to exceed a specified limit under time variation. The prior research has proposed a p+-time event graph, an extension of Petri nets, for modeling the scheduling problem and developed a method of verifying whether a cyclic p+-time event graph or a cluster tool, which repeats identical work cycles, can satisfy the time constraints under time variation. In this paper, we extend and simplify the schedulability analysis method in the prior research for a noncyclic event graph or a cluster tool which performs start-up and close-down operation for a lot or lot switching, and obtain specialized results. We assume that a robot task sequence or firing sequence of transitions is given. Based on the schedulability analysis, we also propose a way of modifying a not always schedulable noncyclic p+-time event graph with some qualifications to be always schedulable, that is, we prolong token holding times at some places or equivalently delay firings of some transitions so as to be always feasible.

A timed Petri net (TPN) has been widely used for modeling, scheduling, and analyzing discrete event dynamic systems. This study examines cyclic scheduling problems of a TPN to minimize the cycle time especially for automated manufacturing systems. Appropriate token routing at each conflict place can make a TPN repeat an identical firing sequence. We propose a systematic procedure to transform a TPN with such cyclic token routing into an equivalent timed event graph (TEG) for which the cycle time and firing schedules can be evaluated by a linear programming (LP). Based on the transformation procedure, we develop an efficient branch and bound algorithm to solve the scheduling problem. A partial solution is defined as a partial token route that has only a subset of token routes for determining the complete schedule. The lower bound of a partial solution is determined by the cycle time of a TEG that has the partial token route. The cycle time of a TEG with an additional token route for a new partial solution is computed by a dual-simplex algorithm which avoids solving the LP completely again. A dynamic branching strategy that prevents unnecessary branching for the scheduling decision is also proposed. We demonstrate the computational efficiency through intensive experiments of cluster tools and robotic flow shops. Note to Practitioners-There are many systems which repeat an identical task sequence such as manufacturing systems, transportation systems, and robotic systems. Maximizing the throughput of such a system by optimizing the cyclic task sequence, which is called a cyclic scheduling problem, has been an important problem. In order to deal with cyclic scheduling problems, this paper uses a timed Petri net (TPN) which is a graphical modeling tool for discrete event dynamic systems. As the size of TPN model increases, the computational complexity of the cyclic scheduling problem exponentially increases due to the combinatorial nature of sequencing problems. Therefore, an efficient algorithm for optimal cyclic scheduling of TPNs is needed. This study proposes an efficient branch and bound algorithm which is kind of a tree search algorithm. Several important techniques are developed. First, a transformation procedure from a TPN to timed event graph is developed. Second, an efficient branching rule which reduces the size of the search tree is proposed. Third, the lower bound which evaluates the cycle time of each node in the search tree is suggested. We verify the efficiency of the algorithm through the experiments on manufacturing systems such as a cluster tool and a robotic flow shop.

Cluster tools, each of which consists of multiple processing modules, one material handling robot, and loadlocks, are widely used for wafer fabrication processes, such as lithography, etching, and deposition. There have been many approaches and algorithms for cyclic scheduling of cluster tools in which the robot repeats a specified sequence for processing identical wafers. However, the lot order size has recently been decreasing due to the larger wafer size and circuit width reductions. In modern fabs, each wafer lot can have different flow patterns and process times for the same process step, and heterogeneous lots are processed consecutively in a tool. Even some tools in a fab have idle time waiting for wafer lots depending on the work-in-process fluctuations. Such different wafer lots and frequent tool state changes cannot be handled with cyclic scheduling methods, and accordingly noncyclic scheduling methods for such cases are required. Therefore, we develop an efficient branch and bound (B&B) procedure for noncyclic scheduling problems of cluster tools to minimize the makespan. Since a timed Petri net (TPN) is known for its powerful modeling ability and analysis capability, the algorithm is developed based on a TPN. We verify the efficiency of the B&B procedure with various cluster tool scheduling problems. There have been many studies on scheduling cluster tools, but most of them utilize different scheduling approaches or develop problem specialized properties. It is impractical to implement all the different methods to a tool scheduler because the scheduling requirements continuously change depending on wafer types and tool architectures. Hence, it is required to have an efficient solution method to address diverse cluster tool scheduling problems in fabs especially for frequent lot switchings and tool state changes due to larger wafer size and smaller lot order size. Therefore, we develop an efficient branch and bound procedure for noncyclic scheduling of a cluster tool with the makespan measurement. Since TPNs have the powerful modeling ability and analysis capability, the algorithm is developed based on a TPN. From the experimental results, we observe that one lot with 25 wafers can be easily solved in a reasonable time. The proposed method can be used for many different scheduling problems of a cluster tool by generating each corresponding TPN model.

Petri nets are useful for modeling and analyzing complex scheduling problems of automated manufacturing systems, such as robotized cluster tools for semiconductor manufacturing and robot cells with diverse and complex tool architectures and scheduling requirements. While there are many scheduling works on cyclic operation cycles of such systems and their Petri net models, automated manufacturing systems have significant noncyclic operation cycles. For instance, cluster tools cannot repeat identical work cycles for start-up and close-down operations of a lot, lot switching, nonidentical wafers, and too small lots. Such noncyclic scheduling problems can also be well modeled by timed Petri nets (TPNs) and can be solved by a branch and bound procedure that explores feasible states by branching and deleting the corresponding nodes in the reachability tree. The tree in general tends to be large, which significantly limits the computational efficiency. The tree generates nodes for all feasible markings regardless of the time evolution information associated with token holding times or firing delays. In this paper, we develop a way of significantly reducing the reachability tree by deleting the nodes or states that are infeasible in view of time evolution. To do this, we propose a time-feasible reachability tree that generates only time-feasible solutions under the earliest starting policy. We then use it for a branch and bound procedure for scheduling a TPN. We demonstrate its computational efficiency improvement with linear cluster tool scheduling problems. Note to Practitioners-TPNs have been widely used for modeling, analyzing, and scheduling discrete-event dynamic systems. Many works have improved the performance of automated manufacturing systems by developing efficient mixed integer programming models, branch and bound algorithms, or specialized strategies with a TPN. The branch and bound procedures and many other scheduling methods for a TPN search solutions by exploring paths in the reachability tree because every possible sequence can be identified as a path in the tree. However, the tree is so large even for a small Petri net. Hence, we propose a reduced reachability tree called a time-feasible reachability tree by eliminating infeasible solutions in view of time evolution. We use the time-feasible reachability tree for a branch and bound procedure for solving a TPN, and its effectiveness is verified with linear cluster tool scheduling problems. A dual-armed linear cluster tool with 25 wafers can be solved easily. We can extend the solvable problem ranges of many scheduling problems with this research.

We examine a non-cyclic scheduling problem of a wet station that performs cleaning processes for removing residual contaminants on wafer surfaces. Several chemical and rinse baths, and multiple robots for transporting jobs are linearly combined in a wet station. A wet station in a fab tends to have different types of jobs. Therefore, it is realistic to consider non-cyclic release of jobs into a wet station. We therefore examine a non-cyclic scheduling problem of a wet station that determines the task sequence of each robot so as to minimize the makespan of a given sequence of different jobs. We develop an efficient branch and bound procedure by examining the scheduling problem. To do this, we first develop a Petri net model for the scheduling problem. By identifying deadlock prevention conditions from the Petri net model, we eliminate partial solutions in advance that eventually will lead to a deadlock. By examining the feasible transition firings or state transition behavior of the Petri net model, we branch only feasible partial solutions or nodes that correspond to feasible state transitions or transition firings. We also develop a tight lower bound based on the bottleneck workload of the baths. We prove computational efficiency of the branch and bound procedure for practical problems.

We examine a scheduling problem of cluster tools that concurrently process two wafer types in a cyclic operational sequence. Whereas the process steps for different wafer types are assigned to different processing modules (PMs), the wafer loading and unloading tasks at the PMs are performed by a single robot. For a given cycle plan, which is a mix of different wafers for each cycle, we wish to determine the robot task sequence so as to minimize the tool cycle time. When a single wafer type is processed, the backward and swap sequences are optimal for single-armed and dual-armed tools, respectively. They are being prevalently used because of their simplicity and robustness. To maintain such advantages in concurrent processing, we introduce and define the concurrent backward and swap sequences (CBSs and CSSs, respectively). We then develop conditions on process times, robot task times, and the number of wafers produced in a cycle for which such CBSs and CSSs are still optimal for concurrent processing. We also show that, for some special cases, the two wafer types can achieve their maximum throughput rates as if each wafer type exclusively uses the tool regardless of other wafer types in progress. When the developed conditions do not hold, an effective mixed integer programming (MIP) model based on the CBSs and CSSs is used for robot task sequencing. Finally, we experimentally verify its efficiency and effectiveness by comparing to the existing scheduling methods for optimal scheduling of cluster tools.

In the semiconductor manufacturing industry, the lot size currently tends to be extremely small, even being only 5-8 wafers, whereas conventional lots have 25 identical wafers. The smaller lot size is made because customers demand extremely small lots, and the number of chips in a large 300 mm wafer has increased. Cyclic scheduling is not applicable for such small lot production because the number of identical work cycles accounts for a small proportion of scheduling as compared to the lengths of the starting and closing transient periods. We therefore examine a new noncyclic scheduling problem of cluster tools for small lot production that considers ready time constraints on the chambers and the robot. The ready times are the epochs when the resources are freed from processing the preceding lot. To solve the scheduling problem, we develop a Petri net model which is a graphical and mathematical method for discrete event dynamic systems. Based on the Petri net model, we also develop a mixed integer programming (MIP) model and a branch and bound (B&B) algorithm for determining an optimal schedule. The B&B algorithm solves lots with up to 25 wafers and eight wafers within 500 s for a single-armed cluster tool and a dual-armed cluster tool, respectively, when three process steps are considered. Therefore, we propose an approximation method for the dual-armed cluster tool that schedules only the first few wafers with the B&B algorithm and the succeeding wafers with a well-known cyclic sequence. From experiments, we conclude that the difference between the approximation method and an optimal makespan is less than 1%. The methods we propose can be used for general noncyclic scheduling problems that can be modeled by Petri nets.

We examine a non-cyclic scheduling problem of a timed Petri net (TPN) with a branch and bound (B&B) algorithm. There have been many approaches and algorithms for conventional scheduling problems such as job shops, resource-constrained project scheduling problems (RCPSPs), and robotized system scheduling problems. Most of these methods have focused on their effectiveness or efficiency in solving their own problems. However, they tend to ignore the issue of compatibility with other scheduling problems and the solution methods are ad hoc and hard to be used for other scheduling problems with even small changes. Petri nets have been widely used for modeling and analyzing complex discrete event dynamic systems, such as robotized manufacturing cells or other automated manufacturing systems. There are studies on scheduling cyclic Petri net models and some non-cyclic Petri net models for specific applications. In this paper, we examine a scheduling problem for non-cyclic TPNs, where there is the starting and end transitions, and the transitions do not repeat an identical firing cycle. We also allow multiple arc weights in TPNs so as to model batch processing of tasks at a resource and multiple units of a resource required for a task. We briefly explain how various scheduling constraints and objectives can be modeled by TPNs. Then, we develop an efficient B&B procedure that utilizes a dynamic branching strategy and a resource-based lower bound. We finally present examples of the B&B algorithm for an RCPSP and a single-armed cluser tool scheduling problem.

We examine a scheduling problem of a wet station with multiple job flows. The wet station performs cleaning processes for removing residual contaminants after wafer fabrication processes. It consists of several chemical and rinse baths, and multiple transport robots. Most studies on scheduling robotized systems including a wet station assume identical jobs and deal with cyclic scheduling that repeats a predefined work cycle. However, jobs arrive dynamically and many different jobs are processed concurrently at a wet station. We therefore examine a non-cyclic scheduling problem of the wet station to minimize the makespan. We first develop a Petri net model and solve the problem using a branch and bound (B&B) algorithm. We also propose a dynamic branching method and evaluate a lower bound based on a bottleneck process. During searching the nodes, we analyze deadlocks and add places to the Petri net model for precedence relations among the robot tasks by applying the deadlock prevention conditions. We finally show that the proposed B&B algorithm is sufficient to solve practical problems.