Tandem Configurations for Automated Guided Vehicle Systems and the Analysis of Single Vehicle Loops Yavuz A. Bozer Mandyam M. Srinivasan Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 February 1988 Technical Report 88-3

Tandem Configurations for Automated Guided Vehicle Systems and the Analysis of Single Vehicle Loops Abstract Automated Guided Vehicle (AGV) systems continue to play a significant role in many low to medium flow manufacturing operations, including Flexible Manufacturing Systems (FMS) and other applications. The relatively inexpensive guide path, coupled with the high degree of flexibility and control offered in vehicle routing, has made AGV systems a proven and viable handling technology of the 80's. Traditionally, AGV systems have been implemented and analyzed assuming that every vehicle is allowed to visit any pickup/deposit point in the system. We introduce a radically different, yet conceptually simple and intuitive approach where the system is decomposed into non-overlapping single vehicle loops operating in tandem. In this paper, we also develop an analytical model to study the throughput performance of a single vehicle loop. The resulting expressions are the first closed form analytical expressions that have been obtained to estimate the throughput capacity for AGV systems in a non-deterministic environment.

TANDEM CONFIGURATIONS FOR AUTOMATED GUIDED VEHICLE SYSTEMS AND THE ANALYSIS OF SINGLE VEHICLE LOOPS 1. Introduction Automated Guided Vehicle (AGV) systems continue to play a significant role in many low to medium flow manufacturing operations, including Flexible Manufacturing Systems (FMS) and other applications. The relatively inexpensive guide path which does not interfere with other material flow systems in the facility, coupled with the high degree of flexibility and control the system offers in vehicle routing, has made AGV systems a proven and viable handling technology of the 80's. Although an increasing number of AGV vendors continue to develop more advanced vehicles and sophisticated control systems, progress in basic academic research has been quite slow (except for certain initiatives taken to develop guide path free or "self-guided" vehicles). Consequently, many vendors and potential users continue to employ simulation as a primary tool in AGV system design and evaluation. Articles that describe successful industrial applications and those that review the state-of-the-art in AGV systems quite often appear in trade journals such as Modern Materials Handling and Material Handling Engineering. (The interested reader may refer to [4], [8], and [11], among others for up-to-date reviews.) In this paper we introduce a radically different and quite promising approach - one that is based on a "tandem configuration" - to design AGV systems. Following a brief literature survey, in section 3 we define tandem configurations for AGV systems and subsequently we discuss their advantages and limitations. In section 4 we develop an analytical model to predict the throughput capacity of a single vehicle operating in a closed loop. (As shown later, such a configuration defines the basic "building block" of tandem AGV systems.) In section 5 we present a set of simulation results to numerically verify the analytical model and demonstrate soe of the insight we gain from it. Lastly, in section 6 we state our conclusions and define future studies we intend to perform on tandem AGV systems. 1

2. Literature Review Throughout the paper, including the literature review, we will assume that the reader is familiar with generally accepted basic terminology used for AGV systems. Readers who are not familiar with such terminology may refer to the AGV handbook published by the Material Handling Institute (MHI) [14] or Koff's article [7]. To the best of our knowledge, the tandem configuration is a novel concept and all studies (refereed or otherwise) in the open literature on AGV systems are concerned with "conventional" systems where each vehicle is allowed to service any station in the system. Consequently, our literature search is limited to a brief overview of technical papers concerned with conventional AGV systems. Studies concerned with conventional AGV systems generally address one or more of the following issues: path configuration, location of pick-up/deposit (P/D) points, throughput capacity estimation, number of vehicles required, and empty vehicle dispatching. A design methodology with general applicability is presented by Maxwell and Muckstadt [9] who study systems with unit load carriers operating on a unidirectional path. The authors develop a deterministic model to derive a lower bound on the number of required vehicles and to determine vehicle routes for given path layouts and flow data. They also present guidelines for locating P/D points along certain segments of the guide path. Studies concerned with empty vehicle dispatching policies are reported by Newton [10], Egbelu and Tanchoco [3], Hodgson et al. [5], and King et al. [6]. The dispatching policy developed by Hodgson et al. and King et al. is based on certain characteristics they observed in an analytical model that was developed for very simple systems (with one or two vehicles and few P/D points). However, in all of the above studies, for reasonably complex systems the primary tool used for evaluating the impact of alternative policies is simulation. A simple but efficient dispatching policy, namely, First-Encountered-First-Served (FEFS), is presented by Bartholdi and Platzman [2]. The authors show that the FEFS policy (which was presented by Stone and Fuller [12] for retrieving records from a rotating drum) can be applied to the case where a single vehicle operates in a closed loop. (With certain restrictions, the results presented by Bartholdi and Platzman also extend to multiple vehicles operating in a single closed loop.) 2

For the static case of the problem, the authors show that the FEFS policy generates nearoptimum results in terms of minimizing the number of vehicle revolutions required to move a predetermined set of loads. For the same objective function, they also obtain a bound to show that the FEFS policy would still perform reasonably well in a dynamic environment where some loads arrive while the vehicle attempts to move loads that are currently in the system. Note that Bartholdi and Platzman [2] use the FEFS policy for a single vehicle operating in a closed loop which was noted earlier to be the basic "building block" of tandem AGV systems. It must be stressed that, although we intend to use the FEFS policy in our study, Bartholdi and Platzman had conventional systems in mind when they presented this policy. There is absolutely no reference to a tandem (or similar) configuration in their paper and their concern for extending the results to multiple vehicles operating in a closed loop clearly reflects their focus on conventional AGV systems. The studies cited above are concerned with "pick & drop" systems. As the name implies, such AGV systems can be employed in all cases where loads are picked up at certain points and delivered via AGVs to their destination points. The alternative concept, where each AGV functions as a work platform on which a job remains until all processing operations are completed, is known as the "stop & go" system. The "pick & drop" system can be used in both warehousing and manufacturing while the "stop & go" system is most appropriate for manufacturing operations such as fabrication and assembly. As seen in the next section, the tandem AGV system is envisioned as a "pick & drop" system. 3. Tandem AGV Systems Although the tandem configuration defined below can be used in both warehousing and manufacturing applications, we will motivate the concept and develop the throughput capacity estimation model for the latter. Consider first a conventional "pick & drop" AGV system used in manufacturing. A typical application is illustrated in Figure 1 where each node represents a station and the solid line represents the guide path. As described later in section 4, each station in Figure 1 may either represent a processor station (with one or more machines) or it may be used strictly as an entry and exit point for loads entering or leaving the system, that is, an Input/Output (I/O) station. 3

The system shown in Figure 1 is defined here as a conventional system since each AGV operating in this system can pick-up a load from any station and deliver it to any other station. That is, each vehicle has access to all stations. Note that each station has an input buffer and an output buffer. The former is used for holding loads dropped off at that station while the latter is used for holding loads that are waiting to be picked up by the AGV. Hence, the input and output buffers represent the "drop" and "pick" points, respectively. By assumption, the input buffer precedes the output buffer as shown in Figure 1. Since each vehicle has access to all stations, conventional AGV systems generally require extensive control systems for vehicle dispatching, vehicle routing, and traffic management. The vehicle dispatching system is concerned with assigning the next task to empty vehicles. As can be seen from several articles published in this area (see, for example, [3] and [5]), methods used for dispatching empty vehicles in conventional systems can be quite complex. The vehicle routing system, on the other hand, assures that full vehicles follow the right path to reach their proper destinations. Depending on the type of system used (that is, single frequency versus multiple frequency), the hardware associated with the routing system becomes rather complicated or expensive as more segments (such as short-cuts and side spurs) are added to the guide path. Lastly, the traffic management system is primarily concerned with avoiding collisions at intersections, P/D points, and other segments on the guide path. Aside from several types of sensors installed on the vehicles, most conventional systems use the "zone blocking" concept where the entire system is divided into zones. The control system (centralized or dedicated to each zone) allows only one vehicle in each zone at one time. Consequently, a vehicle will not be allowed to proceed to the next segment of the guide path if another vehicle is present in that zone. Needless to say, certain delays and slow-downs are encountered by the vehicles as a result of such traffic management techniques that one is forced to use in conventional systems. In short, as described in Koff [7] and numerous other articles, the vehicle dispatching system, the vehicle routing system, and the traffic management system in conventional AGV systems can be quite complex. This results not only in higher control system development costs, but it also hinders the installation phase since debugging the control system and making the entire system operate flawlessly as an integrated unit typically defines the critical path today. Moreover, conventional systems are prone to congestion if "too many" vehicles are used due to poor planning and/or increased material flow requirements. 4

The tandem configuration, on the other hand, is an application of the "divide and conquer" principle to AGV systems. It is based on partitioning all the stations into non-overlapping, single vehicle closed loops with additional P/D points provided as an interface between adjacent loops. An example of a tandem AGV system is shown in Figure 2 where station locations are identical to those shown earlier in Figure 1. Note that each station is assigned to only one loop and that each loop has only one AGV. Vehicle dispatching in tandem AGV systems is significantly less complicated than conventional systems. This is primarily due to the fact that only a single vehicle is dispatched over a smaller number of stations. Also note that traffic management problems within each loop is essentially eliminated since there are no other vehicles to cause interference. However, in tandem AGV systems, a load may be handled by several vehicles before it reaches its destination. In the following two sections, we will attempt to further clarify the advantages and limitations of tandem AGV systems. 3.1 Advantages of the Tandem Configuration The following list is intended to outline the advantages of tandem AGV systems: o Eliminates congestion (such as slow-down or blocking at intersections and P/D points). o Yields a significantly less complicated control system (vehicle dispatching and traffic management) for each loop. o Allows one to use the same control system in each loop. This would reduce development cost and installation effort. o Supports "distributed processing" or "distributed control" since each loop, by construction, is a natural control component of the system. o Facilitates centralized control since individual "loop controllers" can be interfaced with a single central processor. o Facilitates future expansion since one or more loops (along with the corresponding new stations) may be added to the system with minimal or no disruptions to most (or all of the) existing loops. 5

o Within one system, it allows the use of "different" vehicles from the same supplier or several suppliers. That is, all the AGVs need not be identical in control system requirements and/or physical configuration as long as they can all use the P/D points provided as an interface between adjacent loops. Such flexibility may play a critical role in system up-grade or in using specially equipped vehicles in some loops. o Supports the effective use of bi-directional vehicles without the usual problems such vehicles generate in conventional systems. o Supports the effective implementation of "group technology" since each loop (or a group of loops) may be viewed as a "cell." o Facilitates determining the optimum location of each station since the analyst can more easily capture the material handling impact of alternative arrangements around a loop. 3.2 Limitations of the Tandem Configuration A number of limitations can be observed for the tandem configuration. They are outlined as follows: o A load is likely to be handled by two or more vehicles before it reaches its destination. o Requires additional space and guide path (due to non-overlapping loops) and additional P/D points to interface adjacent loops. o Less flexible in tolerating vehicle break-downs. A subset of stations cannot be accessed if a vehicle is down. (May therefore require one or more "stand-by" vehicles.) o Requires balanced workloads among the loops to avoid creating bottleneck loops. o For loads that traverse several loops, it generates the load routing problem (as opposed to the full vehicle routing problem in the conventional system). Note that the first limitation does not necessarily imply that the throughput capacity of a tandem system would always be worse than that of a conventional system. The additional "transit time" 6

incurred by loads that are handled by several vehicles under the tandem system would be traded-off against time delays that occur due to congestion and/or operational inefficiencies (stemming from complicated dispatching problems) in the conventional system. For a given problem, if little or no congestion is anticipated in the proposed conventional system, it may very well be the case that it would require a smaller number of vehicles than the corresponding tandem system with the same throughput capacity. However, as pointed out by a long-time consultant in the field (Apple [1]), the number of vehicles alone does not dictate the preferred system since substantial savings incurred in the control system cost may make the tandem configuration the most economical approach. Obviously, further analysis is required to fully explore the relative strengths and weaknesses of the two concepts from a cost and performance standpoint. However, since the tandem configuration is a new concept, substantial work is necessary to analyze and design tandem AGV systems before one can make a fair and quantitative comparison with conventional systems. Hence, at this point we are not proposing tandem AGV systems as a substitute for conventional systems. We rather view it as a very promising alternative which would outperform the conventional system in certain cases. In the following section we will develop an analytical model to study the throughput capacity of a single vehicle operating in a closed loop. Note that such a system represents the basic "building block" for tandem AGV systems since the overall throughput performance of the system, to a large extent, depends on the performance of the individual loops. Further, in order to obtain an algorithm to partition the system into single vehicle loops, one must first analyze the performance of such a loop with a given set of P/D station locations and flow requirements. The main concern at this point is to predict whether the vehicle will meet the throughput requirement imposed by these stations. It must be stressed that the term "loop" is not used in a strict sense. The user may specify any set of appropriate travel times to be used for loaded vehicle travel; that is, one may use "short-cuts" to reduce loaded vehicle travel time as long as the empty vehicle visits each station in a certain sequence. One may also specify loaded vehicle travel times for a bi-directional AGV. Note that a single vehicle operating in a closed loop can be considered as a single-server polling system, where the server polls the queues in a non-deterministic order. This order will be determined by the presence/absence of loads in the output queues of the stations as they are polled by the vehicle. Although there is considerable literature on polling systems where the server polls the queues in a deterministic sequence, to the best of our knowledge, the method of polling that is 7

being considered in this paper has not been studied previously. For an excellent review on polling systems, the reader may refer to Takagi [13]. 4. Throughput capacity analysis for a single vehicle loop Let M denote the number of stations in a loop. The stations where the loads are processed will be termed as the processor stations. Let e denote the set of processor stations, and let Q denote the set of Input-Output (I/O) stations in the loop. Recall that every station in the loop is assumed to have both an input and an output buffer. The output buffers of I/O stations receive loads from outside the loop, while the output buffer of a processor station receives loads that are processed at that station. In general, let Xi denote the rate at which loads arrive to the output buffer of station i. The AGV picks up a load from the output buffer of a station and delivers it to the input buffer of some other station. Let Ai denote the rate at which the vehicle delivers loads to the input buffer of station i. For ease of exposition, we assume that Ai equals i in steady state at the processor stations. On the other hand, for loops with multiple I/O stations, Ai need not equal ki in general. When a load is delivered to the input buffer of an I/O station, it is assumed to exit from the loop. Note that from conservation of flow, provided that the vehicle is able to meet the demand placed on it, it must be true that X Ai = S Xi. ie Q ieQ Let pij denote the probability that a load, which is picked up by the AGV from the output buffer of station i, is delivered to the input buffer of station j. Note that the Pij terms can be easily computed from the problem description, as will be demonstrated in section 5. (It is implicit that pii = 0.) The values for Ai are then obtained from the unique solution to the system of equations: M Ai = jPjji, (4.1.a) j=l with Ai = Xi, ie 3. (4.1.b) The time taken by the vehicle to pick up a load from the output buffer of station i, transport it from station i to station j, and unload it at station j, is collectively assumed to be a random variable with mean Tij. We assume that each station has ample input and output buffers, so that no blocking of any form can occur. For convenience, whenever an empty vehicle checks the output buffer of a station, we say that the vehicle'inspects' station i. Based on the FEFS dispatching rule, it is assumed that when the vehicle becomes empty, it always follows the same route until it picks up the next load. Without 8

loss of generality, this route is assumed to be 1,2,..,i,i+l,..,M,1,2,... (It is implicit in the discussion that i+1 = 1, when i=M.) The resulting empty vehicle travel time between stations i and i+1 is a random variable with mean ai,+1, which includes the time taken to inspect station i+l. Let Ci denote the expected time between two successive inspections by the vehicle at station i. This term plays an important role in determining the throughput capacity of the loop, and we show below how this may be obtained. For ease of exposition, we will assume, without any loss of generality, that station 1 is an I/O station, and we will refer to C1 as the'cycle time.' Let vi denote the'visit ratio' for station i, which is the expected number of times that the vehicle inspects the output buffer of station i during the cycle time C1. Note that, by this definition, vl = 1. Suppose that we can determine the values of C1 and the visit ratios, vi, for i=2,..,M. Then we can determine Ci, for any other station i (including VO stations) from the identity viCi = viC1. (4.2) Let qi denote the probability that the output buffer of station i is empty at the instant that the vehicle inspects the station. The probability of a service (i.e., that a load is picked up) at station i when the vehicle inspects it is then given by (1-qi), and the expected number of loads picked up from the output buffer of station i in a cycle is thus equal to (l-qi)vi. For stability of the system, this should equal XiC1, which is the expected number of loads arriving at the output buffer of station i during the cycle time C1. Equating these two terms, and using equation (4.2), we obtain Property 1: qi = 1- kii. (4.3) Since qi is non-negative, Property 1 shows that if the vehicle is to meet the demand placed on it by the arrivals to any /VO station i, then we must have Ci < lAi. In other words, every time the vehicle inspects the output buffer of station i it removes a load if it finds one. If no load is found it departs empty. In either case, however, it returns to re-inspect the output buffer of this station Ci minutes later, on the average. Hence, as long as the time between inspections is less than the time between arrivals at an output buffer, the vehicle will be able to meet throughput as far as that station is concerned. Consider, next, the transition matrix R =r(ij)}, i,j=,..M, which specifies the movement of the vehicle between the stations. Suppose that the vehicle is currently at station i. Then, with 9

probability qi, the next station visited is station i+l, while with probability (l-qi)pij, the next station visited is station j. Hence, the elements of this transition matrix are given by r(i,j) = qi + (1-qi)ii+l j = i+1 (44) (1-qi)pij j i+l. Let v = (vi}, i=l,..,M. Noting that vl=l, the visit ratios are uniquely obtained from the set of equations vR = v, with Vl = 1. Thus, M vi = ~ (l-qj)Pjivj + qi-lvi-l, i=2,..,M. (4.5) j=l Let M vif = I (l-qj)pjivj, (4.5.a) j=1 and vie = vi-qi-1. (4.5.b) Equations (4.5), (4.5.a) and (4.5.b) have the following interpretation. The term vi denotes the expected number of times that the vehicle inspects station i in a cycle. This is the sum of two components: (i) the expected number of inspections, vif, at station i in a cycle time C1, where the vehicle arrived loaded at station i, and (ii) the expected number of inspections, vie, in a cycle time C1, where the vehicle arrived empty at station i. Using Property 1 and equation (4.2), equation (4.5) can be rewritten as M vi = XSjClpji + vi- -.i- C1, j=l M and noting from equation (4.1) that X Xjpji = Ai, we obtain j=l vi = vi-1 + (Ai - i-1)C1. (4.6) Consider the state of the output buffer of an arbitrary station i at the instant that the vehicle just inspects it. Let Ti denote the expected time from this instant, until the instant when the next inspection occurs at some station. With probability qi, the vehicle does not find a load waiting in the output buffer of station i, and in this case, the next station inspected is station i+l. Hence, the expected time until the instant when the next inspection occurs is ai,i+l. With probability (1-qi), 10

however, the vehicle finds a load waiting in the output buffer of station i and with probability Pij the destination of this load is station j. Hence, for this case, the expected time until the instant when the next inspection occurs is ij. The term Ti is thus given by M Ti = qi oij+l + (1-qi) ZPijij- (4.7) j=1 Observe that in a cycle, station i is visited vi times. So, from equations (4.7) and (4.3), the cycle time C1 is obtained as M M M C1 = viTi = ~ vi ( qi ii+l + (1-qi) XPijtij), i=l i=l j=1 M M E (oi,+l(vi-XiC1) + Cli pijxij). (4.8) i=l j=l Collecting terms involving C1 in equation (4.8), and setting M M af = ~ Xi ~ ijqij, i=1 j=l we have M ~ ViGii+l C1 M (4.9) 1 - af + ~,Xii,i+l i=1 Note that the term af represents the proportion of time that the vehicle travels loaded, servicing the loads that arrive at the output buffers of the stations. From equation (4.6), substituting i-1 in place of i, vi1 = Vi2 + (Ai-1 - Xi-2)C1 and so, we can write i vi = vi-2+ I (Aj- j.1)Ci. j=i-1 Continuing to express vi, recursively, in terms of vi-3,..., vl, we obtain i vi = Vl + I (Aj-h j-1)C1. (4.10) j=2 11

M Let X = Oi,+l.- From equations (4.9) and (4.10), after some algebraic manipulation, we obtain i=l C1.= (4.11) M i 1 - af+.lX - X (Aj-ij)oi,i+l i=2 j=2 In equation (4.11), set M i P1P = Y. z (Aj-kj)i,i+. i=2 j=2 Interchanging the order of summation, and noting that i+l=l when i=M, the term (p1 is rewritten as M M M Pq) = z (Aj-Xj) o ii+l = X (Aj-)j) aj,1, (4.12) j=2 i=j j=2 k-1 where ajk = aoi,i+ denotes the expected empty vehicle travel time from station j to station k, i=j jek. The resulting expression for the cycle time is then stated as Propertv 2: C1 = (4.13) 1 - acf- (1+ lX From equation (4.12), for the special case where Aj = Xj for all stations, we have Corollary 1: If the rate of arrivals of loads to the loop via I/O station i equals the rate of departures of loads from the loop via VO station i for each i e Q, then vi = v1 + (i - x1)C1, (4.14.a) and C1 = (4.14.b) 1 - af+ iX1 / 12

Corollary 1 has the following important interpretation: recall that in order for the AGV to service all the loads that arrive at the output buffer of I/O station 1, we required that XlC1 < 1. Applying this condition to equation (4.14.b), we obtain IC1 = X< 1. 1 - af+ XiX On simplifying the above inequality, we obtain the following condition for meeting throughput: (f < 1. (4.15) Thus, with the FEFS discipline, when the arrival rate at each I/O station is equal to its departure rate, the only condition for the AGV to meet the throughput demand at any I/O station is that the proportion of time that the AGV travels loaded be less than 1. In other words, it implies that for this special case of the FEFS discipline, the empty vehicle travel times between stations do not affect the throughput capacity of the AGV. Also, note that from equations (4.14.a), and (4.3), it is easily seen that viqi = viql. (4.16) Hence, from equations (4.5.b) and (4.16), we have the following property stated as Corollary 2: If the arrival rates of loads to the loop via /O station i equals the rate of departures of loads from the loop via I/O station i for each i e Q, then vie = vie, i=2,..,M, in other words, the empty vehicle travel is evenly distributed between all stations. In general, from Property 2 we can obtain the condition for the AGV to meet the throughput requirements at any I/O station. Applying the requirement that XC1 < 1 to equation (4.13), we need the following condition: f + (Pi < 1. (4.17) Comparing equation (4.17) with equation (4.15), note that the term (pi acts as a correction factor. Equation (4.17) can be interpreted as follows: in order for the AGV to meet the demand placed on it by station 1, it has to undergo some "mandatory" empty vehicle travel, in addition to the loaded vehicle travel. The term (pi represents the proportion of time that the vehicle is performing such 13

mandatory empty travel, as far as station 1 is concerned. Note that the correction factor could be negative in some cases. We also present below, a relation between the (p terms, which is obtained after some straightforward algebra: k (Pk- Pn = I (j- Aj). (4.18) j=n+l Note that for any processor station j, we have assumed that j = Aj. Consider any I/O station n, and let m be index of the next I/O station, with m>n. Equation (4.18) states that for any processor station having an index k between n and m, we must have (pk = (Pn, k=n+l,..,m- 1. Hence, from equations (4.17) and (4.18), it is clear that in order to check whether the vehicle meets the throughput requirement for the loop, it is enough to check whether the vehicle meets the throughput requirements at the I/O stations alone. 5. Numerical Examples and Discussions In this section, using four numerical examples, we will demonstrate the use of the analytical model and some of the insight we gained. We will also show how the pij values are computed (see equation 4.1.a). The first two problems represent a "balanced" loop where the arrival rate at each I/O station is equal to the departure rate. Hence, to a large extent they are used to demonstrate Corollary 1. The last two problems are not balanced; they are used primarily to demonstrate the results obtained from the analytical model and the impact of "mandatory" empty vehicle travel. In each case, the results obtained from the analytical model are also numerically verified via simulation. Consider a hypothetical problem with eight stations numbered one through eight. Suppose that stations 1, 3, 6, and 7 are I/O stations while the remaining stations are processor stations. As shown in Figure 3, further suppose that the stations are arranged around a circle that resembles the face of a clock. Empty travel time between each position on the "clock" is assumed to be constant and equal to one time unit, say, one minute. Loaded travel time between a pair of stations is obtained by adding one minute to the empty travel time between the pair. The unidirectional vehicle is assumed to travel clockwise around the loop. In the simulation model, on the other hand, we assume that interarrival times to the /O stations, and the processing times at the processor stations are exponentially distributed. The 14

processing capacity of the processor stations are selected such that the expected utilization of each processor is equal to 75%, provided that the vehicle meets throughput. (Any value for the mean processing capacity may be used as long as it exceeds the required processing rate defined by Ai,.) All travel times, empty or otherwise, are assumed to be constant. (Note that the analytical model would work with any distribution for interarrival, processing, and travel times as long as their first moment is defined ) In the above system, five types of jobs (labeled A through E) are processed. For each job type, it is assumed that the number of units produced per hour and the routing (that is, the sequence of stations they visit) are specified. 5.1 Balanced Systems For the first numerical example, suppose that each job type is processed according to the data shown in Table 1. Note that job type E represents all "transit" jobs; that is, those that use the loop only as a transit loop between their origin and destination loops. Also, note that each job type enters and leaves the loop through one of the I/O stations. The data given in Table 1 represents a balanced system since the total rate at which jobs enter through an I/O station is equal to the total rate at which they leave the loop through that station. That is, X1=A1=0.875, sX=A3=0.375, X6=A6=0.250, and X7=A7=0.500 jobs per hour. It is straightforward to compute the pij values from the flow data. For example, job types A, B, and D require processing at station 8. Also, of the 1.25 jobs per hour that leave station 8, 0.375 are destined to station 2 while the remaining 0.875 are destined to station 5. Hence, P82 = 0.375/1.25 = 0.30 and P85 = 0.875/1.25 = 0.70. Using the above data we obtain af = 0.73125 and X = 12/60 = 0.20. Subsequently, using the expressions derived earlier we obtain the following results: C1=27.0423, C3=34.9091, C6=37.6471, and C7=32.5424 minutes per inspection. (The above results were obtained by first computing C1 from equation (4.11). Subsequently, the vi value for i=3,6,and 7 was obtained from equation (4.10). Using each vi value in equation (4.2) yields the corresponding Ci values of interest.) Thus, stations 1, 3, 6, and 7 are inspected at a rate of 2.2187, 1.7187, 1.5937, and 1.8437 times per hour, respectively. Since the rate at which the vehicle inspects stations 1, 3, 6, and 7 exceeds the rate at which loads arrive at these stations, we conclude that the system would meet the required throughput. Note that the difference between the above two rates dictates the rate at which the vehicle would depart empty from a station. 15

For example, consider station 1. Loads arrive at a rate of 0.875 per hour. The vehicle inspects the output buffer of station 1 at a rate of 2.2187 times per hour. Hence, (2.2187 - 0.875) = 1.3437 times out of 2.2187, on the average, the vehicle will depart empty from station 1. In other words, the probability of an empty departure from station 1 is equal to 1.3437/2.2187 = 0.6056. Note that using equation (4.3) to obtain ql yields the same result. The Ci and qi values obtained above were numerically verified using 99% confidence intervals obtained from the simulation model. The results are shown in Appendix 1. For the second numerical example, in order to demonstrate Corollary 1, we simply double the empty travel time between all the stations while maintaining the original loaded travel times. That is, empty travel time between each position on the "clock" in Figure 3 is assumed to be constant and equal to two minutes. Since the same travel times are used for loaded travel, the fraction of time that the vehicle travels loaded remains the same; that is, af = 0.73125. However, the following values are obtained for the cycle times: C1=38.7879, C3=57.3130, C6=65.0847, and C7=51.2000 minutes per inspection. As expected, the vehicle still meets the required throughput since the time between inspections is less than the time between arrivals at each I/VO station. (The Ci and qi values obtained for the second problem were also numerically verified using 99% confidence intervals obtained from the simulation model. The results are shown in Appendix 2.) In the above two examples, no change occurs in af. Therefore, from Corollary 1 and equation (4.15), it can be seen that the vehicle still meets throughput in the second problem although the empty travel times were doubled. To further explore the relationship between the two problems, consider the number of empty trips performed. In both problems the vehicle is empty 26.875% of the time. Hence, given a run length of, say, 1000 minutes, the vehicle will be traveling empty for 268.75 minutes in both cases. From Corollary 2, the empty vehicle travel is evenly distributed between all the stations, that is, vi qi = vj qj for all i and j. Hence, in 268.75 minutes, the vehicle will make 268.75/12 = 22.4 revolutions around the loop in the first problem while it will make 11.2 revolutions in the second problem. In other words, in the first problem, during a 1000 minute interval, one would observe a vehicle, on the average, traveling empty 22.4 times between any two adjacent stations. For the same time interval, one would observe 11.2 empty vehicles in the second problem. Naturally, if the empty travel time was increased three times, then the vehicle would still have met the required throughput, but the number of empty trips observed between adjacent stations 16

would have been three times less. (The above results were numerically verified through simulation with substantially longer simulations runs.) 5.2 Unbalanced Systems For the third numerical example, suppose that the five job types (labeled A through E) are processed according to the data given in Table 2. As before, each job type enters and leaves the loop through one of the I/O stations; that is, station 1, 3, 6, or 7. However, no job enters the loop through station 6 while no job leaves the loop through station 7. As before, job type E represents all "transit" jobs. Given the above data, one may compute the job arrival rate for I/O stations 1, 3, 6, and 7, respectively, as 1i=0.875, X3=1.000, X6=0.0, and X7=0.250 jobs per hour. Likewise, the job departure rates are computed as 0.250, 0.750, 1.125, and 0.0 jobs per hour, respectively. Note that while the total job arrival rate is equal to the total job departure rate, at indiviual I/O stations the two are not equal in this example. Using the above data we obtain af = 0.6896 and X = 12/60 = 0.20. Subsequently, using the expressions derived earlier we obtain the following results: C1=27.1698, C3=28.8000, C6=27.1698, and C7=27.1698 minutes per inspection. That is, stations 1, 3, 6, and 7 are inspected at a rate of 2.2083, 2.0833, 2.2083, and 2.2083 times per hour, respectively. Since the rate at which the vehicle inspects stations 1, 3, and 7 exceeds the rate at which loads arrive at these stations, we conclude that the system would meet the required throughput. (The Ci and qi values obtained for this problem were numerically verified using 99% confidence intervals obtained from the simulation model. The results are shown in Appendix 3.) The fourth and last numerical example is similar to the previous one except for job type E which still enters the loop through station 3 but departs through station 7 (instead of station 6). All the other routing information and the production rates remain the same as they were initially shown in Table 2. The following Ci values can be computed for the fourth problem: C1=27.1698, C3=28.8000, C6=37.8947, and C7=27.1698 minutes. Since the time between inspections at each /VO station is less than the time between load arrivals, once again we can conclude the vehicle will meet the required throughput. (The 99% confidence intervals constructed for this problem are presented in Appendix 4.) 17

The two problems presented above may also be used to provide further insight into empty vehicle travel in unbalanced systems. Consider the first unbalanced problem. Using the Ci and qi values obtained for this problem, one may compute the following empty vehicle trips that would be observed in a time interval of, say, 1000 minutes: vlql= 22.2232 V5q5= 18.0568 V2q2= 22.2232 v6q6= 36.8056 v3q3= 18.0568 V7q7= 32.6389 v4q4= 18.0568 vgqg= 32.6389 (5.1) That is, 22.2232 empty vehicles would be observed between stations 1 and 2, while 18.0568 empty vehicles would be observed between stations 3 and 4, and so on. The above results can be intuitively interpreted as follows. Consider the input rate, Xi and the output rate, Ai given for each I/O station i (see Table 3). The third column in Table 3 shows the difference between these two rates. If the difference is positive, then one may say that empty vehicles are "generated" at that station. If the difference is negative, however, it indicates that empty vehicles are "consumed" at that station. (Since the overall flow is conserved, the total of this column would sum up to zero.) Hence, "mandatory" empty vehicle may be interpreted as the flow of empty vehicles from positive labeled I/O stations to negative labeled I/O stations. In our example problem, we have 0.625 empty trips per hour from station 6 to station 1, and 0.250 empty trips per hour from station 6 to station 3 and to station 7. Given the empty travel time between the above stations, it is straightforward to compute the fraction of time the vehicle would be performing a mandatory empty trip between a pair of VO stations. For example, from station 6 to station 1, (0.625 trips/hr x 5 min/trip) 3.125 min/hr or 5.20833% of the time the vehicle would be performing an empty trip. Likewise, 3.33333% of the time it would be performing an empty trip from station 6 to station 3, and 0.83333% of the time it would be from station 6 to station 7. Furthermore, given a time interval of, say, 1000 minutes we can compute the number of empty trips performed. From station 6 to station 1, for instance, the vehicle would perform (0.625/60) x 1000 = 10.4167 trips in 1000 minutes. Consequently, 9.375% of the time the vehicle would be performing "mandatory" empty travel. Adding this value to the percentage of loaded travel yields 68.95833 + 9.37500 = 78.3333%. The remainder of the time would then be devoted to "non-mandatory" empty travel which would be distributed evenly between all the stations. That is, 21.66666% of the time the vehicle would 18

perform "non-mandatory" empty travel and in an interval of 1000 minutes the vehicle would make 0.216666 x 1000 / 12 = 18.0556 revolutions around the loop. Note that 18.0556 vehicles would be observed between all adjacent stations; hence, let us label it the "base flow." The resulting empty vehicle trips between all the stations can now be obtained by adding the above "base flow" to "mandatory" empty travel performed. That is, using the following values Base flow = 1-2-3-4-5-6-7-8-1 = 18.0556 6tol = 6-7-8-1 = 10.4167 6 to 3 = 6-7-8-1-2-3 = 4.1667 6 to 7 = 6-7 = 4.1667, (5.2) we can compute the empty travel between any pair of stations. For example, from station 7 to station 8 one would observe 32.6390 empty trips in a 1000 minute interval. Adding the appropriate numbers for each pair yields the same result shown earlier by equation (5.1). (Some minor numerical differences exist due to round-off errors.) A similar interpretation may be constructed for the second unbalanced problem where two positive labeled stations (6 and 7) "supply" two negative labeled stations (1 and 3) with empty vehicles. The amount of empty vehicle flow from a positive labeled station to a negative labeled station is proportional to the rate at -which empty vehicles are generated and consumed at each station. In addition to the empty trips predicted above, the analytical model was numerically tested (via simulation) for those cases where the throughput demand placed on the vehicle exceeds its capacity. In such cases the analytical model not only correctly predicts that the throughput requirement is too high but it also indicates which I/O stations would start to "back up." This is possible because the analytical model allows one to compare the cycle time obtained for each I/O station with the interarrival time to that station. Hence, those I/O stations that exceed the vehicle capacity can be quickly identified. 6. Conclusions and Future Work The tandem configuration for AGV systems is a promising concept. It derives much of its strength from the simplicity of the resulting system and the additional flexibility it offers. However, as remarked earlier, the tandem configuration has some limitations and further work is necessary to compare it to traditional systems from a cost and performance standpoint. 19

The analytical model developed in this study for a single vehicle loop is easy to implement and straightforward to use. Its primary purpose is to determine whether the vehicle will meet the required throughput imposed by a given set of P/D station locations and flow requirements. One can also use the model to measure the impact of: using a bi-directional vehicle, adding new stations or deleting some of the existing ones, changing the location of the stations around the loop, and changing the flow values (either in magnitude or in terms of the production routing.) As part of our current research effort, we are using the results from the analytical model to develop a partitioning heuristic that would enable one to construct single vehicle loops from a given set of P/D station locations. Subsequently, using a simulation model, we intend to compare tandem configurations with their traditional counterparts. 20

7. References 1. Apple, J., Personal Communication, 1988. 2. Bartholdi, J. J., II and L. K. Platzman, "Decentralized Control of a Fixed Route Automatic Guided Vehicle System," TR-85-05, Material Handling Research Center, Georgia Institute of Technology, Atlanta, GA, February 6, 1985. 3. Egbelu, P. and J. M. A. Tanchoco, "Characterization of Automatic Guided Vehicle Dispatching Rules," The International Journal of Production Research, Vol. 22, No. 3, pp. 359-374. 4. Gould, L., "Automated Docks, AGVs Drive 99.9% Delivery Accuracy," Modern Materials Handling, Vol. 43, No. 1, pp. 72-75, 1988. 5. Hodgson, T. J., R. E. King, S. K. Monteith, and S. R. Schultz, "Developing Control Rules for an AGV using Markov Decision Processes," to appear in Material Flow. 6. King, R. E., T. J. Hodgson, and S. K. Monteith, "Extracting Heuristic Control Rules for AGV's Using Markov Decision Processes, Unpublished Working Paper, Department of Industrial Engineering, North Carolina State University, Raleigh, NC. 7. Koff, G. A., "Automatic Guided Vehicle Systems: Applications, Controls and Planning," Material Flow, Vol. 4, 1987, pp. 3-16. 8. Lindsay, B., "Warehouse Business Systems and 60 AGVs Track and Route Products at Kodak," Industrial Engineering, Vol. 20, No. 5, pp. 50-54, 1988. 9. Maxwell, W. L. and J. A. Muckstadt, "Design of Automatic Guided Vehicle Systems," lIE Transactions, Vol. 14, No. 2, 1982, pp. 114-124. 10. Newton, D., "Simulation Model Helps Determine How Many Automated Guided Vehicles Are Needed," Industrial Engineering, Vol. 17, No. 2, 1985, pp. 68-78. 11. Schwind, G. F., "AGV's: Creative Solutions Go Looking for Problems," Materials Handling Engineering, Vol. 43, No. 9, pp. 44-47, 1988. 12. Stone, H. S. and Fuller, S. H., "On the Near Optimality of the Shortest-Latency-Time-First Drum Scheduling Discipline," Communications of the ACM, Vol. 16, No. 6, pp. 352-353, 1973. 13. Takagi, H., "Queueing Analysis of Polling Models," ACM Computing Surveys, Vol. 20, No. 1, pp. 5-28, 1988. 14. Considerations for Planning and Installing Automatic Guided Vehicle Systems, Prepared by the AGVS section of the Material Handling Institute, Document #101, 1980. 21

Table 1. Hourly production rates and routing data first balanced problem by job type for the Job Type A B' C D E Routing 1-5-8-2-3 1-4-8-5-7 6-2-6 3-8-5-4-2-1 7-1 Jobs/Hour 0.375 0.500 0.250 0.375 0.500 2.000 TOTAL Table 2. Hourly production rates and routing data first unbalanced problem by job type for the Job Type A B C D E Routing 3-5-8-2-3 1-4-8-5-6 7-2-1 1-8-5-4-2-3 3-6 Jobs/Hour 0.375 0.500 0.250 0.375 0.625 2.125 TOTAL Table 3. Hourly input and output rates at I/O first unbalanced problem stations for the /O Station 1 3 6 7 TOTAL A 0.875 1.000 0.000 0.250 2.125 0.250 0.750 1.125 0.000 2.125 A-A - 0.625 - 0.250 + 1.125 - 0.250 0.000 22

APPENDIX The confidence intervals shown below for each problem were obtained through a simulation code. Ten replications were made for each problem. Starting with an empty system and an empty vehicle, each replication was "warmed-up" for 4,000 loaded vehicle trips followed by 36,000 loaded vehicle trips for data collection. Appendix 1: First balanced problem Theoretical value Theoretical value 99% CI 99% CI C1 [26.6247,27.0774] C3 [34.1668,34.7864] C6 [36.8204,37.6669] C7 [31.9501,32.7219] 27.0420 34.9091 * 37.6471 32.5423 ql [0.6075,0.6144] q2 [0.5724,0.5815] q3 [0.7790,0.7876] q4 [0.6072,0.6164] q5 [0.5191,0.5285] q6 [0.8389,0.8468] q7 [0.7267,0.7346] q8 [0.5164,0.5290] 0.6056 0.5733 0.7818 0.6056* 0.5181* 0.8431 0.7288 0.5181 Appendix 2: Second balanced problem Theoretical value Theoretical value 99% CI 99% CI C1 [38.4381,38.8371] C3 [56.3814,57.2972] C6 [63.8279,65.6286] C7 [50.6890,51.5472] 38.7879 57.3130* 65.0847 51.2000 ql [0.4341,0.4417] q2 [0.4012,0.4076] q3 [0.6345,0.6517] q4 [0.4347,0.4455] q5 [0.3470,0.3594] q6 [0.7223,0.7333] q7 [0.5698,0.5850] q8 [0.3476,0.3580] 0.4343 0.4019 0.6480 0.4343* 0.3496 0.7288 0.5733 0.3496 23

Appendix 3: First unbalanced problem Theoretical value Theoretical value 99% CI 99% CI C1 [26.7828,27.7038] C3 [28.4582,29.3926] C6 [26.8057,27.7293] C7 [26.8057,27.7293] 27.1698 28.8000 27.1698 27.1698 ql [0.5918,0.6098] q2 [0.5586,0.5786] q3 [0.5120,0.5296] q4 [0.5406,0.5626] q5 [0.4512,0.4760] q6 [1.0000,1.0000] q7 [0.8827,0.8897] q8 [0.6013,0.6169] 0.6038 0.5714 0.5200 0.5532 0.4643 1.0000 0.8868 0.6104 Appendix 4: Second unbalanced problem Theoretical value Theoretical value 99% CI 99% CI C1 [26.9851,27.8589] C3 [28.5142,29.6000] C6 [37.4455,38.9853] C7 [26.9424,27.8734] 27.1698 28.8000 37.8947 27.1698 qi [0.5894,0.6102] q2 [0.5567,0.5769] q3 [0.5101,0.5241] q4 [0.5369,0.5583] q5 [0.4474,0.4698] q6 [1.0000,1.0000] q7 [0.8818,0.8890] q8 [0.5978,0.6148] 0.6038 0.5714 0.5200 0.5532 0.4643 1.0000 0.8868 0.6104 24

rmO rrn S) EmEEOm Skh r A Ii' E rl l J 0 6.4 A k< V J Em Em Em Em Em Em [EQ m 0 Figure 1: Traditional AGV System 0 0rllI 0r r Emm - % Er-1 c rO r 0 mT1 m r U _ 4 0 0 0 Figure 2: Tandem AGV System 25

1 8 7 2 6 3 5 Figure 3: Layout for example problem 26