DETERMINING TRANSFER BATCH SIZES IN TRIP-BASED MATERIAL HANDLING SYSTEMS Yavuz A. Bozer and Jonghwa Kim Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 94-6 March 1994 Revised November 1994

DETERMINING TRANSFER BATCH SIZES IN TRIP-BASED MATERIAL HANDLING SYSTEMS Yavuz A. Bozer Jonghwa Kim Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117, USA ABSTRACT Trip-based material handling systems such as AGV systems, lift trucks, etc. are often designed with a given flow matrix (or FROM-TO chart) which is usually treated as the number of loaded trips that the devices must perform per unit time between the workstations. In reality, the number of trips that would result from parts flow in a facility is dictated by the transfer batch size, i.e., the number of parts that are transferred from one workstation to the next in one trip. In this paper, we present analytical and simulation results aimed at determining optimal or near-optimal transfer batch sizes in manufacturing systems. 1 INTRODUCTION Trip-based material handling systems consist of one or more handling devices that are self-powered and operate independently from each other [18]. Examples of tripbased handling systems used in manufacturing include Unit Load Automated Guided Vehicle (AGV) systems, lift trucks, microload Automated Storage/Retrieval (AS/R) systems, bridge cranes, and so on. In a trip-based handling system, a device performs a trip to move one unit load. We assume that the device may handle only one unit load on each trip. (This assumption applies to many handling systems except those such as tractor-trailer systems where a device may pull multiple unit loads at the same time.) The transfer batch size (TBS) refers to the size of the unit load handled on each trip. We assume a discrete parts flow system where the unit load size can be expressed as an integer number of parts handled by the device. 1

In this study, we show that the TBS has a significant impact on the performance of the handling devices as well as work-in-process (WIP) level in the system. However, the problem of determining optimal or near-optimal TBSs has received little attention and, to our knowledge, there are no analytical models presented in the literature. 2 PROBLEM DESCRIPTION In the manufacturing system we study, there are two types of workstations: input/output(I/O) stations and processing stations. Each workstation has an input queue and an output queue. Parts arriving from outside the system are directly placed in the output queue of an I/O station, while parts that require no further processing enter the input queue of an I/O station and leave the system instantly. Each external arrival occurs according to a Poisson process and consists of one or more parts depending on the TBS for that part type. Flow is not necessarily conserved at an I/O station, since parts may enter the system from one I/O station and exit from another. At a processing station, parts arrive at the input queue and wait until the processor is available. When the processor is available, a part is removed from the input queue, one part at a time, by the First-Come-First-Served (FCFS) rule and processed for a certain period. After a part is processed, it is staged by the processor until the desired TBS is reached, at which point the parts are placed in the output queue as a unit load. (Material handling concerns within the workstations are beyond the scope of our study.) Once a unit load is placed in an output queue, it is defined as a "move request" and waits for a handling device to pick it up. The handling device first travels empty to the output queue where the move request is located and then it delivers the load to the input queue of the next station. Thus, each trip consists of empty travel followed by loaded travel. The next load to be moved by an empty device is determined by the empty device dispatching rule. For this study, we assume that the move requests are served on a FCFS basis; i.e., an empty device is assigned to the oldest unit load waiting in an output queue. Although as a dispatching rule the FCFS discipline leads to increased empty device travel, it is easier to treat analytically than other empty device dispatching rules such as shortest-travel-time-first (STTF). When a device becomes empty, if there are no unassigned move requests in the system, the device becomes idle at its last delivery point. Also, at the time a move request occurs, if more than one idle device is available, the oldest idle device is dispatched. In the following study, we are concerned with the handling devices and the total work-in-process (WIP) in the system. The total WIP in the system may be divided into four categories: 1. loads waiting in the input queues, 2. loads being processed and staged by the processors, 3. loads waiting in the output queues, and 4. loads being 2

Exp. WIP ip output input \ queues transfer batch size Figure 1: Transfer batch size.vs WIP moved. Generally speaking, for a fixed throughput level, the expected WIP in the input queues increases with the TBS (see Figure 1). This is due to the fact that the arrival of a unit load is analogous to "bulk arrivals" in queueing. On the other hand, the expected WIP in the output queues generally decreases with the TBS since the number of trips that the devices must perform per time unit decreases as the TBS is increased. Given the tradeoff shown in Figure 1, we are concerned with determining the "optimal" TBS so that the total expected WIP (or the total cost associated with WIP) in the system is minimized. For that purpose, we develop separate analytical models to estimate the expected WIP levels in the input and output queues. For the former, we used an M(b)/G/1 type of approximation. For the latter, we ilsed an MI/G/c type of approximation, where we explicitly capture the empty devices travel time as a function of the device dispatching rule (in this case, FCFS). Remark: Note that determining "optimal" TBS is different from determining the optimal production lot size (PLS) in several ways. First, the PLS is determined by examining the tradeoffs between inventory holding costs and set up costs, while the TBS is determined by examining the tradeoffs between WIP costs associated with the processors and the handling devices. Second, the PLS is determined at a higher level (in the master schedule) than the TBS which is determined at the shop level. Thus, expressed in number of parts, for most manufacturing systems, the TBS is generally considerably smaller than the PLS for a particular part type (unless, of course, PLSs of "one" become a reality). Third, the stochastic behavior of WIP is not explicitly taken into account in determining the PLS. 3

3 LITERATURE REVIEW The expected waiting time of a unit load in an output queue is an important measure to estimate WIP associated with the handling system. However, there are few analytical models that take into account a specific device dispatching rule. Chow [4, 5] presents an approximate analytical model to estimate the utilization of a single device (namely, a storage/retrieval, or S/R machine) and the expected waiting times. Assuming that the S/R machine is never blocked, the first and the second moment of the service time distribution are obtained from the flow matrix by a probabilistic argument. Then, He models the system as a single M/G/1 queue with FCFS service. In approximating the expected waiting times, empty travel of the device is not included as part of the waiting time, since "service" is assumed to start as soon as the S/R machine is dispatched to pick up the unit load. (The service time itself, however, includes empty travel.) Cho [3] also uses the M/G/1 queueing model with FCFS service to model a material handling system with a single device. He estimates the expected waiting times in the output queues by "tagging" a move request. The expected service time and device utilization is the same as in Chow's model [4]. However, Cho includes empty travel time as part of the expected waiting times in the output queues. Also, he shows that his model works well for single-device systems and extends it to multiple-device systems by increasing the speed of a single device by a factor equal to the number of devices. However, Cho observes that his model underestimates the expected waiting times in the output queues for handling systems with multiple devices. Yao and Buzacott [20, 21, 22] model the material handling system as a central server station. In the first study, the service time distribution of the handling system is assumed to be general, while in the other two studies, the service time distribution of the handling system is assumed to be exponential. By modeling the h;rndling system as a central server station, the expected waiting times in the output queues are estimated as a single estimate (i.e., the expected waiting time at the central jsrver queue), regardless of individual workstations. Furthermore, the expected travel times between all the stations are the same regardless of the origin and destination of the move requests. Also, the probability that a job will be routed to a particular station does not depend on where the job is picked up. Solberg [16] and Solot [17] use a similar approach by modeling the material handling system as another workstation. Bertrand [1] extends the classical economic production batch size model to include WIP carrying cost in a production shop consisting of multiple workstations. He uses the closed queueing network analysis developed by Solberg [16] to estimate the expected time in the system for each job. He shows that the production batch size influences the batch waiting time and WIP in the manufacturing system, and that ignoring WIP carrying cost may result in substantial errors in both determining the optimal production batch size and the optimal cost. Also, he develops an 4

iterative algorithm to determine optimal production batch size. However, he models the material handling system as another workstation as Solberg [16] and Yao and Buzacott [20, 21, 22]. Bozer, Cho and Srinivasan [2] develop an iterative algorithm to estimate the expected waiting times in the output queues with a single device operating under the MOD FCFS rule. The algorithm is based on their earlier analytic model [18]. They estimate the expected queue lengths first and use Little's formula to estimate the expected waiting times. Starting with an initial estimate of the queue lengths, they observe that the algorithm fails to converge only when the utilization of the device is around 0.99 or higher. Egbelu [7] proposed an optimization model to determine the container size (i.e., the TBS) and the number of handling devices required. He assumed that only one container is selected for all part types. Hence, the weight capacity of the selected container determines the TBS for each part type; that is, the weight capacity of selected container TBS of part type j = max integer the weight of part type j For each container size, his method requires a number of simulation runs to estimate expected WIP in the system and the number of devices required. Subsequently, he uses the above estimates in an optimization model to determine the optimal container size. Although his model includes several types of costs that occur in a manufacturing system, it relies heavily on simulation. Also, some feasible TBSs are not evaluated since the container is always filled up to its capacity. For example, suppose the weight capacity of a selected container is 500 pounds and a part weighs 100 pounds. Then, TBS of that part type is set equal to five and TBSs of one through four are not evaluated, although such TBSs are feasible with the selected container size. In his later model [8] Egbelu determines the number of processors required in addition to the container size and the number of handling devices required by similar approach. Grasso and Tanchoco [10] investigate the effect of the production batch size from a different point of view. They include the material handling cost and the storage space cost in the cost function of a multi-product MRP problem. The material handling cost is defined as unit cost per move multiplied by the total number of movements in a planning horizon. They show that different batch sizes require different material handling efforts and that including handling and storage costs reduces the optimal order quantities and results in less total cost. 4 ANALYTICAL MODEL TO ESTIMATE WIP 4.1 Notation 5

The following notation is used throughout the paper. In the analytic model, subscript i and j refer to a station, while subscript k refers to a part type. Let M = number of workstations in the system JT = number of part types in the system Dk = demand for part type k (parts/time unit) Qk = transfer batch size of part type k Ri = set of part types which require processing at workstation i ={k I part type k visits workstation i} Qk = the set of workstations at which part type k requires processing ={i | workstation i is visited by part type k} Ai = arrival rate at the input queue of workstation i (unit loads/time unit) AT = sum of the arrival rates at the input queues of workstations (EM1 Ai ) Si = processing time at workstation i (time units/part) E(Ni) = expected number of parts in a unit load arriving at the input queue of workstation i E(Ji) = expected number of parts in a unit load arriving at the output queue of workstation i ( E(Ni) = E(Ji) for processing stations) A, = arrival rate at the output queue of workstation i (unit loads/time unit) AT = sum of the arrival rates at the output queues of workstations (ZM1 Ai = AT ) ND = number of handling devices in the system pij = fraction of jobs routed from workstation i to j P = time required for a device to pick-up or deposit a unit load (constant) oij = expected empty travel time from workstation i to j a(2) = second moment of expected empty travel time from workstation i to j 7Tj = expected loaded travel time from workstation i to j (aij + 2P) T(2) = second moment of the expected loaded travel time from workstation i to j In the above list, Qk is the primary decision variable, while Ai, AT, E(Ni), E(Ji), A,, AT, and Pij are functions of Qk. All others are given as parameters and their values are specified by the user. Note that we implicitly assume that the loaded and empty travel time parameters (a.., o(2), rT, and ri?)) as well as the load pick-up or deposit times (P) are independent of the TBS. This assumption is justified for many trip-based handling systems since the weight of the unit load typically has little or no impact on the travel speed of the device. 4.2 Assumptions We make the following assumptions for the analytical model we develop to estimate the expected WIP in the system: 1. We assume that multiple part types are processed in the system and that the TBS of each part is determined independently. 6

2. No set up times are taken into account for different part types processed at a particular workstation. However, if the set up times are known in advance, they can be incorporated into the service time for the processor. 3. A workstation always has sufficient processing capacity; it is utilized less than 100%. 4. We assume that unit loads are delivered at the input queue of a station according to a Poisson process; the instant at which a unit load is delivered is a random point in time [18]. 5. We assume that the move requests occur according to a Poisson process. This assumption is perhaps not entirely valid. However, a general result of renewal theory shows that the superposition of increasingly many component processes yields a Poisson process [12]. 6. The layout of the system, part routes, throughput requirements for each part type, and the speed of handling device are assumed to be given. 7. We assume that the travel times between the workstations are exponentially distributed with known mean and are independent of the TBS. 8. For the devices, no blocking effects due to possible congestion are taken into account both in developing the analytical model and in simulation. 9. The devices are homogeneous and they each move one unit load at a time; a unit load includes only one part type. 4.3 Expected Waiting Times in the Input Queues Parts arrive in bulk at the input queue of each workstation and the number of parts in each arriving unit load varies depending on the TBS of each part type. In this case, based on Poisson arrival of unit loads, the expected waiting time of a part in the input queue of workstation i, W I', is given as follows [14]: E(S)[E(Ni(2 ) - E(NA)]/E(N,) + ^AE(Ni)E(S!2)) 2[1 - AIE(N,)E(S,)] In equation (1), the arrival rate (unit load/time unit) at each input queue, A,, is given by A,= E -' (2) kER, Qk 7

The first and the second moment of the number of parts in a unit load arriving at the input queue of workstation i are given as follows: Dk Dk Qk kERi E(N,) = Z QkO = (3) kER ZDI = Ai lER QI Dk Q2 DkQk k ERi Note that E(Ni) and E(N,(2)) are assumed to be zero for an I/O station, since all the unit loads arriving at the input queue of an I/O stations either directly enter the output queue or leave the system immediately. By substituting equations (2), (3), and (4) into equation (1), we obtain Dk(Qk - 1) E(S,) jeR 1 + E(S 2) Z Dk k Dk keRi WI = L kE, k Ri 5) 2[1 - DkE(S)]5) kER, On the other hand, the expected waiting time of a unit load in the input queue of station i, W I, is expressed as follows [14]: WI. = WIP' - waiting time due to the parts in the same unit load E(S)[E(N(2)) - E(N,)]/E(N,) + AiE(N,)E(S(2)) 2[1 - A(E(NI)E(S()] E(S,)[E( )) - E(N,)] (6) 2E(N,) By substituting equations (2), (3) and (4) into equation (6), and simplifying, we obtain E(S.)2[ Z Dk(Qk - 1)] + E(S(2))( E Dk) kER, kERt?, W IU =(7) = 2(: Dk)[l - E DkE(Si)] kER, kER, 4.4 Expected Waiting Times in the Output Queues 8

As stated previously, a trip-based material handling device first performs an empty trip and then a loaded trip to satisfy a move request. Under the FCFS dispatching rule, the expected empty travel time to workstation i, Ei, is estimated as follows [3]: MM Ah M A Ei = E Ephj = E -a (8) h=1 j=l AT j=1 A since E= PhjAh = A-. Likewise, the second moment of the expected empty travel time to workstation i, E(2), is given by M A E M AZ'j (9) The expected loaded travel time from workstation i, Li, and its second moment, L(2), are easily obtained by M Li = pijij (10) j=l and M L(2) = pij.r) (11) j=1 where rj = aij + 2P. Note that we include pickup/deposit time, P, as part of the expected loaded travel time. Based on equations (8) and (10), the expected service time for a device to serve a move request at the output queue of workstation i, Ti, is given by T = Ei+ L, (12) and the second moment of the above service time is given by T(2) = E(2 + LI + 2ELi. (13) The expected device utilization is estimated as the total workload divided by the number of devices. The total workload for the handling system, WL, is given by Al WhL = EAiT-.'14) i=1 Thus, the expected device utilization, p, is given by M I r7 M ND (15 ) 9

since the handling system consists of ND homogeneous devices. The device utilization is broken down into two components: the expected fraction of loaded travel time and the expected fraction of empty travel time [18]. The expected fraction of loaded travel time, af, is easily obtained by 1 M M af = ND i Ai E PijTij (16) i=i j=1 or a 1 = JDk E rj (17) k=l Qk ijEfl where Tij is the expected loaded travel time from workstation i to workstation j, where i precedes j in the route. Hence, the expected fraction of empty travel time, ae, is given by ae = p-af. (18) We now estimate the expected waiting time of a unit load in each output queue. Under the FCFS rule, the location of each move request (relative to the location of a device) does not play a role in determining the next move request to be served. (This is not true for handling systems in which a location-dependent dispatching rule-such as the STTF rule is used.) However, the location of each move request affects the expected travel time of the devices. Thus, we can assume that each move request forms a single "conceptual queue" and served by the FCFS rule as long as we keep track of the origin and destination of the move requests. Furthermore, we have assumed that all the move requests occur according to a Poisson process and are independent. Hence, we can model a trip-based material handling system with the FCFS dispatching rule as an (M/G/c) queue with FCFS service. In an (M/G/c) queue with FCFS service, the expected waiting time in the queue is given by the following formula [13]: WE(S2)[AE(S)]c-1 Wq c- I S)]n C (19) 2(c - 1)![c - AE(S)]2 [ [AE()! S] (S) 2(~o n! (c-1)![c-( A(S)], where c is the number of servers, S is the mean service time and A is the arrival rate. In equation (19), AE(S) and AE(S2) represent the first and second moment of the total workload, respectively. The total workload for the handling system was derived earlier in equation (14), and the second moment of the total workload is equal to ZM1 AiTi2). Thus, the expected waiting time of a unit load in an output queue is 10

given by M M Wq -' (20) Wq i=l t__ i1M (20) M M M N1 [EZiTi] [Z iTi]ND 2(ND - 1)![ND - E AT]2 E =l+ M L=1 (ND- 1)![ND - AEiT] i=1 While deriving equation (20), the waiting time in the output queue is defined as the time spent by a move request from the instance of arrival at the output queue to the instance of receiving service. However, in a trip-based handling system, the device starts empty travel while the move request physically remains in the output queue until the device arrives and picks it up. Therefore, the actual expected waiting time of a move request in the output queue of workstation i, WOY, is defined as the time spent by a move request from the instance of arrival at the output queue to the instance of being removed by a handling device and is given by WOt = W +Ei. (21) 4.5 Expected Time in the System The expected time in the system of a unit load for part type k, TW1k, is given by TWk = E (WI' + PRu + WO' + rtj), (22) i,jEQk where PRu is the expected "time at the processor" at workstation i. Time at the processor is defined as the time spent by the first part of a unit load from the instance of its removal from the input queue to the instance of its placement in the output queue of workstation i. Since parts are "staged" by the server until all the parts in the unit load are processed, PR L is given by PRU = QkE(Si). (23) In equation (22), the right-hand side represents the expected time spent by a unit load at workstation i plus the expected travel time from workstation i to the workstation j. Recall that parts arrive at the input queue of a workstation as a unit load and are picked up from the output queue as a unit load. Thus, the expected time spent by a unit load at a workstation is equal to the expected time spent by a part at the workstation. Also, the expected travel time of a unit load is equal to the expected travel time of a part, since parts are moved as a unit load. Hence, the 11

expected time spent by a unit load in the system is equal to the expected time spent by a part, by definition. 4.6 Expected WIP in the System In this section, the expected total WIP in the input queues, output queues, and in the system are estimated by Little's formula. First, the expected total WIP in the input queues, WIPEn, is given by M WIPn = Z AiE(Ni)WIP i=1 M = EZ E DkWIP. (24) i=l kERi Second, to express the expected total WIP in the output queues in terms of the number of parts, the expected number of parts in a move request should be calculated. The expected number of parts in a move request which arrives at workstation i, E(Ji), is obtained as - Qk E Dk kERt Qk 5ER E(Ji) = = (25) Therefore, the total expected WIP in the output queues, WIPTut, is obtained as M WIPut = AE(Ji)WIl i=i M = E ES DkWO. (26) i=l kER, Recall that E(Ji) is equal to E(Ni) for the processing stations since flow is conserved (i.e., A, = A-). However, at I/O stations, E(Ni) is assumed to be zero, while E(Ji) may have a positive value depending on the job routing. Finally, the total expected WIP in the system, WIP:8y, is obtained as JT Dk JT WIPTr, = T Qk- TW = DkTWk. (27) k=l k k=l In the next chapter, the performance of the above model, which we refer to as the "WIP model" is evaluated via simulation. 5 EVALUATION OF THE WIP MODEL 12

To test the WIP model, we used three layouts: layout 1 from Srinivasan, Bozer and Cho [18], layout 2 we generated, and layout 3 from Egbelu [6]. Layout 1 and corresponding input parameters are presented in this section, while layout 2 and input parameters used with layout 2 and 3 are presented in Appendix. Layout 1 is shown in Figure 2 with the distance matrix shown in Table 1. Input parameters, including the number of part types, the throughput requirements for each part type, job routings, and the speed of the devices are shown in table 2. The processing time at each station is assumed to be exponentially distributed with the same known mean regardless of part type. The utilization of each processing station is assumed to be 0.7. Also, the travel times between the workstations are assumed to be exponentially distributed. To evaluate the WIP model, we compare the results obtained by the WIP model with those obtained from simulation. All the simulation results are obtained from 10 replications, in which at least 1000 unit loads of each part type are processed through the system. ( The simulation model simulates the "actual" system. That is, load arrivals to input and output queues of processing stations are dictated by the simulation model; they are not generated as a Poisson process.) For simplicity, we varied the TBS of part type 6 only. Also, as we increase the number of devices, we reduce the device speed and increase the pickup/deposit time to maintain comparable device utilization. In evaluation of the WIP model, we have observed similar trends between different layouts. Thus, in this section, we present the results obtained with layout 1 and present the results obtained with other layouts in Appendix. 5.1 Expected Waiting Times in the Input Queues The results obtained with layout 1 are presented in Figure 3 for each processing station. In Figure 3, the lines labeled as WIP represent the results obtained by the WIP model, while the lines labeled as sim 1, 2, and 4 represent the results obtained via simulation with 1, 2, and 4 devices. As the TBS increases, the WIP model shows two types of trends. For the "affected' workstations (i.e., those workstations on the route of part type 6 such as workstations 5, 8, 9 and 11), the WIP model overestimates the expected waiting times in the input queues. On the other hand, for "unaffected" workstations, (i.e., those that are not on the route of part type 6 such as workstations 6, 7 and 10), the expected waiting times in the input queues are independent of the TBS in the WIP model, while the simulation results suggest that it slightly increases with the TBS. The difference between the two results are small if the TBS is small but becomes large as the TBS increases. We also observe from the simulation that the number of devices in the system has little or no effect on the expected waiting times in the input queues. The same is true for the WIP model since in the WIP model, the expected waiting time in the input queue of a workstation is estimated independent of the number of devices. (Recall that the handling system always meets 13

I I I I =.. 6 E}- - - - -....................., 1........................................................................... —I O 1V stations 1-pi 2 g) I processing stations Figure 2: Layout 1 Table 1: Distance matrix of layout 1 station number 1 2 3 4 5 6 7 8 9 10 11 1 0 22 47 30 14 32 46 8 27 31 17 2 22 0 36 29 23 24 38 14 16 20 14 3 47 36 0 33 37 19 12 39 27 16 41 4 30 29 33 0 16 14 21 25 13 28 27 5 14 23 37 16 0 18 32 16 17 32 18 6 32 24 19 14 18 0 14 27 8 23 29 7 46 38 12 21 32 14 0 41 22 18 43 8 8 14 39 25 16 27 41 0 19 23 9 9 27 16 27 13 17 8 22 19 0 15 21 10 31 20 16 28 32 23 18 23 15 0 25 11 17 14 41 27 18 29 43 9 21 25 0 Table 2: Job routes and throughput requirements #1: layout 1 part type parts/min Job Route 1.LI 1 0.1 1 5 - 6 - 7 - 9 - 10 3 2 0.2 1 - 8 - 11 - 10 - 6 - 9 - 3 3 0.1 1 - 11 - 5 - 8 - 7 - 4 4 0.1 2 - 10 - 9 - 7 - 6 - 4 5 0.1 2 - 8 - 5 - 10 - 7 - 6 3 6 0.2 2 - 11 - 8 - 9 - 5 - 4 Device speed:from 200 (with 1 device) to 50 (with 4 devices) distance units/min Pickup/deposit time is neglegible. 14

(a) station 5 (b) station 6 12 12 - WIP --- WIP 11 112 — 4i — sim1 - ---- simi 10- sim2 10.............. sim2 sim4 - sim4 0- 9o 8 8 -. 7, C 7, I 6, _ 6, 2 4 6 8 1 2 4 6 8 1 E E 10- O)W- 5 3 3 2 2 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS TBS (c) station 7 (d) station 8 12 12 -WIP WIP 11 im 11., c siml 1~0 0sim2 10 0 sim2 sim4 9- sim4 8 o 8 0 1 c -c 7. E E 5 -ft. 5 _ 4: I; 43 3 2 I 2 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS TBS Figure 3: Expected waiting times in the input queues, layout 1 15

(e) station 9 (f) station 10 12- 12 --- WP - WiP 11 11 -i —4 —I siml - —. — siml 10 - sim2 10- ---- sim2 0. 0. 2 sim4 6 8 10 12 sim4 19- 9cr 8 cr;.E 7- - 7-.c J=1? E 5-. 5. 6 C 33 2'_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ I' _ 1'2 21 ^^r'JS r I 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS TBS (g) station 11 12WIP 11 -siml 10 -- -- sim2 sim4 09 - 8. - 7 616 E 5 3 0 2 4 6 8 10 12 TBS Figure 3: (contd.) Expected waiting times in the input queues, layout 1 16

throughput requirements.) In spite of the absolute differences observed, the results of the WIP model generally agree with the simulation results in terms of the overall trends. That is, as the TBS increases, the waiting times in the input queues increase or remain approximately the same depending on the route of job type 6. 5.2 Expected Waiting Times in the Output Queues For the output queues, we compare the results of the WIP model not only with the simulation results but the single faster device approximation (SFDA) using M/G/1. (Although Srinivasan, Bozer and Cho [18] state that the SFDA is not likely to yield satisfactory results, we will evaluate it for comparison purpose.) Figures 4, 5, and 6 show the results obtained with 1, 2, and 4 devices, respectively. Each graph presents the expected waiting times in the output queues obtained by SFDA (mgl), by the WIP model (WIP), and by simulation (sim). In general, the WIP model estimates the expected waiting times in the output queues reasonably well, regardless of the TBS or the number of devices. The maximum relative error is less than 15% and in most cases, it is less than 10%. Also, the absolute error of the WIP model is very small, less than 6 seconds in all cases. The results agree with our earlier claim; that is, the expected waiting times in the output queues decrease as the TBS increases. As the TBS increases, the total workload (the number of unit loads moved by the handling system per time unit) decreases since the throughput requirement of each part type and the number of devices is fixed. Thus, the expected device utilization decreases, which decreases the expected waiting times in the output queues. In comparison to SFDA, the results obtained by the WIP model remain reasonably close to the simulation results. However, SFDA underestimates the expected waiting times in the output queues and the differences become larger as the number of devices increases (and the speed of the devices is reduced proportionally at the same time). This confirms the observation made earlier by Srinivasan and Bozer [19], who stated that using a smaller number of faster devices results in less expected waiting times in the output queues than using a larger number of proportionally slower devices. 5.3 Expected Device Utilization The expected device utilization serves as an important measure to determine the number of devices. (Recall that the expected device utilization should be less than 1.0. to meet the throughput requirement.) In Table 3, we compare device utilizations estimated by the WIP model and by simulation for the TBSs of 1, 5, and 10. Note that 17

TBS =1 2 ~F111~- maL: _ --;~- O mgl=WIP 0.8........ Q.. ^:':::;:..-..... I sim CL Sim o 0.0 0.4 C 0.2 1 2 3 4 5 6 7 8 9 10 11 station no. TBS=5 0.6 0.6 0.2 0.0 1 2 3 4 5 6 7 8 9 10 11 station no. Figure 4: Expected waiting times in the output queues, layout 1 with one device 18

TBS=1 1.2 = r'8'!?? I | ^; i; Omgl o 0.6 sim E o~0.2 0.0 1 2 3 4 5 6 7 8 9 10 11 station no. TBS=5 0.8 0.6' C o 0.4 1 2 3 4 5 6 7 8 9 10 11 station no. TBS=1 0 0.8 0.6cr C 2 0.0 1 2 3 4 5 6 7 8 9 10 11 station no. Figure 5: Expected waiting times in the output queues, layout 1 with two devices 19

on waiting time in the output queue waiting time In the output queue waiting time in the output queue 0 0 0 0 0 0 0 0 0 0 0 - o o o o o _ o o o b r _ o o _ _ n o ro ^. 0) bo o o io v b> bo o o v oo ro C, — I.............. %,. |...,.. ~~~- - ~- - -........ -.....,.-. I.................... M 0 I M Mj I c,, 0D P | \ 0 0 t X 1'...........,...-.-7 Cb Cb Oc

Table 3: Expected device utilization, layout 1 transfer batch 1 device 2 devices 4 devices size of job 6 WIP simulation WIP simulation WIP simulation 1 0.8536 0.8507 0.8536 0.8494 0.8536 0.8494 5 0.7150 0.7130 0.7150 0.7112 0.7150 0.7101 10 0.6972 0.6901 0.6972 0.6891 0.6972 0.6885 the expected device utilization estimated by the WIP model is the same regardless of the number of devices since we adjusted the speed of the device and the pickup/deposit times to maintain the same expected device utilization as the number of devices varies. The results in Table 3 indicate that the WIP model slightly overestimates the expected device utilization. However, the errors are less than 2% in all cases. 5.4 Total WIP in the System We use the data shown in Table 4, which is designed to test the cases where the expected device utilization is higher than 0.9. We use six devices and increase the TBS for each part one at a time. The results are shown in Figure 7 for each part type. (The results for part types 4 and 5 are not shown since they are almost identical to those obtained for part type 1.) If the device utilization is high (> 0.9) such as in Figure 7a and 7d, the WIP model estimates total expected WIP in the input queues quite accurately, while it underestimates total WIP in the output queues. This contradicts the observations made in Section 5.1. However, it can be explained as follows: Since the throughput requirement of part type 1 (7a) represents only a small portion of the total throughput, increasing the TBS of part type 1 does not noticeably increase the expected number of parts in a unit load arriving at the input queues. In addition, we observe in Section 5.1 that the WIP model estimates the expected waiting times in the input queues more accurately when the expected number of parts in a unit load carriving at the input queues is smaller. Hence, the WIP model estimates the expected total Table 4: Job routes and throughput requirements #2, layout 1 art type parts/min Job Route 2.L1 1 0.01 1 - 5 - 6 - 9 - 11 - 10 - 3 2 0.03 1 - 7. 5 - 8 - 10 - 11 - 3 3 0.08 1 - 6 - 7 10 9 4 4 0.01 2 - 5 7 - 8 11 - 6 - 3 5 0.01 2 7 9 8 - 6 - 11 - 4 6 0.02 2 - 5 - 8 - 9 - 10 - 4 Device speed:from 100 (with I device) to 20 (with 4 devices) distance units/min Pickup/deposit time:is neglegible. 21

(a) part 1 (0.01 parts/min) (b) part 2 (0.03 parts/min) 60- 60 — 50 50 total(sim) total(WIP) 40 40 total(sim) g 20- V^. |P^ - 20- - i(sim ) total(WIP).30 0 30 - I. input IP)' 20 output(sim) 20 input(sim) 10 input(WIP, sim) output(WIP) 10 10.oinput(WIP, sim) 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS TBS 0.9968 2 utilization of the device > 0.9399 0.9968 > utilization of the device > 0.7656 (c) part 3 (0.08 parts/min) (d) part 4 (0.02 parts/min) 60 — _ 60total(WIP) 50 - 50 total(sim) total(sim) 40 - 40 o- 30-. 30 input(sim)' 2. 20 input(WIP, sim) 20 - 20 - ou put(sim) 10 10 - output(WIP, sim) 4 output(WIP) 0 2 4 6, 8 10 12 0 2 4 6 8 10 12 TBS TBS 0.9968 > utilization of the device > 0.6139 0.9968 > utilization of the device > 0.9275 Figure 7: Expected total WIP in the system 22

WIP in'the input queues quite accurately. On the other hand, increasing the TBS of part type 1 reduces the total workload for the handling system only by a small amount. Therefore, the device utilization remains above 0.9 even when the TBS is increased to 10. It is well known in heavy traffic theory that when utilization is very high, the margin of error for an approximate model becomes large. Due to the above reasons, total WIP in the output queues estimated by the WIP model results in larger absolute errors. If the device utilization is less than about 0.9, such as in Figures 7b and 7c, the total WIP in the input queue is overestimated, while total WIP in the output queue is close to the simulation results, which is in agreement with our previous observations. In general, if the device utilization is high, the error in the total WIP in the output queues "dominates" the error in the total WIP in the input queues, resulting in an underestimation of the total WIP. Otherwise, the error in total WIP in the input queues "dominates" the error in the total WIP in the output queues and, consequently, the total WIP is overestimated. However, regardless of the device utilization, the WIP model captures the changes in total WIP quite accurately as the TBS increases. Note that the expected total WIP in the output queues is almost "flat" as the TBS becomes large. That is, as the TBS increases, the increase in total WIP in the input queues surpasses the decrease in total WIP in the output queues. It indicates that there is an upper bound for the optimal TBS. In summary, the WIP model performs best when the TBS is small and the device utilization is not too high (less than approximately 0.85).It also captures the behavior of the expected total WIP in the system as a function of the TBS over a wide range of parameter/TBS values. 6 DETERMINING THE "OPTIMAL" TRANSFER BATCH SIZE In this section, alternative objectives are considered to minimize the operational cost of a manufacturing system within the context of transfer batch sizing. These objectives are used with several constraints to formulate optimization problems. Subsequently, we compare the solution obtained by the WIP model with simulation results. 6.1 Alternative Objectives One simple cost function is the one based only on the expected WIP cost. In the constraints, the utilizations of both the workstations and the devices should be less than 1.0 to avoid infeasible systems. However, since we assume that a workstation always has sufficient processing capacity, only the device utilization is included as a constraint. Also, there is an upper bound on the TBS of each part type, since the 23

volume or weight capacity of a device is limited. The resulting problem is formulated as follows: (P1) MIN CwWIPY8s s.t. p 1 Qk < UBk k=1,...,JT Qk: positive integer. where Cw is the unit cost of WIP in the system per time unit and UBk is the upper bound on the TBS of part type k. Note that, if necessary, two different cost coefficients can be used for the expected total WIP associated with the processors and the handling system. The expected WIP associated with the handling system consists of WIPTLt and the expected number of parts being handled. To obtain the expected number of parts being handled, the expected number of parts in a unit load, PU, is necessary, which is obtained as EM1 AiE(Ji)/AT. Thus, the expected number of parts being handled is given by PU oaf ND. Also, the expected WIP associated with the processors are obtained by subtracting the expected WIP associated with the handling system from the expected total WIP in the system. Hence, the objective function can be rewritten as (P2) MIN Cwi( WIPTS - WIPTt - PU. cf - ND) + Cwo( WIPu't + PU. a. ND) where Cwi is the unit cost of WIP associated with the processors per time unit and Cwo is the unit cost of WIP associated with the handling system per time unit. In Problems 1 and 2, the number of devices is assumed to be given and fixed. However, the number of devices is also an important design variable since the number of devices is likely to affect the expected WIP level. In combining the fleet-sizing problem with the transfer batch sizing problem, the unit cost of a device should be converted to its annual (or monthly) equivalent cost, since the initial investment in a device is a non-recurring cost. Also, the capital investment required for the devices should be within the budget constraint of the firm. The resulting problem can be formulated as follows: (P3) MIN Cw WJIPTY8 + CDND s.t. p<l Qk UBk, k = 1,..., JT CDND < B " Qk: positive integer. where B is the available budget for the devices, and CD is the equivalent cost per time unit per device. (Maintenance costs and other operational costs associated with a device can be included in CD.) The cost associated with each space in the input or output queue may also be included in the objective function (as in Grasso and Tanchoco [10]). Since we assume 24

infinite queue capacities in this study, we will not address the space cost. However, if necessary, the space cost can be included as part of Cwi and Cwo in Problem 2. 6.2 Preliminary Numerical Results To demonstrate the type of solutions obtained from the WIP model, Problem 1 is used with Cw = 1 and UBk = 10 for all k. Layout 1 is used with the data in Table 4 and the number of devices is varied from one to six devices. (This time, we do not adjust the device speed and P/D time.) The TBSs are obtained through exhaustive enumeration; i.e., we consider all possible TBSs and use the WIP model to estimate the resulting expected WIP. In Figure 8, ten best solutions determined by the WIP model are shown as vectors, where the kth component represents the TBS of part type k. Also, simulation results obtained for each vector are presented in Figure 8 along with linear regression lines based on the method of least squares. We cannot claim that the solutions determined by the WIP model are the actual optimal solutions since the WIP model itself is an approximate model. However, in section 6.3, we evaluate the solutions obtained from the WIP model and show empirically that (within the solution space we could search) they are optimal or near-optimal solutions. First, the best solution obtained by the WIP model is the best or second-best solution according to the simulation results. Also, although we incur some errors in estimating the absolute WIP levels, the WIP model accurately captures the relative changes in total WIP as a function of the TBSs. Second, the trends in objective function values show "flatness" in both results, regardless of the number of devices. For example, the difference between the objective value of the best solution and the objective value of the 10th best solution is less than 5%. Therefore, any of the 10 solutions may be acceptable for practical purposes. To further check the sensitivity of the objective function,.we randomly generated five new solutions, which meet the throughput requirements and are in the interval of the best solution ~ 2 parts. The simulation results with five randomly generated solutions are shown in Figure 9, where the first five TBSs are five best solutions shown in Figure 8, while the last 5 TBSs are those generated randomly and sorted by ascending order of their objective values. The results suggest that the objective function values vary significantly, especially when the number of devices is large. For example, with five devices, the total expected WIP in the system with TBS (1,1,2,1,1,1) is about 40% more than the total expected WIP with the TBS (1,2,2,1,1,1), although the two TBSs differ only in part type 2. Hence, our preliminary results indicate that although the objective function may be "flat" around the "optimal" solution, it may still be sensitive to small changes in the TBS of certain part type. On the other hand, in Figure 9, the objective function is less sensitive when smaller number of devices is used. This can be explained as follows: when the number of devices is small, the TBS 25

total wip in the system (no. of parts) total wip in the system (no. of parts) Cl Cl Cl C OC 0 C CD CD O _ ).r 0) D o 0).b 0) o 0 3,4,4,4,4,3 7,8,8,7,7,7,' I_* I 3,4,4,4,44r4 7,8,8,7,8,7 3,4,4,3,4,4- 6,8,8,7,8,7 4,4,4,4,4,3-1 I 7,8,8,8,7,7 1. 1 0 E P 3,4,4,4,3,4 | 0 6,8,8,7,7,7 0 (.I -4 -a, -i a - 4,4,4,4,3,- 6,8,8,8,7,7, 4,4,4,3,4 7,8,8,7,7, 0-'. 3 4,4,4,4,3,3.4 8,8,8,7,7,7 4,4,4,3,3, 7,8,8,7,7,~

total wip n the system (no. of parts) total wip in the system (no. of parts) C,~*TJ~~~~~~~~~~~~~~~~~~~C o5' I, a.,.,.. I.I e-4-\ * I 00' >l,2,2,2, g @ \2,3,3,2,2, v' O 1,2,2,2,2, 2,3,3,2,3, 2,2,2,1,2,- b 2,3,3,3,2,2 2 2 1 It 2 33,32, 2 2,2,2,1,2,2 b 2 3,3,3,2,3, |,a 0 0 \. CC 1,2,2,2, 2, 2,2,3,3,3,2 0,1\32 \ *2,2,3,3,2,i0 i s *.1 I i =I 0 0 2,2,2,3,2,2 3, 2,3,3,3,2 C)'n C \ % 2,2,2,1,3, 2,2,3,3,2,3

total wip in the system (no. of parts) total wip in the system (no. of parts) _Ot C 1aoI $ ~..~c oo 1,1,2,1,1,1 — c \' 1,2,2,1,1,- o 11,1,2,1.,1-' 1,2,2,1,2,1- \ 1,1,2,2,1,1 1,2,2,2,1,1 |o \\P I Cb c n ro AI' I,2,2,2,2, S 2,,,111 \" \ 1 *,,,122 \ co I 1,2,1,2,2,1- I, 1 2,2,2, ^ 1,2,1.2,2,1- ^\ ~0 1,1,2,2,2,2- II,2 1I,2, I1,1 1,2 2,2,2,1,2,1 <i 2,2,1,1,2,1 2,2,2,2,1,1 q 2,, 2 2,2,1,1,1,1 2,12,1,2, 2-

oq ~5t=~~~ ~ total wip in the system (no. of parts) total wip in the system (no. of parts) CD ~ i. I & o en o U1 O O o o o > I.... I t 1 3,4,4,4,4-, P 7,8,8,7,7,7 P 3,4,4,3,4, 9 7,8,8,,7,8, 734,4,4,4,4,41 p 1 6,8,8,,7,8, Q. 3,4,4,4,53, P 6,8,8,7,7,7 C CL UD a4 3 —4.4.3.- - - - - -- 6.8.8.7.8.7- - i ~ o'. I _ 4,5,3,4,4,,7 34,5,4,4,56,5- 7,6,8,8,7,9 I I 4,,,,, = 9, 6 4,5,,4,4,,- 7,98, 87,9, - 3, 4.5. 5. 5.4.5 \ 9.6,8,9,8,9, - o-*.________________________ ___ _ __ _ ________________J

total wip in the system (no. of parts) total wip in the system (no. of parts) | N 9 O 8 O Ne O U t > X RS w I. I. I. * I. I I' I' I' 2,2,2,2,2, P g 2,3,3,2,2, 2 I I 1,2,2,2,2 2 0 \ 2,3,3,2,3,2P I I \ 2,2,2,2,1,,21 3 2,3,3,2,2,1 ~ 0. 2,2,2,2,,2- 2,3,3,2,3 - - - - --- -- -i- ---- - -- -- --- - - ---- ----..m < o \ 2,3,2,2, 2, 2- 3,3,3,2,33- o 23,2,2,32,33 1, 3, 23,2, 3, to l IX I ~~~0i~~~~~~A I 2,3,2,3,2,- 2,3,4,3,3, 0 2,3,3,2,2, 0 3,3,4,3,2,3-, 2 1,3,3,2,3, 2,3,2,2, ^3~~1~~~ OP

o. total wip in the system (no. of parts) total wip in the system (no. of parts) o C. C0.. %)c C C c) C C. C) Ci U0 U1 0 U1 D - -' C C, CD,-& C) I I ~ I I'- 1,1,2,1,1,1- 1,2,2,1,,1'1 to. \\ Cb LI C),1,1,2,2,1,13 0 1,2,2,2,1,1 2,1,2,1,1,1-'_ 2,2,2,1,1,1' 0 0 ~-' I,I, 12,2,12,1 a I 1,2,2,1,1, a -I a. C a, 12,2,1,1,1- b 0 2,2,2,2,2,13Cl) e_ 2,2,3,3,3,2- q.. 2,3,2,3,2,3 - %, 3,1,2,1,3, 1,12,2,1,1,1. q h CTbC -iII ~ 0~I1

of each part type is generally large to meet the throughput requirement. Therefore, the absolute total expected WIP in the system is already high. Therefore, varying the TBS by 1 or 2 parts produces relatively small differences in the objective function values. Third, in Figure 8, the difference between the TBS of each part type in a given solution is only one or two parts, which may imply that there is no significant difference between the TBS of each part type in the "optimal" solution. We also observe in Figure 8 that part type 3, which has the largest throughput requirement, also has the largest TBS. To further investigate the effect of the throughput requirement on the solution, we tested the case with all the parts having the same throughput requirements as shown in Table 5, where the device speed and the pickup/deposit times are the same as in Table 4. We tested with 2, 4, and 6 devices and the results are presented in Figure 10, where the TBSs represent 1st, 5th, 10th, 15th, and 20th best solutions. The trends in the objective values ares similar to those shown in Figure 8. However, the TBS of each part type shows a larger variation. That is, the same throughput requirement does not necessarily result in the same TBS. This small experiment indicates that the throughput requirement is not the only parameter which affects the "optimal" TBS. For that reason, we need to perform sensitivity analysis on how other parameters may affect the optimal TBS. 6.3 Neighborhood Search To further test the quality of the solution determined by the WIP model, we simulated all the feasible solutions within the ~ 2 range of the "optimal" solution (determined by exhaustive enumeration using the WIP model). Subsequently, we simulated all such feasible solutions and ranked the resulting objective function values in ascending order. Then we compared the rank obtained from simulation with the rank obtained from the WIP model. The results presented in Figures A12, A13, and A14 in Appendix indicate that above two rankings are highly correlated (with correlation coefficients of 0.9 or larger). Scatter diagrams also support the above observation. Given that our main concern is to determine the good solutions, we compared the quality of the solutions determined by the WIP model and simulation. Table 6 summarizes ten best solutions obtained by the WIP model and the corresponding objective values obtained by simulation for those TBSs. Also, ten best solutions and objective values determined by simulation are presented. The last column shows percent errors relative to the WIP model. The "optimal" solution obtained from the WIP model is not always the best solution obtained from simulation results. However, taking into account that the error in the objective value is quite small (less than 5% in all test problems) and that simulation results contain random variation, we conclude that the WIP model leads to good solutions. 32

Table 5: Job routes and throughput requirements #3: Layout 1 part type parts/min Job Route 3L1 1 0.026 1 - 5 - 3 2 0.026 1 - 7 - 5 - 6 - 9 - 8 - 10 - 11 - 3 3 0.026 1 - 6 - 10 - 9 - 4 4 0.026 2 - 5 - 10 - 11 - 6 - 3 5 0.026 2 - 7 - 8 - 11 - 4 6 0.026 2 5 - 7 - 8 - 9 - 4 (a) no. of devices=2 58 56 WIP t 0 54 6 54 E 0 52 C50 1 0 —-......... -....-0 5S simulation 48 CI C' 4' C' C; C) C; C; C; CD ~ u) i CD Co TBS Figure 10: Solutions obtained with parts that have equal throughput requiremnents 33

Cb cr total wip in the system (no. of parts) 0 total wip in the system (no. of parts) tJI oi m oi G a) as X) ca cu o v * bo ro; o M ( ~ cn ~. -) -%) 0) 2_ __1_ _ _ _ _ _ _ 2,1,1,1,2,1, 2,2,1,2,2, 2,1,2,1,1,1- 2 2,2, 2,2, 2 20. I \ \ I? * \3I o 0 "~ — I ~' - 0' - 4,1,11,2,1- 0 1,1,2,1,2,1 2,2.1,2,3, 2

Table 6: Comparison of solutions obtained by the WIP model and simulation Best 10 solutions by the WIP model __Best 10 solutions by simulation Obj. value %error _ Rank T.B.S. Obi. value in simulation T.B.S. Obi. value 95% C.I. (col. 5-col.7)/col. 7 1 2 3 3 2 2 2 44.011 39.525 2 3 3 2 2 2 39.525 2.189 0.00% L 2 2 3 3 2 32 44.157 39.835 2 3 3 3 2 2 39.531 1.900 0.77% a 3 2 3 3 3 22 44.223 39.531 2 3 3 2 2 3 39.796 1.971 -0.67% y 4 3 3 3 2 22 44.271 40.238 2 3 3 2 3 2 39.835 2.402 1.01% o 5 2 3 3 2 23 44.412 39.796 2 4 3 2 2 2 39.971 1.329 -0.44% u 16 2 2 3 3 32 44.431 40.663 3 3 3 3 2 2 40.127 1.718 1.34% t 7 2 2 3 2 3 3 44.445 40.776 2 4 3 2 3 2 40.226 1.535 1.37% 8 3 2 3 3 32 44.456 40.315 3 3 3 2 2 2 40.238 2.078 0.19% 1 9 2 2 3 3 3 3 44.467 41.036 2 3 3 3 3 2 40.239 2.282 1.98% 10 2 2 3 3 2 3 44.504 41.042 3 2 3 3 3 2 40.315 1.511 1.80% Avg. 40.276 39.980 1 3 2 2 3 2 99.351 87.490 2 3 2 3 2 86.727 4.200 0.88% L 2 2 3 2 3 2 100.105 86.727 4 2 2 3 2 87.115 2.743 -0.45% a 3 2 2 3 3 2100.411 87.581 3 2 2 3 2 87.490 3.710 0.10% y 4 4 2 2 32 100.628 87.115 3 2 3 3 2 87.559 3.059 -0.51% o 5 3 2 3 3 2 100.730 87.559 2 2 3 3 2 87.581 3.567 -0.03% u 6 3 2 2 3 3 101.065 88.401 3 2 2 4 2 87.604 4.182 0.91% t 7 3 2 3 2 101.209 88.041 3 3 2 3 2 88.041 4.418 0.00% 8 3 3 2 2 2 101.482 88.973 2 2 2 4 2 88.073 4.313 1.02% 2 9 2 2 3 3 101.590 89.317 3 2 2 3 3 88.401 4.548 1.04% 10 3 2 2 4 2 101.637 87.604 2 3 2 4 2 88.552 4.196 -1.07% _ Avg. 87.881 87.714 1 4 4 4 4 3 62.501 56.374 33 4 3 4 53.596 4.345 5.18% L 2 3 4 4 4 3 62.548 56.085 3 4 3 3 4 53.761 5.693 4.32% a 3 3 4 3 3 4 62.646 53.761 2 4 3 3 4 54.195 5.617 -0.80% y 4 4 4 3 4 3 62.692 57.042 4 4 3 3 4 54.453 5.774 4.75% o 5 3 3 4 4 4 62.746 55.183 2 5 3 3 4 54.515 6.194 1.23% u 6 4 3 3 4 4 62.768 56.556 4 4 2 3 4 54.555 5.947 3.67% t 7 3 3 4 4 62.796 55.514 3 4 4 3 4 54.685 5.197 1.52% 8 5 4 4 43 62.847 57.287 2 4 4 3 4 54.717 5.220 4.70% 3 9 4 4 3 3 4 62.851 54.453 2 6 2 3 4 54.958 5.385 -0.92% 10 4 3 4 4 4 62.878 57.139 3 3 4 4 4 55.183 4.429 3.54% _Avg. _55.93911 54.462 _

6.4 Genetic Algorithm Although we used exhaustive enumeration to determine the "optimal" solutions in the preliminary results, needless to say it takes a very long time when the number of parts is large. To search the solution space more systematically and in a more efficient manner, we decided to apply a Genetic Algorithm (GA) which seems suitable for our problem structure. GAs are search algorithms developed by Holland [11] and his colleagues, based on the mechanics of natural selection and genetics. A simple GA is composed of three operations: reproduction, crossover and mutation. (Readers may refer to Goldberg [9].) The advantage of a GA is that it can handle complex objective functions, even discontinuous functions, which represent a major obstacle for classical optimization techniques. Also, the concepts are simple and easy to program yet powerful. The disadvantage of a GA is that it is not guaranteed to find the global optimal solution and the quality of the solution depends on the population size, crossover probability, and mutation probability. Also, some problems may require long computation times, especially if the objective function is time consuming to evaluate. We tested several variations of a simple GA to evaluate the quality of the resulting solutions. After testing various problems, we constructed a simple GA with "elitist reproduction" and "biased mutation." Elitist reproduction is a technique to pass over the best solutions from the previous generation to the next generation. Mutation is the occasional (with small probability) random alteration of the value of a string position. In the biased mutation, we alter the value of a string based on the current value of the string instead of altering randomly. For instance, if a string is picked to be mutated and it's value lies in the lower half interval of the feasible region, then the value of that string is altered to a random integer in the upper half interval of the feasible region and vice versa. We stop the algorithm either when it reaches the maximum number of iterations (1000 in our test cases) or the 15th current best solution is not improved for 50 iterations. With the above settings, the GA we developed obtained the same "optimal" solutions we obtained with exhaustive enumeration for all the test problems (see Table 7). 7 CONCLUSIONS We have demonstrated that the TBS affects both the expected WIP in the input queues and the output queues and proposed an analytical model to determine the "optimal" TBS. Subsequently, we have shown that the the "optimal" solution determined by the WIP model is comparable to solutions obtained by simulation. We are currently working on testing more problems and extending the application of the WIP model. We are testing the cases where all the parts are required to have the same TBSs and testing the performance of the WIP model under other than the 36

Table 7: "Optimal" solutions obtained by Genetic Algorithm I device 3 devices 5 devices Layout Enumeration G.A. Enumeration G.A. Enumeration G.A. I T.B.S. 7,8,8,7,7,7 7,8,8,77,7,7 2,3,3,2,2,2 2,3,3,2,2,2 1,2,2,1,1,1 1,2,2,1,1,1 Total WIP 110.79 110.79 44.01 44.01 31.54 31.54 2 T.B.S. 8,7,7,8,6 8,7,7,8,6 3,2,2,3,2 3,2,2,3,2 2,1,2,2,1 2,1,2,2,1 Total WIP 252.925 252.925 99.3507 99.3507 70.893 70.893 3 T.B.S. 11,11,11,11,10 11,11,11,11,10 4,4,4,4,3 4,4,4,4,3 2,2,3,2,2 2,2,3,2,2 Total WIP 160.88 160.88 62.5 62.5 42.9147 42.9147 Number of population = 50.. Crossover probability = 0.7 Mutation probability = 0.01 Elitist reproduction = 8%

FCFS dispatching rule. Also, we are testing dynamic transfer batch sizing, where a range of TBSs is used instead of a fixed value. In this paper, we assumed that the number of devices is given. However, the model can be easily extended to determine the "optimal" number of devices in conjunction with the "optimal" TBSs. 38

References [1] Bertrand, J. W. M., "Multiproduct Optimal Batch Size with In-Process Inventories and Multi Work Centers," IIE Transactions, Vol. 17, No. 2, pp. 157-163, 1985. [2] Bozer, Y. A., M. S. Cho and M. M. Srinivasan, "Expected Waiting Times in Single-Device Trip-Based Material Handling Systems," Technical Report 90-17, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, 1990, to appear in the European Journal of Operational Research. [3] Cho, M. S., "Design and Performance Analysis of Trip-Based Material Handling Systems in Manufacturing," Ph.D. Dissertation, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, 1990. [4] Chow, W. M., "Design for Line Flexibility," IIE Transactions, Vol. 18, o. 1, pp. 95-108, 1986. [5] Chow, W. M., "An Analysis of Automated Storage and Retrieval Systems in Manufacturing Assembly Lines," IIE Transactions, Vol. 18, No. 2, pp. 204-214, 1986. [6] Egbelu, P. J., "The Use of Non-Simulation Approaches in Estimating Vehicle Requirements in an Automated Guided Vehicle Based Transport System," Material Flow, Vol. 4, Nos. 1-2, pp. 17-32, 1987. [7] Egbelu, P. J., "Economic Design of Unit Load-Based FMSs Employing AGVs for Transport," Intl. Journal of Production Research, Vol. 31, No. 12, pp. 2753-2775, 1993. [8] Egbelu, P. J., "Concurrent Specification of Unit Load Sizes and Auto;mated Guided Vehicle Fleet Size in Manufacturing System," Intl. Journal of Production Economics, Vol. 29, pp. 49-64, 1993. [9] Goldberg, D. E., Genetic Algorithms, Addison-Wesley Publishing Co., New York, 1989. [10] Grasso, E. T. and J. M. A. Tanchoco, "Unit Load and Material Handling Considerations in MaterialIRequirements Systems," Material Flow, Vol. 1, pp. 79-87, 1983. [11] Holland, J. H., Adaptation in Natural and Artificial Systems, The University of Michigan Press, MI, 1975. 39

[12] Kuehn, P. J., "Approximate Analysis of general Queueing Networks by Decomposition," IEEE Transactions on Communications, Vol. COM-27, No. 1, pp. 113126, 1979. [13] Nozaki, S. and S. Ross, "Approximations in Finite Capacity Multiserver Queues with Poisson Arrivals," Journal of Applied Probability, 15, pp.826-834, 1978. [14] Ross, S. M., Introduction to Probability Theory, Academic Press Inc., FL, 1985. [15] Solberg, J.J., "The Optimal Planning of Computerized Manufacturing Systems: CAN-Q User's Guide," School of Industrial Engineering, Purdue University, West Lafayette, IN, 1980. [16] Solberg, J. J., "Capacity Planning with a Stochastic Workflow Model," AIIE Transactions, Vol. 13, No. 2, pp. 116-122, 1981. [17] Solot, P. and J. M. Bastos, "MULTIQ: A Queueing Model for FMSs with Several Paallet Types," Journal of the Operational Research Society, Vol. 39, No. 9, pp. 811-821, 1988. [18] Srinivasan, M. M., Y. A. Bozer and M. S. Cho, "Trip-Based Material Handling Systems: Throughput Capacity Analysis," IIE Transactions, Vol 26 No. 1, pp. 70-89, 1994. [19] Srinivasan, M. M. and Y. A. Bozer, "Which One is Responsible for WIP in Manufacturing: The Workstations or the Material Handling System," Intl. Journal of Production Research, Vol. 30, No. 6, pp. 1369-1399, 1992. [20] Yao, D. D. and J. A. Buzacott, "Modeling the Performance of Flexible Manufacturing Systems," Intl. Journal of Production Research, Vol. 23, No. 5, pp. 945959, 1985. [21] Yao, D. D. and J. A. Buzacott, "Models of Flexible Manufacturing Systens with Limited Local Buffers," Intl. Journal of Production Research, Vol. 24, Nlo. 1, pp. 107-118, 1986. [22] Yao, D. D. and J. A. Buzacott, "Modeling a Class of Flexible Manufacturing Systems with Reversible Routing," Operations Research, Vol. 35, No. 1, pp. 8793, 1987. 40

APPENDIX Table Al: Job routes and throughput requirements #1, layout 2 part type parts/min Job route 1.L2 1 0.027 11 - 8 6 - 10 -11 3 2 0.041 1 - 4 - 9 - 7 - 14 - 17 - 2 3 0.041 2 - 14 1 - 10 - 12 - 13 - 3 4 0.055 3 - 16 - 18 - 15 17 - 2 5 0.027 3 1 1- 8 - - 6 - 13 3 Device speed:from 35 (with 3 devices) to 15 (with 7 devices) distance units/i P/D time = 5.16 (with 3 devices) to 12 (with 7 devices) secs Processor utilization=0.75 *, j:;:::::;:'-;:::;::;::':::i:.:.....i...:.g.....,H............. i: _ _.:^ ii. _ __..t. _ _ I M t t l A ft M M 1 | 6 _ M _: _1 (II I/O station fl1 proce ssing station *' 51fFigure A I' Layout 2 41:::: - - it $ii:: - 5;:^:.:,:::: F —. t A-m- AB F Il Layou: |1 >;::::..:1R 1 3..;. -14i I ~-:L: mI:E:~~.......................rltii~~j~.i~i~i`;i::~~~iii~i f zijr'ljr mE..irjli.tli~iiiiriiiiitiiiri 7:;rYYYIYYYY~...... i — iA 17 TUT' HT:............. Each grid represents one distance unit. C 1/0 station 1~ processing station Figure A 1: Layout 2 41

(a) station 4 (b) station 5 60 6OO,~. ~~~~~~WIP 58 0 sim7 180 1 Sim50s ——,, —- sim / el. ~ sim3 Cr 400 J 56 40 c 0. ~S e *.***...~*5 300 c 54 -B — WIP -— ee —- 200 * — ~ — sim7 2 aJ — sim 5 52 CMm - - sim3 100 0 2 4 10 12 0 2 4 6 8 10 12 TBS of part 5 TBS of part 5 (c) station 6 (d) station 7 200 62 - - WIP ------- sim7 6"" 150 ----- sims g Iso - - sim3 r Cr X58| 100 5 c C e e ^ji^^^i 54- WIP E 50 E — 4 — sim7 _c c 52- - sim3 0-.-.. 0-, -I-, -, - - 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS of part 5 TBS of part 5 Figure A2: Expected waiting times in the input queues, layout 2 42

(e) station8 (f) station9 200 60 WIP WIP * +. —.. —-" sim7. e- sim7 = =4.sim3 e 150 * sim3 s a' 0' e 100=| X 0 F 56 00. 562 __.68 1 10 2 4 6 8 1 100 -"' -. 54 C C E5 5 0 E 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS of part5 TBS of part5 (g) station 1 0 (h) station 1 1 38 200 WIP WIP ---- sim7 "" sim7 ssims:~.............. sims g 36 --— sm3 1 sim3 34- e 100 E E = 32- s 50 30 0 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS of part5 TBS of part5 Figure A2: (contd.) Expected waiting times in the input queues, layout 2 43

(i) station 2 (j) station 1 3 60- 120 - WIP -; WIP'-*-...-.sim7 -------- sim7 5 0 54 2 60 C C E..E 52 40 C C Co. "^- sim7o;...-.- sims 50 sim32 =... sim3 0 2 4 6 8 10 12 0 2 4 6 8 10 12 (k) station1 4 (1) station1 5 341 28 -CWIP 1 "- WIP Q. 56- 80v 32O.......................... -.. sim S 6,C ~~~~~~~~~~~C 0 2 4 6 8 1012 0 2 4 6 8 10 TBS of part5TBS of part5 E E 26- 20 - (U'a C' 24 0 ~, \.,.... 0 2 4 6 8~10 12 0 2 4 6 8 10 12 TBS of part5 TBS of part5 Figure A2: (contd.) Expected waiting times in the input queues, layout 2 44

(m) stationl 6 (n) stationl 7 46 30-- WIP - WIP — sinr7 -- sim7 44 ------ sim5 ---- sim?- sim3 sim3 42 i 26 C 6) 0 O a O O OB a O 40 24 -~. " E E 38 22 *3..3, C - 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS of partS TBS of part5 (o) station 1 8 47WIP ------- sim7 45 -- sim5 ---- sim3 43 -c E 41 - e^^:^ 1. E, 39c: 37 -, -,10 20 2 4 6 },8 10 12 TBS of part5 Figure A2: (contd.) Expected waiting times in the input queues, layout 2 45

-1-;: waiting time in the output queue waiting time in the output queue waiting time in the output queue ~ Pi W O O I rr P o rv r - c. I.,... I l. *...a,.,..._ c^U c CO'cO ODO I? * O_..o. - - - - - - - -- - - - - - -,. QC Vn - - _ _ - -------- ------ co OD s CDc C

"T3 orq;>.~ waiting time in the output queue waiting time in the output queue waiting time in the output queue 0 —' IX) 0 bn 0 - ro C) 4 n O0 N - 0' 0 Cb'0 0. cn 0 00_ o _. o =. o_..- o c 0O' "Cb -4, ct ) =. eL 3 C'b

~ m B sim 10 TBS=5 or8 oa1 2 3 4 5 6 7 8 9 10 11 12 13 14 1516 17 18 station no. ~ _______6TBS= 1 3 0.C ~ 4 E2 4, ~ S 1 2 3 4 5 6 7 8 9 10 11 12 131415 1617 18 station no.:3o~ ~ TBS=5 4.48 _='c 2 V 1 2 3 4 5 6 7 8 9 1011 12131415161718 station no. 6igue EptTBS=10 6 4' 0 3E O 2 1 2 3 4 5 6 7 8 9 10 11 12131415161718 station no. 48

(a) part 1 (0.027 parts/min) (b) part 2 (0.041 parts/min) 100 120 total(WIP) 80- total(WIP total(sim) S * 60:inp total(sim)W 8020 Fg sD _Wnput( s i) 1 200. oa(I)/ l120 20 outpt(WIP) output(sim) utput(sm) 0 *........ 0::: - -— _:.^:-'^.:.:t^: O0-'- m ~ m * m * * O- 0 0 2 4 610 12 0 8 10 12 TBS TBS 0.8677 > device utilization > 0.7488 0.8677 2 device utilization > 0.6634 (c) part 3 (0.041 parts/min) (d) part 4 (0.055 parts/min) 120 120 100 total(WIP) 100 t 8049totalim)'' 8total(sim) total(sim), ci * -^'input(W 20- 20 utput(WIP) Otinput(sim) output(WIP) output TB^ TBS 0.8677 > device utilization > 0.7171 0.8677 > device utilization ~ 0.6529 (e) part 5 (0.027 parts/min): same trend as in graph (a) Figure A6: Expected total WIP in the system, layout 2 eith 7 devices 49

Table A2: Job routes and throughput requirements #1, layout 3 part type parts/min Job route 1.L3 0.02 1 - 4 - 3 - 6 2.2 0.08 1 - 7 - 6 - 5 - 8 - 2 3 0.06 1 - 5 - 7 - 2 4 0.04 1 - 8 - 3 - 4 - 2 5 0.07 1 - 3 - 7 - 4 - 6 - 8 5 2 Device speed:from 270 (with 5 devices) to 150 (with 9 devices) distance units/min P/D time = 8.34 (with 3 devices) to 15 (with 7 devices) secs Processor utilization=0.75 *We changed station label in the original layout so that stations 1 and 2 become I/O stations. (a) station 3 (b) station 4 80- 80 -a WIP WIP 70- --- sim9 70- -. sim9............... sim7.........- -..... sim7 40.. sim57 sim ~.- -' o 2 4 6 8 o 12 2 4 6 8 12 TBS of part 5 TBS of part 5 Figlite A7: Expected waiting times in the input queues, layout 3 50 404 40E E 30-*j 30 C C 20 20 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS of part 5 TBS of part 5 Figurie A7: Expected waiting times in the input queues, layout 3 50

(c) station 5 (d) station 6 40- 50 WIP a- WIP 35s (e) station 7( station 8 — 4 —-- sim9 —-- sim9l 3 -0-40 sims 4-6 — sim5 si 30 S = C5 C 5 Ec c'" * 20 -10 10..,~,o. — 2i i 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS of part 5 TBS of part 5 (e) station 7 (f) station 8 40 40 WIP a WIp _ —_ sim9 7 sim9 ------ -- sim 7.............. S W -— 4 —- simS — 4 — simS - 30- - 30 0.0 20 20 E E 10 - - 10 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS of part 5 TBS of part 5 Figure A7: (contd.) Expected waiting times in the input queues, layout 3 51

TBS=1 1 2 WIP station no. TBS5sim 0 C 4 23 2 El 1 1 2 3 4 5 6 7 8 station no. TBS-15 3 0 o T 0 CD 1 2 3 4 5 6 7 8 station no. Figure A8: Expected waiting times in the output queues, layout 3 with 5 devices 52 J~

o5 > waiting time In the output queue waiting time in the output queue waiting time in the output queue Cb c -.0 -n' 0 O L e- IV "CIE I I I Cb cn- co co 0C c<

TBS-1 12 WIP:= I Sim 10. 0. 0 45 2 1 2 3 4 5 6 7 8 station no. TBS-5 4 0 53 C2 C'0 1 2 3 4 5 6 7 8 station no. TBS=1 0 6 0 3 2 E *1 1 2 3 4 5 6 7 8 station no. 54

(a) part 1 (0.02 parts/min) (b) part 2 (0.08 parts/min) 40 60 total(sim).... \:.'tota(W.IP) s.| 50- total(WIP. 30 yM*c~ 4 |40 - ~~1 /~^....;~t v }i40 total(sim) ~ 20 input(sim) o 30 bt~ ~ ~ ~~~~~~~J. fS^ " input(WIP 1PE I.^ nput(WIP) nPut(sim) C 1 20 output(sim) e 10 output(WIP) 10 output(WIP) output(sim) 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS TBS 0.9266> device utilization 2 0.8726 0.9266? device utilization > 0.6803 (c) part 3 (0.06 parts/min) (d) part 4 (0.04 parts/min) 50- - 50 total(sim) total(sim) 40"..^40. 1 ^^^'"WP)|e.....^ total(WIP) totat(WIP),:, t. 30-'. 300 input(sim Iin^ inoutput(sim ) output(WIP) u-.P.|. |... -,..,..output(WIP) 0 2 4 6 8 10 12 0 2 4 6 8 10 12 TBS TBS 0.9266> device utilization > 0.8409 0.9266> device utilization > 0.8116 (e) part 5 (0.07 parts/min): same trend as in graph (b) Figure All: Expected total WIP in the system, layout 3 55

Layout 1: 3 devices (Correlation coeff.=0.9432) 4000 - -^' -. - - -, -_., ~' J -., - -. - -- - - 3r 2500 --.. - - e iE lo 12000 -w-.,- - ~5 0 0 -- --- -- -.,_,, r — 0 500 1000 1500 2000 2500 3000 3500 Rank by the WIP model Figure A12: Ranks by the WIP model and simulation, layout 1 56

Rank by simulation 0 0 c 0n 0 0 0oo 0 I.=I 1%" Of o ~ -- ~ ~ ~ - " - - -.,..- -4- -- 0 -- lg*%^I,; )ji I PA, 0 --'..j*"(^'i~.' * 0 CA) Ig e Joell;0 o lull \,.,. g,..'~~~I) ~ ~ I -I, 0o ~r3 3."'*!*;~' o.C... 0.. Dg ( I *^ 01 iJ o 09, ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~~~~~I I; 0D I (O i;3(, s_ rrl'Iri~~~~~~~~~~~~~~~~~~~

Layout 3: 3 devices (correlation coeff.=0.8932) 2000 - 1600 - - -.= -.-. "-'-.. ~-~ 1600............................... e... - ~ 20 -. -- -- - ~..' -..' -- -..i- i. -. i. - - * -. -.o. -".' *'~ I s' * -' -''.''' "'''-'I. -a.-..: ".-.. -.- -. - 1 0 4008001200160 40l 400 0 106 0 r r r r5

UNIVERSITY OF MICHIGAN 1 311 I I11111111 39015047350643