INTELLIGENT DISPATCHING RULES FOR TRIP-BASED MATERIAL HANDLING SYSTEMS Yavuz A. Bozer and Chih-kuan Yen Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 95-16 September 1995

INTELLIGENT DISPATCHING RULES FOR TRIP-BASED MATERIAL HANDLING SYSTEMS' Yavuz A. Bozer Chih-kuan Yen Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117, USA ABSTRACT It has been shown in the literature that the manner in which empty devices in a trip-based material handling system are dispatched affects the overall productivity of the handling system. Existing dispatching rules: 1. do not assign a move request until a device deposits a load and becomes empty: 2. wit h the exception of orle rule. do not allow an empty device to be reassigned to allotlher move request: 3. do not consider all of the available information It lcit as the status of otiler devices) before assigning a move request: 4. ima eIad l to sizal)le enpty travel (also known in industry as '"dead heading") which i(.duces the efficiencv of the system. In this paper. we present two new dis)it ( linirg rules. namely. modified shortest-travel-time-first (MIOD STTF) and ll((lii g- tased-dynamic-d(ispatching (B2D2). which address the above shortcorllings and take advantage of infor-ration that should be readily available li (e'rtrallv controlled svstenis. 'I ie latter rule also uses a new concept for,tl\ ice dispatching in that all thle devxic(e.s (ellpty or otherwise) are allowed to "Iid" on ilcoming move req(luests. Sitmllat ion results indicate that, compared to existing rules. both.IOI) S'l'[ ' a(n [3'D2 improve system performance ol,1silderabllv. 'Thlis study was partially sup)l)orte (l I) Dr Bozer's Presidential Young Investigator.\ward tunder NSF Grant DD.I -8S.-585-2

1 Introduction and Assumptions Material handling. is an essential component of manufacturing. If the handling system does not deliver the right parts at the right time, it often leads to significant losses due to machine idling, missed due dates, and elevated work-in-process (WIP). Widespread use of just-in-time (JIT) deliveries on the factory floor has further increased the need for a responsive and efficiently run material handling system. However, since material handling is generally viewed as a "non-value added" operation, it typically receives less capital and less investment priority than production equipment. Consequently, coupled withl the cost of modern handling equipment (such as automated guided vehli(cles or ergonomically designed lift trucks), many manufacturing concerns i <\., t <trrolngi incentive to use their existing (or proposed) handling systems i,, t ilir liat iri num efficiency. I lie )ltrtictilar nlaterial hlandlinlg system we address in this study is,i ril-l~,ded mraterial halndling systell..-\ccording to Srinivasan, Bozer. al(l (t', 'i. a trip-based hardllinrg i svt iii consists of one or more self-powered di.\xvices that operate independent ltl al d a;synchronously. To move a unit l,,dt. i.e.. to serve a nove re,(piet. t li' dlevice must perform a trip, whicl i- comiposed of empty travel (froml tine current location of the device to the -\tt ion that placed the move r(tlictst ) followed bv loaded travel. It is assumed 1

that a device moves only one unit load on each trip. Examples of tripbased material handling systems include unit load automated guided vehicles (AGVs), lift trucks, cranes, freight elevators, and manual handling systems (where a person represents the device). Consider the manufacturing system shown in Figure 1, where there is one input/output (I/O) station and three processor stations. The I/O station serves as an entry/exit point for the system while a processor station represents either a machine, a group of machines, or a processing department. (Of course, there may be more than one I/O station and all the processor stations need not be identical.) Each station has a dedicated input queue and output quitIf. Loads arriving at a station are deposited at the input queue of that t1atlionl. where they wait to be processed. Loads that are ready to be moved arc, placed in the output queue of that station, where they wait to be picked lup [y a (levice. (Material handling u-ilhin a station is not considered.) Loads th[at arrive from outside the systen.enter the output queue of an I/O station. I oads ttiat require no further processing are delivered to the input queue of an I/O station where they are ass,,,ilmel to leave the system instantaneously. Note< that an empty (loaded) trilp occurs from the input (output) queue of one station to the output (inpullt ) (iclllr of the other. There are a number of issues iivolved in the design and operation of a

Departure Arrval II111 I 1 (nput - Output queue queue I/O station Output queue 4 Input queue nput queue Output queue 0 0 eS J1LI Devices Output ' Input queue queue rrm 3 rn Empty travel __ __ __ __ __.... Loaded travel Figure 1: A Trip-Based Mlaterial Handling System rip-btased material handlinlg systemil. Thie most notable design issues incl!.i e ti e llnlmber of devices requlired alnd( flow ath design, while one of th e i,. )operational issues is device dispat clitig. wllich is basically concerned with 1.isi glinlg each move request to onle of t li( dlevices. (Depending on the particllar t! pe of trip-based handling systeml involved, there could be other operatioral is>(es ranging from operator fatiglte to battery charging; such issues are oe 3

yond the scope of our study.) Existing dispatching rules in the literature - and those typically used in industry - wait until a device becomes empty before making the above assignment. Therefore, device dispatching has generally been referred to as empty device dispatching. In this study, we take a more general view of dispatching and do not necessarily wait until a device is empty before assigning a move request to it. Assuming that the flow path and the flow volumes are given, and that the empty or loaded travel routes among the stations are defined, the primarN objective in device dispatching has been to reduce empty travel. Note that, withi the above assumptions, total loaded travel per time unit that must be performed by all the devices is given and fixed. Hence, the efficiency of the IIar (llilg system, and the resulting expected waiting times of move requests Crt t l1 olut l t lqueues. to a large extent depends on how well empty device T1;\c l i,- lallaged..-\lthough empty trips are unavoidable in virtuall'y 11 it;p-based handling systems. enlptv travel is unproductive and it increases tlh ttile it takes for a device to.erve a mlove request. \\'e make the following remlainriin assumlptions for the study: 1. Multiple job types art pIlocessed through the system. Eachl job type. which is chara(ctcrizcl by the sequence of stations it visits, is assumed to be of e(tilal priority. The arrival rate of each job 4

type entering the system is fixed. 2. Devices follow a well-defined flow path (or aisle structure) while traveling; i.e., the path from one station to another is known and given. An "intersection" is formed when two flow paths (or aisles) cross each other. 3. The (empty or loaded) device travels at a constant speed independent of the job type it serves. 4. The devices do not interfere with one another; any congestion that may exist is negligible. 5. The processing time associated with each job on each processor is a random variable with a known distribution. 6. Loads in eachl input queue are processed on a FCFS basis. 7. Tie distance from the input queue to the output queue of a station is negligible. S. Devices and nlacilie.s never break down. \\e present the above list to fullyl de(fine the system we later simulate. As i will I)ecome evident in section 3.. some( of the above assumptions are made oily for simplicity and they are not an ilnherent part of the two dispatching Iilles we present in this paper. namellly. MOD STTF and B2D2. Since these

rules (particularly B2D2) deviate significantly from existing rules and they attempt to use existing information more effectively, we refer to them as "intelligent" dispatching rules (although, strictly speaking, we have not used artificial intelligence techniques). The remainder of the paper is organized as follows: in section 2 we review existing dispatching rules in the literature. In section 3, we describe the MOD STTF rule and the B2D2 rule. Simulation results aimed at comparing the performance of the above two rules against one another and against existing rules are presented in section refsec-pe. Lastly, we summarize the results and disculss possible future research directions in section 5. 2 Literature Review I'l ere are a number of papers concerned with developing empty device dis)ati (ilg rules. Egbelin and Tanchoco [2] proposed and evaluated the modifiedtir-1 -comle-first-served (I FC'FS) rule. allonlg others. The MIFCFS rule differs froml the first-come-first-scrvedl ( ('IFS) rule in that only the load at the liead of an output queue can issue a love r(equest from that station. (Note that M.I"('FS does not attempt to reduc( mptlly) device travel; rather, it seems concerned with allocating the material handling capacity more equitably among the stations.) Using simulation. tlle authors compared the performance of 6

MFCFS with other rules such as random-work-center (RW), shortest-traveltime-first (STTF), longest-travel-time-first (LTTF), and maximum-outgoingqueue-size (MOQS). Simulation results suggest that the MFCFS rule is superior to other dispatching rules if the input and output queue sizes are finite, whereas, the STTF rule performs competitively with MFCFS if queue characteristics are not considered. However, the results are based on only one layout with no replications, and the performance measures are not compreIhensive. For example. the expected WIP in the input and output queues, and the expected device utilization, are not reported..-\lso. under STTF, some output queues backed up since a device would (deliver a load at station i and then serve another station even if there was:i;llli la(ile(l Ilmove request waitinlg at the output queue of station i. This \d- prirlaril due to the layout and the fact that the output queue was not I (.f c Id.-l\ l(ocated close to the input queue of a station. Such results show i lii tl th per forilance of the STTF rule can be layout dependent and sonli tI atiuns may be "orphlaned." Simllulation was also usedl I! {ls'.'ll and Tanchoco [3] to evaluate four (Illlt!\ vehicle dispatchinlg rule.s: largest iunmber in queue (LNQ), longest \\,it mig time (L\WT), preferred(l ordler 1) nearest load (POR), and random.tl>i'immIlemlt (RAN). The results idl(licate that the LVWT rule had the smallest I

mean flow time while the LNQ rule reduced the average maximum queue length. However, in both measures the best rule did not show a significant difference over other rules, including STTF. Hodgson, King, and Monteith [4] use a Markov Decision Process (MDP) to develop a control strategy, namely, RULE, for material handling systems with one unit load or double-load AGV. RULE is based on the characterization of the optimal control policy obtained from the MDP. Under RULE, when a device becomes empty, a score is computed for each move request and the empty device is assigned to the move request with the maximum score (we refer the reader to [4] for details). An empty device assigned to a move request can be reassigned to another move request since the above score is rccopl>)tlted at each station the emlpty vehicle must pass through. The score computed for each move request is partly determined by three l)par',llter values specified by the user. The performance of RULE is likely to h)e affected by these parameter settings. which are difficult to generalize. Ille authors use simulation to compllare RI'LE with STTF for small systems with one unit load or one (doublle- loal.A\(;\. For a unit load AGV. the results irnl(icate that RULE is at nost 1.'2('1 i(btter than STTF in terms of throughput an(l it improves the average otllptll queue length by at most 5.4%. In a sul)bseqluent study. King. Hodgsorn. an1d Nlonteith [5] use simulation to further

compare RULE with STTF in layouts with 7 to 14 stations and one or two AGVs. The maximum improvement in the average (output) queue length they report is approximately 14%. Bartholdi and Platzman [6] proposed and analyzed a decentralized dispatching rule, namely, first-encountered-first-served (FEFS), for AGV systems where all the stations are arranged around a simple closed loop. Under FEFS. an empty AGV travels along the loop to poll the stations and it serves the first move request it encounters. For a static system (where a fixed sit of move requests are given a priori), the authors show that, under FEFS, the AGV; w'ill travel no more than once around the loop beyond the optimal number of revolutions required to serve all the move requests. Under dvillic conditions. they showed that the AGV will travel no more than twice the Imliinirnium number of revolutions possible. Although the FEFS rule is a siIl'Ile. decentralized rule that may be effective in closed loop systems v,;hl oI. or few ACGVs. it is not as effective as centralized rules used in general i... Iol,-circIular) configurations (see. for examlple. Egbelu and Tanchoco [2; Hlan and McGinnis [7j develolpedl tie mIost significant move (MSMI) rult o (isp)atch a microload storage/retrieval (S/R) machine with finite input a;ld Ioutput buffers. The MS.IS rule uses known processing times to determi(-e the due date at a given pickup station aind computes a priority index fo' each 9

station. The pickup station with the highest priority index is then selected. The performance of MSM was compared against the MFCFS and STTF rules via simulation. The authors empirically showed that, with buffer sizes of one unit load each, the MSM rule performs better in terms of throughput. However, when the buffer size is increased, the throughput difference between the above rules is reduced. The MSM rule was not evaluated in a nondeterministic setting with multiple devices (since microload AS/R systems contain a single S/R machine in each aisle). Srinivasan. Bozer and Cho [1] proposed an alternate modification to the FCFS rule. namely, the MOD FCFS rule, where they attempt to reduce niriecessary empty device travel that results with the FCFS rule. Under the MO()) I"('FS rule. utpon delivering a load at station i, the empty device first Iil),ccts the output queue of station i. If its empty. the device serves the "(,diest" iove request in the systein (as in FCFS); otherwise, the device i: asi,_,e'(d to the load at the output queue of station i. The authors present an irtnal.tical model to estimate systeml throtughput under the MOD FCFS rule. According to their simulation res.ltl. tlhe.vMOD FCFS rule outperformed tile I('FS and NIFCFS rules. and it was coIlll)arable to the STTF rule. Sal)uncuoglu and Homlmertzlhein i S] proposed a dynamic dispatching al-,'oritlhm (DDA) for scheduling machines and AGVs in a FMS with finite 10

queue capacities. The DDA rule consists of four hierarchical levels to assign jobs to AGVs. The four levels are: 1. identifying stations whose input and output.buffers are full, 2. identifying the load in the central buffer area with the most available space in the destination input queue, 3. identifying the starving workstations, 4. identifying a load which has the highest chance of being processed earliest at the next workstation. To schedule a job on a machine. a priority index, based on known processing times and two subjective scaling factors, is computed for each candidate job in the input queue. The authors use simulation to evaluate the performance of DDA against two alternative machine/AGV scheduling rules, namely, shortest-processingtime (SPT)/STTF and SPT/MOQS. They observed that when the machine utilization is over 807(. the DDA rule hlas the smallest mean flow time. However. tihey did not investigate whether the improvement in mean flow time Swas a restult of better rmacline scheduling or better AGV dispatching. Furthe rriore. the jobs are assigned to the AGV's only one at a time. In sliort. existing device (lispa.Tatcllil rules: 1. do not assign a move re(tuest 'nlt il a device deposits a load and )(becomes emnpty; 2. with the exception of t 1'IE. do not allow an enlpty (device to beI reassigned to another move re(qllest ( reassignment under RULE is colsi(lerel only at the stations an empty device 111must pass through); 3. do not consider all of the available information (such 11

as the status of other devices, which should be readily available in centrally controlled systems) before assigning a move request; 4. may lead to sizable empty travel (also known in industry as "dead heading"). Furthermore, results in the literature indicate that, except possibly for special cases - such as the single-device microload AS/R system or a layout where certain stations may be inadvertently "orphaned" - the STTF rule generally performs better than the other rules. Along with FCFS, the STTF rule is also one of the rules used frequently in industry (particularly in AGV systems). Hence, in this study we will use the STTF rule as our "benchmark." (For small systems with few stations and one device, RULE outperforms STTF by a small margin. Since the parameter settings in RULE are specified i)! t lle user. we do not know how RULE would compare with STTF in general. However. since we were able to obtain sizable improvements over STTF. we \ill riot compare our results with RU'LE.) 3 Dispatching Rules: MOD STTF and BD'2 In t ils section we present two new d(isjlatchliing rules, namely, modified shortesttravel-time-first (MIOD STTF) and, I),il(lillg-based-device-dispatching (B2D2) to inprove the efficiency of tril)-bia.d llmaterial handling systems by reducing cllpt!y device travel. As thle Ilailne illlplies. MOD STTF is a modification of 12

the STTF rule, which is a commonly used rule in industry (particularly in AGV dispatching). In contrast, B2D2 represents a new paradigm for device dispatching - it is based on each device (empty or otherwise) placing a "bid" for each move request as the move requests arrive at the output queues. 3.1 The MOD STTF Rule The MOD STTF rule is similar to the STTF rule in that: 1. it assigns empty devices to move requests based on the location of the device relative to the move request(s), and 2. a device may be assigned. to at most one move request at any given instant. However, MOD STTF deviates from STTF in two significant aspects: 1. an empty device may be reassigned to another irlox', requelsst. and 2. one empty device may "release" another empty device. \1,,. lt'ler MIOD STTF. we investigate the impact of "parking" an idle (d\.ice al a "strategic" p)oint rather than letting the device remain idle at its ia-t locatioln. Fo dlescribe the XIOD STTF rule. we first need to define "committed" and -lllclmlll;itted" empty devices. Supl)pose that device d has just become empty.it -Tation i. Further suppose tihat t i1 closest move request is at station j. If l lie distance from station i to sltionI. saxj., r. is less than or equal to a threshold value (that we define later). then device d is committed to the 13

move request at station j and vice versa (i.e., the move request at station j is committed to device d). If rij is greater than the threshold, however, then device d is assigned to the move request at station j but there is no commitment; i.e., device d starts traveling empty towards station j without having committed itself - we refer to this as "uncommitted empty travel." Likewise, the move request at station j is assigned but not committed to device d. Note that. under the above scenario, when device d becomes empty at station i, it will consider all the move requests in the system except the committed ones. Also, at any given instant: 1. a move request is either committed or uncommitted, and 2. an uncommitted move request is either as>inlled to a device or it is not. Likewise. at any instant, a device may be: 1. traveling loaded (including the pick-up/deposit operations), 2. traveling f'I1p)ty and committed. 3. traveling enpty but uncommitted, 4. traveling et'lll)t to a parking point for idl(e devices. or 5. parked and idling at the plarking Ipoint. A device cannot be assignedl to a move request if all the output (l'ilies are empty or all th e nove reyiw(lsts in the system are committed: i.e., anl unassigned device is define(d a an idle (levice. whether it is traveling or parked. Of course, an unassigIne(l dev\ ic is uncommitted. by definition. Consider next the scenario where ltevice d is traveling empty but uncom 14

mitted towards the move request at station j (which we will label as move request j for brevity). On its way to station j, if device d passes through a station or an intersection, then it will reconsider its assignment; i.e., it will consider all the uncommitted move requests in the system (assigned or otherwise, including those that may have arrived after it was assigned to move request j) and identify the closest one. Suppose the closest move request is at station k (k f j). Further suppose that device e is traveling empty but uncommitted towards move reqiiust k. If device e is closer to station k than device d, then device d ignores move request k and considers the next closest uncommitted move request. Otherwise. device d is assigned to move request k and device e is "released," i.e.. it becomes unassigned. Hence. under MOD STTF, an uncommitted llove request may have at most one device traveling empty but uncommitted Tow\\r(d it. Likewise. no move request may be committed to more thai,iie 'device and vice versa. (Obviously, the distance threshtol(d use(l with MOD STTF (in decidi l, to comrimit a device or not) plays a key role. Instead of requiring a user-specr'.cd distataice threshold, we propose t(o tlus (istance information obtained direct ly fronl the layout. One possible approach is to sort the distances betw-er. all pairs of stations (in non-decreasing order) and use, say, the 60th percent ile as 15

the threshold. That is, if the distance from the empty device to the closest move request is greater than 60% of all the distance values in the layout, then the device would be assigned but not committed to it. An alternate approach is to set the threshold distance relative to the average distance traveled per loaded trip (which is straightforward to obtain from the data). For example, if the distance to the closest move request is greater than the average loaded trip, then the device would be assigned but not committed to it. We considered both of the above types of threshold values in our simulation experiment; the results will be shown in section 4. In the above description of MOD STTF, a device reconsiders its assign1I1ent only when it travels through a station or intersection. Obviously, if ll t lie (uncommitted) devices were allowed to reconsider their assignnments ('er!y tille a new nmove request arrived, MOD STTF is likely to perform I,1iter. However. considering that a device can change its route only at an im lt'ere'tioIl. we do not believe that the additional complexity generated b)! -,(1i a chanIge would be justifiel (especially in systems where the flow pat I I' 1ltlit(irectional). Letting TH denote the (listait'i t lr.elshold. the MOD STTF rule canl be forIlially presented as follows: whenelver a ilove request arrives at. say, out)put (qieuie i. the following sequence is executed: 16

1. If there are no idle (i.e., unassigned) devices, STOP. Otherwise, consider each unassigned device (traveling or parked), and label the closest one as device d. (If an unassigned device is traveling, the distance to output queue i is measured from the next intersection on the device's route.) Let the distance from device d to output queue i be ri. 2. If Ti < TH, then commit device d to move request i and vice versa; STOP. Otherwise, assign device d to move request i and initiate uncommitted empty travel; STOP. Whenever: 1. a loaded device, say, device d, deposits a load at, sax, station i; 2. an uncommitted (empty) device, say, device d, reaches a station or can intersection (say. point i): or 3. an uncommitted device at point i is r ledas'ed( by another device; then tie following sequence is executed: 1. If there are no uncommitted move requests (or they have all been tli.l; l (1 considered). (lispatch device d to the parking point for idle devices: S l (). Otlherwise. identify tile (nex;t) closest uncommitted move request. say. IIloe requlest j. and denote its dlistance to point i as rT. 2. If there is no empty devicet alreadyl assigned to move request j. go to:I. Otherwise. denote the assigned e(lrlpty device by e and go to 4.:. If Tj < TH. then comnlit levice d to move request j and vice versa; STOP. Otherwise. assign dreice( d to ilove request j without committing 17

either one and initiate uncommitted empty travel; STOP. 4. Let the next intersection on device e's route be denoted by k. Also. let the distance from intersection k to move request j be denoted by rkj. If T7j > Tkj, go to 1. Otherwise, release device e and go to 3. Under MOD STTF, idle devices wait at a parking point. An obvious parking point is the station where the device delivered its last load. An alternate approach is to park idle devices at stations that place the most move requests: that is. idle devices can be dispatched to those stations with the highest move request arrival rates. Even if idle devices are somewhat evenly allocated among such stations, our preliminary simulation results indicated illtt sulch a parking strategy has little or no noticeable impact on systen l'rforilarnce: therefore. we did not further pursue this approach..-\ t ird approach is based on parking all the idle devices at a single point. s<;!. )oint p. such that the expecte(l enlpty travel time from point t) to all!,t ti on inr the system is inilinlized. I'sing the nlove request arrival rate at ea1chi station as a "weight." and rectiliniear travel distances, it is straightforW.ar(1 to compute the ol)tirmllll loc;at ion of point p. which is a "minisum" locat ion (see [9]). Of course. if ploiIlt I/ does not overlap with the flow path, oic needs to construct "contour lines" [(]. For simplicity, however, instead of ulsing contour lines, we pickedl tli(e closest station (to the optimal minisurn 18

location) as the parking point. While it may not be desirable to send all the idle devices to the same point, in a properly designed trip-based handling system, very seldom one would find many idle devices waiting at the parking point. (If this is not the case, then there is excess device capacity and dispatching/parking strategies are not as critical.) We also stress that, an idle device may be assigned or committed to a move request if it arrives before the device reaches the parking point. In section 4 we will show the impact of the above "minisum parking" strategy. 3.2 The B2D2 Rule L':ti tili (dispatching rules wait until a device becomes empty and then as-ili ()oIy! onle mlove request to it. \\hile MOD STTF may also assign a move izliet1 when a device is released (by another device) or it is heading to tile PIarkiii point, it alsoawaits until tile device is ready to receive its next assignmllnt anri tthen it assigns (or comrlliits) only one move request. Furthermore. A.ll the (lispatching rules assign mlove requlests to devices without explicitly (coni(derinlg the status of the otlier de(vices. Assigning the move requests only one at a time and doing it oily when11 a device is ready for an assignment offers some inherent flexibility in that a move request is not prematurely 19

committed to a device (and vice versa). It also tends to "automatically" balance the workload among the devices since a device cannot be assigned another move request until it serves the current one. However, one can also argue that such an approach is very "myopic" and may lead to unnecessary empty travel especially since the assignments are made without considering the status of the other devices. As an alternate, we propose the B2D2 rule where all the devices place a "bid" for each move request. In fact, with B2D2, we do not wait until a device is ready for its next assignment. Instead, as soon as a move request is received. all the devices in the system (whether they are traveling loaded, empty. or idle) are allowed to place a bid. Once all the bids are received, we att'telpt to assign or commit the move request to the device with the lowest,li(l. stul)ject to the distance threshold \we described earlier under MOD STTF. More slecifically. ulnder B2D2. we maintain two sets of lists for each device (I: one set. say. Cd; represents all the.move requests that have been committed to (levice d. while the other set. say. I'(. represents all the move requests thiat have been assigned but not rcomllllitted to device d. To keep.the rule simllle and manageable. we assumell' that: 1. all the move requests in Cd are served in the order in which tlhe w.ere placed in Cd (i.e., we do not attempt to further reduce empty travel by resequencing the entries in Cd each time 20

a new request is added to it), and 2. the set UCd may contain at most one move request. When move request i arrives, the bid placed by device d is equal to the total (remaining) distance it must travel to serve all the move requests currently in Cd, plus the empty travel distance from the destination station of the last move request in Cd to output queue i. If Cd is empty but U'Cd is not, then device d's bid is equal to the empty travel distance to output queue i from the next intersection on device d's route. Lastly, if both tCd and ( Cd are empty, then device d's bid is equal to the empty travel distance from station j (where device d became idle) to output queue i. Suppose device d is the lowest bidder. If the above empty travel distance tu, otp)llt queue i is less than the threshold distance, then move request i is cmllllittedl to device d7. i.e.. it is added to Cd; otherwise, device d is assigneec klt rot conlmitted to move request i provided that UCd is empty. If L'C.s rot etMty!. then we attempt to "swap" move request i with the one alrcaL.J it U('Ci if it reduces empty travel; if it does not. then device d is declat(i riceligible for move request i a1(l we consider the next smallest bid. After all the bids have I)eenr collsildeired if move request i has not bleen commiitted to or assigned to a!ny d'vice. then it is placed in a list, say, ( A, unltil the next move request arrives. At that point, all the move reqi!es'.s 21

(i.e., the ones in UA, plus the one that just arrived) are offered, one at a time, for bidding and the above process is repeated for each move request. Hence, bidding occurs only when a move request arrives, and all the devices are allowed to bid on the new request as well as all the move requests in UIA. When device d has served all the move requests in Cd, it begins serving the move request in UCd on an uncommitted basis. If UCd is empty, then device d becomes idle at its last delivery station. Lastly, whenever we add a move request to Cd, we remove the move request in UCd (if any) and allow all the devices. including device d, to bid on it again. Although this may slightly increase the number of bids we process per unit time, it ensures that a nove request does not unnecessarily wait in UCd if it can be committed to tt l l'lr d(evice. IBefore we formally present the B2D2 rule, we need the following notation. I.t! ' I' I = distance threshold \1{ / = inove request z I) = set of devices /.l = set of unassignedl Tlove re(que'lsts I I ), - = bid placed by device d for.MR i ltI;: = empty distance device dl mlust travel to reach NIR i 9)

Cd = set of MRs committed to device d 'Cd = set of MRs assigned to but not committed to device d (may not contain more than one MR) DSd = destination station of the last MR in Cd U;sing the above notation, and the bidding process described earlier, the flow chart for B2D2 is shown in Figure 2. 4 Performance Evaluation III this section we will evaluate the performance of the MOD STTF rule,aid tthe B2D2 rule relative to STTF and MIOD FCFS via simulation. As we f'llllrke(d earlier. since the STTF rule is one of the most competitixe rules ill tih literature. we will use tlie STTF restilts as a "benchmark." All tlie P"'erc(t! improvements we report are relative to STTF. In order to perform as coIlpl)ete ail evaluation as possible, we report ldevice statistics as well as work-il-lproce.ss (\WIP) results for each rule we I('st (l. \\e also used four di flcre lIt lay ou ts (L-l through L-4) to test tie rules: L-4 was taken from [1]..\ll the (lata for L-1. L-2. and L-3 are shown.\Appenlldix I. except for the distaince matrix for L-3. which is too large to 23

MRj mves ' - |N Is D' = o | Y Figture 2: Flow Chlart for B2D2 24

present here. For each device we present the: 1. Fraction of time the device is performing committed empty travel, 2. Fraction of time the device is performing uncommitted empty travel, 3. Fraction of time the device is traveling empty (committed or otherwise), and 4. Average device utilization (which includes all empty or loaded device travel, plus load pickup and deposit times). Of course, with STTF and MOD FCFS, all empty travel must be interpreted as committed empty travel since there is no device reassignment. For W\IP results, we present the: 1. average time a load spends in the system (including the time it spends in the input queues and the time re(quired at each processor station to process the load), 2. average time a load 1,pell(' in an output queue waiting for a device, 3. maximum output queue.I/, o,,served in the system. and 4. average time a load spends in an input,il'tl'e watitingl for a processor. Although the second and third statistics are tli oie' that are most likely affected i)1! the performance of the handling.\st(1l11. we report all four of thei ablove statistics since it presents a inore (oillplete \\'IP picture. \\e also inclided(l tie maximum output queue size in ot ('valiation to identify any st:itiot ttlhat nla' possil)l be "orphaned" by alnlV of the rules we tested. Tlhe results we report were oltaine(l from a simulation model written 25

in GPSS/H. Each layout/rule combination was simulated for 10.000 loaded trips per device per replication. Ten replications were performed for each layout except L-3, for which we used 5 replications due to its large size. All the confidence intervals we report are 95% intervals. In addition to those we presented in section 1, we assume that jobs from outside the system arrive according to a Uniform distribution and that all the processing times are uniformly distributed. To ensure that there are no bottleneck processors, processing capacities are adjusted to achieve an average processor utilization in the range of 70% to 80%. For simplicity, we assume that the handling times are deterministic and that the device speed is equal to one distance unit per unit time: load deposit and pick up times are assumed to be negligible. FThe results of the simulation exp)eriment are presented in Table 1. where wai slhow tile percent inmprovemnent achieved in reducing empty travel along \\lli t li aforemeneltioned device and( \\IP statistics. For both MOD STTF a1i(l IS1[). we report results obtained with various distance threshold values. 'I'he first distance threshold value( shown for each layout reflects the averige loaded trip length in distaic'( Unllits (diis). For example. for. L-l1 the ax'eraige loaded trip is alpproxiN11alll.i' (eq(1al to 12 du's. Tie remaining (listaice values are based on the (sortc d) list of all the distance values obtained fromt the layout. For L-l. 1) (29! d*l's corresponds approximately to the 26

15th (30th) percentile. For L-2, 45 du's corresponds approximately to the 30th percentile. For L-3, 17 (25) du's corresponds approximately to the 20th (40th) percentile. Lastly, for L-4, 28 (41) du's corresponds approximately to the 20th (35th) percentile. In addition, with MOD STTF, we report results obtained with "minisum parking" versus letting the idle device stay at its last delivery station. The results are fairly consistent across the four layouts we tested.. smaller threshold value generally produces better results. (Further reductio:is inl the threshold values, however, did not lead to noticeable improvements.) \\e also observe that "minisum parking" under the MOD STTF rule leads to little or no improvement in system performance (which was the primary ('treaonI we did not test "minisum parking" under the B2D2 rule). P'erhlaps the most significant conclusion we draw from Table 1. however, is ti it Iotll.MOD STTF and B2D2 outperform STTF by a substantial mar -n inx te('rs of reducing both empty device travel and the average output qli.e xwa it iig tine. Furthernore. the rlaxirllniti queue lengths we observe undetr:il tI1( rules seem very reasonable aldl do not indicate any "orphaned" static'..-\nother conclusion we d(raw froil Tabl)e 1 is that B2D2 performs bite r than M.OD STTF. Althougli at first 13'D2 may appear to be more cornplex. we b)elieve it is a rule that can be easily implemented because the "bid. 'inI i" 27

concept has intuitive appeal; it is easy to program and easy to explain to a plant manager or production supervisor. Table 1 also shows that MOD FCFS is not a competitive rule. It is outperformed by the STTF rule. (We must stress, however, that the MOD FCFS rule lends itself more readily to analytical modeling; we refer the reader to [2] for details.) Lastly, in all the layout/rule combinations we tested, the average input queue waiting time does not appear to be sensitive to the dispatching rule used. As a result. savings in average time in system (i.e.. total expected WIP) are not as dramatic. However, in Table 1, if we take tile rIlinimum average output queue waiting time obtained under B2D2 and coimpare it with the average output queue waiting time obtained under STTF, w\ fiid t iat tile percent reduction in average waiting time ranges from 25% to I'r/ for tle four layotlts. This would result in substantial savings due to less \\ ill t lie outpllt quesues; it may even allotw the elimination of one or morte \ I(<'(. Note that, thle expected device utilization under STTF ranges from -,'/i (!):o 9'. while it ranges from (i';i to 79% under B2D2, which indicates *\(.c,<- hlandling capacity. To furtller test the excess hlalnlSliIII caplacity offered by B2D2, we mainl1 1led t lie same number of tdevice- s ill (eac( layout but we gradually increased tli( t hrotlghput requirement ()h re(lucing the interarrival time of the jobs 28

Table 1: Simulation Results (a) Layout 1 (16 stations/3 devices) Distance Percent Device Average Tume Avg. Out Max Out Avg. Input Threshold Comm. Empty Uncomm. Empty Total Empty Imprvsnt. Utilzn. in System Que. W.T. Queue Que. W.T. MOD ST,1F 12 0. 1525 ~ 0.0002 0.3653 ~ 0.0001 0.5178 t 0.00 9.73% 85.16% 82.76 ~ 0.52 2.90 ~ 0.01 2 2.80 t 0.05 MOD ST1F 121 0.1414 ~ 0.0002 0.3598 ~ 0.0001 0.5012 ~ 0.0001 12.62% 83.50% 82.11 ~ 0.49 2.75 ~ 0.01 2 2.78 ~ 0.07 MOD STITF 19 0.3244 ~ 0.0002 0. 1965 ~ 0.000 1 0.5209 ~ 0.0001 9.19% 85.47% 83.10 ~ 0.63 2.97 ~ 0.01 2 2.80 ~ 0.06 MOD STTF 191 0 3172 t 0.0002 0. 1917 ~ 0.0001 0.5089 ~ 0.0001 11.28% 84.77% 82.45 ~ 0.53 2.81 ~ 0.01 2 2.75 ~ 0.09 MOD STTF 29 0 4519 t 0.0002 0.0883 ~ 0.0001 0.5402 ~ 0. 5.82% 87.40% 83.57 ~ 0.46 3.00 ~ 0.01 2 2.78 ~ 0.06 MOD STTF 291 0.4418 ~ 00001 0.0736 ~ 00001 0.5154~0I.00 10.15% 84.92% 83.18 ~0.45 2.85 ~0.01 2 2.79 ~0.08 B2D2 12 0.1449 ~ 0.0001 0.3088 ~ 0.0001 0.4537 ~ 0.0001 20.90% 78.77% 79.94 ~ 0.38 2.57 ~ 0.01 2 2.84 ~ 0.09 132D2 19 0.3221 ~ 0.0002 0. 1401 ~ 0.0002 0.4623 ~ 0.0002 19.40% 79.53% 80.35 ~ 0.32 2.71 ~ 0.01 2 2.79 ~ 0.10 B2D2 29 0 4449 ~ 00002 0.0386 ~ 00002 0.4835 ~0.0004 15.71% 81.66% 81.36 ~0.47 2.94 ~0.01 2 2.75 ~0.02 STTF 0 5736 ~ 0.0002 ________ 0.5736 ~- 0.000. 90.74% 84.73 ~ 0.32 3.42 ~ 0.01 2 2.80 ~ 0.06 MOD FCFS 0 6188 i- 0.0001. 0.6188 ~- 0.0001 95.26% 87.81 ~ 0.27 4.28 ~ 0.01 2 2.79 ~ 0.11 park at mirusum station 8 (b) Lavout 2 (18 stauions/5 devices) 1)~~~~~~~~anre ~~~~~~~~~~~Percent Device Average Time Avg. Out Max Out Avg Input Tr~~re~o~d Comm Empty U~ncomm Empty TotalI Empty lniprm-nt Utilzn. in System Que W T Queue Que W T NIO ) S-T7F 29 0 2094: 00002 0.2087 0 00001 0.4181 0.000~ 22 161-, 77.89% 165.03 ~ 0.62 4.72 ~ 0.01 3 6.25 0 007 MO[)STTF 29 02177:00002 01909:00001 0.4087:0.000 12. Z911- 76.95% 163-87 ~0.47 4.20 ~0.01 3 6 26:0 05 MO0DSTF 45 0 3390~0 0002 0.1076 0 0001 0.4466:0.000 16 857- 80.74% 165-29 ~0.37 4.80 ~0.01 3 6.26~0.11 MODSTT-=-F 450 0 3415:t0 0003 0.0960:0 000 1 0.4375 0.000 IS 15 4% 79.83% 164.26 ~0.28 4.31 ~ 0.01 3 6 20 ~ 006 H:-L)2 29 0 1945:=0.0003 0.1299:+0 0002 0.3244 0. 39 60'-, 68-47% 163.52 ~0.59 4.07 ~ 0.01 2 6.22 ~ 003 R 202 45 0 2923:i0 0001 0 0515:00001 0.3437 O.O0 36 01%1 70.40% 163.57 ~ 062 4.14 ~0.01 2 6.20~0 06.STTF 0 5371:0 0001. 0.5.371 -*0.00A], 89~80%7 172 39~0.61 5.76 ~0.01 3 6.25~0 08 MOD FCFIS 0 5974 ~-0 0001. 057000 95 82%/ 185.12:0.39 7.42 ~0.01 4 6.28~0.06 parK at minisum Station 15 29

Table 1: (continued) Simulation Results.(c) Layout 3 (50 stations/15 devices) Distance Percent Device Average Time Avg. Out Max Out Avg. Input T'hreshold Comm. Epy Uncomm. mt Total Empty Imprvmt. Utilz. in System Que. W.T. Queue Que. W.T MOD STT 11 0.2330 ~ 0.0002 0.2428 ~ 0.0001 0.4758 ~ 0. 18.72% 77.65% 128.78 ~ 0.62 1.60 ~ 0.01 4 2.64 0.07 MO D SITJF II* 0.2359 ~ 0.0002 0.2558 ~ 0.0002 0.4917 ~ 0. 16.01% 79.24% 129.63 ~ 0.58 1.63 ~ 0.01 4 2.65 ~0.06 MOD S'ITF 17 0.3359 ~ 0.0002 0. 1541 ~ 0.0002 0.4900 ~ 0. 16.30% 79.07% 130.36 ~ 0.79 1.66 ~ 0.01 4 2.65 ~0.06 MOD SITT 170 0.3470 ~ 0.0002 0. 1519 ~ 0.000 1 0.4989 ~0.0 14.78% 79.96% 131.63 ~ 0.86 1.70 ~ 0.01 4 2.66 ~0.05 MOD STTF 25 0.4448 ~ 0.0002 0.0781 ~ 0.0002 0.5229 ~0. 10.68% 82.36% 136.79 ~ 0.67 1.88 ~ 0.01 4 2.68 ~ 0.06 MOD STTF 250 0.4658 ~ 0.0002 0.0718~ 0.0002 0.5376 ~.W 8.17% 83.83% 137.45 ~ 0.81 1.95~ 0.01 4 2.65 ~ 0.06 B 2D2 I11 0.2192 ~0.0001 0.1251~0.0001 0.3443~0. 41.19% 64.50% 129.58 ~0.71 1.60~0.01 4 2.69 ~0.08 B 2D2 17 0-2799 ~ 0.0002 0.0703 ~0.0001 0.3502 0.000 40. 18% 65.09% 129.96 ~ 0.36 1.62 ~0.01 4 2.70 ~ 0.05 B2D2 25 0.3268 ~ 0.0001 0.0289 + 0.0001 0.3557 ~0.000 39.24% 65.64% 130.32 ~ 0.68 1.65 ~0.01 4 2.71 ~ 0.11 SITrF 0 5854 ~ 0.0002. 0.5854 ~0.000. 88.61% 148.28 ~ 0.46 2.21 ~0.01 4 2.66 ~ 0.09 MOD FCFS 0.6568 ~ 0.0001. 0.6568 + 0.000. 95.75% 159.24 ~ 0.37 4.39 ~0.01 4 2.69 ~ 0.08 park at minusumn station 23 (d) Layout 4 (20 stations/8 devices) Percent Device Average Turne Avg. Out Max Out Avg Input Tn.-e,:oid Comm Empty UncommEmy Total Emty 1prvmt Utilzn. in Systemn Que W T Queue Que WT M IODSTF 20 0 2181:!0 0002 0 2147,:00002 0.4329:0.00 2239% 80.90% 84.04 +0.06 2.68:t0.01 3 3 48:I003 MIODS1TF 20' 0 2154:-0 0003 0.2227:0 0003 0.4381:0. 2 14 6-, 81 42%' 84 15 ~0.09 2.69~t0.01 3 3 48~005 MOD 1 'SlTF 28 0 3106:=0 0002 0 1401:0 0001 0.4507:0.000 1 92 01 82-69%-, 84-15 ~ 008 2.70 ~0.01 3 3.4 7:002 MOD STF 28'1 0 3122~+0 0002 0 1454:0 0001 0.4576-0.000 17 96% 83.38%', 84 28:t009 2.71 ~ 0.01 3 3 47:0 05 MO DS1TF 41 0 4163:-0 0002 0.0646:0 000 1 0.4809:0.000 13 79% 85.71% 86-03 ~0.09 3.03 ~ 0.01 3 3.50 ~0.03 M 0ODS7T;,F 410 0 4237 t0 0001 0 07 15:f00001 0.4952 -0.000 11272% 87 14%', 86 81 ~ 010 3.10 ~0.01 3 350 ~ 006 li21)2 20 0 1681:t0 0002 0.07 36:z0 000 1 0.2417:0.0001 56 67% 61 73% 81.82 ~ 018 2.14 ~0.01 2 3.46 ~0.09 1320.! 28 0 2118~0 0001 0.0336:t0 000 1 0.2454:0.0002 56 01% 62-15% 82-36 ~0.24 2.21~0.01 2 3 42~0%0 132102 4 1 0 2437:0 0002 0 0084:0000O1 0.2521 - *0f '4) 54 80% 62.82% 82 60:t0.23 2.24~0.01 2 3 44:0 05 Is=TF 0 5578:0 0001. 0.557- 0.000 - 93 41I%' 91,98:i0 07 4.10~0.01 3 3 40:0.09 NIO DFCFS 0602~0001 0.60912:-0.0001. 98,55%- 101,76~t0.12 5.91:0.01 5 3 42~ 008 park at niinisumn Station 12:30

arriving from outside the system). The results are shown in Table 2, where the first column for each rule/layout combination corresponds to the original throughput level while the second and third columns represent an increase in the throughput level. As long as they both meet throughput, MOD STTF is superior to STTF. However, it is clear that B2D2 has the strongest performance. \Ne replaced deterministic handling times with uniformly distributed handling times and repeated the above experiment in its entirety (including the inflated throughput levels). The results we observed were virtually identical to the ones we reported above for deterministic handling times. 5 Conclusions and Future Work \\. j)r(' ('t two new( dispatching rules. namely, the modified shortest-travelnitr-tirist (MOD STTF) rule and the bidding-based- dynamic-dispatching i)' 1) ruile. to improve the efficillecy of trip-based material handling s!stelis. The MOD STTF rule use.s, (listallce-based threshold to determine if.n11 'llempty levice should be conmmit tdll to a move request or not. Under MOD S.TF. a device which is assiglledl lbt not committed to a move request is illowed( to travel towards that 'move request but it may be reassigned to antt her tmlove request at any station or intersection that it passes through. The 31

Table '2: Simulation Results with Inflated Throughput Rates (a) Device Utilization Dispatching Rules L-I1 (16a3devic..) L - 2 (18affidevices) L -.3 (50efl8devices) L - 4 {20&Bdevices) MOD FCFS 95.26% 99.40% lunstable 95-82% 99.74% unstable 95.75% 99.99% unsatble4 98.55% 99.93% Tunstable STT"F 90.74% 96.27%Iunstable 89.80%j96.53% unstable 88.61% 97.88% unstable 93.41% 97.88% unstable MOD STTF'. 83 50% 91.64% u nstable 76.95% 88.67% unstable 77.65% 90.86% 'instable4 80.90% 90 85% uinstabl. BBDD 78.77% 88 37% 198.89% 68 47%j1 82.39% 1 98 62% 164 50% [ 77.14% 198 14 67%j74-66%1993 (b) Percentage of Time Devices Travel Empty Dispatching Rules L. 1 (16sd~devices) L - 2 (18./5devices) L.3 (50u/15devices) L - 4 (20&S/devices) MOD FCFS 61.88% 160-18% Tunstable 59 74% 57.20% Tunstable 65.68% I 67.22% unstable 60.92% 55-64% unstable STTF 57-36% 457.06% junstable 53 71% 53.99% 4unstable~ 58.54% 462.48% unstable 55.78% 53.59% unstable MOD STT 50 12% 452 37% unstable 40 87% 45 96% 4unstablel47.58% 455.54% unstable 43.29% 46.19% unstable. BBDD 45 37% 149 15% 132-33% 32 44% 39 85% 141.57% j34-43% I40,42% 146-38% 24.17%j 30 37 % 12375% (c) Time in System f)i —natchinr Rulea L - 1 16fst3devices) L - 2 I l8./5devicesi L - 3 (5Os/15devices) L - 4 (20u/Bdevices) MOD FCFS 871 81 j 5 62j unstable 185 12 17,3 78 unstable 159.24 160.57 unstable 101 76 99 25 unstable S=T 8~4 7 7551 unstable 172.39 152 56 ~unstable 148-284 140 23 ~unstable 91.98 709 junstable -MOD S=I 82 11 7 2 20 ~unstable 183 87 144 71 ~unstable 128 781115 91 unstable 84.04 73 87 unstable ~~44 )~~~ 93 66 1&5 142 70 145 67 129 58 1 1585 1 120 47 81 82 1 66 14 J 71 55 (d) Average Output Queue Waiting Time:.,.p)i4chjnC Rules L - I 116e/3devacesi L -2' (1Ba'5devsces i L - 3 (SWu/5devices) L - 4 120in/8devices) MOD FCFS 42"'8 50 unsteblel 4. 1If ( 14 u rtaLble 4 39 5 51 unstable 5 91 7d04. unstable S1T 3 42 38 unstAhlel 'e 4 I." unsable 2 21 2 43 unstable 4 10 4 42 unstable MOD.S=1 27-5 3 12 u101AN'J. I4 4~ 4.' uns-tahile 1 60 17I-,9 unstable 2 68 2 85 Iuns-table BBDD 2 57 J2Q Q5 4 j4' 0 6 -17 32I142A 2 4el Max Output Queue Size ),-r.itrhinr' Rules L - 1 l6s/3devices ' 1. 2 *I ko/deviegi) L -3 (50s/15deviceu) L - 4 (20u/8deviceul MOD FCFS 2 3 unstable 4 j 5 unstable 4 6 unstable 5 6 unstable S1TF 2 3 unstable____ 4 unstable 4 6 unstable 3 4 unstable MOD S= ~ 2 3 unst.Abl 3 unstable 4 5 unstable 3 4 usal BBDD 2 3 7 j.: 2 7 4 5 9 2 3 7:32

B2D2 rule, on the other hand, is a novel application of the "bidding" concept to trip-based handling systems. Under B2D2, each device places a bid based on its current workload, and the system tries to assign or commit each move request to the lowest bidding device provided that a distance-based threshold is met. Each device is allowed to bid on each (uncommitted) move request. Simulation results indicate that both of the above rules perform considerablv better than the shortest-travel-time-first (STTF) rule, which is a ver:, competitive rule and widely used in industry. Although both rules are mo;:e elaborate than STTF and similar rules, they are not unreasonably complex. In fact. wve believe the bidding concept has intuitive appeal. Our study can be extended in several directions. For example, one can icl(ld(l tie impact of device downtimes and reallocate the workload of a d(o\ dit'evice' to the others in the most effective manner possible. Also, we,-,IItlIe(lI throlghout the study that all the move requests have equal priori ()ne 1may(l develop new rules, or nodlify the ones presented here, to captue thle( overall priority assigned to each job processed and moved through ie ste'rll. See. for example. Egbelui [10]. who presents a "demand driven" r1l where mlove requests are not all treated equally. Another possibility is to inctorporate the processing tiles into the dispatching rule by 'anticipa'Ing" the mlove requests whenever possible. 33

APPENDIX I Input Data for Layout 1 (i) Layout 0 13: Processor station (1i) Distance Matrix Stat,.i No, 4 5 7 10 11 12 3 4 15 16 t 0 10 40 20 22 17 29 30 44 41 34 43 30 n 60 20 10 3.40 32 27 11 20 30 21 44 57 50 3 30 O60 0 40 60 22 20 28 33 49 40 40 49 16 13 30 4 10 20 40 0 30 IX 30 22 17 21 30 40 41 34 47 0 5 40 10 60 30 0 38 40 32 27 19 20 20 11 44 57 40 6 x 38 22 18 38 0 12 20 15 27 28 32 39 26 35 52 7 20 40 20 30 40 12 0 13 29 20 20 29 14 27 40 X 22 32 2X 22 32 20 X 0 5 21 1 18 27 12 25 38 9 17 27 33 17 27 15 13 5 0 16 17 23 28 17 30 43 10 29 11 49 21 19 27 9 21 16 0 9 19 20 33 46 39 II 30 20 40 30 20 2 20 IM 17 9 0 10 19 24 37 30 12 40 30 40 40 20 32 20 I 3 19 10 0 9 24 37 30 13 41 21 49 41 1I 39 29 27 28 20 19 9 0 33 46 29 14 4 34 44 16 34 44 2 14 12 17 33 24 24 33 0 13 26 15 43 57 13 47 57 35:' 25 30 46 37 37 46 13 0 17 16 60 50 n) 60 40 A n 3 J)x 1 9 30 30 29 26 17 0 (iii) Routing Matrix and Interarrival Times Irnirs JoD I Ype KjUmC R SCqucnce )l SIt.in. \ ' I,ic in.Ln i mic r I -i ' 6 I 5It I ) -O 2 2 10 11 12 13 5 15)00 3 1 1 5 16 1 ' 14 )o0n0 - - I 34

APPENDIX I Input Data for Layout 2 (i) Layout O 1/O station E: Processor station (ii) Distance Matrix Suuon No 2 3 59 10 II 12 13 14 15 16 17 18 1 0 43 9 1 575 8767 82 30 95 746477 32 46109 66 5 2 80 0 109 95 88 100 24 95331 108 87 77 90 45 59 122 79 64 3 51 63 0 66 59 71 87 26 81 39 18 48 21 62 30 13 50 35 4 64 28 93 0 72894 52 79 15 92 71 61 74 29 43 106 63 48 5 46 68 77 61 0 12 92 21 76 34 55 45 58 57 71 90 91 76 6 34 56 65 49 42 0 80 9 64 22 43 33 46 45 59 78 79 64 7 56 20 85 71 64 76 0 71 7 84 63 53 66 21 35 98 55 40 8 25 47 56 40 33 45 71 0 55 13 34 24 37 36 50 69 70 55 9 93 13 122 108 101 113 37 108 0 121 100 90 103 58 72 135 92 77 10 54 76 43 69 62 74 100 29 84 0 21 11 24 65 73 56 93 78 11 33 55 64 48 41 53 79 8 63 21 0 *32 45 44 58 77 78 63 12 43 65 32 58 51 63 89 1I 73 311 10 0 13 54 62 45 82 67 13 70 82 19 85 78 90 106 A45 100 58 37 67 0 81 49 32 69 54 14 35 11 64 50 43 55 35 50 42 63 42 32 45 0 14 77 34 19 IS 21 43 50 36 29 '41 67 36 51 49 28 18 31 32 0 63 66 51 16 38 50 67 53 46 58 74 53 68 66 45 35 48 49 17 0 37 22 17 37 13 66 52 45 57 37 52 44 65 44 34 47 48 16 79 0 21 18 52 28 81 67 60 '2 67 g9 80 59 49 62 63 31 94 15 0 (iii) Routing Matrix and Interarnval Times (mins) ob Tvpei Roure Sequence of Suuon% acattrjI nur T me b 1 I I bI65O 2 1 4 9 7 1 4 17 2 402.60 3 2 14 12 I 10 12 13 3 402-60 4 j 16 18 15 I 2 297 00 I I I I q 1 1 A 610 50 33

APPENDIX I Input Data for Layout 3 (i) Layout 1: VO stabon E Processor station @ Bu ldng interlace (ii) Routing Matrix and Interarrival Times (mins) h f,. irrp R iccu m Se.ue 1 n.,,. St -j - Intan Tire.jY, i 39, _,.,.,. i ---. '2 45 40 20 17 ^ IO I 5 34 5 252.26 3 3 4 47 43 42 41: 19 12 2 28 27 26 6 52.26 4 1 44 45 21 17 8 II Ii I 23 24 32 33 5 252.26 5 ' 4R 4# 47 42 20 a 14 II I0 13 31 37 38 4 23226 6 3 49 47 4342 0 I 9:3 4. 25 27 6 252.26 7 I 44 45 40 21 17 IA 1 | I 10 13 31 34 5 252.26 3 3 50 36 32 33 34 38 126.13 v '": 'R O *' 15 2~ r 4 252 26 36

References [1] M. M. Srinivasan, Y. A. Bozer, and M. Cho, "Trip-Based Material Handling Systems: Throughput Capacity Analysis," IIE Transactions, Vol. 26, No. 1, 70-89 (1994). [2] P. J. Egbelu, and J. M. A. Tanchoco, "Characterization of Automatic Guided Vehicle Dispatching Rules," International Journal of Production Research, Vol. 22, No. 3, 359-374 (1984). [3] D. S. Russell, and J. M. A. Tanchoco, "An Evaluation of Vehicle Dispatching Rules and Their Effect on Shop Performance," Material Flow, Vol. 1. 271-280 (19S4). [1 T.. l.odgson. R. E. King, S. K. Monteith, and S. R. Schultz, "Declo)irlg (Control Rules for an AGV using Markov Decision Processes,".1ao( rial FloW. Vol. 4, 85-96 (1987). i1. I.. King. T. J. Hodgson. and S. K. Monteith, "Extracting Heuristic Control Rules for AGV;s' using Mlarkov Decision Processes," Belgian Journal of OR, Stat. and C(orp. Sci., Vol. 27, No. 2, 3-17 (1987). [6] J. J. Bartholdi, III, and L. 1K. Platzman, "Decentralized Control of a Fixed Route Automatic (;i(lded Vehicle System," IIE Transactions, 37

Vol. 21, No. 1, 76-81 (1989). [7] M. H. Han, and L. F. McGinnis, "Control of Material Handling Transporter in Automated Manufacturing," IIE Transactions. Vol. 21, No. 2, 184-190 (1989). [8] I. Sabuncuoglu, and D. L. Hommertzheim, "Dynamic Dispatching Algorithm for Scheduling Machines and Automated Guided Vehicles in a Flexible Manufacturing System," International Journal of Production Research, Vol. 30, No. 5, 1059-1079 (1992). [9] R. L. Francis, L. F. McGinnis, and J. A. White, " Facility Layout and Location: An Analytical Approach," Prentice Hall (1992). [10] P. J. Egbelu. "Pull Versus Push Strategy for Automated Guided Vehicle Load Management in a Batch Manufacturing System," Journal of Manufacturing Systems Vol. 6. No.:3. 209-221 (1987). 38