EXPECTED WAITING TIMES IN SINGLE-DEVICE TRIP-BASED MATERIAL HANDLING SYSTEMS Yavuz A. Bozer Myeon-Sig Cho Mandyam M. Srinivasan Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 90-17 July 1990

Expected Waiting Times in Single-Device Trip-Basted Material Handling Systems Yavuz A. Bozer Myeon-Sig Cho Mandyam M. Srinivasan Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Abstract In an earlier paper we presented an analytical model which can be used to estimate the expected device utilization and the expected station cycle times (i.e., the average time between two successive arrivals of a device at each station) in a manufacturing system served by trip-based material handling devices. Assuming that empty devices are dispatched according to the Modified First-Come-First-Served rule, the model provides the expected device utilization, which the analyst can use to determine whether the system is stable; that is, whether a proposed handling system meets the required throughput. In this paper we present an analytical model to estimate the expected waiting times for move requests that occur in single-device, trip-based handling systems such as cranes, freight elevators, microload AS/RS, unit load tandem AGVs, etc. The model not only represents a conceptual contribution but it also considerably enhances the original model from a practitioner's viewpoint since expected waiting times (and the associated mean queue lengths) can play an important role in deciding whether the system performance is "acceptable" even if the device utilization indicates that the system is "stable."

1. Introduction Material handling technology has changed dramatically during the last decade, mostly due to the introduction of computers and automation. White [1987] states that "the changes of the past will seem small in comparison with the changes anticipated in the next decade." According to Industrial Engineering [1986], the sales of nonautomated material handling equipment produced by U.S. manufacturers alone will grow 8. 1% per year to a total of $12. 1 billion in 1994. The significance and role of material handling systems are understood better today and, both in research and practice, more time is being devoted to the design and analysis of handling systems. However, primarily due to a lack of general-purpose analytical design models, many handling systems used today are designed through simulation models. Although simulation is a powerful analysis tool, it is often an expensive and time consuming undertaking. In an earlier paper (Srinivasan, Bozer and Cho [1989]), we presented an analytical model to estimate the throughput capacity of trip-based material handling systems for a wide range of handling and layout alternatives. In this paper, we present an analytic model to estimate the expected waiting times experienced by move requests that occur in single-device, trip-based handling systems. The performance of the analytic model is evaluated through simulation. There are several examples of single-device, trip-based handling systems. Unit load automated guided vehicles (AGVs) in tandem AGV systems, the storage/retrieval (S/R) machine in microload automated storage/retrieval (AS/R) systems, industrial robots, freight elevators, and cranes are good examples of such systems. Although the authors do not classify it as such, the interested reader may refer to Tompkins and White [1984, p. 143] for a fairly extensive list of single-device and multiple-device trip-based handling equipment. In the paper, a container or load moved by the device is referred to as a "job" or "move request." Trip-based handling systems where the device can concurrently move multiple jobs with different destinations are beyond the scope of this study. Tractor-trailer AGV systems and people moving elevators, for example, fall in this category. (Note that with such systems the definition of a "trip" may take several forms.) 1.1. Problem Environment Consider a 4-station trip-based material handling system depicted in Figure 1, where the input/output (I/O) stations are represented by stations 1 and 2, and the processor stations are denoted by stations 3 and 4. There is an input queue and an output queue for each station 1

including the I/VO stations. We assume that all the input and output queues have sufficient capacity so that the device or the processors seldom get blocked. Departure U Arrival input qInpute I Output queue queue.^w queue Output Input E queue 8 queue Input - Output queue queue Output Input queue queue - - - - - Empty travel - Loaded Travel Figure 1. Typical trip-based handling system. Jobs from outside the system enter through one of the I/VO stations and, when all the operations have been completed, they exit through one of the I/O stations. An incoming job arrives directly at the output queue of an I/O station while an outgoing job is deposited at the input queue of an I/VO station where it is assumed to exit from the system instantly. That is, no processing takes place at the VO stations. A processor station represents either one machine, or a group of machines (a cell), or a department. Jobs to be processed are removed from the corresponding input queue and later, when processing is complete, they are placed in the corresponding output queue without delay. (Material handling needs within a station is beyond the scope of our study.) Although certain job characteristics may change after processing, we assume that as far as the material handling system is concerned, flow is conserved at each processor station. The dispatching rule used for the device when it becomes empty is the Modified First-ComeFirst-Served (MOD FCFS) rule introduced by Srinivasan, Bozer and Cho [1989]. Under this rule the device, upon delivering a job at the input queue of station i, first inspects the output queue of that station. If one or more move requests are found, then the device is assigned to oldest move request. If the output queue of station i is empty, the device serves the oldest move request in the 2

system (regardless of its location). However, if the device finds no move requests in the system, it stays idle at station i until a job is completed at one of the stations. Using simulation, Srinivasan, Bozer and Cho [1989] show that the MOD FCFS rule is comparable in throughput performance to the Shortest-Travel-Time-First (STTF) rule. 2. Literature Review We first review previous studies that fall within our definition of trip-based handling systems. Subsequently, we review a related area, namely, polling models. 2.1. Trip-Based Handling Systems To the best of our knowledge, in the manufacturing arena, there is no general-purpose analytical model which can be used to determine the expected waiting times in trip-based material handling systems. Those that are reported in the literature have certain shortcomings and they are developed for specific types of material handling equipment, primarily microload AS/R systems and (pick&drop) AGV systems. Consider first the microload AS/R system. Chow [1986a] presents an approximate analytical model to predict the utilization of the S/R machine and the expected waiting time by modeling the system as an M/G/1/FCFS queue. That is, the arrival of the move requests (from the stations) are assumed to follow a Poisson process while the S/R machine has a general service time distribution. Assuming that the S/R machine never finds the destination buffer full, approximate values for the first and second moments of the S/R machine service time are obtained from the flow matrix by a simple probabilistic argument. The S/R machine is assumed to serve each move request according to this distribution regardless of the actual origin and destination of a move request (and the position of the S/R machine before it begins service). The performance of the approximate model is not fully explored in the paper. Furthermore, the FCFS rule leads to unnecessary empty travel for the S/R machine. In a subsequent paper, Chow [1986b] uses a simulation model to evaluate alternative dispatching rules for the S/R machine. In the context of an industral robot or microload AS/R systems, Toro-Ramos and McGinnis [1990a and 1990b] study the performance of a single-device system where the capacity of both the. input and output queues is finite. While the first study [1990aJ assumes that a full input queue blocks the sending station, the second study [1990b assumes that each station has a temporary storage area which is used when the S/R machine finds the input queue becomes full. In both studies, the authors estimate the expected device service time per job and the expected waiting time for the move requests. In the first study, they approximate empty device travel by a model 3

suggested in Egbelu [1987]. That is, the empty device dispatching rule is not explicitly taken into account. In the second study, the authors use an iterative scheme to obtain the empty device travel time. To estimate the expected waiting time for the move requests, they use a network of queues with a central server station, which has certain limitations as described later in this section. Consider next AGV systems. Relative to microload AS/R systems (where a single S/R machine serves a set of workstations), AGV systems are generally more difficult to analyze since all stations are served by a fleet of AGVs. However, due to the relatively large number of current and potential AGV applications in manufacturing, AGV systems have received considerably more attention in the literature. We will limit our discussions to AGV studies that are concerned with or applicable to single-vehicle systems. A new concept for designing AGV systems is suggested by Bozer and Srinivasan [1988]. The authors propose a tandem AGV system which is based on partitioning all the stations into nonoverlapping, single-vehicle loops, thereby eliminating possible congestion. They develop an analytical model to estimate the throughput capacity of a single vehicle serving a set of stations under the first-encountered-first-served (FEFS) rule as described by Bartholdi and Platzman [1985]. With FEFS, an empty vehicle continues to travel and polls each station according to a predetermined sequence. The vehicle serves the first job that it encounters while polling. This is a decentralized rule as opposed to FCFS, STTF, and MOD FCFS which are centralized dispatching rules. That is, with FEFS, the vehicle needs only local information in "deciding" which move request to serve next. With the other dispatching rules, however, the vehicle generally needs to "know" the oldest or closest move request in the system. Hodgson, King and Monteith [1987] develop a heuristic empty vehicle dispatching rule for a single-vehicle system. This dispatching rule, labeled "rule", is based on certain characteristics they observed in an analytical model that was developed for very simple systems (where the maximum number of stations is equal to four and the buffer space for each output queue is limited to one). Although the rule is truly dynamic in the sense that the destination of the empty vehicle is reevaluated at every station it passes, three scaling factors are required for reevaluation. (Each scaling factor is determined subjectively.) In the study, the performance of "rule" is tested against the Vehicle Looks For Work (VLFW) rule, which is equivalent to the STTF rule. The authors empirically observe that "rule" provides shorter expected output queue lengths. Yao and Buzacott [1985, 1986, and 1987] model a flexible manufacturing system as a network of queues with a central server station, which represents the material handling system. (Jobs traveling between processing stations go through the central station by definition.) Each station has 4

one or several (parallel) servers. In all three studies the authors assume that all the stations have limited local buffers, except for the [1986] study where the buffer of the central station has infinite capacity. Since the material handling system is modeled as a central station, it is difficult to use the above models to capture the performance of the handling system with reasonable accuracy. This is primarily because in central server models delivery times between all the stations are the same regardless of where the job is picked up and where it needs to be delivered next, and the probability that a job will be routed to a particular station does not depend on the previous station. 2.2. Polling Models In trip-based handling systems discussed in this paper, a single device serves a set of stations in a non-deterministic order. Recall that, under the MOD FCFS rule, when the device delivers a job at the input queue of a station, it immediately inspects the output queue of that station. If the output queue is empty, the device is dispatched to pick up the oldest move request elsewhere in the system. A related system is a polling system in which a single server polls and serves multiple stations. However, there is a fundamental difference between polling systems and-trip-based handling systems as explained below. Polling systems have received considerable attention from researchers primarily in computer science and have served as an analysis tool for data transfer from terminals to a central computer and for token passing schemes in local area networks. An excellent survey of polling models can be found in Takagi [1990]. Four types of service disciplines have typically been modeled and studied: exhaustive, gated, limited, and decrementing. In a limited service system, which is the appropriate service discipline for material handling systems, the server serves upto k > 0 requests at a station each time the station is polled. The case where k = 1 is generally known as the non-exhaustive service discipline. These systems are more difficult to analyze than exhaustive and gated service systems (Takagi [1990]), and the exact analysis for the expected waiting times at the stations in systems with more than two stations is unknown at present. Consequently, there has been considerable work on developing approximation techniques to estimate the expected waiting times (see, for example, Boxma and Meister [1987] and Srinivasan [1988]). The fundamental difference between a "traditional" polling model and our model is that, in a traditional polling model, the server moves continuously to find and serve a customer. In other words, polling occurs continuously until a customer is found. However, in our model, polling occurs only at instances of loaded device arrival. Due to this fundamental difference in the 5

modeling assumptions, it is not possible to directly apply the results of polling models to evaluate single-device trip-based material handling systems. 3. The Model In this section we develop an approximation for the expected waiting times in the output queues of single-device material handling systems. We consider a system with M stations. Let t1 denote the set of processor stations, and let Q denote the set of I/O stations in the system. (Recall that every station in the system is assumed to have both an input and an output queue.) The rate at which jobs arrive at the output queue of station i is denoted by ki. To perform a trip, the device picks up a job from the output queue of a station and delivers it to the input queue of some other station. Let Ai denote the rate at which the device delivers jobs to the input queue of station i. We assume that Ai equals hX in steady state at the processor stations. (This also implies that a processor station may never be a bottleneck in the system.) For I/O stations, Ai need not equal Xi in general. However, from conservation of flow, provided that the device is able to meet the demand placed on it, we must have Cie Ai =,isQn Xi. Recall that when a job is delivered at the input queue of an I/O0 station, it is assumed to exit from the system instantly. Let Pij denote the probability that a job, which is picked up by the device from the output queue of station i, is destined for station j. (It is implicit that pii = 0.) The values for Ai are obtained from the unique solution to the system of equations: M Ai = kjPji, for ie Q, and Ai = i, for ie i. (3.1) j=l Let XT denote the total arrival rate at the output queues of all stations. Note that from conservation of flow, XT = iMI hi = i Ai. Recall that we assume each station has sufficiently large input and output buffers so that the device and the processors seldom get blocked. We also assume that the distance between the input and output queues of a station is negligible. (It is straightforward to extend the model to include non-negligible distances between these two queues.) Recall that under the MOD FCFS discipline, whenever a device delivers a job at the input queue of a station, it "inspects" (the output queue of) that station. The time taken by the device to pick up a job from the output queue of station i, transport it from station i to station j, unload it at station j, and then inspect station j, is collectively assumed to be a random variable with mean Tij, and second moment T2]. The empty device travel time from the output queue of station i to the 6

output queue of station j is a random variable, with mean aij and second moment ),2, which includes the time taken to "inspect" station j. (Strictly speaking, when the device arrives at a station empty, it knows that there should be a job waiting at the station; however, we will still use the term inspect.) It is implicit that Tii —-2)=0, and that oii=a)=0. In the following discussion, unless specified otherwise, the index for any summation is assumed to be over the range 1 through M. Let caf (ce) denote the proportion of time that the device is traveling loaded (traveling empty) and let p = af + ace denote the utilization of the device. Clearly, if the device is to meet the required throughput, we must have p < 1. Observe that the term af is easily computed from the input data as af = xi PijTij (3.2) i j Let qif denote the probability that the output queue of station i is empty at the instant it is inspected by the (loaded) device and let qif denote its complement, i.e., qif = l-qf. An expression for qif, in terms of p and the data parameters, is presented in Srinivasan, Bozer and Cho [1989]. We present the expression below, without proof: qif (T - Xi) (p -a f- (Pi) + ( -), (3.3) AiX r where X = i j ij, (3.4a) i j and (Pm = X A(Ai-i m) X ij. (3.4b) Tj i j km Equation (3.3) presents an expression for qif in terms of the unknown p. An approximate expression for p in terms of qif is obtained as follows. We assume that the term qif represents the probability that the output queue of station i is empty at an arbitrary instant in time, and that the qif s are independent. (This implies that the loaded device inspects the output queues at arbitrary instants in time.) Thus, the product n qif gives the probability that all output queues are empty at 1 an arbitrary instant in time, and so we obtain p = l- n qif (3.5) i 7

Equations (3.3) and (3.5) suggest the following iterative algorithm to compute p. We start with an initial estimate for p and compute the qif values from equation (3.3). Next, using these qif values, we compute the new value of p from equation (3.5), and so on, until two successive estimates for p are reasonably close. It is shown in Srinivasan, Bozer and Cho [1989] that this algorithm will always converge, and return a value of p < 1, if and only if af + max (pi < 1. To guarantee that the solution is unique, we further require that Xi + Ai < XT (which is true by definition), and X/T = Xi "i j oji < 1. The latter condition is a sufficient condition, and XT not a necessary one. We were unable to prove that the latter condition always holds if cXf + maX (Pi is less than 1. Therefore, we generated 66,000 problems with af + max (Pi very close to 1, and oij set equal to Tij for all i,j. (Note that the uniqueness condition is more likely to be violated for such problems.) However, none of the problems violated the condition. Also, except for 24 cases which were generated with a sparse routing matrix, in all the problems X/XT was less than caf. Provided that the device meets the required throughput, the value of p and the values for qif,-i = 1,...,M, obtained above are next used to derive the expected waiting times in the output queues. 3.1. Expected Waiting Times in the Output Queues The basic approach followed here is similar to the one presented by Srinivasan [1988] who obtains the expected waiting times in polling systems with non-exhaustive service. Note, however, that the system with the MOD FCFS rule has characteristics that are quite different from a polling system. To obtain the expected waiting times in the output queues, we assume that the arrival process of jobs at each output queue is Poisson, and that these processes are independent of each other. This implies that jobs are delivered (arrive) at the output queues at arbitrary instances in time. Consider a tagged job that arrives at output queue i. Since Poisson arrivals see time averages (Wolff [1982]), the tagged job finds the steady state distribution of jobs present at output queue i. Let Pi(n) denote the probability that the tagged job finds n jobs already present at output queue i, and let WOi(n) represent the conditional expected waiting time for the tagged job, given that it finds n jobs at output queue i upon arrival. Let WOi denote the expected waiting time for the tagged job arriving at output queue i. Then 8

00 WOi = A Pi(n)WOi(n). (3.6) n=O If we can estimate the values of Pi(n) and WOi(n), we can determine WOi from equation (3.6). To estimate WOi(n), we consider two cases: n=0 and n>0. If the tagged job finds no jobs at output queue i upon arrival, the device is either busy or it is idle at station j, j=l,...,M. Let xi denote the probability that the device is busy when the tagged job arrives. For this case let CB denote the expected time for the device to return to station i. On the other hand, if the tagged job finds the device idle, then the tagged job automatically becomes the oldest job in the system, and the idle device is dispatched to station i. Let CI(denote the expected time for the device to arrive at station i from the idle state. Thus, for n=0, WOi(O) = xiCB + (l-)C. (3.7) If the tagged job finds n>O jobs at output queue i upon arrival, we define the job at the head of this output queue as the Head-Of-Line (HOL) job. The expected waiting time for the tagged job is the sum of two quantities: (i) the expected time, CH, starting from the time of its arrival until the time the device arrives at that station to pick up the HOL job, and (ii) the expected time for the device to pick up the n-1 remaining jobs, followed by a visit to pick up the tagged job; that is, the expected time for the device to complete n successive cycles where the expected value of a cycle is denoted by Cs. Thus, WOi(n) = CH + nCS, n > 0. (3.8) Hence, from equations (3.6), (3.7) and (3.8), 00 WQ = Pi(0)[xiCB + (l-xi)Cl | + Pi(n) (C + nC ) n=l 00 00 = Pi(0)[XiCB + (l-X)Ci] + CH E Pi(n) + Cs n Pi(n). n=l n=l 00 Noting, from Little's law, that S n Pi(n) = XiWOi, we have n=l Pi(O)[XiC, + (l-Xi)C] + [1 - Pi(O)]CH iWOi =i -- 1 -I (3.9) 9

Note that we had determined p by assuming that qif represents the probability that the output queue of station i is empty at an arbitrary instant in time. Hence, Pi(0) is approximated by qi. Therefore, to estimate WOi, the values of xi, C H, C, CB, and cS need to be determined. Since the probability that the device is busy is p, the expression for xi is derived by conditioning on the number of jobs present at output queue i when the tagged job arrives as follows: p = Probability that the device is busy P(device busy I n=0) Pi(0) + P(device busy I n > 0) (1-Pi(0)) xiPi(O) + l-Pi(0), since the device cannot be idle when n > 0. Hence, xi= 1 - 1 - p = 1 - p xi P P= 1 - Pj(0) = 1 - (3.10) Pi(NO) qi The expected time for the device to arrive at station i from the idle state, Ct, is determined-by assuming that the location of the idle device is proportional to the rate at which a device delivers jobs at the input queue of station i, that is, C = ji (3.11) j XT Consider next, CH that is, the expected time required for the device to pick up the HOL job. In this case, the tagged job always finds the device busy, i.e., traveling either loaded or empty. Let'k (L'k) denote the event that the device is traveling empty (loaded) from j to k at the time of arrival of the tagged job at station i. Let C" denote the time required for the device to pick up the HOL job at output queue i. Then: C, = E[Cf] = X [E[C" I EJk P{P(Ejk + E[C I Lk] P{LJk}]. (3.12) j k Note that af/p is the probability that the device is traveling loaded since the tagged job always finds the device busy. Given that the device is traveling loaded, the proportion of time that it is traveling (loaded) from j to k is obtained as XjPjk jk/ oaf. Therefore, P{L. k) is given by: ({ = f XjPjk Tk XjPjk jk pLk (3.13)a P o f P 10

The term P{E(j} is obtained in a similar manner. Since the tagged job finds the device traveling loaded with probability af/p, it is clear that it finds the device traveling empty with probability 1 - ocf/p. To determine the proportion of time that the tagged job finds the device traveling empty from j to k, we proceed as follows. Each time the device delivers a job at station m (which occurs at a rate Am), it checks the output queue of that station and with probability qmf, it finds the output queue empty. Consequently, an empty trip is initiated from m at a rate of Amqmf. With probability p/(XT - Xm), the device next moves to station p to pick up a waiting job and the expected travel time to station p is amp. Note that we are considering the case where the tagged job finds n > 0 jobs in the output queue of station i. Hence, if the tagged job finds the device moving empty out of station i, this implies that the n jobs must have all arrived during the empty trip out of station i (to some other station). Since the probability of this is small, we exclude this case from further consideration and set P{ti} = 0. Therefore, given that the device is traveling empty, the probability, HJ', that the tagged job arriving at station i finds the device moving (empty) from j to k is Xk Ajqj. k jk Hjk =. (3. 14) jk = ~ArnAmq Xmp'mP m:i P (AT- m) The term P{tJik) is now determined from P{(k = ji H k, j i. (3.15) P We next develop an expression for EIC' I Lkl. Recall that this is the case where the tagged job finds the device traveling loaded from station j to station k and there are n>O jobs in output queue i ahead of the tagged job. Let Bk denote the expected time for the device to first visit station i from the instant at which the loaded device arrives at station k. With this definition, we set = 0. The term E[C I Li] is then simply obtained as E[C I Lk] = t2/2Tjk + Bk. (3.16) Equation (3.16) follows since the tagged job interrupts a loaded trip from j to k. The expression for E[CH I t j is obtained in a similar manner. Let Fk denote the expected time for the device to first visit station i from the instant at which the device arrives at station k and picks 11

up a job waiting there. (We are implicitly considering two possible situations here: either the device arrives empty at station k to pick up a job waiting there, or the device arrives at station k loaded and finds a job in the output queue of the station.) Note that Fi = 0, by definition. Since the tagged job interrupts an empty trip from j to k, we have E[C I j] = &j/2ojk + Fk, (3.17) The term Bk is obtained by conditioning on the possible events that can occur when the (loaded) device delivers a job at station k: (1) there is a job in the output queue of station k; (2) there is no job in the system except the HOL job (at output queue i); (3) there are one or more jobs to pick up at output queue m, m ~ k (in addition to the HOL job), and the oldest job is located at output queue m. Figure 2 depicts the above events graphically. Finds a job at k. (Event 1) Loaded device arrives | ~ No job in the system [at station k. | ___ jGob at k. ^ ^^ except for HOL job at i. (Event 2) Some jobs to pick up in addition to The job at m is HOL job at i the oldest job. (Event 3) Figure 2. The possible events encountered by a loaded device arriving at station k. We obtain the probabilities of the above events, and the expected time for the device to return to station i for each event, as follows: Event 1: The expected time for the device to return to station i is FR. Recall that qkf is the conditional probability that the device finds a job in the output queue of station k, given that it just delivered a job at its input queue. Hence, Event 1 occurs with probability qkfEvent 2: The expected time for the device to return to station i is aki, since the HOL job is the only job in the system. The probability of this event is approximated by nl qnf nwi Event 3: The expected time for the device to return to station i is okm + FAm. To determine the probability of this event, let Qn denote the expected queue length at output queue n, and let Qi denote the expected queue length at output queue i, given that there is at least one job at output queue i. The term Qi is approximated as follows: 12

Q* _ Qi Q i l-Pi(0) (3.18) - 1-Pi(O) qif Let Ri = Q /(niik Qn + Qi) denote the conditional probability that the HOL job is the oldest job, given that output queue k is empty, and there is at least one job at output queue n, nwi,k. Let Rmk = QmA(n(i,k Qn + Qi ) denote the conditional probability that the job at station m, m#i, is the oldest job, given that output queue k is empty, and there is at least one job at output queue n, ndi,k. (Clearly, output queue i is non-empty.) In other words, the above conditional probabilities are assumed to be proportional to the length of the output queues. Then the probability that output queue k is empty, at least one job is present at station n, nii,k, and the job at output queue m is the oldest job to serve, is approximated by (qk - lqnf ) Rmk. Hence, we obtain nfi Bk = q k n Fkki + (k- f) f RmHk + (kkm+ nFn) k fi. (3.19) nfi nfi mnk Conditioning on the destination of the device which is arriving at station k, Fk is obtained from Fk = X Pkj(kj + B). (3.20) j Recall that Fi = 0 by definition. So, from equations (3.19) and (3.20), we have a system of M-1 independent equations in the M-l unknown variables, Fk, kfi, which can be solved to obtain these values for a given i. Following this, equation (3.19) can be used to obtain Bk. The term Ci is obtained, analogous to CH, as CB = E[CB] = l [EB I;k P } + E[C I Ljk PLj} ], (3.21) j k where E[C? I Lik], E[CB I Ejk], and P{L'k} are given by equations (3.16), (3.17) and (3.13) respectively, and CB is the time required for the device to pick up the tagged job. In equation (3.21), the term P(EJk) is obtained using similar arguments as was used to derive equations (3.14) and (3.15). When the tagged job arrives at output queue i, no empty trip toward this station is in progress. This is because the tagged job sees no jobs waiting at output queue i. Hence P{ji} = 0. As a consequence, we should also modify the probability that the device moves from station m to station p as Xp(XT - Xi - Xm), when m ~ i, to account for the fact that if the device becomes empty at station m, then it will not move to station i. Hence, the term Hk is obtained as: 13

AHjqik ~H ~i - ~jJf(XT - 8(i,j)i - 3i) jki Hjk = - 6(ij)-k (3.22) m pi Amqmf (T - (i,m)km -i) where 6(i,m) = 0 if m=i, and is equal to 1 otherwise. The term P(Ej'} is now obtained as P{k} = P a H, k i. (3.23) P Finally, the term CS is estimated as follows. Since the device picks up a job from output queue i, it travels loaded to station j with probability Pij, following which it takes a time Bj to next return to i. Hence, Cs = Pij (j + Bj). (3.24) j Substituting equations (3.10), (3.11), (3.12), (3.21), and (3.24) into equation (3.9), we may obtain the expected waiting times in the output queues. However, to compute theC conditional probabilities for event 3 in equation (3. 19), we assumed that the expected output queue length at each station was known. Therefore, we propose the following iterative method to find the expected waiting times in the output queues: Step 0: Assign the initial values of the expected output queue lengths, that is, old Qi, i=l,...,M. Step 1: Compute the expected waiting times, WOi, i=l,...,M, from equation (3.9). Step 2: Compute new set of expected output queue lengths, new Qi, i=l,...,M, using Little's law. Step 3: If lold Qi - new Qil < e for i=l,...,M, then the WOis obtained in step 1 are the expected waiting times, stop, else set old Qi = new Qi for i=l,...,M, and go to step 1, endif. In order to test the conditions under which the above algorithm converges, we randomly generated 500 problems. From these problems we observed empirically that the above algorithm fails to converge only if the estimated fraction of time that the device is busy, p, is very high, i.e., p > 0.99. We also observed that the above algorithm, if it converges, always returns a unique set of expected waiting times, regardless of the initial values for the expected output queue lengths. 14

4. Experimental validation In order to test the performance of the analytical model, we simulated two different layouts with various processing time and traveling time distributions. The first layout, namely, LI, is shown in Figure Al where stations 1 and 2 are the I/O stations. Note that no jobs are received through station 2. The routing matrix and the distance matrix for LI are presented in Table Al and Table A2, respectively. The interarrival time for jobs received through station 1 is equal to 30 minutes. Similar data for layout 2, that is, L2 (shown in Figure A2), are presented in Table A3 and Table A4. In L2 we have four I/O stations numbered one through four. The interarrival time is equal to 4.9, 9.8, and 14.7 minutes for stations 1, 2, and 4, respectively. Note that no jobs are received through station 3. In both layouts, it is assumed that the arrival of jobs from outside the system follows a Poisson process. It is also assumed that the device travels at a speed of 15 and 75 distance units per minute in LI and L2, respectively. The pick-up or deposit time is assumed to be equal to 1/3 and 1/15 minutes in Li and L2, respectively. While a device is allowed to move in only one direction in L1, a device in L2 can move in both directions. Both loaded and empty travel times are computed by assuming that the device always follows the shortest path. The travel time from the input queue to the output queue of a station is assumed to be negligible. The first layout could represent a single vehicle AGV system (that operates as part of a tandem AGV system), while the second layout can be viewed as a shop which is served by an overhead crane. Obviously, these are only examples of potential single-device applications. For both layouts, the expected processing time at each processor station is set equal to that value which yields an expected processor utilization of 0.75. For each layout, we examine three travel time distributions and two processing time distributions. The empty travel time distributions considered are deterministic, uniform with a coefficient of variation (CV) equal to 0.4, and exponential. (The loaded travel time is obtained by simply adding the (constant) pick-up and deposit times.) The processing time distributions considered are exponential and uniform with a CV equal to 0.4. In order to obtain steady state statistics, we first make a single simulation run starting with an empty system and the device idling at an I/O station. For "warm-up" purposes appropriate statistics are cleared when 10,000 loaded trips are performed. After the warm-up period, ten observations (i.e., replications) on each measure of performance are recorded. Each observation is based on 10,000 loaded trips. 15

Table 1 shows af, ae, and af+ae obtained from the simulation model under different combinations of travel and processing time distributions. As we anticipated, the results indicate that the expected device utilization is not affected by either the processing time or travel time distributions. The expected waiting times in the output queues obtained from the analytical model and the simulation model are shown in Table 2. Figure 3 graphically depicts the results obtained for several problems selected from Table 2 for both layouts. The simulation results indicate that the analytical model performs reasonably well for both layouts and travel time/processing time distributions examined. Note that, in addition to the overall (weighted) expected waiting time, the analytical model provides reasonably accurate estimates for each output queue. Table 2 also indicates that, on a relative scale, the analytical model appears to provide more accurate estimates if the processing times are exponentially distributed. This is perhaps a consequence of assuming Poisson arrivals of jobs at the output queues. In other words, since the analytical model does not explicitly consider the processing time distribution, the expected waiting times predicted by the model remains the same for alternative processing time distributions. Thus, as can be seen from Table 2, when the processing time distribution is changed from exponential to uniform (while the travel time distribution is kept the same), the analytical model generally overestimates the expected waiting times. The same is not true for the travel time distribution since the analytical model accounts for both the first and second moments of the empty and loaded travel time distributions. 5. Conclusions In this paper we developed an analytical model to estimate the expected waiting times for move requests that occur in a manufacturing system served by a single-device, trip-based material handling system. We assume that the empty device is dispatched according to the Modified FirstCome-First-Served (MOD FCFS) rule which is comparable in performance to the Shortest-TravelTime-First (STTF) rule. In an earlier study (see Srinivasan, Bozer and Cho [19891), we derived an analytical model to estimate the expected device utilization. Using this model, one can evaluate a proposed system to determine whether the single device will be able to satisfy all the move requests, that is, whether the system is stable. Although system stability is the primary concern in designing material handling systems, given that a proposed design is stable, the device utilization alone does not fully explain the performance of the system. Obviously, as the expected device utilization increases, the 16

expected waiting times (and the corresponding mean queue lengths) will increase as well. However, this relationship is usually highly non-linear and "predicting" the expected waiting times directly from the expected device utilization can generate misleading results. Hence, we believe the analytical waiting time model presented here can be used to further evaluate the performance of stable systems by examining the expected waiting times at each station. In fact, even if the expected device utilization is less than 1.0 and the system is said to be stable, the expected waiting times (and the corresponding mean queue lengths) can be unacceptably long. Note that, due to the non-linear relationship mentioned earlier, a relatively small increase in the expected device utilization may very well render the system performance "unacceptable" even though it may be a "stable" system. Thus, in our view, the expected waiting time expressions derived in this study are not only useful from a theoretical point of view, but they also play a significant role in practice. Using our waiting time model, combined with the earlier model which determines the expected device utilization, the analyst can rapidly evaluate a large number of layout and handling alternatives at an early stage of the design process. 17

Table 1. Simulated device utilization with various combinations of processing and travel time distributions. Processor util. = 0.75 Layout Utilization Deter/ Deter/ Unifo/ Unifo/ Expon/ Expon/ Expon(l) Unifo Expon Unifo Expon Unifo af 0.433 0.433 0.433 0.433 0.432 0.432 L 0.270 0.270 0.268 0.269 0.262 0.260 af + a. 0.703 0.703 0.701 0.701 0.694 0.693 0.564 0.563 0.565 0.565 0.566 0.566 L2 0.314 0.322 0.313 0.321 0.305 0.311 ___ __af + o 0.877 0.885 0.878 0.886 0.871 0.877 (1) A/B: A is the travel time distribution and B is the processing time distribution. The travel time distribution applies to both empty and loaded travel. For example, a uniform "travel time" distribution implies uniformly distributed empty travel times and uniformly distributed loaded travel times; the two travel times are independent. 18

Table 2. Expected waiting times in the output queues: simulation and analytical results. (Layout 1) Processor util. = 0.75 Station Deter/Expon(l) Deter/Unifo Unifo/Expon No. Simulation Analytical Simulation Analytical Simulation Analytical model model model 1 7.96, 8.67(2) 8.30 6.91, 7.44 8.30 8.32, 9.09 8.54 2 0.0, 0.0 0.0 0.0, 0.0 0.0 0.0, 0.0 0.0 3 6.51, 7.32 6.78 4.49, 4.74 6.78 6.76, 7.60 7.01 4 7.87, 8.51 8.12 5.91, 6.14 8.12 8.09, 8.85 8.33 5 7.54, 8.18 7.38 5.62, 5.92 7.38 7.97, 8.69 7.58 6 7.00, 7.68 7.35 4.84, 5.07 7.35 7.33, 8.07 7.58 7 8.80, 9.65 8.91 6.75, 7.07 8.91 9.20, 9.91 9.10 Weighted waiting 7.45, 8.13 7.65 5.65, 5.96 7.65 7.78, 8.50 7.87 time__ _)''.... Processor util. = 0.75 Station Unifo/Unifo Expon/Exon Expon/Unifo No. Simulation Analytical Simulation Analytical Simulation Analytical model model model 1 7.21, 7.89 8.54 9.88, 10.73 9.77 8.99, 9.60 9.77 2 0.0, 0.0 0.0 0.0, 0.0 0.0 0.0, 0.0 0.0 3 4.68, 5.02 7.01 8.24, 9.09 8.21 6.06, 6.47 8.21 4 6.17, 6.40 8.33 9.55, 10.51 9.44 7.51, 7.85 9.44 5 5.75, 6.25 7.58 9.10, 9.86 8.64 7.19, 7.64 8.64 6 5.17, 5.43 7.58 8.60, 9.68 8.76 6.45, 6.76 8.76 7 7.00, 7.51 9.10 10.65, 11.97 10.10 8.48, 9.07 10.10 Weighted waiting 5.90, 6.30 7.87 9.20, 10.03 9.03 7.40, 7.77 9.03 time ____________ (1) A/B: A is the travel time distribution and B is the processing time distribution. (2) A,B: A (B) is the lower (upper) limit of the 95% confidence interval. 19

Table 2. (Contd.) Expected waiting times in the output queues: simulation and analytical results. (Layout 2) (Layout_____2 ___Processor util. = 0.75 Station Deter/Expon(l) Deter/Unifo Unifo/Expon No. Simulation Analytical Simulation Analytical Simulation Analytical model _model model 1 2.02, 2.55(2) 2.31 1.68, 2.13 2.31 2.13, 2.61 2.34 2 1.84, 2.31 1.99 1.55, 2.00 1.99 1.95, 2.41 2.02 3 0.0, 0.0 0.0 0.0, 0.0 0.0 0.0. 0.0 0.0 4 1.85, 2.29 1.94 1.56, 1.97 1.94 1.95, 2.33 1.96 5 1.72, 2.13 1.73 1.28, 1.60 1.73 1.84, 2.22 1.76 6 1.65, 2.04 1.68 1.24, 1.54 1.68 1.74, 2.09 1.71 7 1.90, 2.32 1.96 1.44, 1.80 1.96 2.00, 2.38 1.99 8 1.72, 2.13 1.76 1.31, 1.63 1.76 1.83, 2.20 1.78 9 1.62, 2.03 1.67 1.21, 1.48.67 1.71, 2.09 1.70 10 1.77, 2.23 1.81 1.33, 1.67 1.81 1.87, 2.31 1.84 11 1.80, 2.19 1.80 1.31, 1.61 1.80 1.90, 2.28 1.83 Weighted waiting 1.78, 2.21 1.86 1.38, 1.72 1.86 1.89, 2.28 1.89 time _______ _____ Processor util. = 0.75 Station Unifo/Unifo Expon/Expon Expon/Unifo No. Simulation Analytical Simulation Analytical Simulation Analytical model ___model model 1 1.82, 2.19 2.34 2.43, 2.96 2.50 2.14, 2.61 2.50 2 1.69, 2.05 2.02 2.24, 2.70 2.16 2.00, 2.42 2.16 3 0.0, 0.0 0.0 0.0, 0.0 0.0 0.0, 0.0 0.0 4 1.68, 2.05 1.96 2.16, 2.67 2.09 1.94, 2.37 2.09 5 1.36, 1.65 1.76 2.08, 2.48 1.90 1.59, 1.89 1.90 6 1.32, 1.60 1.71 1.97, 2.40 1.85 1.54, 1.86 1.85 7 1.53, 1.85 1.99 2.26, 2.65 2.12 1.79, 2.12 2.12 8 1.39, 1.64 1.78 2.05, 2.51 1.92 1.63, 1.92 1.92 9 1.30, 1.55 1.70 1.93, 2.39 1.84 1.52, 1.80 1.84 10 1.44, 1.70 1.84 2.10, 2.60 1.97 1.67, 1.97 1.97 11 1.42, 1.67 1.83 2.12, 2.52 1.97 1.67, 1.97 1.97 Weighted waiting 1.48, 1.77 1.89 2.13, 2.57 2.0 3 1.73, 2.06 2.03 time __________________ _______________ ______ (1) A/B: A is the travel time distribution and B is the processing time distribution. (2) A,B: A (B) is the lower (upper) limit of the 95% confidence interval. 20

10 - 8E w 66 *3. 3 462 - O - a Simulation I Analytical model I- C14~~~~ 4i 0I,_zA 1" twr IC I —. a) Deterministic travel time and exponential processing time. (Layout 1) 10 - 8 - Q E I" 6 - 6 42 - 0' - r r rT _ CC e -o 3 b) Deterministic travel time and uniform processing time. (Layout 1) Figure 3. Expected waiting times in the output queues. 21

3 * Simulation P Analytical model 2 1 0 3 - C4 en. i 00. O - c) Uniform travel lime and exponential processing time. (Layout 2) E._ I".l_ esll 2 1 0 - " s4 C E'r th.C - 00 O, -- l* 30 d) Uniform travel time and uniform processing time. (Layout 2) Figtre 3. (Contd.) Expected waiting times in the output queues. 22

I. v- I 1P' 5 6o. 7 -— ^ —-- -- -- -.Aii u[3 =~ 0 I/O station D: Processor station Figure Al. Layout 1 with 2 I/O and 5 processor stations. Table Al. Routing matrix of jobs in Layout 1. Station No. 1 2 3 4 5 6 7 1 0.0 0.0 0.5 0.5 0.0 0.0 0.0 2 0.0 0.0 0.0 0.0 0.0 0.0 0.0 3 0.5 0.0 0.0 0.0 0.5 0.0 0.0 4 0.0 0.0 0.0 0.0 0.3 0.7 0.0 5 0.0 0.5 0.1 0.0 0.0 0.4 0.0 6 0.2 0.0 0.5 0.0 0.0 0.0 0.3 7 0.0 0.3 0.1 0.6 0.0 0.0 0.0 Table A2. Travel distance matrix for Layout 1 (distance units). Station No. 1 2 3 4 5 6 7 1 0 62 16 42 36 28 48 2 58 0 38 64 44 36 16 3 64 46 0 26 50 42 62 4 38 50 18 0 24 16 36 5 50 26 30 56 0 28 42 6 22 84 38 64 58 0 70 7 42 54 58 84 28 56 0 23

467 r - -' -^ —& A I -4 —b-4 —b —.-4 a ^b I. A., " "& -~m wW I * * I.-. L Lc ^QJ -c4M 0: /O station -: Processor station Figure A2. Layout 2 with 4 I/O and 7 processor stations. Table A3. Routing matrix of jobs in Layout 2. Station No. 1 2 3 4 5 6 7 8 9 10 11 1 0.0 0.0 0.0 0.0 0.2 0.2 0.0 0.2 0.2 0.0 0.2 2 0.0 0.0 0.0 0.0 0.2 0.1 0.1 0.2 0.1 0.1 0.2 3 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 4 0.0 0.0 0.0 0.0 0.2 0.4 0.0 0.1 0.1 0.1 0.1 5 0.1 0.1 0.1 0.2 0.0 0.1 0.0 0.1 0.1 0.1 0.1 6 0.0 0.0 0.1 0.1 0.1 0.0 0.2 0.1 0.2 0.2 0.0 7 0.0 0.1 0.2 0.1 0.0 0.2 0.0 0.1 0.2 0.0 0.1 8 0.2 0.0 0.0 0.0 0.2 0.1 0.1 0.0 0.2 0.1 0.1 9 0.0 0.2 0.1 0.0 0.1 0.2 0.1 0.2 0.0 0.1 0.0 10 0.0 0.2 0.2 0.1 0.0 0.1 0.0 0.1 0.1 0.0 0.2 11 0.2 0.0 0.1 0.1 0.2 0.0 0.1 0.0 0.1 0.2 0.0 Table A4. Tavel distance matrix for Layout 2 (distance units). Station No. 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 24

BIBLIOGRAPHY Bartholdi, J.J.,III and Platzman, L.K. [1985], "Decentralized Control of a Fixed Route Automatic Guided Vehicle System," HIE Transactions, Vol. 21, No. 1, pp. 76-81, 1989. Boxma, O.J. and Meister, B. [19871, "Waiting time approximations for cyclic-service systems with switchover times," Performance Evaluation, Vol. 7, No. 4, pp. 299-308. Bozer, Y.A. and Srinivasan, M.M. [1988], "Tandem Configurations for Automated Guided Vehicle Systems and the Analysis of Single Vehicle Loops," to appear in HIE Transactions. Chow, W.M. [1986a], "Design for Line Flexibility," llE Transactions., Vol. 18, No.l, pp. 95108. Chow, W.M. [1986b], "An Analysis of Automated Storage and Retrieval systems in Manufacturing Assembly Lines," lHE transactions, Vol. 18, No. 2, pp. 204-214. Egbelu, P.J. [1987], "The Use of Non-Simulation Approaches in Estimating Vehicle Requirements in an Automated Guided Vehicle Based Transport System," Material Flow, Vol. 4, pp. 17-32. Hodgson, T.J., King, R.E., and Monteith, S.K. [1987], "Developing Control Rules for an AGVS using Markov Decision Processes," Material Flow, Vol. 4, pp. 85-96. Srinivasan, M.M. [1988], "An Approximation for Mean Waiting Times in Cyclic Server Systems with Nonexhaustive Service," Performance Evaluation, Vol. 9, pp. 17-33. Srinivasan, M.M., Bozer, Y.A., and Cho, M.S. [19891, "Trip-Based Material Handling Systems: Throughput Capacity Analysis," submitted to lIE Transactions. Takagi, H. [1990], "Queueing Analysis of Polling Models: An Update," Stochastic Analysis of Computer and Communication Systems, H. Takagi (editor), Elsevier Science Publishers B.V. (North-Holland), Amsterdam. Tompkins, J.A. and White, J.A. [1984j, Facilities Planning, John Wiley & Sons, NY. Toro-Ramos, Z.R. and McGinnis, L.F. [1990a], "Performance Modeling for a Single Material Handling Device with Random Service Requests: Part I: Pure Blocking," Proceedings of the 1990 Material Handling Research Colloquium, pp. 271-283, Hebron, Kentucky. Toro-Ramos, Z.R. and McGinnis, L.F. [1990b], "Performance Modeling for a Single Material Handling Device with Random Service Requests: Part II: Blocking with Recourse," Proceedings of the 1990 Material Handling Research Colloquium, pp. 285-297, Hebron, Kentucky. White, J.A. [1987], "The Changing World of Material Handling," Material Flow, Vol. 4, pp.205207. Wolff, R.W. [1982], "Poisson Arrivals See Time Averages," Operations Research, Vol. 30, pp. 223-231. Yao, D.D. and Buzacott, J.A. [1985], "Modeling the Performance of Flexible Manufacturing Systems," International Journal of Production Research, Vol. 23, No.5, pp.945-959. Yao, D.D. and Buzacott, J.A. [1986], "Models of Flexible Manufacturing Systems with Limited Local Buffers," International Journal of Production Research, Vol. 24, No. 1, pp. 107-118. Yao, D.D. and Buzacott, J.A. [19871, "Modeling a Class of Flexible Manufacturing Systems with Reversible Routing," Operations Research, Vol. 35, No. 1, pp.87-93. Industrial Engineering [1986], "ASRS Sales Are Expected to Rise 500% by 1994," Vol. 18, No. 7, pp.6. 25

UNIVERSITY OF MICHIGAN 3 9015 04732 7054