Noncyclic scheduling of dual-armed cluster tools for minimization of wafer residency time and makespan

Abstract

Cluster tools are used for semiconductor wafer fabrication. A cluster tool consists of several loadlock modules, processing modules, and material handling armed robots to transfer wafers between loadlocks and processing modules. Most conventional scheduling methods consider a cyclic schedule to minimize makespan. We consider noncyclic scheduling of dual-armed cluster tools. In practice, it is important to minimize wafer residency time in processing modules to maintain the surface quality of wafers. In the noncyclic operations, the cluster tool causes deadlock which may lead to excessive loss in the wafer fabrication process. We propose an efficient deadlock-free scheduling method for the noncyclic scheduling problem of a dual-armed cluster tool to minimize the residency time and makespan. The proposed method is applied to a dual-armed cluster tool with a non-revisiting process and a revisiting process. Computational results demonstrate the effectiveness of the proposed method.

Keywords

Scheduling cluster tools Petri net residency time deadlock prevention

Introduction

In the semiconductor industry, manufacturers utilize cluster tools to produce silicon wafers. A typical cluster tool comprises loadlock modules (LL), several process modules (PM), and a dual-armed transfer module (TM) to transfer wafers between LL and PM. The scheduling of cluster tools has received considerable attention due to increasing demand for silicon wafers. In cluster tools, deadlocks occur due to the absence of an intermediate buffer. Therefore, it is extremely important to generate a deadlock-free schedule to maximize throughput of cluster tools.

Generally, most studies on scheduling cluster tools focus on finding the optimal cyclic schedules^1–11 when the cluster tools are operated in a steady state. A dual-armed cluster tool is often operated at a constant cycle by employing swap strategies.³ With a swap strategy, the sequence of operations is repeated, that is, a processed wafer is unloaded from a module into an empty robot arm and the subsequent wafer from another robot arm is immediately loaded into the module. Task sequencing is simplified using swap strategies. Cyclic scheduling is easier for analyzing the model because a swap strategy reduces the computational complexity of combinatorial problems.

However, in practice, the optimal schedule is not always cyclic when the operations include transitive situations such as start-up, processing time variations, cleaning, lot-switching, and maintenance. Noncyclic scheduling is often required to deal with non-steady states. In those situations, it is difficult to measure throughput in only one cycle.¹² Several studies have reported noncyclic scheduling of dual-armed cluster tools^13–18 and multi-cluster tools.^19,20 The optimal transient cycles of a single-armed cluster tool with parallel chambers have been derived.¹³ These studies showed that a generalized backward sequence has the minimum makespan for single-armed cluster tools with parallel chambers. To minimize makespan, branch and bound algorithms have been developed for the noncyclic scheduling problem when cluster tools handle consecutive small lots, that is, less than 25 identical wafers.^14,15 A schedulability analysis was conducted for noncyclic scheduling of time-constrained cluster tools with processing time variation,¹⁶ for example, start-up transient processes with wafer revisiting.¹⁷ In addition, the Petri net decomposition approach has been applied to noncyclic scheduling of dual-armed cluster tools.¹⁸

In chemical vapor deposition for processing the wafer surface, a wafer must be unloaded immediately after processing by PM. Otherwise, the quality of the wafer’s surface is immediately deteriorated by gas and heat within the PM if the residency time increases. Many related articles about the scheduling of cluster tools consider the residency time constraints of wafers.^1,5–8,21 To the best of our knowledge, no attempts have been made for bi-objective minimization of residency time and makespan in the noncyclic scheduling of dual-armed cluster tools. Practitioners always choose the appropriate schedule by considering the tradeoff between makespan and residency time. For example, they attempt to minimize makespan when demands are high to maximize throughput. On the other hand, they attempt to minimize residency time when customers’ demands are low or they are specific orders to satisfy high-quality specification. This is the main motivation of this article. However, the minimization of residency time in the noncyclic scheduling of cluster tools has been extremely difficult due to the increased number of alternative operations. In addition, noncyclic operations may cause a deadlock depending on the controller. The occurrence of deadlock results in seriously reduced throughput and deterioration of product quality. Deadlock-free scheduling is also a key issue in noncyclic scheduling. Noncyclic scheduling methods have been studied based on dispatching rules without considering deadlocks. The authors have addressed a mixed-integer linear programming model for bi-objective optimization of makespan and total wafer residency time.²² In this article, we propose a mixed-integer formulation of noncyclic scheduling of dual-armed cluster tools that requires less computational effort. A heuristic algorithm to minimize the weighted sum of makespan and total residency time is developed to find a near-optimal solution. The proposed method is applied to the noncyclic scheduling problem with revisiting processes to minimize makespan and residency time. Computational experiments are conducted to demonstrate the performance of the proposed method. The performance of these methods is investigated from computational experiments.

The remainder of this article is organized as follows. We first define the problem description for multi-objective noncyclic scheduling problem for dual-armed cluster tools. The problem is formulated as a mixed-integer linear programming problem. Then, we propose a heuristic algorithm to solve the problem. We show the application to the noncyclic scheduling of cluster tools with revisiting processes. Computational experiments are conducted. Finally, we conclude the article and state future research.

Noncyclic scheduling problem of dual-arm cluster tool with residency time

The scheduling problem of a general structure of dual-armed cluster tool is described in this section.

Scheduling problem of dual-armed cluster tools

We consider a dual-armed cluster tool consisting of four processing modules (PM1-PM4), two LL (LL1, LL2), and a dual-armed TM with fixed 180° angle double picking. A wafer can be transferred between LL and PM or between the PMs. If a wafer is loaded into LL or unloaded from LL, a wafer requires a certain period of duration for changing its pressure. The TM can rotate 360° in two ways where it can hold at most two wafers. We assume that unloading and loading of the TM contain the rotation to its specified target.

For example, for unloading a wafer in PM1, first, the robot arm with no wafer is rotated in front of PM1, and then, it holds a wafer by extending the arm. The series of operations is called unloading. Furthermore, the time required for loading/unloading is assumed to be constant since the difference of the robot arm rotation time is sufficiently small with respect to the processing time of PM. Figure 1 shows one of wafer flow patterns of the dual-armed cluster tools with two LLs, four PMs (PM1–PM4), and a dual-armed TM. All wafers have an identical wafer flow pattern. The wafer flow patterns are classified into a single flow, revisit flow, multi-flow, and so on. We assume a single-wafer flow pattern—LL1 → PM1 → PM2 → LL2 (flow pattern (1))—and a revisiting process—LL1 → PM1 → PM2 → PM1 → PM2 → LL2 (flow pattern (2)). Each LL and each PM can hold only one wafer at the same time. Deadlock is the situation when no wafer can be loaded or unloaded due to lack of resources. A wafer can be transferred between LL and PM or between the PMs. When a wafer is loaded into LL or unloaded from LL, a certain period of time, denoted by $θ_{LL 1}, θ_{LL 2}$ , is required. TM can hold two wafers at the same time and move 360° in both directions. For example, to unload a wafer in PM1, first, the arm which holds no wafer moves to the front of PM1. Then, the wafer is loaded into PM1 by extending the arm. A series of operations is called unloading. The time required for loading or unloading is assumed to be constant.

Figure 1.

The structure of a dual-armed cluster tool and wafer flow patterns: (a) wafer flow pattern (1) and (b) wafer flow pattern (2).

In a cyclic operation, each TM repeats the identical operational sequence of unloading from PM, loading into PM, unloading from LL, and loading into LL. This is called a swap operation. In noncyclic scheduling, the swap operation is not assumed, but the operational sequence of the TM is derived to minimize the objective function. Once a wafer is loaded in PM, the processing time of $θ_{PM}$ is required. The processing cannot be preempted once the processing is started. The wafer residency time is the difference between the completion time of processing in PM and the unloading time from PM. All wafers arrive at time 0. There are two objective functions in this study. The first objective is to minimize the makespan to improve system performance of the cluster tool. The second objective is to minimize the total residency time of wafers to maintain the quality of wafers. The scheduling problem treated in this article is to find a deadlock-free and an optimal operational sequence and timing of the TM to minimize the makespan and the residency time for the 25 wafers which are identical.

According to the wafer flow pattern, the operational sequence of the TM for one wafer is as follows. A wafer is moved by the TM between modules. For example, when a wafer is transferred from LL1 to PM1, first the wafer is unloaded from LL1 and then the wafer which is held in the TM is loaded to PM1. As explained above, for flow pattern (1), there are six operations by the TM which is performed: unloading from LL1, loading into PM1, unloading from PM1, loading into PM2, unloading from PM2, and loading into LL2.

Formulation of mixed-integer linear programming problem

We develop the mixed-integer linear programming formulation of the noncyclic scheduling problem of a dual-armed cluster tool with two objectives to minimize the makespan $(J_{1})$ and the residency time of wafer $(J_{2})$ . The aim of the formulation is to obtain an exact optimal solution rather than approximate solutions. We consider all possible, feasible solutions. The objective function is the weighted sum of the makespan and the residency time of wafers. Indices, sets, parameters, and decision variables are defined as follows.

Indices

s: processing order of operations of TM

$i, j$ : index of wafers $(1, \dots, N)$

$k, l$ : index of operations of TM $(1, \dots, 6)$

The operations of the TM for wafer i $(i = 1, \dots, N)$ are denoted by $A_{i}^{1}$ to $A_{i}^{6}$ .

$A_{i}^{1}$ : unloading operation of wafer i from LL1

$A_{i}^{2}$ : loading operation of wafer i to PM1

$A_{i}^{3}$ : unloading operation of wafer i from PM1

$A_{i}^{4}$ : loading operation of wafer i to PM2

$A_{i}^{5}$ : unloading operation of wafer i from PM2

$A_{i}^{6}$ : loading operation of wafer i to LL2

The precedence relation between the operations of $A_{i}^{k}$ and $A_{j}^{l}$ is denoted by $((i, k), (j, l))$ .

Sets

V: set of nodes in the directed graph representing the arm operations.

E: set of arcs in the directed graph representing the sequence of TM operations.

Parameters

$θ_{LLi}$ : processing time of LL i

$θ_{M}$ : handling time of TM

$θ_{PMi}$ : processing time of PM i

$d_{A_{i}^{k}}$ : incremental difference of number of wafers by $A_{i}^{k}$ (−1 if $A_{i}^{k}$ is loaded and 1 if $A_{i}^{k}$ is unloaded)

N: the number of wafers

Decision variables

$t_{i}^{0}$ : arrival time of wafer i in LL1

$t_{i}^{1}$ : unloading time of wafer i from LL1

$t_{i}^{2}$ : loading time of wafer i to PM1

$t_{i}^{3}$ : unloading time of wafer i from PM1

$t_{i}^{4}$ : loading time of wafer i to PM2

$t_{i}^{5}$ : unloading time of wafer i from PM2

$t_{i}^{6}$ : loading time of wafer i to LL2

$t_{i}^{7}$ : finished time of wafer i from LL2

$W_{A_{i}^{k}}$ : number of wafers held in TM immediately after $A_{i}^{k}$ $((i, k) \in V)$

$α_{((i, k), (j, l))}$ : binary variable that the operation of $A_{i}^{k}$ is executed immediately before operation $A_{j}^{l}$ in TM $((i, k), (j, l)) \in E)$

Directed graph representation of the operational sequence of the TM

In order to represent a feasible operating sequence of the TM, we construct a directed graph $G = (V, E)$ where each node represents the operations of the TM and each arc represents the precedence relationship of those operations. A directed graph is represented by an adjacency matrix denoted by $6 N \times 6 N$ square binary matrix T. A set of nodes is denoted by $V = {(i, k) | i = 1, \dots, N, k = 1, \dots, 6}$ .

An example of a directed graph of two wafers is shown in Figure 2. First, all nodes in V are connected with vertical and horizontal arcs as shown in Figure 2(a) by the precedence relations between these operations. Then, each node is connected to the set of nodes that satisfies the feasibility condition with all possible operations. In this case, node $(b, a)$ for operation $A_{b}^{a}$ is connected to all possible nodes of $(i, k)$ for operation $A_{i}^{k}$ for $k > a, b - 4 < i < b$ because these consecutive operations are feasible in both directions where a is an integer with $1 \leq a \leq 6$ and b is an integer with $1 \leq b \leq N$ . A directed graph is constructed as Figure 2(b). A path from an initial node $(1, 1)$ to $(N, 6)$ represents a feasible solution of the TM.

Figure 2.

Directed graph representation of the operational sequence of the TM: (a) vertical and horizontal arcs and (b) directed graph of activity sequence for transfer module (TM).

Problem formulation

The mixed-integer programming (IP) formulation of the noncyclic scheduling problem for dual-armed cluster tool is written as follows

minimize γ t_{N}^{7} + δ \sum_{i = 1}^{N} {(t_{i}^{3} - t_{i}^{2} - θ_{M} - θ_{P M 1}) + (t_{i}^{5} - t_{i}^{4} - θ_{M} - θ_{P M 2})}

(1)

Subject to equations (2)–(21)

t_{j}^{l} - t_{i}^{k} + M (1 - α_{((i, k), (j, l))}) \geq θ_{M} (((i, k), (j, l)) \in E)

(2)

t_{i}^{1} - t_{i}^{0} \geq θ_{LL 1} (i = 1, \dots, N)

(3)

t_{i}^{2} - t_{i}^{1} \geq θ_{M} (i = 1, \dots, N)

(4)

t_{i}^{3} - t_{i}^{2} \geq θ_{M} + θ_{PM 1} (i = 1, \dots, N)

(5)

t_{i}^{4} - t_{i}^{3} \geq θ_{M} (i = 1, \dots, N)

(6)

t_{i}^{5} - t_{i}^{4} \geq θ_{M} + θ_{PM 2} (i = 1, \dots, N)

(7)

t_{i}^{6} - t_{i}^{5} \geq θ_{M} (i = 1, \dots, N)

(8)

t_{i}^{7} - t_{i}^{6} \geq θ_{M} + θ_{LL 2} (i = 1, \dots, N)

(9)

t_{i + 1}^{0} - t_{i}^{1} \geq θ_{M} (i = 1, \dots, N - 1)

(10)

t_{i + 1}^{2} - t_{i}^{3} \geq θ_{M} (i = 1, \dots, N - 1)

(11)

t_{i + 1}^{4} - t_{i}^{5} \geq θ_{M} (i = 1, \dots, N - 1)

(12)

t_{i + 1}^{6} - t_{i}^{7} \geq 1 (i = 1, \dots, N - 1)

(13)

\sum_{((1, 1), (i, k)) \in E} α_{((1, 1), (i, k))} = 1

(14)

\sum_{((i, k), (N, 6)) \in E} α_{((i, k), (N, 6))} = 1

(15)

\sum_{((i, k), (j, l)) \in E} α_{((i, k), (j, l))} = 1 ((i, k) \in V ∖ {(1, 1), (N, 6)})

(16)

\sum_{((j, l), (i, k)) \in E} α_{((j, l), (i, k))} = 1 ((i, k) \in V ∖ {(1, 1), (N, 6)})

(17)

W_{A_{1}^{1}} = 1, W_{A_{N}^{6}} = 0

(18)

\begin{array}{l} W_{A_{i}^{k}} = \sum_{((j, l), (i, k)) \in E} (α_{((j, l), (i, k))} W_{A_{j}^{l}} + α_{((j, l), (i, k))} d_{A_{i}^{k}}) \\ ((i, k) \in V ∖ {(1, 1), (N, 6)}) \end{array}

(19)

2 \geq W_{A_{i}^{k}} ((i, k) \in V ∖ {(1, 1), (N, 6)})

(20)

α_{((i, k), (j, l))} \in {0, 1} (((i, k), (j, l)) \in E)

(21)

ℕ is the set of nonnegative integers. The objective function (1) is the weighted sum of the makespan and the residency time. $γ$ and $δ$ are the weighting factors for $J_{1}$ and $J_{2}$ , respectively. Constraints (2) ensure the precedence relation between the operations of $A_{j}^{l}$ and $A_{i}^{k}$ . At least $θ_{M}$ time is required to perform the operation $A_{j}^{l}$ just after the operation of $A_{i}^{k}$ . M is a sufficiently large positive number. Constraints (3)–(9) indicate that a wafer cannot be transferred from each module before the completion of the processing at each module. Constraints (10)–(13) indicate that two wafers cannot be processed at the same time in LL1, PM1, PM2, and LL2, respectively. The loading time of wafer $i + 1$ is always delayed than the unloading time of wafer i. Constraints (14) and (15) specify the initial and final nodes in a path. Constraints (16) and (17) denote that all nodes except $(1, 1), (N, 6)$ must be in a path. Constraints (18) relate to the number of wafers held by the TM at the initial and final conditions. Constraints (19) determine the number of wafers held in TM at each node. The number of wafers held by TM is the number of wafers held at the previous node plus its change which is calculated by $d_{A_{i}^{k}}$ . Constraints (20) restrict the number of wafers held by TM and it is not greater than two. Constraints (21) define the range of decision variables. The constraints (19) are linearized as follows

\begin{array}{l} 0 \leq β_{((j, l), (i, k))} \leq 2 α_{((j, l), (i, k))}, \\ ((i, k) \in V ∖ {(1, 1), (N, 6), ((j, l), (i, k)) \in E) \end{array}

(22)

\begin{array}{l} W_{A_{j}^{l}} - 2 (1 - α_{((j, l), (i, k))}) \leq β_{((j, l), (i, k))} \leq W_{A_{j}^{l}}, \\ ((i, k) \in V ∖ {(1, 1), (N, 6)}, ((j, l), (i, k)) \in E) \end{array}

(23)

\begin{array}{l} W_{A_{i}^{k}} = \sum_{((j, l), (i, k)) \in E} (β_{((j, l), (i, k))} + α_{((j, l), (i, k))} d_{A_{i}^{k}}), \\ ((i, k) \in V ∖ {(1, 1), (N, 6)}) \end{array}

(24)

Heuristic algorithm for deadlock-free scheduling problem of cluster tools for minimization of residency time and makespan

General-purpose solvers for solving the mixed-IP formulation can solve only small-scale problems. Because the exact algorithms such as branch and bound cannot solve large-scale instances, we propose a heuristic algorithm to derive a near-optimal solution efficiently. The main idea of the heuristic algorithm is to construct a candidate of solution by two phases. The one is to generate a deadlock-free operational sequence of wafers by Petri net modeling. After a feasible sequence is derived, an optimal schedule is generated by solving linear programming problem with a fixed operational order. In the following sections, the Petri net modeling and deadlock prevention policy are introduced.

Petri net modeling and deadlock prevention policy

Petri net model can be easily applied to any wafer flow and it can prevent deadlock situations by analyzing the specific construction of the Petri net model (siphons, for example).²³ Hence, we use a Petri net model for flow pattern (1). The purpose is to obtain feasible operating sequences of the TM.

Definition of state and events of Petri net

Places, events, and transitions for wafer flow pattern (1) are defined as follows (Table 1).

Table 1.

Symbols of places and transitions for flow pattern (1).

State	Place	Event	Transition
Wafer staying in LL1	$LL 1$	Wafer is unloaded from LL1	$E 1$
Wafer staying in arm (first time)	$ARM 1$	Wafer is loaded to PM1	$E 2$
Wafer staying in PM1	$PM 1$	Wafer is unloaded from PM1	$E 3$
Wafer staying in arm (second time)	$ARM 2$	Wafer is loaded to PM2	$E 4$
Wafer staying in PM2	$PM 2$	Wafer is unloaded from PM2	$E 5$
Wafer staying in arm (third time)	$ARM 3$	Wafer is loaded to LL2	$E 6$
Wafer staying in LL2	$LL 2$

PM: process modules; LL: loadlock modules.

The Petri net model for wafer flow pattern (1), which is denoted by $P N_{R}$ , is shown in Figure 3(a). There are three resource places. $RPM 1$ and $RPM 2$ represent that two or more than two wafers cannot be processed at each PM. RARM represents that the robot arm can hold at most two wafers at the same time.

Figure 3.

$P N_{R}$ and $P N_{R + DF}$ for a dual-armed cluster tool with flow pattern (1): (a) $P N_{R}$ for wafer flow pattern (1) and (b) $P N_{R + DF}$ for wafer flow pattern (1).

Deadlock prevention policy

The strict minimum siphon that might lose all tokens is called potential deadlock. If all of the strict minimum siphons of Petri net have no possibility to lose all tokens, the Petri net is deadlock-free. In Zhong and Li,²⁴ siphons are detected by solving the mixed-integer linear programming problem and the monitor places are introduced to prevent a potential deadlock from losing all tokens in the siphons. It is possible to prevent deadlock of the cluster tools by adding monitor place for all empty siphons of the Petri net model. We apply the deadlock detection policy proposed by Li et al.²⁵ to our Petri net model $P N_{R}$ as shown in Figure 3 to find three potential deadlocks. The Petri net $P N_{R + DF}$ with monitor places for three potential deadlocks is shown in Figure 3. The unloading and loading operations contain the moving for TM. The wafer flow pattern (1) is represented by state and events as defined above. The capacity constraints of each place are represented by adding resource places. The resource place $RPM 1$ restricts that only one wafer can exist in PM. RARM restricts that the number of wafers in TM is equal or less than two. The initial marking of each resource place is $M_{0} (RPM 1) = 1$ , $M_{0} (RPM 2) = 1$ , and $M_{0} (RARM) = 2$ , as shown in Figure 3. $VS 1$ , $VS 2$ , and $VS 3$ are the monitor places for deadlock prevention based on Nishi and Matsumoto (2015).¹⁸ We have applied a deadlock detection policy to Petri net $P N_{R + DF}$ , and then, we have confirmed that there is no potential deadlocks in $P N_{R + DF}$ . It was shown that $P N_{R + DF}$ was deadlock-free and maximally permissive controller.¹⁸

Heuristic algorithm with Petri net simulations

The heuristic algorithm repeats the generation of one feasible operational order of the TM and an optimal timing of operations when the order of operations is fixed. The proposed algorithm is as follows.

Step 0. Set $t = 0$ .

Step 1. Select the set of the enabled transitions. Then, one transition is randomly chosen and it is fired.

Step 2. Set $t = t + 1$ . If the current marking reaches the final marking, go to Step 3. Otherwise, go to Step 1.

Step 3. Fix the feasible operational order of the TM and then determine an optimal timing of firing such that the objective is minimized.

Step 4. Obtain the value of the objective function from the obtained schedule. Save the best one and the best solution.

Steps 1–4 are repeated a specified number of times and then output the best solution. It is the random search, so there is a possibility to obtain the same solution many times, and the resulting solution is not always optimal.

Formulation of starting time calculation when the operation sequence of the arm is fixed

If a feasible operational order of the TM is fixed, then we can obtain the sequence of state transitions. Then, we can define the ith operation of TM as follows.

$A M_{s}$ : the starting time of the sth processed operation of TM $(s = 1, \dots, 6 N)$ .

The formulation is simply written as follows

minimize γ t_{N}^{7} + δ \sum_{i = 1}^{N} {(t_{i}^{3} - t_{i}^{2} - θ_{M} - θ_{P M 1}) + (t_{i}^{5} - t_{i}^{4} - θ_{M} - θ_{P M 2})}

(25)

Subject to equations (26)–(35)

A M_{s + 1} - A M_{s} \geq θ_{M} (s = 1, \dots, 6 N - 1)

(26)

t_{i}^{1} - t_{i}^{0} \geq θ_{LL 1} (i = 1, \dots, N)

(27)

t_{i}^{3} - t_{i}^{2} \geq θ_{M} + θ_{PM 1} (i = 1, \dots, N)

(28)

t_{i}^{5} - t_{i}^{4} \geq θ_{M} + θ_{PM 2} (i = 1, \dots, N)

(29)

t_{i}^{7} - t_{i}^{6} \geq θ_{M} + θ_{LL 2} (i = 1, \dots, N)

(30)

t_{i + 1}^{0} - t_{i}^{1} \geq θ_{M} (i = 1, \dots, N - 1)

(31)

t_{i + 1}^{2} - t_{i}^{3} \geq θ_{M} (i = 1, \dots, N - 1)

(32)

t_{i + 1}^{4} - t_{i}^{5} \geq θ_{M} (i = 1, \dots, N - 1)

(33)

t_{i + 1}^{6} - t_{i}^{7} \geq 1 (i = 1, \dots, N - 1)

(34)

t_{i}^{k} \geq 0 i = 1, \dots, N; k = 0, \dots, 7)

(35)

The objective function (25) is the weighted sum of the total completion time and the total residency time. $γ$ is the weight coefficient of completion time, and $δ$ is the weight coefficient of residency time. We set $γ$ and $δ$ to 1. Constraints (26) mean that the moving time $θ_{M}$ is required after the previous operation when the operational order of the TM is fixed, and the operation of the arm is only performed once. The problem is a linear programming problem that can be solved by simplex algorithms.

Reduction of arcs in the directed graph in section “Formation of mixed-integer linear programming”

We consider the redundancy of the directed graph for configuring IP formulation. The directed graph represents all feasible operational sequences of the TM. However, in order to obtain only the optimal solution efficiently, we restrict the number of diagonal arcs in the graph. The diagonal arcs in the graph of Figure 2(b) can be reduced. If the arcs are not adopted in a number of solutions, we do not have to connect them from the beginning of the graph construction phase because these solutions using these arcs are not optimal. From the exact solutions obtained from the IP, the arcs to be adopted as a solution are analyzed. A node $A_{b}^{a}$ is connected to all nodes $A_{b - 1}^{k}$ if it satisfies $a < k < a + 3$ , $A_{b - 2}^{k}$ if it satisfies $a + 1 < k < a + 4$ , and $A_{b - 3}^{k}$ if it satisfies $a + 3 < k < a + 6$ in both directions where a is any integer number satisfying $1 \leq a \leq 6$ and b is any integer number satisfying $1 \leq b \leq N$ . If we assume that an operating sequence is feasible, then a node $A_{b}^{a}$ is not connected to any nodes not satisfying above inequalities.

Application to noncyclic scheduling problem with revisiting processes

We apply the proposed method to the noncyclic scheduling problem of dual-armed cluster tools with revisiting process. In the revisiting process, wafer visits some processing modules for multiple times. It is more challenging to solve the noncyclic scheduling problem with revisiting process.

Petri net modeling

We consider the wafer flow pattern $LL 1 \to PM 1 \to PM 2 \to PM 1 \to PM 2 \to LL 2$ . In this section, the Petri net model for the dual-arm cluster tools is developed w here all the wafers have the same process flow pattern. The wafer flow is represented by (1, 1, 1, 1). Hereafter, this flow is called flow pattern (2). The Petri net modeling and deadlock prevention policy are applied. The symbols for places and transitions are shown in Table 2.

Table 2.

Symbols for places and transitions for flow pattern (2).

State	Place	Event	Transition
Wafer staying in LL1	$LL 1$
Wafer staying in arm (first)	$ARM 1$	Wafer is unloaded from LL1	$E 1$
Wafer staying in PM1 (first)	$PM 11$	Wafer is loaded to PM1 (first)	$E 2$
Wafer staying in arm (second)	$ARM 2$	Wafer is unloaded from PM1 (first)	$E 3$
Wafer staying in PM2 (first)	$PM 21$	Wafer is loaded to PM2 (first)	$E 4$
Wafer staying in arm (third)	$ARM 3$	Wafer is unloaded from PM2 (first)	$E 5$
Wafer staying in PM1 (second)	$PM 12$	Wafer is loaded to PM1 (second)	$E 6$
Wafer staying in arm (fourth)	$ARM 4$	Wafer is unloaded from PM1 (second)	$E 7$
Wafer staying in PM2 (second)	$PM 22$	Wafer is loaded to PM2 (second)	$E 8$
Wafer staying in arm (fifth)	$ARM 5$	Wafer is unloaded from PM2 (second)	$E 9$
Wafer staying in LL2	$LL 2$	Wafer is loaded to LL2	$E 10$

PM: process modules; LL: loadlock modules.

The Petri net $PN 2_{R}$ represents the flow pattern (2), which is shown in Figure 4(a). The Petri net $PN 2_{R + DF}$ is obtained by adding monitor places to $PN 2_{R}$ to prevent deadlock as shown in Figure 4(b). $VS 1$ , $VS 2$ , and $VS 3$ are monitor places. We apply a potential deadlock detection policy to Petri net $PN 2_{R + DF}$ , and then, we confirm that there are no potential deadlock and deadlock-free in $PN 2_{R + DF}$ . We show that the derived deadlock prevention policies are optimal. Table 3 shows the total number of reachable states, the number of deadlocks, and the number of legal markings.

Figure 4.

$PN 2_{R}$ and $PN 2_{R + DF}$ for a dual-armed cluster tool with flow pattern (2): (a) $PN 2_{R}$ for wafer flow pattern (2) and (b) $PN 2_{R + DF}$ for wafer flow pattern (2).

Table 3.

The number of reachable states for $PN 2_{R}$ and $PN 2_{R + DF}$ .

	Wafer flow pattern (1)		Wafer flow pattern (2)
	$P N_{R}$	$P N_{R + DF}$	$PN 2_{R}$	$PN 2_{R + DF}$
Number of wafers	25	25	25	25
Number of reachable markings	828	738	3191	2563
Number of legal markings	738	738	2563	2563
Number of deadlocks	90	0	628	0

From the results of Table 3, the number of reachable markings for $P N_{R + DF}$ is totally the same with the number of legal markings of $P N_{R}$ . Also, the number of reachable markings of $PN 2_{R}$ is totally the same with that of $PN 2_{R + DF}$ . It indicates that the derived deadlock prevention policy is optimal and it is a maximally permissible controller.

Formulation of starting time calculation for revisit process

The starting time of operations are computed by solving the linear programming problem

\begin{matrix} minimize & γ t_{N}^{11} + δ \sum_{i = 1}^{N} {(t_{i}^{3} - t_{i}^{2}) + (t_{i}^{5} - t_{i}^{4}) \\ + (t_{i}^{7} - t_{i}^{6}) + (t_{i}^{9} - t_{i}^{8})} \end{matrix}

(36)

A M_{s + 1} - A M_{s} \geq θ_{M} (s = 1, \dots, 10 N - 1)

(37)

t_{i}^{1} - t_{i}^{0} \geq θ_{LL 1} (j = 1, \dots, N)

(38)

t_{i}^{3} - t_{i}^{2} \geq θ_{M} + θ_{PM 1} (i = 1, \dots, N)

(39)

t_{i}^{5} - t_{i}^{4} \geq θ_{M} + θ_{PM 2} (i = 1, \dots, N)

(40)

t_{i}^{7} - t_{i}^{6} \geq θ_{M} + θ_{PM 1} (i = 1, \dots, N)

(41)

t_{i}^{9} - t_{i}^{8} \geq θ_{M} + θ_{PM 2} (i = 1, \dots, N)

(42)

t_{i}^{11} - t_{i}^{10} \geq θ_{M} + θ_{LL 2} (i = 1, \dots, N)

(43)

t_{i + 1}^{0} - t_{i}^{1} \geq θ_{M} (i = 1, \dots, N - 1)

(44)

t_{i + 1}^{2} - t_{i}^{3} \geq θ_{M} (i = 1, \dots, N - 1)

(45)

t_{i + 1}^{4} - t_{i}^{5} \geq θ_{M} (i = 1, \dots, N - 1)

(46)

t_{i + 1}^{6} - t_{i}^{7} \geq θ_{M} (i = 1, \dots, N - 1)

(47)

t_{i + 1}^{8} - t_{i}^{9} \geq θ_{M} (i = 1, \dots, N - 1)

(48)

t_{i + 1}^{10} - t_{i}^{11} \geq 1 (i = 1, \dots, N - 1)

(49)

t_{i}^{k} \geq 0 (i = 1, \dots, N; k = 0, \dots, 11)

(50)

where $t_{i}^{0}$ is the arrival time of wafer i in LL1, $t_{i}^{1}$ is the unloading time of wafer i from LL1, $t_{i}^{2}$ is the loading time of wafer i to the first operation of PM1, $t_{i}^{3}$ is the unloading time of wafer i from the first operation of PM1, $t_{i}^{4}$ is the loading time of wafer i to the first operation of PM2, $t_{i}^{5}$ is the unloading time of wafer i from the first operation of PM2, $t_{i}^{6}$ is the loading time of wafer i to the second operation of PM1, $t_{i}^{7}$ is the unloading time of wafer i to the second operation of PM1, $t_{i}^{8}$ is the loading time of wafer i to the second operation of PM2, $t_{i}^{9}$ is the unloading time of wafer i to the second operation of PM2, $t_{i}^{10}$ is the loading time of wafer i to LL2, and $t_{i}^{11}$ is the finished time of wafer i from LL2.

Computational experiments

Computational experiments are conducted to show the performance of the proposed method. The parameters are selected as $θ_{LL 1} = 10 s$ , $θ_{L L 2} = 10 s$ , $θ_{M} = 7 s$ , $θ_{PM 1} = 120 s$ , and $θ_{PM 2} = 120 s$ .

Effects of multi-objective optimization

First, we compare the solutions of the heuristic algorithm to minimize only $J_{1}$ (CASE 1) and the one to minimize both $J_{1}$ and $J_{2}$ (CASE 2). The number of wafers is 25. An Intel^® Core™ i7-4770 CPU 3.40 GHz and 8.00 GB was used for computations. The computational results of the heuristic algorithm for flow patterns (1) and (2) are shown in two cases of CASE 1 and CASE 2 (Table 4). The number of iterations was 10,000.

Table 4.

Computational results of the proposed method.

		CASE 1			CASE 2
	Wafer	$J_{1}$	$J_{2}$	Time	$J_{1}$	$J_{2}$	Time
Flow pattern (1)	25	1328	276	594.7	1456	56	714.7
Flow pattern (2)	25	7481	603	634.4	7488	406	652.3

For flow pattern (1), the total residency time of CASE 2 is significantly decreased from that of CASE 1 by the minimization of both objectives $(J_{1} + J_{2})$ ; however, the makespan $(J_{1})$ is not much increased. For flow pattern (2), the total residency time of CASE 2 is decreased to 25% in CASE 2; even, the makespan of CASE 2 is slightly increased 10% of CASE 1. From these results, we can confirm that the minimization of both objectives can be achieved without lowering throughput of the cluster tools.

Effects of reduction of arcs in the exact algorithm

The IP formulation and the reduced IP formulation are compared. The computational results are shown in Table 5. We set parameters to $θ_{LL 1} = 10 s$ , $θ_{LL 2} = 10 s$ , $θ_{M} = 7 s$ , $θ_{PM 1} = 20 s$ , and $θ_{PM 2} = 20 s$ . One case is when only makespan is minimized (hereafter, this case is called CASE 1). Another case is considering residency time (hereafter, this case is called CASE 2). “ $J_{1}$ ” is the makespan, “ $J_{2}$ ” is the residency time, “ $Obj .$ ” is the value of the objective function, “Wafer” is the number of wafers, and “Time” is the total computation time (s). Moreover, “–” mean that we could not obtain results due to insufficient memory, and time represents the computation time when the computation is stopped.

Table 5.

Computational results of IP and reduced IP for flow pattern (1).

	IP				Reduced IP
Wafer	$J_{1}$	$J_{2}$	$Obj .$	Time	$J_{1}$	$J_{2}$	$Obj .$	Time
4	226	2	228	5.1	226	2	228	0.9
6	310	6	316	246.4	310	6	316	28.2
8	−	−	−		394	10	404	134.8

IP: integer programming.

From Table 5, we can see that the reduced IP can obtain an optimal solution in a short computation time less than that of IP. Moreover, although IP cannot obtain a solution of eight wafers in CASE 2, the reduced IP can obtain an optimal solution of eight wafers. The reduced IP can reduce the computation time and the application ranges.

Comparison of the performance of IP and the proposed method

The computational results of flow patterns (1) and (2) by the heuristic method in the previous section (hereafter called proposed method) and IP are compared. In IP, a general-purpose solver (CPLEX 12.6) was used to solve the mixed-IP models. Tables 6 and 7 show the comparison of the performance of those methods for flow patterns (1) and (2) when the number of wafer is changed from 4 to 25. The number of iterations is 10,000 in the proposed method.

Table 6.

Computational results of IP and the proposed method for flow pattern (1) (CASE 1: $J_{1}$ only and CASE 2: $J_{1} + J_{2}$ ).

		IP				Proposed method
CASE	Wafer	$J_{1}$	$J_{2}$	$Obj .$	Time	$J_{1}$	$J_{2}$	$Obj .$	Time
1	4	226	18	226	4.4	226	16	226	424.4
1	6	310	42	310	67.5	317	20	317	502.5
1	8	394	67	394	353.8	419	46	419	522.8
1	25	−	−	−		1328	276	1328	594.7
2	4	226	2	228	5.1	238	0	238	488.0
2	6	310	6	316	246.4	317	20	337	491.1
2	25	−	−	−		1456	56	1512	714.7

IP: integer programming.

Table 7.

Computational results of IP and the proposed method for flow pattern (2) (CASE 1: $J_{1}$ only and CASE 2: $J_{1} + J_{2}$ ).

		IP				Proposed method
CASE	Wafer	$J_{1}$	$J_{2}$	$Obj .$	Time	$J_{1}$	$J_{2}$	$Obj .$	Time
1	4	1268	0	1268	6149.9	1286	7	1286	989.7
1	6	−	−	−		1822	28	1822	1002.5
2	4	1268	0	1268	3245.4	1286	0	1286	1112.9
2	6	−	−	−		1811	0	1811	1127.4

IP: integer programming.

For both wafer flows, the makespan obtained by CASE 2 is nearly the same as that of CASE 1. It is worthwhile to minimize makespan and residency time in the objective function. The computation time of the exact algorithm with CPLEX increases drastically with an increasing number of wafers. Therefore, IP cannot obtain even a feasible solution for 25 wafer problems in both cases due to insufficient memory. For wafer flow (2), CPLEX cannot solve the problems with greater than six wafers because there are too many binary variables in the IP models. The proposed method can derive solutions that are close to optimal for small-scale problems. The total computation time of the proposed method is independent of the number of iterations and even an increasing number of wafers. We can obtain a better solution without requiring a large amount of computation time. The performance of the solutions obtained by the proposed method is close to the optimal solution derived by CPLEX. The formulation of the proposed method is simple because the operating sequence of the TM is obtained by Petri net simulation. Then, the total computation time of the proposed method is less sensitive to the influence of the number of wafers. From these results, the effectiveness of the proposed method is confirmed.

Conclusion

In this study, we have proposed a heuristic algorithm for noncyclic scheduling of dual-armed cluster tools with revisiting processes to minimize wafer residency time and makespan. A Petri net model was used to generate a feasible operational order without deadlocks. The maximally permissive deadlock prevention policy has been derived from the original Petri net models. If the operational order is fixed, the scheduling problem is formulated as a linear programming problem to minimize makespan and total residency time. In the proposed method, the generation of a feasible sequence and solving the linear programming problem are repeated with Petri net simulations to minimize the objective functions. The performance of the proposed method was compared to that of CPLEX. The results demonstrated that total residency time can be reduced without reducing the performance of the makespan. The computation time of the proposed method is much less than that of CPLEX. Thus, the effectiveness of the proposed method has been confirmed. In future, we will investigate the proposed method for more complex cluster tools such as multi-cluster tools.

Footnotes

Acknowledgements

The authors would like to thank anonymous reviewers for their valuable suggestions and comments to improve this article.

Academic Editor: Wu Naiqi

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is partially supported by TEPCO Memorial Foundation.

References

Rostami

Hamidzade

Camporese

An optimal periodic scheduler for dual-arm robots in cluster tools with residency constraints. IEEE T Robotic Autom 2001; 17: 609–618.

Zuberek

WM.

Timed Petri nets in modeling and analysis of cluster tools. IEEE T Robotic Autom 2001; 17: 562–575.

Pan

Zhou

Qiao

. Modeling and scheduling of cluster tools dealing with wafer revisiting: a brief review. In: Proceedings of the 2015 IEEE international conference on networking, sensing and control, Taipei, Taiwan, 9–11 April 2015, pp. 271–275. New York: IEEE.

Qiao

Zhou

MC.

A Petri net-based novel scheduling approach and its cycle time analysis for dual-arm cluster tools with wafer revisiting. IEEE T Semiconduct M 2013; 26: 100–110.

Qiao

Zhou

MC.

Scheduling of dual-arm cluster tools with wafer revisiting and residency time constraints. IEEE T Ind Inform 2014; 10: 286–300.

Qiao

Zhou

MC.

Schedulability and scheduling analysis of dual-arm cluster tools with wafer revisiting and residency time constraints based on a novel schedule. IEEE T Autom Sci Eng 2015; 45: 472–484.

Qiao

Zhou

MC.

Petri net modeling and wafer sojourn time analysis of single-arm cluster tools with residency time constraints and activity time variation. IEEE T Autom Sci Eng 2012; 25: 432–446.

Pan

Qiao

. A novel algorithm for wafer sojourn time analysis of single-arm cluster tools with wafer residency time constraints and activity time variation. IEEE T Autom Sci Eng 2015; 45: 805–818.

Chu

. Petri net-based scheduling of single-arm cluster tools with reentrant atomic layer deposition processes. IEEE T Autom Sci Eng 2011; 8: 42–55.

10.

Chu

. Petri net modeling and cycle-time analysis of dual-arm cluster tools with wafer revisiting. IEEE T Syst Man Cy A 2013; 43: 196–207.

11.

Zhou

Chu

. A Petri-net-based scheduling strategy for dual-arm cluster tools with wafer revisiting. IEEE T Syst Man Cy A 2013; 43: 1182–1194.

12.

Wikborg

Lee

Noncyclic scheduling for timed discrete-event systems with application to single-armed cluster tools using Pareto-optimal optimization. IEEE T Autom Sci Eng 2013; 10: 699–710.

13.

Kim

D-K

Lee

T-E

Kim

H-J.

Optimal scheduling of transient cycles for single-armed cluster tools with parallel chambers. IEEE T Autom Sci Eng 2016; 13: 1165–1175.

14.

Kim

H-J

Lee

J-H

Jung

. Scheduling cluster tools with ready time constraints for consecutive small lots. IEEE T Autom Sci Eng 2013; 10: 145–159.

15.

Kim

H-J

Lee

J-H

Lee

T-E.

Noncyclic scheduling of cluster tools with a branch and bound algorithm. IEEE T Autom Sci Eng 2015; 12: 690–700.

16.

Kim

H-J

Lee

J-H

Lee

T-E.

Schedulability analysis for noncyclic operation of time-constrained cluster tools with time variation. IEEE T Autom Sci Eng 2016; 13: 1409–1414.

17.

Pan

Qiao

Zhou

MC.

Scheduling and analysis of start-up transient processes for dual-arm cluster tools with wafer revisiting. IEEE T Semiconduct M 2015; 28: 160–170.

18.

Nishi

Matsumoto

Petri net decomposition approach to deadlock-free and non-cyclic scheduling of dual-armed cluster tools. IEEE T Autom Sci Eng 2015; 12: 281–294.

19.

Watanabe

Nishi

. A new deadlock prevention policy for multi-cluster tools with dual path. In: Proceedings of IEEE international conference on systems, man and cybernetics, Sandiego, CA, 5–8 October 2014, pp.1330–1335. New York: IEEE.

20.

Watanabe

Nishi

. Deadlock prevention policy for multi-cluster tools with multi-flow. In: Proceedings of IEEE international conference on industrial engineering and engineering management, Bangkok, Thailand, 10–13 December 2013, pp.611–615. New York: IEEE.

21.

Kim

J-H

Lee

T-E

Lee

H-Y

. Scheduling analysis of time-constrained dual-armed cluster tools. IEEE T Semiconduct M 2003; 16: 521–534.

22.

Sakai

Nishi

. Non-cyclic scheduling of dual-armed cluster tools for bi-objective minimization of wafer residence time and makespan. In: Proceedings of the 2016 IEEE international conference on industrial engineering and engineering management, Bali, Indonesia, 4–7 December 2016. New York: IEEE.

23.

Murata

Petri nets: properties, analysis and applications. P IEEE 1989; 77: 541–580.

24.

Zong

A deadlock prevention approach for flexible manufacturing systems without complete siphon enumeration of their Petri net models. Eng Comput 2009; 25: 269–278.

25.

Zhou

Jeng

A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions. IEEE T Autom Sci Eng 2008; 5: 182–188.