Minimizing cycle time in large robotic cells.

1. Introduction

Robots are now used for many different applications in manufacturing (Asfahl, 1985). One important application of robots in semiconductor manufacturing is their use for material handling in robotic cells. A robotic cell is a set of processing stations (or stages) arranged

within the reach of a robot. Each station has a single or multiple identical processing unit(s). One of the most general cell layouts is the robot-centered cell (Groover, 1987) illustrated in Fig. 1, where the cell consists of three stations ([S.sub.1], [S.sub.2], [S.sub.3]), each having one processing unit. These stations are served by a central robot.

Robot-centered cells are common in practice (Asfahl, 1985) and are frequently used in the semiconductor manufacturing environment for wafer fabrication. The robot unloads wafers (or products or parts) from, transports them between, and loads them onto, the stations. For example, in a three-station robotic cell (Fig. 1), each part passes through the same sequence of locations from the input tray (I), through stations [S.sub.1], [S.sub.2] and [S.sub.3], and finally onto the output tray (O), as in a classical flowshop. After it loads a part onto a station, the robot either waits for the part to finish its processing, or moves to another station to unload any other finished part, or moves to the input tray to pick up a new part. At any point in time, a part in the cell is either on one of the stations or being handled by the robot. There are no buffers at or between the processing stations. Neither a station nor the robot can be in possession of more than one part at any time. Furthermore, the processing of a part at a station is nonpreemptive.

We address here the problem of scheduling a robot's operations in robotic cells that repetitively produce identical parts. We solve this problem for a Texas-based company called FSI International Inc., a manufacturer of robotic cells for semiconductor wafer fabrication companies. Since these wafers command a high price, minimizing the average time needed to produce a wafer is a critical issue for wafer fabrication companies, especially when the robotic cell operates at full capacity. Thus, the objective of this research is to minimize the per unit cycle time (hereafter also called the cycle time), i.e., the average time to produce a wafer in the steady state, which in turn would help FSI's customers to achieve their target throughput. We worked with FSI on three different robotic cell configurations. For given cell data, such as the number of stations and processing time requirement of wafers at each station, one must determine the optimal sequence of moves performed by the robot, in order to minimize the cycle time.

[FIGURE 1 OMITTED]

Cycle time minimization is possible either by investing more in hardware or by using the best logic to operate a given station-robot combination to intelligently push more wafers through the system per unit time. Wafer fabrication companies want FSI to design a cell that meets their requirements (i.e., the target throughput) with a minimum investment in hardware. In order to produce more wafers per unit time without increasing the investment in hardware, FSI has been using dispatch-type robot movement scheduling methods. Better robot movement scheduling methods would help FSI to find a solution with the minimum hardware cost that satisfies the requirement of its customers: the mass producers of semiconductor wafers.

Scheduling problems encountered in robotic cells with m stations, each having one processing unit, have been widely studied in the literature. Sethi et al. (1992) define an important class of cyclic schedules for the sequences of robot moves. One such cyclic schedule, defined by the well known robot moves called downhill permutation, will be described in Section 4.1. In a cyclic schedule of robot moves, the same sequence of states is repeated over and over again. A cycle in such a schedule begins at any given state and ends when that state is next encountered. For a given instant of time, the state of the robotic cell is specified by the following parameters: (i) list of wafers that are in process; (ii) where each of these wafers is residing (on the robot, or on a station); (iii) the exact amount of processing that remains to be done at a station for each wafer currently in progress; (iv) the waiting time for each wafer after it has completed its processing at a station; and (v) the location of the robot.

In each cycle of a cyclic schedule, one or more wafers is completed. If q wafers are produced in a cycle, we call the cycle a q-unit cycle. In this case, the cycle time (T) is equal to the total time required to produce q wafers divided by q. We confine our discussion to cyclic schedules and study the steady-state operations of the system under various cyclic scheduling options. We show later that, in terms of cycle time, our cyclic solution is superior to the dispatching rule currently being used by FSI.

Literature reviews for the problem of scheduling robot moves in robotic cells having one processing unit at each station may be found in Sriskandarajah et al. (1998), Crama et al. (2000) and Dawande et al. (2004). Herrmann (2003) provides a branch-and-bound algorithm to find the optimal time needed to process a lot in two- and three-station robotic cells with one processing unit at each station. Crama and Van de Klundert (1999) show that the best one-unit cycle is optimal for three-station robotic cells in an additive robot travel time setting, where the total time required to travel between stations [S.sub.i] and [S.sub.j], i [not equal to] j, is [[summation].sub.h=i.sup.j-1] [[delta].sub.h] if i < j and [[summation].sub.h=j.sup.j-1] [[delta].sub.h] if j < i ([[delta].sub.i] is the robot travel time between [S.sub.i] and [S.sub.i+1], in both directions). Moreover, Crama and Van de Klundert (1997) propose a polynomial-time algorithm to find an optimal one-unit cycle in an additive robot travel time setting. Nevertheless, Brauner et al. (2003) show that the problem of finding an optimal one-unit cycle is NP-hard in the general setting. Hence, we propose an efficient metaheuristic algorithm to solve the problem for m stations in a general robot travel time setting. In order to evaluate the quality of the proposed solution, a lower bound on the cycle time is also provided in this paper. We find that the downhill permutation achieves optimal solutions for practically relevant problem instances of robotic cells having one processing unit at each station.

The robotic cell having multiple identical processing units at stations has received scant attention in the literature. Perkinson et al. (1996) develop a set of theoretical models to characterize the effect of multiple processing units on the cycle time. They do not address the problem of cycle time minimization, which is considered in this paper. Herrmann et al. (2000) provide a network model and a simulation model for evaluating the impact of changes in processing times and process parameters on the performance of a robotic cell (also called cluster tool) having multiple processing units at stations. Wood (1996) derives a formula for the cycle time of such cells, but he also does not consider the problem of minimizing the cycle time. The main focus of this paper is to address the scheduling problems in such cells, specifically those that arise in real industrial automated setups, with the objective of cycle time minimization. Such setups are designed and sold by FSI.

The remainder of this paper is organized as follows. Section 2 describes three different types of robotic cells and the scheduling procedure currently being used at FSI. Notations are given in Section 3. In Section 4, we describe the calculation of cycle times for all three different types of robotic cells. Lower bounds on cycle times are derived in Section 5. The development of metaheuristic methods are described in Section 6. Section 7 summarizes the results of computational experiments and provides a brief overview of the implementation. Section 8 concludes the study.

2. Types of robotic cells

Currently, there are three different types of robotic cells that FSI International Inc. designs and manufactures, as described below:

1. SURC, the Single Unit Robotic Cell: this cell has a single processing unit at each processing station. In it, a robot, which is at the center of the cell, performs all material handling activities. A typical cell arrangement is shown in Fig. 1. For SURC, Sethi et al. (1992) define one-unit cycles, which are described in Section 4.1.

2. MURC, the Multiple Unit Robotic Cell: In such cells, at least one processing station has multiple identical processing units. If some of the stations have high processing times, then using multiple processing units is a very useful way of achieving the throughput goal. In view of developing a cyclic solution here, we define a class of robot move cycles called the Least Common Multiple (LCM)-unit cycles. Section 4.2 provides details on these cycles. In practice, the number of identical processing units at a station varies from one to four.

3. LMURC, the Linked Multiple Unit Robotic Cell: this cell has multiple identical processing units at some stations with at least one pair of adjacent processing stations linked by a local material handling device. Two stations [S.sub.i] and [S.sub.i+1] are called a linked pair if a local material handling device transfers the wafer from station [S.sub.i] to [S.sub.i+1]. In this case, the robot is not required in the transfer of the processed wafer from [S.sub.i] to [S.sub.i+1]. If two stations are linked in this way, they have an equal number of processing units. That is, each processing unit of the first station in the pair is linked to the corresponding processing unit of the second station in the pair. LMURC is useful when the cycle time is constrained by the robot's ability. In this case, it is advisable to reduce the workload on the robot by providing linked stations. In the robotic cells studied, if stations [S.sub.i] and [S.sub.i+1] are linked, then stations [S.sub.i+1] and [S.sub.i+2] (also [S.sub.i-1] and [S.sub.i]) are not linked. In other words, no station can be part of two linked pairs. This restriction is imposed due to physical locations of different stations.

FSI currently uses a heuristic dispatching rule called the Longest Waiting Pair (LWP) to schedule the robot activities within the cell. The idea behind the LWP rule may be stated as follows. In order to decide the next robot move during processing, the rule tracks: (i) the wafers that are completed at processing stations and waiting to be moved; and (ii) the empty stations waiting to receive wafers. The wafer and station combination that has the largest total waiting period is chosen by the robot to perform its next activity. Any tie is broken arbitrarily.

For example, consider a four-station robotic cell where the wafer has to be processed on stations in this order: [S.sub.1], [S.sub.2], [S.sub.3] and [S.sub.4]. Each station has only one processing unit. Let [a.sub.i] be the waiting time of a wafer at station [S.sub.i] after the completion of its processing. Let [b.sub.i] be the waiting time of station [S.sub.i] after the wafer is unloaded from it. At a given moment, a wafer at station [S.sub.1] is completed with a waiting time of [a.sub.1] = 4 seconds, the station [S.sub.2] is empty with a waiting time of [b.sub.2] = 8 seconds, a wafer at station [S.sub.3] is completed with [a.sub.3] = 3 seconds and the station [S.sub.4] is empty with [b.sub.4] = 10 seconds. For the next move, the robot has two options in this case. The robot can either unload a wafer from [S.sub.1] and load it onto [S.sub.2] or unload a wafer from [S.sub.3] and load it onto [S.sub.4]. The total waiting period for the [S.sub.1]-[S.sub.2] combination is 12 seconds ([a.sub.1] + [b.sub.2] = 4 + 8) and for the [S.sub.3]-[S.sub.4] combination it is 13 seconds ([a.sub.3] + [b.sub.4] = 3 + 10). Thus, LWP will choose the [S.sub.3]-[S.sub.4] combination since ([a.sub.3] + [b.sub.4]) is the longest waiting time. In other words, the robot will unload a wafer from [S.sub.3] and load it onto [S.sub.4].

3. Notation

We now present the notation used to describe the robotic cell scheduling problems.

[S.sub.1],..., [S.sub.m] = Processing stations of the robotic cell, where the indices are in the same order as the processing sequence of wafers. Here, stations [S.sub.i] and [S.sub.i+1] are called adjacent stations.

I = Input tray. Let us consider I to be the station [S.sub.0].

O = Output tray. Let us consider O to be the station [S.sub.m+1].

[p.sub.i] = Processing time of a wafer at station [S.sub.i], i = 1, 2,..., m.

[l.sub.i] = Time taken by the robot to load a wafer onto station [S.sub.i], i = 1, 2,..., m.

[l.sub.m+1] = Time taken by the robot to drop a wafer at O.

[u.sub.0] = Time taken by the robot to pick up a wafer at I.

[u.sub.i] = Time taken by the robot to unload a wafer from station [S.sub.i], i = 1, 2,..., m.

[S.sub.i.sup.-] = Robot's activity of loading a wafer on to station [S.sub.i] as well as the moment when the wafer is just loaded at [S.sub.i], i = 1, 2,..., m.

[S.sub.m+1.sup.-] = Robot's activity of dropping a wafer at O and the corresponding moment as above.

[S.sub.i.sup.+] = Robot's activity of unloading a processed wafer from station [S.sub.i] and the corresponding moment when the wafer is just unloaded from [S.sub.i], i = 1,..., m.

[S.sub.0.sup.+] = Robot's activity of picking up a wafer at I and the corresponding moment as above.

E = ([[chi].sub.1],..., [[chi].sub.m], [S.sub.h.sup.j]) = Current state of the system, where [[chi].sub.i] = [phi] (respectively, [OMEGA) if station [S.sub.i] is free (respectively, occupied by a wafer). The robot has just loaded (respectively, unloaded) station [S.sub.h] if j = -(respectively, +), for 0 [less than or equal to] h [less than or equal] m + 1.

[w.sub.i] = Waiting time of the robot before unloading a wafer at station [S.sub.i], i = 1,..., m.

t-[[t.sub.i,j]][.sub.(m+2)X(m+2)] = Robot travel time matrix when the robot is moving with a wafer, where the robot travel time from [S.sub.i] to [S.sub.j] in this case is denoted by [t.sub.i,j], i = 0, 1,..., m, m + 1 and j = 0, 1,..., m, m + 1.

t'-[[t'.sub.i,j]][.sub.(m+2)X(m+2)] = Robot travel time matrix when the robot is moving without a wafer, where [t'.sub.i,j] denotes the robot travel time between stations [S.sub.i] and [S.sub.j] without carrying the wafer.

[v.sub.i] = Number of multiple identical processing units at station [S.sub.i] in MURC and LMURC, i = 1, 2,..., m.

[S.sub.i,[j.sub.i]] = ([j.sub.i])th unit at station [S.sub.i] in MURC and LMURC, i = 1,..., m and [j.sub.i] = 1,..., [v.sub.i].

4. Calculation of cycle times

In this section, we introduce some basic concepts and notions to describe the cyclic scheduling of operations in a robotic cell. A robot in a robotic cell performs three kinds of operations: (i) loading parts onto stations; (ii) unloading parts from stations; and (iii) transporting parts between stations. We describe a robot schedule in terms of load/unload station activities. Obviously, such a sequence would uniquely define the travel of the robot between stations (i.e., from/to which station the robot travels, and when).

4.1. One-unit cycles for SURC

In a one-unit cycle, the cell producing a single wafer type returns to the same state after each wafer is produced. Thus, in such a cycle, all the loading activities, [S.sub.i.sup.-], i = 1, 2,..., m + 1, and all the unloading activities [S.sub.i.sup.+], i = 0, 1,..., m, must be carried out exactly once. Since the unloading activity of a station [S.sub.i.sup.+] implies the loading activity of the subsequent station [S.sub.i+1.sup.-], we need only m + 1 activities, [S.sub.i.sup.-], i = 1,..., m + 1 to define a one-unit cycle. [S.sub.m+1.sup.-] is a convenient point to begin the cycle. Since [S.sub.m+1.sup.-] means [S.sub.m.sup.+], we consider the following m + 1 basic activities: [S.sub.m.sup.+], [S.sub.1.sup.-], [S.sub.2.sup.-],..., [S.sub.m.sup.-]. Any two consecutive activities uniquely determine the robot moves between those activities. Therefore, a cycle can be uniquely described by a permutation of m activities: [S.sub.1.sup.-], [S.sub.2.sup.-],..., [S.sub.m.sup.-]. In an optimal cycle, we require that the robot move path is as short as possible between activities. The following are the one-unit robot move cycles for m = 2:

[C.sub.1,2]: {[S.sub.2.sup.+], [S.sub.1.sup.-], [S.sub.2.sup.-], [S.sub.2.sup.+]}, [C.sub.2,2]: {[S.sub.2.sup.+], [S.sub.2.sup.-], [S.sub.1.sup.-], [S.sub.2.sup.+]}.

We briefly interpret the cycle [C.sub.2,2] by following the sequence of basic activities in [C.sub.2,2] starting with an occurrence of [S.sub.2.sup.+]. It will become clear shortly that the starting initial state of this cycle is as follows: the robot has just unloaded wafer [P.sub.1] from [S.sub.2] and [S.sub.1] is occupied by wafer [P.sub.2]. The robot move sequence includes the following activities: the robot moves to O, drops [P.sub.1] at O, moves to [S.sub.1], if necessary waits until [P.sub.2] has been processed, unloads [P.sub.2] from [S.sub.1], moves to [S.sub.2], loads [P.sub.2] onto [S.sub.2], moves to I, picks up wafer [P.sub.3] at I, moves to [S.sub.1], loads [P.sub.3] onto [S.sub.1], moves to [S.sub.2], if necessary waits until [P.sub.2] has been processed, unloads [P.sub.2] from [S.sub.2]. Similarly, there are six one-unit cycles for m = 3 and 24 one-unit cycles for m = 4. Note that the one-unit cycle defined by {[S.sub.m.sup.+], [S.sub.m.sup.-], [S.sub.m-1.sup.-],..., [S.sub.2.sup.-], [S.sub.1.sup.-], [S.sub.m.sup.+]} is called the downhill permutation (or reverse permutation) since the machine loading activities are sequenced in the decreasing order of machine indices (Crama et al., 2000; Dawande et al., 2004).

In order to derive the cycle time for a given cycle in a cyclic schedule, we define the state of the system by E = ([[chi].sub.1],..., [[chi].sub.m], [S.sub.h.sup.j]), as described in Section 3. This state space representation is sufficient for deriving cycle times. Now we consider a cell having two stations and show how the cycle time can be evaluated for two possible cyclic schedules in this case: [C.sub.1,2] and [C.sub.2,2].

Starting from the initial state E = ([phi], [phi], [S.sub.2.sup.+]), where the robot has just unloaded a wafer from [S.sub.2] and [S.sub.1] is empty, one-unit cycle [C.sub.1,2] includes the following robot activities: moves to O([t.sub.2,3]), drops the wafer ([l.sub.3]), moves to I([t'.sub.3,0]), picks up a wafer (say P) ([u.sub.0]), moves to [S.sub.1]([t.sub.0,1]), loads ([l.sub.1]), waits until P has been processed at [S.sub.1]([p.sub.1]), unloads ([u.sub.1]), moves to [S.sub.2]([t.sub.1,2]), loads ([l.sub.2]), waits until P has been processed ([p.sub.2]), unloads ([u.sub.2]). Therefore, the cycle time [T.sub.1,2] for [C.sub.1,2] can be written as:

[T.sub.1,2] = [t.sub.2,3] + [l.sub.3] + [t'.sub.3,0] + [u.sub.0] + [t.sub.0,1] + [l.sub.1] + [p.sub.1] + [u.sub.1] + [t.sub.1,2] + [l.sub.2] + [p.sub.2] + [u.sub.2].

Starting from the initial state E = ([OMEGA], [phi], [S.sub.2.sup.+]), where the robot has just unloaded a wafer from [S.sub.2] and [S.sub.1] has a wafer, one-unit cycle [C.sub.2,2] includes the following robot activities: moves to O([t.sub.2,3]), drops the wafer ([l.sub.3]), moves to [S.sub.1]([t'.sub.3,1]), if necessary waits for the wafer ([w.sub.1]), unloads ([u.sub.1]), moves to [S.sub.2]([t.sub.1,2]), loads ([l.sub.2]), moves to I([t'.sub.2,0]), picks up a wafer ([u.sub.0]), moves to [S.sub.1]([t.sub.0,1]), loads ([l.sub.1]), moves to [S.sub.2]([t'.sub.1,2]), if necessary waits for the wafer ([w.sub.2]) unloads ([u.sub.2]). Hence, the cycle time [T.sub.2,2] for [C.sub.2,2] is given as:

[T.sub.2,2] = [t.sub.2,3] + [l.sub.3] + [t'.sub.3,1] + [w.sub.1] + [u.sub.1] + [t.sub.1,2] + [l.sub.2] + [t'.sub.2,0] + [u.sub.0] + [t.sub.0,1] + [l.sub.1] + [t'.sub.1,2] + [w.sub.2] + [u.sub.2].

The robot has to wait for the wafer if the wafer is still being processed when the robot comes to unload it. Therefore, a solution ([T.sub.2,2], [w.sub.1], [w.sub.2]) to the following problem will define a state condition of SURC operating under cycle [C.sub.2,2] for the given cell data:

[T.sub.2,2] = [t.sub.2,3] + [l.sub.3] + [t'.sub.3,1] + [w.sub.1] + [u.sub.1] + [t.sub.1,2] + [l.sub.2] + [t'.sub.2,0] + [u.sub.0] + [t.sub.0,1] + [l.sub.1] + [t'.sub.1,2] + [w.sub.2] + [u.sub.2],

[w.sub.1] = max{0, [p.sub.1] - [t'.sub.1,2] - [w.sub.2] - [u.sub.2] - [t.sub.2,3] - [l.sub.3] - [t'.sub.3,1]} and

[w.sub.2] = max{0, [p.sub.2] - [t'.sub.2,0] - [u.sub.0] - [t.sub.0,1] - [l.sub.1] - [t'.sub.1,2]}.

In this case, finding a solution ([T.sub.2,2], [w.sub.1], [w.sub.2]) is straightforward. A solution for [w.sub.2] can be obtained from the equation for [w.sub.2]. Then by substituting [w.sub.2] into the equation for [w.sub.1], we obtain the solution for [w.sub.1]. Finally, [T.sub.2,2] could be determined by substituting both [w.sub.1] and [w.sub.2] into the cycle time formula for [T.sub.2,2]. Cycle time calculation is not always so straightforward. A linear programming method can be used to efficiently find a steady-state solution for any given one-unit cycle (Kumar, 2001). Readers can also refer to Crama et al. (2000) who provide efficient algorithms for cycle time computation in various robotic cell configurations.

4.2. LCM-unit cycles for MURC

Consider a manufacturing process which consists of three sequential operations on three different stations [S.sub.1], [S.sub.2] and [S.sub.3]. A cell consists of two identical processing units at station [S.sub.2] (called [S.sub.21] and [S.sub.22]) and one unit each at [S.sub.1] and [S.sub.3]. Since we have a total of four processing units, there are 4! = 24 one-unit cycles. However, some cycles are not feasible. Consider, for example, cycle {[S.sub.3.sup.+], [S.sub.2,1.sup.-], [S.sub.2,2.sup.-], [S.sub.1.sup.-], [S.sub.3.sup.-], [S.sub.3.sup.+]} is not feasible as consecutive loading of wafers on the second station processing units [S.sub.2,1] and [S.sub.2,2] is not possible. In order to avoid infeasible cycles, we consider a class of robot move cycles called the LCM-unit cycles, where LCM is set equal to the least common multiple of [v.sub.i], i = 1,..., m. Although [lambda]-unit cycles (where [lambda] is the minimum number of units at any station) have been studied by Herrmann (2003), our work is the first of the kind that proposes LCM-unit cycles.

In our approach to construct LCM-unit cycles, we concern ourselves primarily with the robot move sequences associated with one-unit cycles. A one-unit cycle can be specified by a loading sequence. For example, consider a one-unit cycle [C.sub.1,4]: {[S.sub.4.sup.+], [S.sub.3.sup.-], [S.sub.1.sup.-], [S.sub.4.sup.-], [S.sub.2.sup.-], [S.sub.4.sup.+]}, where m = 4. Since this loading sequence uniquely defines a robot move sequence, we shall also use [C.sub.1,4] to denote the robot move sequence associated with the cycle.

The LCM-unit cycle obtained from the one-unit robot move sequence [C.sub.x,y] is denoted by [[GAMMA].sub.x,y]. An LCM-unit cycle is a concatenation of n nearly identical one-unit robot move sequences in the following manner, where n is the LCM of [v.sub.i], i = 1,..., m. [[GAMMA].sub.x,y] is a robot move sequence where sequence [C.sub.x,y] repeats itself successively exactly n times. Consider an example with m = 4, [v.sub.1] = 3, [v.sub.2] = 2, [v.sub.3] = 1 and [v.sub.4] = 2. Thus, the LCM of [v.sub.1], [v.sub.2], [v.sub.3] and [v.sub.4] is six, i.e., n = 6. Now we provide the LCM-unit cycle corresponding to one-unit cycle [C.sub.1,4]: {[S.sub.4.sup.+], [S.sub.3.sup.-], [S.sub.1.sup.-], [S.sub.4.sup.-], [S.sub.2.sup.-], [S.sub.4.sup.+]}. From this, we can construct the associated LCM-unit cycle [[GAMMA].sub.1,4] as follows: [[GAMMA].sub.1,4] = {[C.sub.1,4.sup.1], [C.sub.1,4.sup.2], [C.sub.1,4.sup.3], [C.sub.1,4.sup.4], [C.sub.1,4.sup.5], [C.sub.1,4.sup.6]}, where:

[C.sub.1,4.sup.1] = {[S.sub.4,1.sup.+], [S.sub.3,1.sup.-], [S.sub.1,1.sup.-], [S.sub.4,1.sup.-], [S.sub.2,1.sup.-]},

[C.sub.1,4.sup.2] = {[S.sub.4,2.sup.+], [S.sub.3,1.sup.-], [S.sub.1,2.sup.-], [S.sub.4,2.sup.-], [S.sub.2,2.sup.-]},

[C.sub.1,4.sup.3] = {[S.sub.4,1.sup.+], [S.sub.3,1.sup.-], [S.sub.1,3.sup.-], [S.sub.4,1.sup.-], [S.sub.2,1.sup.-]},

[C.sub.1,4.sup.4] = {[S.sub.4,2.sup.+], [S.sub.3,1.sup.-], [S.sub.1,1.sup.-], [S.sub.4,2.sup.-], [S.sub.2,2.sup.-]},

[C.sub.1,4.sup.5] = {[S.sub.4,1.sup.+], [S.sub.3,1.sup.-], [S.sub.1,2.sup.-], [S.sub.4,1.sup.-], [S.sub.2,1.sup.-]},

[C.sub.1,4.sup.6] = {[S.sub.4,2.sup.+], [S.sub.3,1.sup.-], [S.sub.1,3.sup.-], [S.sub.4,2.sup.-], [S.sub.2,2.sup.-]}.

In order to precisely define an LCM-unit cycle, we need to specify the processing unit from which the robot unloads the wafer. If a processing station has multiple processing units, then the earliest loaded processing unit is unloaded at that station. For example, [S.sub.3,1.sup.-] in [C.sub.1,4.sup.4] implies that the robot loads the processing unit 1 at [S.sub.3]. To perform this activity, the robot unloads the wafer from the earliest loaded processing unit at [S.sub.2]. In this case, processing unit 2 is the earliest loaded processing unit at [S.sub.2], because processing unit 1 is loaded (i.e., [S.sub.2,1.sup.-]) in [C.sub.1,4.sup.3] and processing unit 2 is loaded (i.e., [S.sub.2,2.sup.-]) in [C.sub.1,4.sup.2].

Definition 1. LCM cycles have the following characteristics:

* The number of parts produced in one cycle is n, where n = LCM[[v.sub.1], [v.sub.2],..., [v.sub.m]].

* For each station [S.sub.i], the loading of its processing units is done in an increasing order, beginning with [S.sub.i,1.sup.-], then [S.sub.i,2.sup.-],..., [S.sub.i,[v.sub.i].sup.-].

* From the moment of unloading a processing unit [S.sub.i,j.sup.+], the loading activity of that processing unit [S.sub.i,j.sup.-] will occur within the next m loading activities in the cycle.

* When unloading a station, the earliest loaded processing unit at that station will be unloaded.

Cycle time derivation for MURC is similar to SURC, with the only difference being that the former uses LCM-unit cycles and the latter uses one-unit cycles. Here, the per unit cycle time is equal to (Cycle Time of LCM)/(LCM).

4.3. LCM-unit cycles for LMURC

Consider an example of m = 4 with one processing unit at each station, and stations [S.sub.2] and [S.sub.3] are linked. In this case, the material handling between stations [S.sub.2] and [S.sub.3] is done by an integrated material handling device, and the robot is not required for this operation. Therefore, the loading operation on the second station of the linked pair (i.e., [S.sub.3.sup.-]) does not appear in the robot move cycle. Hence, in this case there are six one-unit cycles, as shown below:

[C'.sub.1,4]: {[S.sub.4.sup.+], [S.sub.1.sup.-], [S.sub.2.sup.-], [S.sub.4.sup.-], [S.sub.4.sup.+]}, [C'.sub.2,4]: {[S.sub.4.sup.+], [S.sub.1.sup.-], [S.sub.4.sup.-], [S.sub.2.sup.-], [S.sub.4.sup.+]},

[C'.sub.3,4]: {[S.sub.4.sup.+], [S.sub.4.sup.-], [S.sub.1.sup.-], [S.sub.2.sup.-], [S.sub.4.sup.+]}, [C'.sub.4,4]: {[S.sub.4.sup.+], [S.sub.2.sup.-], [S.sub.4.sup.-], [S.sub.1.sup.-], [S.sub.4.sup.+]},

[C'.sub.5,4]: {[S.sub.4.sup.+], [S.sub.2.sup.-], [S.sub.1.sup.-], [S.sub.4.sup.-], [S.sub.4.sup.+]}, [C'.sub.6,4]: {[S.sub.4.sup.+], [S.sub.4.sup.-], [S.sub.2.sup.-], [S.sub.1.sup.-], [S.sub.4.sup.+]}.

If some of these stations have multiple identical processing units, then an LCM-unit cycle can be constructed similar to the one shown in previous section. Cycle time derivation for LMURC is slightly different from that of SURC and MURC, because the material handing between linked station pairs is not done by the robot. In the case of a linked stations pair, the robot loads the wafer at the first station of the pair and unloads from the second station. A local material handling device transfers the wafer from the first station to the second station. The robot may have to wait before loading a wafer onto the first station until the previously loaded wafer is transferred from the first station to the second station. Therefore, we define [w'.sub.i] as the waiting time of the robot before loading a wafer at [S.sub.i], where [S.sub.i] is the first station of a linked pair. In addition, [y.sub.i,i+1] denotes the wafer move time between linked stations [S.sub.i] and [S.sub.i+1]. Let [z.sub.i] denote the waiting time of the wafer after the processing is completed at the first station of the linked pair [S.sub.i] before it is transferred to [S.sub.i+1].

Let us again consider the same example of m = 4 with one processing unit at each station, and stations [S.sub.2] and [S.sub.3] are linked. Starting from the initial state where the robot has just unloaded a wafer from [S.sub.4], robot move cycle [C'.sub.4,4]: {[S.sub.4.sup.+], [S.sub.2.sup.-], [S.sub.4.sup.-], [S.sub.1.sup.-], [S.sub.4.sup.+]} includes the following robot activities: moves to O ([t.sub.4,5]), drops the wafer ([l.sub.5]), moves to [S.sub.1] ([t'.sub.5,1]), if necessary waits for the wafer to be processed on [S.sub.1] ([w.sub.1]), unloads the wafer ([u.sub.1]), moves to [S.sub.2] (t.sub.1,2]), if necessary waits at [S.sub.2] before loading the wafer ([w'.sub.2]), loads ([l.sub.2]), moves to [S.sub.3] ([t'.sub.2,3]), if necessary waits for the wafer ([w.sub.3]), unloads ([u.sub.3]), moves to [S.sub.4] ([t.sub.3,4]) loads ([l.sub.4]), moves to I ([t'.sub.4,0]), picks up a wafer ([u.sub.0]), moves to [S.sub.1] ([t.sub.0,1]), loads ([l.sub.1]), moves to [S.sub.4] ([t'.sub.1,4]), if necessary waits for the wafer ([w.sub.4]), unloads ([u.sub.4]). Therefore, the cycle time is:

T = [t.sub.4,5] + [l.sub.5] + [t'.sub.5,1] + [w.sub.1] + [u.sub.1] + [t.sub.1,2] + [w'.sub.2] + [l.sub.2] + [t'.sub.2,3] + [w.sub.3] + [u.sub.3] + [t.sub.3,4] + [l.sub.4] + [t'.sub.4,0] + [u.sub.0] + [t.sub.0.1] + [l.sub.1] + [t'.sub.1,4] + [w.sub.4] + [u.sub.4].

When the robot comes to unload the wafer at a station, it has to wait if the wafer is still being processed. Hence,

[w.sub.1] = max{0, [p.sub.1] - [t'.sub.1,4] - [w.sub.4] - [u.sub.4] - [t.sub.4,5] - [l.sub.5] - [t'.sub.5,1]} and

[w.sub.4] = max{0,[p.sub.4] - [t'.sub.4,0] - [u.sub.0] - [t.sub.0,1] - [l.sub.1] - [t'.sub.1,4]}.

Note that [w.sub.2] does not appear in the cycle time equation because the robot does not transfer the wafer between [S.sub.2] and [S.sub.3]. Instead, [w'.sub.2] appears in the cycle time equation, which is the robot's waiting time before loading the wafer onto [S.sub.2].

In order to find equations for [w'.sub.2] and [w.sub.3], we need to define the state of the linked pair when the robot moves to [S.sub.2] to load a wafer onto it. At that time, both the stations of the linked pair cannot have a wafer. Therefore, the possible states at that time are: (i) a wafer somewhere at the linked stations pair; or (ii) no wafer at the linked stations pair. If the linked pair is in the first state, we say that it is in the loaded state, and if it is in the second state, it is said to be in the free state.

We first find the equations for [w'.sub.2] and [w.sub.3] when the linked pair is in the loaded state. Recall that [z.sub.2] denotes the time the wafer waits on [S.sub.2] after being processed before it is transferred to [S.sub.3] through the integrated material handling device. The robot can load the wafer onto [S.sub.2] only if the previously processed wafer on [S.sub.2] has been transferred to [S.sub.3]. Note that the previous wafer was loaded onto [S.sub.2] in the previous cycle. Therefore, [w'.sub.2] = max{0, [p.sub.2] + [z.sub.2] - [t'.sub.2,3] - [w.sub.3] - [u.sub.3] - [t.sub.3,4] - [l.sub.4] - [t'.sub.4,0] - [u.sub.0] - [t.sub.0,1] - [l.sub.1] - [t'.sub.1,4] - [w.sub.4] - [u.sub.4] - [t.sub.4,5] - [l.sub.5] - [t'.sub.5,1] - [w.sub.1] - [u.sub.1] - [t.sub.1,2]}.

In this case, when the robot comes to load a wafer onto [S.sub.2], there is always one wafer somewhere in the linked pair. Therefore, any wafer loaded onto [S.sub.2] is unloaded from [S.sub.3] only after another wafer has been loaded onto [S.sub.2]. Hence, [w.sub.3] = max{0, [p.sub.2] + [z.sub.2] + [y.sub.2,3] + [p.sub.3] - T - [t'.sub.2,3]}. After substituting the value of T in this equation and simplifying, we get: 2[w.sub.3] = max{0,[p.sub.2] + [z.sub.2] + [y.sub.2,3] + [p.sub.3] - [t.sub.4,5] - [l.sub.5] - [t'.sub.5,1] - [w.sub.1] - [u.sub.1] - [t.sub.1,2] - [w'.sub.2] - [l.sub.2] - 2[t'.sub.2,3] - [u.sub.3] - [t.sub.3,4] - [l.sub.4] - [t'.sub.4,0] - [u.sub.0] - [t.sub.0,1] - [l.sub.1] - [t'.sub.1,4] - [w.sub.4] - [u.sub.4]}.

After loading a new wafer (say [P.sub.2]) onto [S.sub.2], the robot moves to [S.sub.3]. If the previously loaded wafer (say [P.sub.1]) is not processed on [S.sub.3], the robot waits there and then unloads [P.sub.1]. Therefore, the processed wafer [P.sub.2] on [S.sub.2] has to wait ([z.sub.2]) until the robot has unloaded the previously loaded wafer [P.sub.1] from [S.sub.3]. Hence, [z.sub.2] = max{0, [t'.sub.2,3] + [w.sub.3] + [u.sub.3] - [p.sub.2] - [y.sub.2,3]}. A steady-state solution can now be found using the following Linear Program (LP) called LP (load) as follows:

Min T = [t.sub.4,5] + [l.sub.5] + [t'.sub.5,1] + [w.sub.1] + [u.sub.1] + [t.sub.1,2] + [w'.sub.2] + [l.sub.2] + [t'.sub.2,3] + [w.sub.3] + [u.sub.3] + [t.sub.3,4] + [l.sub.4] + [t'.sub.4,0] + [u.sub.0] + [t.sub.0,1] + [l.sub.1] + [t'.sub.1,4] + [w.sub.4] + [u.sub.4],

subject to

[w.sub.1] [greater than or equal to] [p.sub.1] - [t'.sub.1,4] - [w.sub.4] - [u.sub.4] - [t.sub.4,5] - [l.sub.5] - [t'.sub.5,1],

[w.sub.4] [greater than or equal to] [p.sub.4] - [t'.sub.4,0] - [u.sub.0] - [t.sub.0,1] - [l.sub.1] - [t'.sub.1,4],

[w'.sub.2] [greater than or equal to] [p.sub.2] + [z.sub.2] - [t'.sub.2,3] - [w.sub.3] - [u.sub.3] - [t.sub.3,4] - [l.sub.4] - [t'.sub.4,0] - [u.sub.0] - [t.sub.0,1] - [l.sub.1] - [t'.sub.1,4] - [w.sub.4] - [u.sub.4] - [t.sub.4,5] - [l.sub.5] - [t'.sub.5,1] - [w.sub.1] - [u.sub.1] - [t.sub.1,2],

2[w.sub.3] [greater than or equal to] [p.sub.2] + [z.sub.2] + [y.sub.2,3] + [p.sub.3] - [t.sub.4,5] - [l.sub.5] - [t'.sub.5,1] - [w.sub.1] - [u.sub.1] - [t.sub.1,2] - [w'.sub.2] - [l.sub.2] - 2[t'.sub.2.3] - [u.sub.3] - [t.sub.3,4] - [l.sub.4] - [t'.sub.4,0] - [u.sub.0] - [t.sub.0,1] - [l.sub.1] - [t'.sub.1,4] - [w.sub.4] - [u.sub.4],

[z.sub.2] [greater than or equal to] [t'.sub.2,3] + [w.sub.3] + [u.sub.3] - [p.sub.2] - [y.sub.2,3], [z.sub.2], [w.sub.1], [w'.sub.2], [w.sub.3], [w.sub.4] [greater than or equal to] 0.

We call the LP formulation for the free state linked pair LP (free). In this case, the equations for T, [w.sub.1] and [w.sub.4] remain the same as LP (load). The other equations are:

[w'.sub.2] = [z.sub.2] = 0 and [w.sub.3] [greater than or equal to] [p.sub.2] + [y.sub.2,3] + [p.sub.3] - [t'.sub.2,3].

Let us now consider a general robotic cell having m stations and k linked pairs. Given a robot move cycle and linked pairs state for this cell, the cycle time can be easily calculated by constructing and solving an LP similar to that of LP (load) or LP (free). This LP will have [w'.sub.i] and [z.sub.i] constraints corresponding to each [S.sub.i] - [S.sub.i+1] linked pair, where i = 1,..., k. Expressions of these constraints will be similar to those in the above example. Other constraints for non-linked stations and the objective function can also be derived similarly.

5. Lower bounds on cycle times

In order to evaluate the quality of the solutions obtained by the metaheuristic algorithms in the next section, we develop the following lower bounds (LBs) on the cycle times for three robotic cell models under investigation.

5.1. LB for SURC

The following theorem establishes a LB on the cycle time for SURC.

Theorem 1. For any one-unit cycle in SURC, the per unit cycle time T satisfies:

T [greater than or equal to] max{[m.summation over (i=0)]([u.sub.i] + [l.sub.i+1]) + [m.summation over (i=0)][t.sub.i,i+1][m.summation over (i=1)]min{[p.sub.i], [min.[j[not equal to]i, j[less than or equal to]m]]([t'.sub.i,j])} + [min.[j[less than or equal to]m]]{[t'.sub.m+1,j]}, [max.[1[less than or equal to]i[less than or equal to]m]]{[p.sub.i] + [u.sub.i] + [t.sub.i,i+1] + [l.sub.i+1] + [t'.sub.i+1,i-1] + [u.sub.i-1] + [t.sub.i-1,i] + [l.sub.i]}}.

Proof. Let us begin with the first argument in this theorem. The robot must load and unload all the stations. In addition, the robot must pick the wafer at I and must drop the wafer at O. The total time for these activities is [[summation].sub.i=0.sup.m] ([u.sub.i] + [l.sub.i+1]). In order to load [S.sub.i], the robot must travel from [S.sub.i-1] to [S.sub.i] with the wafer and also must travel to O in order to drop the wafer. [[summation].sub.i=0.sup.m] [t.sub.i.i+1] is the total time required for these activities. Every time the station [S.sub.i], i = 1,..., m, is loaded, there will be time taken either for processing ([p.sub.i]) or for a robot move without the wafer (which takes a time of at least [min.sub.j[not equal to]i,j[less than or equal to]m] {[t'.sub.i.j]}). After dropping a wafer at O, the robot must travel from O to some station [S.sub.j] without the wafer. Mi[n.sub.j[less than or equal to]m] {[t'.sub.m+1,j]} is the minimum time required for this activity.

For the second argument, observe that the sequence of actions between the start of [S.sub.i]'s unloading and the completion of its next loading must include the following activities: unload [S.sub.i] (in a time of [u.sub.i]), travel from [S.sub.i] to [S.sub.i+1] with wafer (in a time of [t.sub.i,i+1]), load [S.sub.i+1] (in a time of [l.sub.i+1], travel by some route from [S.sub.i+1] to [S.sub.i-1] without the wafer (the minimum possible time is [t'.sub.i+1,i-1]), unload [S.sub.i-1] (in a time of [u.sub.i-1]), travel from [S.sub.i-1] to [S.sub.i] with wafer (in a time of [t.sub.i-1,i]), and load [S.sub.i] (in a time of [l.sub.i]). Adding all these terms, the minimum time between the start of [S.sub.i]'s unloading and the completion of its next loading can be written as [u.sub.i] + [t.sub.i,i+1] + [l.sub.i+1] + [t'.sub.i+1,i-1] + [u.sub.i-1] + [t.sub.i-1,i] + [l.sub.i]. Thus, the minimum time between each loading of [S.sub.i] is [p.sub.i] + [u.sub.i] + [t.sub.i,i+1] + [l.sub.i+1] + [t'.sub.i+1,i-1] + [u.sub.i-1] + [t.sub.i-1,i] + [l.sub.i]. [black square]

5.2. LB for MURC

For MURC, let [t.sub.murc] = [[t.sub.[i.sub.a],[j.sub.b]]][.sub.([[summation].sub.i=1.sup.m][v.sub.1]+2)X([[summation].sub.i=1.sup.m][v.sub.i]+2)] be the robot travel time matrix when the robot is moving with a wafer, where the robot travel time from the ath unit of [S.sub.i] to the bth unit of [S.sub.j] is denoted by [t.sub.[i.sub.a],[j.sub.b]], i = 0, 1,..., m, m + 1, j = 0, 1,..., m, m+1, a = 1, 2,..., [v.sub.i], and b = 1, 2,..., [v.sub.j]. Let us define [t.sub.i,j.sup.min] = [min.sub.a,b]([t.sub.[i.sub.a],[j.sub.b]]), [t'.sub.i,j.sup.min] is defined similarly when the robot is moving without any wafer.

Theorem 2. For any LCM-unit cycle in MURC, the per unit cycle time [T.sub.LCM]/LCM satisfies:

[T.sub.LCM]/[LCM] [greater than or equal to] max{[m.summation over (i=0)]([u.sub.i] + [l.sub.i+1]) + [m.summation over (i=0)][t.sub.i,i+1.sup.min] + [m.summation over (i=1)] min{[p.sub.i], [min.[j[not equal to]i,j[less than or equal to]m]]([t'.sub.i,j.sup.min])} + [min.[j[less than or equal to]m]] {[t'.sub.m+1,j.sup.min]},

[max.[1[less than or equal to]i[less than or equal to]m]]{([p.sub.i] + [u.sub.i] + [t.sub.i,i+1.sup.min] + [l.sub.i+1] + [t'.sub.i+1,i-1.sup.min] + [u.sub.i-1] + [t.sub.i-1,i.sup.min] + [l.sub.i])/[v.sub.i]}},

where [T.sub.LCM] is the cycle time of the LCM-unit cycle.

Proof. The proof of first argument is similar to that in Theorem 1. For the second argument, observe that the sequence of actions between the start of the unloading of the ath unit of [S.sub.i] and the completion of its next loading must include the following activities: unload [S.sub.i] (in a time of [u.sub.i]), travel from [S.sub.i] to [S.sub.i+1] with a wafer (the minimum possible time is [t.sub.i,i+1.sup.min]), load [S.sub.i+1] (in a time of [l.sub.i+1]), travel by the some route from [S.sub.i+1] to [S.sub.i-1] without the wafer (the minium possible time is [t'.sub.i+1,i-1.sup.min]), unload [S.sub.i-1] (in a time of [u.sub.i-1]), travel from [S.sub.i-1] to [S.sub.i] with the wafer (the minimum possible time is [t.sub.i-1,i.sup.min], and load [S.sub.i] (in a time of [l.sub.i]). As a minimum, this time is [u.sub.i] + [t.sub.i,i+1.sup.min] + [l.sub.i+1] + [t'.sub.i+1,i-1.sup.min] + [u.sub.i-1] + [t.sub.i-1,i.sup.min] + [l.sub.i]. Thus, the minimum time between each loading of the ath unit of [S.sub.i] is [p.sub.i] + [u.sub.i] + [t.sub.i,i+1.sup.min] + [l.sub.i+1] + [t'.sub.i+1,i-1.sup.min] + [u.sub.i-1] + [t.sub.i-1,i.sup.min] + [l.sub.i]. It is easy to see that each unit of [S.sub.i] is loaded LCM/[v.sub.i] times in an LCM-unit cycle. Therefore, the second argument follows. [black square]

5.3. LB for LMURC

Let [t.sub.lmurc] = [t.sub.murc] = [[t.sub.[i.sub.a],[j.sub.b]][.sub.([summation].sub.i=1.sup.m][v.sub.i]+2)X([[summation].sub.i=1.sup.m][v.sub.i]+2)] (see previous section). Also, [t.sub.i,j.sup.min] and [t'.sub.i,j.sup.min] are defined similar to that in MURC. Let [S.sub.d] be the set of stations linked to their down-stream machines, [S.sub.u] be the set of stations linked to their upstream machines and [S.sub.w] be the set of stations not linked.

Theorem 3. For any LCM-unit cycle in LMURC, the per unit cycle time [T.sub.LCM]/LCM satisfies:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [T.sub.LCM] is the cycle time of LCM-unit cycle and

L[B.sub.i] = max{([p.sub.i] + [y.sub.i,i+1] + [p.sub.i+1] + [u.sub.i+1] + [t.sub.i+1,i+2.sup.min] + [l.sub.i+2] + [t'.sub.i+2,i-1.sup.min] + [u.sub.i-1] + [t.sub.i-1,i.sup.min] + [l.sub.i])/2, ([l.sub.i] + [p.sub.i]), ([p.sub.i+1] + [u.sub.i+1])}.

Proof. The proof of first argument is similar to that in Theorem 1. The proof of second argument which is derived for the set of stations [S.sub.w] is same as that in Theorem 2.

For the third argument (L[B.sub.i]/[v.sub.i]), let us consider two stations [S.sub.i] [member of] [S.sub.d] and [S.sub.i+1] [member of] [S.sub.u]. When the robot loads wafer on to the ath unit of [S.sub.i], the ath unit of [S.sub.i+1] may either be empty (i.e., in a free state) or have a wafer (i.e., in a loaded state). Note that the minimum time between the start of unloading of the ath unit of [S.sub.i+1] and the completion of next loading of the ath unit of [S.sub.i] is [u.sub.i+1] + [t.sub.i+1,i+2.sup.min] + [l.sub.i+2] + [t'.sub.i+2,i-1.sup.min] + [u.sub.i-1] + [t.sub.i-1,i.sup.min] + [l.sub.i], as shown in the proof of Theorem 2. During this time period, the linked pair is empty in the case of a free state. Since the total processing time at the linked pair is [p.sub.i] + [y.sub.i,i+1] + [p.sub.i+1], the minimum time between each unloading of the ath unit of [S.sub.i+1] in the free state is [p.sub.i] + [y.sub.i,i+1] + [p.sub.i+1] + [u.sub.i+1] + [t.sub.i+1,i+2.sup.min] + [l.sub.i+2] + [t'.sub.i+2,i-1.sup.min] + [u.sub.i-1] + [t.sub.i-1,i.sup.min] + [l.sub.i].

For the loaded state case, let us consider the steps of loading three consecutive wafers ([P.sub.1], [P.sub.2] and [P.sub.3]) onto the ath unit of [S.sub.i]. Here, the robot must load [P.sub.2] onto the ath unit of [S.sub.i] before unloading [P.sub.1] from the ath unit of [S.sub.i+1]. Therefore, after unloading [P.sub.1] from the ath unit of [S.sub.i+1], the next wafer to be loaded onto the ath unit of [S.sub.i] is [P.sub.3]. Hence, the minimum time between unloading of wafers [P.sub.1] and [P.sub.3] from the ath unit of [S.sub.i+1] is [p.sub.i] + [y.sub.i,i+1] + [p.sub.i+1] + [u.sub.i+1] + [t.sub.i+1,i+2.sup.min] + [l.sub.i+2] + [t'.sub.i+2,i-1.sup.min] + [u.sub.i-1] + [t.sub.i-1,i.sup.min] + [l.sub.i]. Therefore, the minimum time between each unloading of the ath unit of [S.sub.i+1] is ([p.sub.i] + [y.sub.i,i+1] + [p.sub.i+1] + [u.sub.i+1] + [t.sub.i+1,i+2.sup.min] + [l.sub.i+2] + [t'.sub.i+2,i-1.sup.min] + [u.sub.i-1] + [t.sub.i-1,i.sup.min] + [l.sub.i])/2.

The rest of the third argument is given as follows. Every wafer loaded onto [S.sub.i] requires at least [l.sub.i] + [p.sub.i] time on loading and processing. Every unloaded wafer from [S.sub.i+1] spends at least [p.sub.i+1] + [u.sub.i+1] time in processing and unloading. It is easy to see that each unit of [S.sub.i+1] is unloaded (and each unit of [S.sub.i] is loaded) LCM/[v.sub.i] times in an LCM-unit cycle. Hence, the third argument follows. [black square]

6. Genetic algorithms

Since the problem of finding an optimal one-unit cycle is NP-hard in the general robot travel time setting (Brauner et al., 2003), we develop a Genetic-Algorithm (GA)-based metaheuristic technique to seek an optimal or near-optimal solution. GAs have been successfully applied to many different scheduling problems. References on the application of GAs for scheduling and other operations research problems have been summarized in Reeves (1997). In view of the advances made in tackling scheduling problems using GAs, we develop a GA to schedule the robotic cell. GAs belong to the class of heuristic optimization techniques that utilize randomization as well as directed smart search to seek the global optima. The development of GAs was inspired by evolutionary processes through which life is believed to have evolved in to its present forms (Goldberg, 1989).

6.1. GA for SURC

When applied to the SURC scheduling problem, GAs view sequences of loading the stations as chromosomes (candidate solutions), e.g., for a cell with six stations, the chromosome corresponding to the robot move cycle {[S.sub.6.sup.+], [S.sub.3.sup.-], [S.sub.2.sup.-], [S.sub.1.sup.-], [S.sub.4.sup.-], [S.sub.6.sup.-], [S.sub.5.sup.-], [S.sub.6.sup.+]} is 3 2 1 4 6 5. The second position in this chromosome has the value "2" which means load station [S.sub.2] ([S.sub.2.sup.-]). These chromosomes are members of a population. Each chromosome is characterized (merited) by its fitness. Here, the fitness of a chromosome is measured by the inverse of the associated cycle time.

The GA procedure works iteratively and each new iteration is called a generation. The following GA parameters are used in the evolution of solutions: elite fraction (ef), population size (ps), probability of crossover ([p.sub.c]), probability of mutation ([p.sub.m]) and number of generations ([n.sub.gen]). Note that the downhill permutation is an optimal one-unit cycle for a few special cases of robotic cells (Crama et al., 2000; Dawande et al., 2004). Although our problems do not satisfy those special cases, downhill permutation may still be a good solution. Hence, at the beginning of the GA search, we take one chromosome as the downhill permutation and the other ps - 1 chromosomes are generated randomly.

Selection is a key operation in a GA search. One effective way of performing selection is to select the elite (chromosomes having higher fitness) (Goldberg, 1989). We keep the ef upper fraction of the population and remove the others. Selected chromosomes are reproduced in such a way that the total number of chromosomes in the population is again ps. We use a roulette wheel selection procedure for reproduction where each chromosome has a roulette wheel slot that is sized in proportion to its fitness. A simple spin of this weighted roulette wheel yields a reproduced chromosome.

A crossover operator allows chromosomes to mate with one another, based on the value of [p.sub.c], to produce children. In scheduling problems, crossover is implemented slightly differently from the manner it is done in simple optimization. One has to worry here about avoiding infeasible solutions. Details of crossover and mutation operators for SURC are provided in Appendix 1.

A key challenge in GAs is the optimization of the computational effort in balancing exploration (of the solution space) and exploitation (of the features of good solutions). This balance is greatly affected by the choices of the different GA parameters. This problem itself is an optimization problem and guidelines here are still very few (Davis, 1991). After performing some trial runs, we found that the following parameter values are suitable for SURC: ps = 100, [p.sub.c] = 0.95, [p.sub.m] = 0.1 and ef = 0.25.

6.2. GA for MURC

In this case, the chromosomes are exactly the same as those for SURC. Unlike SURC, however, the fitness (i.e., the inverse of the cycle time) of a chromosome is measured here by constructing the associated LCM-unit cycle from the one-unit cycle corresponding to that chromosome.

6.3. GA for LMURC

Since the cycle time calculation requires the robot move cycle as well as the linked pairs state, we need to define a two-dimensional chromosome with one dimension to describe the robot move cycle and the other dimension to indicate the state of linked pairs. For the same example as in Section 4.3 with robot move cycle [C'.sub.4.4], if the linked pair is in loaded state, then the chromosome representation is as shown in Fig. 2.

[FIGURE 2 OMITTED]

The first row shows the loading sequence which is the same as that in SURC and MURC. The second row shows the corresponding linked pairs state. If a station is not linked, its representation in the second row is always-1. Note that only the first station ([S.sub.2]) of the linked pair appears in the first row, since the robot does not load the second station ([S.sub.3]) of the linked pair. If the linked pair is in a loaded state, then the column corresponding to the first station of the linked pair contains a one in the second row; otherwise it contains a zero. Details of crossover and mutation operators for LMURC are given in Appendix 2.

7. Computational experiments

For the computational studies, we consider 80 randomly generated problems and four actual problems. The random problems are generated for four values of m (m = 8, 12, 16, and 20). For each m, 20 problems are generated according to the guidelines offered by Hall and Posner (2001). For all the stations, processing times are drawn from the uniform distribution U (5, 130) seconds, since it closely represents realistic problem instances. Hence, we consider all the four principles suggested by Hall and Posner (2001); (i) purpose; (ii) comparability; (iii) unbiasedness; and (iv) reproducibility. Our experimental data also has the required properties mentioned in Hall and Posner (2001) such as variety and practical relevance. For all the random and actual problems, the robot travel times used are based on the current physical layout of stations at FSI. These travel times are general and it should be noted that the problem of finding an optimal one-unit cycle is NP-hard in the general robot travel time setting (Brauner et al., 2003).

7.1. Computational studies for SURC

Table 1 shows the results for randomly generated problems. In the table, the percentage improvement obtained using the GA rather than the LWP is defined as:

Percentage Improvement = [[Cycle time using LWP - Cycle time using GA]/[Cycle time using LWP]] X 100.

Similarly, the percentage gap of GA from the lower bound is defined as:

Percentage gap = [[Cycle time using GA - LB on Cycle time]/[LB on Cycle time]] X 100.

In each row, the "Max," "Avg" and "Min" columns show the maximum, average and minimum values, respectively, for the 20 randomly generated problems for that row. The average CPU times are also calculated similarly.

In order to provide a statistical measure of the significance of the improvement obtained using our GA over the LWP, we perform the one-tailed t-test for each row as follows. Let [[mu].sub.g] be the average cycle time using the GA for a given row and [[mu].sub.1] be the corresponding value using LWP. We test the null hypothesis [H.sub.0]: ([[mu].sub.g] - [[mu].sub.1]) = 0 against the alternative hypothesis [H.sub.1]: ([[mu].sub.g] - [[mu].sub.1]) < 0 for each row separately. The p-value of this test is provided for each row in Table 1.

Table 1 shows that the gap of the GA from the LB is zero for all the problems. Hence, the GA provides the optimal solution for all these problems. We also note that the downhill permutation always achieves the LB. Consequently, the proposed GA converges very quickly with the downhill permutation as one of its starting solutions. Hence, the CPU time for the GA is very small. For all the problems, CPU times are given for running a C++ program on Windows 2000 with a Pentium III 750 MHz processor.

The t-test results show that the p-value is approximately zero for each value of m. Therefore, the null hypothesis is rejected at any level for each value of m. Hence, the improvement made by using the GA rather than the LWP is statistically significant for all the problem instances. This result is supported by the fact that the average percentage improvement varies between 3.1 and 6.1%. It can be easily shown that a 3.1% decrease in the cycle time yields a 3.2% increase in the number of wafers and a 6.1% decrease in the cycle time provides a 6.5% increase in the number of wafers. These robotic cells having a single robot currently operate at about 10 000 wafers per month, so these improvements range from 320 to 650 more wafers per month. Each wafer contains a hundred or more chips, which may translate into an increased revenue of between $10 000 to $30 000 for every additional wafer. Hence, although a 3.1% improvement may appear to be small and although these robotic cells do not operate at full capacity throughout the year, the potential annual revenue implications can be in the millions of dollars for FSI's customers.

Table 2 shows the gap of the GA from the LB and the improvements made using the GA for four actual problems. We observe that the percentage gap of the GA from the LB is zero for all the problems and hence the GA always provides the optimal solution. The improvements (2.01-5.45%) are also significant. Again, the downhill permutation achieves the LB for all four problems.

Note that the cycle time evaluation of the LWP is done via simulation using an Excel package. Unlike one-unit cycles, the LWP does not guarantee a cyclic solution. In the case of a tie for the competing longest waiting pairs in LWP, the tie is broken arbitrarily, and hence the solution is not necessarily cyclic.

7.2. Computational studies for MURC

In most of the problem instances for SURC, we observe that the cycle time obtained by the GA is limited due to a large processing time at some of the stations. Therefore, we can obtain a smaller cycle time by introducing multiple identical processing units at bottleneck stations. In MURC, we use the same problems as in SURC but the number of processing units is more than one at the bottleneck stations. The number of processing units [v.sub.i] at station [S.sub.i] was set equal to an integer approximately equal to [P.sub.i] (the processing time in seconds) multiplied by the target throughput (in wafers per second).

Table 3 shows the results for 80 randomly generated problems. We assume appropriate target throughput values for these problems in order to reflect the real world situation. Accordingly, the desired values of [v.sub.i] are estimated. We note that the solutions obtained by the GA are not always downhill permutations. Descriptions of the columns in Table 3 are similar to those in Table 1. The average gap of the GA from the LB is very small (0.6-2.9%). We would like to emphasize that this gap is computed with respect to the LB on the optimum solution rather than the optimum solution itself. Therefore, it is likely that the actual gap between the GA and the optimal solution is smaller than that reported in Table 3. Note that the minimum percentage gap in every row is zero, which indicates that the GA obtains the optimal solution for at least one problem instance in every row. It is also found that the downhill permutation achieves the LB only for 10 problems out of 80 randomly generated problems. For all other problems, it fails to achieve the LB.

The t-test results again show that the improvement made using the GA rather than the LWP is statistically significant for all the problem instances and the average percentage improvement varies between 5 and 5.5%. Table 4 shows the gap of the GA from the LB (2.5-3.7%) and percentage improvements (0.5-10%) made using the GA rather than the LWP for four actual problems.

7.3. Computational studies for LMURC

In MURC, we observe that the robot is usually busy and that the cycle time is usually limited by that robot's workload. Therefore, the workload on the robot could be reduced by providing local material handling devices between some of the stations. Here, we use the same problems which were tested for MURC, but link some of the adjacent stations. Based on physical locations and processing characteristics, only a few of the adjacent stations can be linked in the robotic cells being used.

Table 5 shows the results for 80 randomly generated problems. The average gap of the GA from the LB is very small (0-2%) and hence the GA solution is very close to the optimal solution. Downhill permutation does not achieve the LB for any of the problems tested and the solutions obtained by the GA are not downhill permutations. The result of the t-test again shows that the improvement made using GA rather than the LWP is statistically significant for all the problems. This result is supported by the fact that the average percentage improvement varies between 3.6 and 6.5%. Table 6 shows the gap of the GA from the LB (0-2.5%) and the percentage improvements made using GA rather than the LWP (1.5-11.3%) for four actual problems.

7.4. Implementation

Robotic cells use controllers to supervise and sequence the movements of the robot (Herrmann, 2003). FSI implemented and tested the proposed robot move schedules in the controller of a simulator robotic cell. In the future, FSI will use the cyclic solutions in the logic of robotic cell controllers. The initialization of the cell is done in a manner that the robot skips infeasible activities in the beginning until the robot can follow the proposed cyclic sequence. We illustrate this initialization process using a one-unit cycle, [C.sub.2,4]: {[S.sub.4.sup.+], [S.sub.4.sup.-], [S.sub.3.sup.-], [S.sub.2.sup.-], [S.sub.1.sup.-], [S.sub.4.sup.+]}, for m = 4 and each station has one processing unit. Note that all the stations are empty when the processing begins. In the beginning, the robot skips activities [S.sub.4.sup.+], [S.sub.4.sup.-], [S.sub.3.sup.-] and [S.sub.2.sup.-] since stations 4, 3, 2 and 1 do not have wafers. It then performs [S.sub.1.sup.-] by picking up a wafer at I and loading it onto [S.sub.1]. The robot again skips [S.sub.4.sup.+], [S.sub.4.sup.-] and [S.sub.3.sup.-] and performs [S.sub.2.sup.-] and [S.sub.1.sup.-]. It then skips [S.sub.4.sup.+] and [S.sub.4.sup.-] performs [S.sub.3.sup.-], [S.sub.2.sup.-] and [S.sub.1.sup.-]. Now the robot skips [S.sub.4.sup.+] and performs [S.sub.3.sup.-], [S.sub.2.sup.-] and [S.sub.1.sup.-]. Finally, the robot can follow the sequence of activities as specified in [C.sub.2,4] without skipping any activities. Hall et al. (1998) show that this initialization process leads to steady-state conditions after executing a finite number of robot activities in m-station robotic cells. A similar process can be used if the system starts in any other state that is not part of the cycle.

8. Conclusions

We study the problem of minimizing the per unit cycle time of an m-stage robotic cell operating without buffers. This problem is solved for FSI International Inc. We consider three robotic cell configurations that are presently used by FSI and other designers of robotic cells. The contributions of the present work may be summarized as follows:

* We introduced the concept of LCM-cycles to devise cyclic solutions for robotic cells having multiple identical processing units. LCM-cycles are efficient, simple, and easy to understand and implement. Since an LCM-cycle is cyclic in nature, it gurantees the repeatability of the solution and helps in the precise evaluation of the per unit cycle time without elaborate simulation, unlike other methods used so far in practice. Hence, FSI can now guarantee the throughput to its customers in a more precise manner. It also helps in delivering high quality wafers as they are produced here by consistent robot move sequences.

* In practice, robotic cells having single robot currently operate at about 10 000 wafers per month. Hence, an average reduction in cycle time of between 0.5 and 11.3% would deliver around 50 to 1274 more wafers per month. Since a wafer contains a hundred or more chips, the increased revenue would amount from $10 000 to $30 000 for every additional wafer. Hence, although these improvements may appear to be small and robotic cells may not operate at full capacity throughout the year, the potential annual revenue implications can be in the millions of dollars for FSI's customers.

* We also develop a theoretical LB on the per unit cycle time to determine the efficacy of the proposed methods. The average gaps of the proposed algorithms from these bounds are very small (0-3.7%), indicating that the proposed solutions are very close to the optimal solution.

* Robotic cells are used in many different industries such as manufacturing of automotive parts, glass products, cosmetics, fiber-optics, and printed circuit boards (Dawande et al., 2004). The proposed methods may also be used for all these industries.

* It is shown that a cyclic solution defined by downhill permutation achieves optimal solutions for practically relevant problem instances of one robotic cell configuration (i.e., SURC). This finding provides an useful insight for solving other similar scheduling problems.

In addition, this work contributes significantly to the designing of robotic cells as follows:

* A photolithography robotic cell costs between $2000 000-$5000 000. Therefore, it is very important to design the system intelligently in order to maximize the utilization of the stations and robots. In other words, a company would like to achieve the target throughput with a minimum investment in hardware. In this context, the methods developed would help the company in evaluating the maximum throughput for various possible cell designs.

* The proposed methods would also enable a company to perform sensitivity analysis on the effect of various possible future process changes such as increasing processing times at some stations and reducing processing requirements at others, for instance.

Presently this work is being extended to robotic cells having multiple robots. Comparable ideas are being used for these cells. Initial results at FSI show that the improvements in two-robot and three-robot cells are proportionately much larger than that in single robot cells.

Appendices

Appendix 1: Crossover and mutation operators for SURC

A key consideration in designing the crossover operator is the avoidance of infeasible solutions. First, we select the mating pairs of chromosomes at random from the population. Two children are then produced from a selected pair of parents using a one-point crossover (Goldberg, 1989) as follows: the elements on the left-hand side of a randomly selected point are always inherited from parent 1 to child 1 and from parent 2 to child 2. For example, in Fig. A1, the fifth point is selected for dividing parents 1 and 2. Then, as shown in Fig. A2, stations 1, 4, 3, 2 and 6 are transferred from parent 1 to child 1 in the same order. Similarly, stations 6, 2, 5, 1 and 3 are transferred from parent 2 to child 2 in the same order. Now the remaining elements of child 1 (i.e., stations 5, 7 and 8) are selected in the order they appear in parent 2 (i.e., station 5 first, then 8 and finally 7). Similarly, the remaining elements of child 2 (i.e., stations 4, 8 and 7) are selected in the order they appear in parent 1 (i.e., station 4 first, then 7 and finally 8). Two children produced in this way are always feasible. This crossover process is repeated for all the selected pairs of parents.

The children produced after crossover are given a chance to mutate according to [p.sub.n]. We use the arbitrary two-column change mutation, where a column of chromosome is exchanged with another randomly selected column in the same chromosome. Hence, feasibility is always maintained in this type of mutation. In Fig. A3, the column 3 of child 1 is exchanged with the column 7 of child 1.

Appendix 2: Crossover and mutation operators for LMURC

Consider an example with m = 8, where linked stations pairs are [S.sub.2] - [S.sub.3] and [S.sub.6] - [S.sub.7]. Two parents for this example are shown in Fig. A4. We now illustrate the one-point crossover. First the crossover point is chosen randomly (say the third column) and then the first rows of child 1 and child 2 are filled similar to that in SURC. The second rows of children are filled correspondingly (see Figs. A4 and A5). The mutation operator and the values of the GA parameters used are the same as that in SURC.

[FIGURE A1 OMITTED]

[FIGURE A2 OMITTED]

[FIGURE A3 OMITTED]

[FIGURE A4 OMITTED]

[FIGURE A5 OMITTED]

Table 1. Gap of the GA and the improvements made using the GA rather
than the LWP for a random dataset in SURC

                                         Improvement using the
               Percentage gap of the     GA rather than the LWP
Number of      GA from the LB                  Percentage
stations, m   Max    Avg     Min         Max      Avg      Min

 8            0       0       0          7.7      3.1      1.6
12            0       0       0         11.2      4.1      1.7
16            0       0       0         11.0      5.2      1.8
20            0       0       0         10.0      6.1      1.9

                      Improvement using the    Avg CPU time
Number of             GA rather than the LWP   (seconds)
stations, m           p-value of t-test       LWP        GA

 8                    3.7 X [10.sup.-7]       3.6        1.4
12                    2.8 X [10.sup.-6]       3.1        2.3
16                    1.1 X [10.sup.-8]       7.3        3.1
20                    1.9 X [10.sup.-11]      4.1        4.0

Table 2. Gap of the GA and the improvements made using the GA rather
than the LWP for actual problems in SURC

                            Percentage
             Percentage     improvement using  CPU time
Number of    gap of the GA  the GA rather      (seconds)
stations, m  from the LB    than the LWP       LWP  GA

 6           0              2.61               3    1.47
11           0              2.01               3    1.93
11           0              2.62               3    1.66
12           0              5.45               3    2.01

Table 3. Gap of the GA and the improvements made using the GA rather
than the LWP for a random dataset in MURC

                                       Improvement using the GA
             Percentage gap of         rather than the LWP
Number of    the GA from the LB     Percentage
stations, m  Max  Avg  Min        Max   Avg  Min  p-value of t-test

 8           2.8  0.6  0          15.6  5.0  0.5  1.48 X [10.sup.-5]
12           3.2  2.9  0          15.7  5.2  0.7  4.73 X [10.sup.-6]
16           3.1  2.4  0          14.3  5.5  0.9  8.49 X [10.sup.-7]
20           3.0  1.8  0          11.0  5.1  0    1.78 X [10.sup.-7]

             Avg CPU time
Number of    (seconds)
stations, m  LWP   GA

 8            2.2    52.7
12            3.0   103
16            6.5   145
20           15    1441

Table 4. Gap of the GA and the improvements made using the GA rather
than the LWP for actual problems in MURC

                            Percentage
             Percentage     improvement using  CPU time
Number of    gap of the GA  the GA rather      (seconds)
stations, m  from the LB    than the LWP       LWP  GA

 6              3.721           0.46            2   6.84
11              3.100           1.43            3   1.72
11              3.100           1.35            2   1.47
12              2.482           9.98            3   9.80

Table 5. Gap of the GA and the improvements made using the GA rather
than the LWP for a random dataset in LMURC

                                 Improvement using the GA
             Percentage gap of   rather than the LWP
Number of    the GA from the LB     Percentage
stations, m  Max  Avg  Min       Max    Avg  Min  p-value of t-test

 8           0    0    0         16.7   6.5  2.4  1.14 X [10.sup.-7]
12           2.7  0.8  0         12.3   6.2  0.1  5.74 X [10.sup.-7]
16           2.5  2.0  0          6.96  3.6  0.5  4.21 X [10.sup.-7]
20           2.3  0.5  0         11.4   6.0  0.4  4.82 X [10.sup.-9]

             Avg CPU time
Number of    (seconds)
stations, m  LWP   GA

 8            2.5   38.6
12            3.1   43.7
16            4.6  153
20           15    420

Table 6. Gap of the GA and the improvements made using the GA rather
than the LWP for actual problems in LMURC

                            Percentage
             Percentage     improvement using  CPU time
Number of    gap of the GA  the GA rather      (seconds)
stations, m  from the LB    than the LWP       LWP  GA

 6           0              11.26              2    1.63
11           2.487           1.50              3    1.90
11           2.487           1.64              2    1.57
12           1.585           7.51              5    1.35

Acknowledgement

The research was supported in part by FSI International Inc., Allen, TX.

Received June 2002 and accepted May 2004

References

Asfahl, C.R. (1985) Robots and Manufacturing Automation, Wiley, New York, NY.

Brauner, N., Finke, G. and Kubiak, W. (2003) Complexity of one-cycle robotic flow-shops. Journal of Scheduling, 6(4), 355-372.

Crama, Y., Kats, V., Van de Klundert, J. and Levner, E. (2000) Cyclic scheduling in robotic flowshops. Annals of Operations Research, 96, 97-124.

Crama, Y. and Van de Klundert, J. (1997) Cyclic scheduling of identical parts in a robotic cell. Operations Research, 47, 952-965.

Crama, Y. and Van de Klundert, J. (1999) Cyclic scheduling in 3-machine robotic flowshops. Journal of Scheduling, 2(1), 35-54.

Davis, L. (ed.) (1991) Handbook of Genetic Algorithms, van Nostrand Reinhold, New York, NY.

Dawande, M., Geismar, H.N., Sethi, S.P. and Sriskandarajah, C. (2004) Sequencing and scheduling in robotic cells: recent developments. Journal of Scheduling (to appear).

Goldberg, D.E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Boston, MA.

Groover, M.P. (1987) Automation, Production Systems, and Computer-Integrated Manufacturing, Prentice-Hall, Englewood Cliffs, NJ.

Hall, N.G., Kamoun, H. and Sriskandarajah, C. (1998) Scheduling in robotic cells: complexity and steady state analysis. European Journal of Operational Research, 109, 43-63.

Hall, N.G. and Posner, M.E. (2001) Generating experimental data for computational testing with machine scheduling applications. Operations Research, 49(7), 854-865.

Herrmann, J.W. (2003) Sequencing wafer handler moves to improve cluster tool performance, in Proceedings of the 2003 Industrial Engineering Research Conference, Portland, OR, May 18-20, 2003.

Herrmann, J.W., Chandrasekaran, N., Conaghan, B.F., Nguyen, M.Q., Rubloff, G.W. and Shi, R.Z. (2000) Evaluating the impact of process changes on cluster tool performance. IEEE Transactions on Semiconductor Manufacturing, 13(2), 181-193.

Kumar, S. (2001) Analytical and metaheuristic solutions for emerging scheduling problems in e-commerce and robotics. Ph.D. Dissertation, The University of Texas at Dallas, Dallas, TX.

Perkinson, T.L., Gyurcsik, R.S. and McLarty, P.K. (1996) Single-wafer cluster tool performance: an analysis of the effects of redundant chambers and revisitation sequences on throughput. IEEE Transactions on Semiconductor Manufacturing, 9(3), 384-400.

Reeves, C.R. (1997) Genetic algorithms for the operations researcher. Informs Journal on Computing, 9(3), 231-250.

Sethi, S.P., Sriskandarajah, C., Sorger, G., Blazewicz, J. and Kubiak, W. (1992) Sequencing of parts and robot moves in a robotic cell. International Journal of Flexible Manufacturing Systems, 4, 331-358.

Sriskandarajah, C., Hall, N.G. and Kamoun, H. (1998) Scheduling large robotic cells without buffers. Annals of Operations Research, 76, 287-321.

Wood, S.C. (1996) Simple performance models for integrated processing tools. IEEE Transactions on Semiconductor Manufacturing, 9(3) 320-328.

SUBODHA KUMAR (1,*), NATARAJAN RAMANAN (2) and CHELLIAH SRISKANDARAJAH (3)

(1) University of Washington Business School, Seattle, WA 98195, USA

E-mail: subodha@u.washington.edu

(2) FSI International Inc., Allen, TX 75013, USA

(3) School of Management, University of Texas at Dallas, Richardson, TX 75083, USA

E-mail: chelliah@utdallas.edu

*Corresponding author

Biographies

Subodha Kumar is an Assistant Professor at the University of Washington Business School. He has a Ph.D. degree from the School of Management, University of Texas at Dallas in the field of Management Science and Information Systems. He received his MBA degree from the University of Texas at Dallas, a Master of Technology degree from the Indian Institute of Technology, Kanpur, in Industrial and Management Engineering and a B.Sc. degree in Mechanical Engineering from BIT Sindri, India. His research interests lie in the general area of scheduling, e-commerce, database and robotics. He is a member of INFORMS and AIS.

Natarajan Ramanan is a senior member of the technical staff at FSI International and an adjunct faculty at Southern Methodist University. He has a Ph.D. degree in Mechanical Engineering from the Ohio State University. He is a licensed professional engineer in the state of Texas. He is in charge of advanced technology development for the microlithography division of FSI. His research interests are in the areas of photoresist processing, computational fluid dynamics and transport phenomena. He serves as the Vice Chair and program chair of ASME North Texas Section and is a member of ASME and IEEE.

Chelliah Sriskandarajah is a Professor at the School of Management of the University of Texas at Dallas. He has a Ph.D. degree from the Higher National School of Electrical Engineering of the National Polytechnic Institute of Grenoble, France, in the field of Production Automation and Operations Research. He received an M.Sc. degree in Industrial Engineering and Management from the Asian Institute of Technology, Bangkok, and a B.Sc. degree in Mechanical Engineering from the University of Sri Lanka. His research revolves around solving various production planning and scheduling problems with the aim of making the production process more economic and efficient. His research interests lie in the general area of production planning and scheduling, machine scheduling theory, supply chain management and performance evaluation of production systems. He has published over 50 scholarly articles in leading journals. Over the years, his research has been supported by a number of sponsors including the National Science Foundation, USA, the Natural Sciences and Engineering Research Council, Canada, Manufacturing Research Cooperation of Ontario, Canada, and NATO. He is an Associate Editor of INFOR and is a member of IIE, INFORMS, IEEE, POM and CORS.

Contributed by the Scheduling/Production Planning/Capacity Planning Departments