We provide scheduling techniques to enable cluster tools to produce different kinds of wafers at the same time. In this model, the multi-route model, wafers can visit different processing modules in their path. Some of these processing modules may have a limit on how long they allow the wafer to stay after the process is finished. If none of the modules have this timing constraint, we provide a greedy algorithm to schedule the multi-route cluster tool. However, if some modules have a timing constraint, the scheduling problem becomes more complicated, and an exhaustive search in a very large search space must be performed to find the optimal schedule. The exhaustive search may take as long as an hour to come up with the answer, and is not practical. We provide a simulated annealing technique to find a near-optimal schedule. To evaluate each state in the simulated annealing we need to solve a linear programming system. Instead of solving that LP system with conventional methods, we provide a much faster method. This method that uses shortest path algorithm and binary search improves the performance of the simulated annealing significantly. Our experiments showed that we can find a near-optimal solution in less than 2 minutes with this method.

This paper discusses two scheduling techniques for dual-arm cluster tools that address both process module and transport-module residency constraints and throughput requirements. The first technique is an extension of our previous work (2000) that only addressed process-module residency constraints. For cases with long process times, this technique can take a long time to find the solution and is not practical. Hence, we use this algorithm mainly as a benchmark for comparison. The second technique that uses a linear programming method with several heuristics can find the optimal solution very efficiently. An analytical and experimental analysis of this technique shows the correctness, completeness and efficiency of this technique.

In a cluster tool where process modules have residency constraints, an optimal schedule may need to buffer the partially processed wafers. In previous approaches, one of the active resources (i.e. the transport module) was used as a temporary buffer. In this approach we try to use a resource that is usually available in cluster tools and is only used for tool maintenance reasons. This passive module that we refer to as buffer module, can hold the partially processed wafers, and free the transport module (TM). Our experiment shows that in 57% of the cases, because the TM can perform other actions while the wafer is buffered in the buffer module, a schedule with better throughput was found.

Discusses a scheduling technique, for cluster tools, that addresses postprocessing residency constraints and throughput requirements. The residency constraints impose a limit on the postprocessing time that a material unit spends in a processing module. The technique searches in the time and resource domains for a feasible schedule with a maximum throughput. It operates in two main phases; the initial one of which (and the lower complexity one) computes a simple periodic schedule. For a large number of problem instances, the simple periodic schedule feasibly solves the problem. If a feasible schedule cannot be found in the first phase, the scheduler enters phase two (the higher complexity one) to compute a feasible schedule. During this phase, the scheduler incrementally increases the period only if necessary, to keep the throughput at a maximum. Several heuristics are designed and added to reduce the complexity of the scheduling algorithm. The resulting schedules are deadlock free, since resources are scheduled according to the times that they are available. Analytical and experimental analyses demonstrate the correctness and efficiency of our proposed technique.