- Email: [email protected]

Int. J. Production Economics 100 (2006) 65–75 www.elsevier.com/locate/ijpe

Multi-attribute responsive dispatching strategies for automated guided vehicles U¨mit Bilge, Go¨kc- e Esenduran, Nebibe Varol, Zeynep O¨ztu¨rk, Burcu Aydın, Aysun Alp Industrial Engineering Department, Bog˘azic- i University, 80815 Istanbul, Turkey Received 24 April 2003; accepted 5 October 2004 Available online 24 November 2004

Abstract This paper discusses responsiveness in automated guided vehicle dispatching. The additive multi-attribute dispatching rule employs two attributes, output buffer length and travel time to pick-up, to prioritize the tasks based on the current system status, while the weights convey information about the relative criticality of the processing and transportation sub-systems. The main responsiveness of the system is inherent in the manner these weights are determined. Two approaches are proposed for this purpose: parametric approach where the weights are calculated at the beginning of each planning horizon based on expected system characteristics; and dynamic approach where the system is allowed to update the weights throughout evolution utilizing some system statistics. Simulation experiments under various scenarios evaluate the performances of the proposed dispatching strategies based on facility throughput. r 2004 Elsevier B.V. All rights reserved. Keywords: Automated guided vehicles; Dispatching; Responsiveness

1. Introduction In response to highly speciﬁc and rapidly changing customer needs, manufacturing environments are becoming increasingly dynamic with several product types and frequent changes in product mix and production volume. The resulting Corresponding author. Tel.: +90 212 359 7071;

fax: +90 212 265 1800. E-mail address: [email protected] (U. Bilge).

agility requirement in production capability and management also applies to material handling since changes in demand pattern leads to changes in shop-ﬂoor material ﬂow patterns as well. Automated guided vehicles (AGVs), with their capability of following programmable paths, allowing intelligent control and interfacing with various other automated entities, can offer the material handling ﬂexibility demanded by such systems. The basic problem with such a dynamic and ﬂexible environment is that it seldom reaches

0925-5273/$ - see front matter r 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.ijpe.2004.10.004

ARTICLE IN PRESS 66

U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

steady state, therefore the strategies and rules used in managing the AGV ﬂeet should be ‘responsive’ rather than static. The decisions should be responsive to the main critical resources in the system—namely, the processing capacity and the transportation capacity—which not only depend on the design of the system but also change throughout time depending on demand structure. Responsive behavior may be required in many stages of decision making regarding management of material ﬂow: (i) selecting the next work center for a job when alternative processing routes exist; (ii) matching AGVs with loads waiting in the output buffer areas of workstations, i.e., dispatching; (iii) selecting the path the AGV should take to reach its destination, i.e., routing. In this study, we focus on the second of these issues and propose two multi-attribute responsive AGV dispatching strategies. AGV dispatching heuristics that appear in literature can be grouped with regard to their decision-making approaches as follows:

Single-attribute dispatching rules such as shortest travel time (STT), minimum remaining outgoing queue space (MROQS), ﬁrst-come ﬁrst-served (FCFS) which consider only one aspect of the system. Examples are provided in the studies by Egbelu and Tanchoco (1984), Sabuncuog˘lu and Hommertzheim (1992a). Hierarchical dispatching algorithms that consider several different criteria that are applied sequentially. Sabuncuog˘lu and Hommertzheim (1992a), Egbelu (1987a), Yim and Linn (1993), Taghaboni (1997), and Kim et al. (1999) provide this kind of algorithms. Multi-attribute dispatching rules that help making decisions in the presence of multiple, usually conﬂicting objectives by using several criteria simultaneously. Klein and Kim (1996), Kim and Hwang (1999), Tan and Tang (2001) discuss such algorithms.

Two of the most signiﬁcant single-attribute dispatching rules are STT and MROQS, however neither of them performs consistently well in every problem. The STT rule aims to minimize the travel time of empty vehicles by assigning AGVs to pick

nearest loads, and thus maximizes the loaded utilization of vehicles. This is a valid approach when AGVs are a scarce resource in the system. In jobs shops with limited buffer space, when an output buffer becomes full, the workstation becomes blocked. The MROQS rule aims to prevent workstation blocking by prioritizing the loads based on the remaining space in the output buffer they are waiting in. Avoiding machine blockage and waste of production time in this manner becomes a critical issue for a system where workload is high. Although it can thus be conjectured that MROQS performs better when system workload is high and STT should be preferred when the trafﬁc system is the bottleneck, the interactions between the resources are often too complex to be captured by a single static criteria. Hierarchical dispatching algorithms, on the other hand, attempt to combine two or more criteria sequentially in a hierarchical framework. Such a hierarchical framework, however, does not lend itself to modiﬁcation in response to the evolution of the production environment. Kim et al. (1999) use a workload balancing index which tries to balance the total number of parts in each workstation as the primary rule, and employ an ‘urgency index’ which takes into account empty travel time, workstation starving and blocking for tie-breaking. Those multi-attribute dispatching rules that allow key parameters of their aggregate decision function to be tuned through feedback obtained from the system have self-adaptive capability. Klein and Kim (1996), and Tan and Tang (2001) discuss the use of fuzzy logic to ﬁnd a compromise between several criteria. Kim and Hwang (1999) propose an adaptive dispatching algorithm that utilizes both current system status and historical information to update the parameters in a decision function that combines travel time with source and destination queue availabilities. These three attributes are presented in the form of bidding functions belonging to AGVs and workstations and the dispatching function used to integrate their values is in product form. The dispatching strategy proposed in this study employs two criteria: the ﬁrst is based on the travel time, while the second utilizes information on

ARTICLE IN PRESS U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

output buffers. The two criteria, which prioritize the tasks adaptively based on status of the system, are combined by additive weighing method, where the weights convey information about the relative criticality of the processing and transportation sub-systems for the job-shop environment at hand. The main responsiveness of the system is inherent in the manner these weights are determined. We propose two approaches for this purpose. In the ﬁrst one, the weights are updated at the beginning of each planning horizon to be used throughout that interval, i.e., a shift. This approach assumes that the product mix, processing routes, expected processing times, available number of machines and vehicles, as well as the AGV ﬂow path are known and will be ﬁxed for the planning horizon. In the second approach, this assumption is relaxed and the system is allowed to update the weights throughout evolution utilizing some system statistics. A hypothetical manufacturing environment with several work centers and two alternative AGV ﬂow path layouts are created and simulation experiments under various scenarios are conducted to compare the performances of the proposed dispatching rules with STT and MROQS based on facility throughput. The additive dispatching function and the two methods for specifying the weights are described in Section 2 in detail. Section 3 presents the computational studies, while conclusions are summarized in Section 4.

2. Additive dispatching rule In general, a dispatching decision is required whenever the system enters in a state where there are one or more eligible AGVs and one or more eligible parts waiting in the output buffers of workstations, simultaneously. This description of the dispatching state generalizes the workstationinitiated and vehicle-initiated dispatching cases, as well as single-load/multi-load AGVs and FIFO or random access output buffers. Note that for AGVs with single-load carrying capacity the eligible set reduces to idle vehicles, and for the sake of simplicity, the reader may assume the case with

67

single-load AGVs in what follows, although the dispatching rule developed can easily be extended to multiple-load AGV systems. Under the proposed multi-attribute dispatching rule, whenever the system is in a dispatching state, the most preferred AGV-workstation pair (j,s) is selected such that D ¼ maxfDjs ¼ ðW P F WS ðsÞ þ W T F V ðj; sÞÞ=ðW P þ W T Þg; where the weights WP and WT reﬂect the relative criticality of the processing and transportation sub-systems, respectively, while FWS and FV correspond to two criteria involved, as described below: F V ðj; sÞ ¼ d js ; 0pd js p1; F WS ðsÞ ¼ Bs qs ; 0pqs p1: The variable djs denotes normalized travel distance from current location of vehicle j to the pick-up station of workstation s. The pair with maximum distance has value of 1. Since shorter distance is preferable the minus sign is used. The variable qs, on the other hand denotes the normalized output buffer size, i.e. current buffer length/buffer capacity, of workstation s. Note that when used individually, (d js) corresponds to STT and qs reduces to MROQS. The parameter Bs is an index for ‘‘proneness to blocking’’ for workstation s as deﬁned by Kim and Hwang (1999). Initially, all Bs are equal to one. A workstation that experiences a blocking is suspected to have a high risk of having another blocking compared to others. Therefore, whenever workstation k gets blocked, the value of Bk is increased while the values of others are decreased. Suppose that the tth blocking has just occurred at workstation k, the updating procedure works as follows: Btj ¼ Bt1 j ð1 DÞ for all jak; Btk ¼ Bt1 k þD

X

Bt1 j :

jak

Determination of the incremental parameter D requires some experimentation with the system.

ARTICLE IN PRESS 68

U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

It is now necessary to ﬁnd a reasonable basis to determine the weights WT and WP. We propose two methods: one is based on parameters of the given system and calculated off-line, while in the second weights are calculated dynamically on-line. 2.1. Parametric weights This approach assumes that the product mix, processing routes for each product type, the expected processing time for each operation are known for the planning horizon. This information along with design parameters such as number of available machines and AGVs, and distances among workstation load transfer locations are used to develop expressions for the weights. These are then used statically over the planning horizon until a change occurs in the system in which case new weights are calculated. WP is deﬁned as an aggregate measure of machine scarcity which is given by the ratio of the total number of machines required for the system to Pthe available number of machines: WP = P k (Expected total utilization of workstation k)/ k (no. of machines in workstation k). If WP is close to one then the system is highly loaded, if WP41 then the workload exceeds the available capacity. Similarly, to develop an expression for WT a measure for the criticality of the transport resource should be deﬁned. Let ¯tul be the average unloaded trip time to pick a load, and L be the time required for pick-up operation, or loading time. ð¯tul þ LÞ can be used as a proxy measure for AGV response time to a transfer call. Obviously, unloaded trip times are not known a priori since the origin and destination of each empty run is based on a dispatching decision. However, an estimate for ¯tul can be obtained by estimating the total unloaded travel time of AGVs using one of the methods described by Egbelu (1987b). Expected processing ¯ on the other hand, can be time per operation, P used as a proxy measure for the frequency of ¯ can be transport calls. Therefore, ð¯tul þ LÞ=P interpreted as the capability of AGVs to serve the transfer calls. If this ratio is greater than one then the unloaded trips are too long to meet the demand of the workstations. However, this ratio

does not take into account the number of AGVs in the system. If number of AGVs is not enough, then the situation is even worse, and if there are more AGVs than needed, then this excess can improve the situation. So a correction factor Uagv given by (Estimated AGV requirement /Available number of AGVs) is used. AGV requirement can be estimated again by using one of the methods suggested by Egbelu (1987b). As a result, the criticality index for the transportation system is calculated as ¯ W T ¼ ð¯tul þ LÞU agv =P: It may be worthwhile to compare this criticality index with those that were previously suggested in literature. Tanchoco et al. (1987) deﬁned the ‘‘cycle ratio’’ for this purpose as the ratio of the average operation time per part to the average total transport time required to move a part from the ﬁrst to the last workstation. The time required to do pick-up or drop-off operations is not included in the transport time. The ‘‘T/P ratio’’ used by Han and McGinnis (1989) is the ratio of the pure travel time for one transfer to the pure processing time on a workstation. This also does not consider the pick-up or drop-off times. In the ‘‘P/T ratio’’ suggested by Kim and Tanchoco (1993) the average transport time per transfer includes the pick-up or drop-off times. Note that in all of these the transport time corresponds to the loaded trip time and unloaded trips are not considered. The criticality index deﬁned here is based on average unloaded trip duration and pickup time as well as an AGV scarcity factor. Preliminary experimentation with these different indices indicated that the one proposed here seems to be a more appropriate measure of the criticality of the transport resource. 2.2. Dynamic weights In this approach, the system is allowed to ‘learn’ its own characteristics throughout evolution and calculate the weights periodically referring to some system statistics. The method to update the weights in each period is described below starting with WPt. Let TWCarrt be the total work content of jobs that have arrived during period t. If total

ARTICLE IN PRESS U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

workload in a period t exceeds the total available machining time for the period (TMT), then the excess work will overﬂow to the next period congesting the system. Deﬁne wPt as the observation related to the criticality of the processing subsystem during period t. Hence, wPt ¼ ðTWCarrt þ overflowt1 Þ=TMT; and

69

Table 1 Characteristics of workstations

WS1 WS2 WS3 WS4 WS5

Number of machines

Input buffer capacity

Output buffer capacity

2 1 2 2 1

3 2 4 4 2

3 2 4 4 2

if wPt 41 then overflowt ¼ ðwPt 1ÞTMT; else overflowt ¼ 0: The weight is calculated using a smoothing function with a as the smoothing constant:

Table 2 Processing data for the test facility

W Pt ¼ awPt þ ð1 aÞW Pt1 :

Job type Processing sequence and time (s)

Mix (%)

To calculate the second weight, the observation related to the criticality of the transportation subsystem during period t, wTt, is smoothed in a similar fashion:

A B C D E

10 25 20 25 20

WS1(180)-WS2(240)-WS3(360) WS1(200)-WS2(260)-WS4(240)-WS5(180) WS2(220)-WS3(320)-WS1(280)-WS4(220) WS3(300)-WS4(220)-WS5(140) WS1(280)-WS3(340)-WS4(160)

W Tt ¼ awTt þ ð1 aÞW Tt1 : Average waiting time at output buffers during period t, AWTt, is proposed as a measure of AGV response time to a transfer call. Hence, wTt in the above smoothing function is calculated as ¯ t; wTt ¼ AW T t =P where Pt is the average processing time per operation for jobs that arrive during period t. By means of these smoothing functions the effects of both the historical trend and the possible shifts in product types, demand mix or arrival process are incorporated in the weights. WPt and WTt calculated at the end of each period t will be normalized and used as weights during period t+1. Initial values WP0 and WT0 are taken as 0.50 and the system quickly smoothes these to the actual values. The smoothing constant and the length of the updating period t should be determined through some experimentation.

3. Numerical experimentation The experiments are conducted based on a hypothetical facility whose operating data are provided in Tables 1 and 2 (Bilge et al., 2002).

Jobs are randomly generated according to the part mix ratio. Jobs enter the system through the Receiving Department and leave through the Shipping Department. Parts at the input buffers of workstations are processed on the ﬁrst-come ﬁrst-served basis, whereas parts at the output buffers can be loaded on AGVs in any order. The AGVs can carry one unit load at a time and they are always routed along the shortest path to their destination. Breakdowns are not considered. To avoid possible deadlock situations, a Central Buffer station is used as temporary storage. Figs. 1 and 2 show two different ﬂow-path layouts created for the simulation experiments. In Layout A the ﬂow path is a single loop, whereas in Layout B there are two short-cuts that make Receiving close to many delivery points while some of the workstations become more difﬁcult to be reached from others. A software previously developed by Bilge et al. (2000) for simulation of AGV systems is used as the experimentation environment. The objectoriented architecture of this software provides the ﬂexibility to model a large range of job shop environments and implement new decision algorithms with different levels of intelligence and

ARTICLE IN PRESS 70

U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

Fig. 1. Layout A for simulation experiments.

Fig. 2. Layout B for simulation experiments.

complexity with relative ease. The described test facility is modeled in this environment and the proposed algorithms are implemented in C++ and included in the decision tools library of the software along with existing ones. Preliminary experimentation is carried out to determine the parameters used in the algorithms. The smoothing constant a is set to 0.80, the updating period for the dynamic weights is selected as 1 h, and D for updating B values in FWS is set to 0.167 (1/number of stations excluding Receiving and Shipment).

3.1. Comparison with single-attribute dispatching rules The performances of the proposed strategies that will be referred as PARAMETRIC and DYNAMIC are compared to STT and MROQS rules with respect to the number of jobs that can be completed in two shifts. Seven cases with different relative processing and transportation sub-system criticalness are prepared: Case 1: The processing times in Table 2 ¯ ¼ 120: AGV speed is are divided by two giving P

ARTICLE IN PRESS U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

1 m/s. Loading time (L) and unloading time of a part are 30 s each. Case 2: The processing times are as in Table 2 ¯ ¼ 240: AGV speed is 0.5 m/s. Loading giving P time (L) and unloading time of a part are 30 s each. ¯ ¼ 240: AGV speed is 1 m/s. Loading Case 3: P time (L) and unloading time of a part are 30 s each. ¯ ¼ 240: AGV speed is 1 m/s. Loading Case 4: P time (L) and unloading time of a part are 10 s each. Case 5: The processing times in Table 2 are ¯ ¼ 480: AGV speed is multiplied by two giving P 1 m/s. Loading time (L) and unloading time of a part are 30 s each. ¯ ¼ 480: AGV speed is 1 m/s. Loading Case 6: P time (L) and unloading time of a part are 10 s each. ¯ ¼ 480: AGV speed is 1 m/s. Loading Case 7: P time (L) and unloading time of a part are 10 s each. Number of machines is increased to meet expected machine requirements in each workstation resulting in a total of 12 machines in the system. In Case 1 the system is very lightly loaded. In Case 2 AGV sub-system is severely, in Case 3 moderately critical with respect to processing subsystem. Case 4 is a balanced case where capacities meet demand for both sub-systems. For Cases 5 and 6 workstations are bottleneck. In Case 7 processing sub-system is moderately critical. Each simulation experiment lasts 21 h with ﬁve replications. The results of the ﬁrst ﬁve hours are discarded in order to account for the predetermined transient period, and the results of the remaining 16 h (two shifts) are used for analysis. In Fig. 3 which displays the results for layout A with four AGVs, it can be seen that for cases 1 to 3 STT rule performs very well as opposed to MROQS which is the worst. In these cases, PARAMETRIC and DYNAMIC rules perform much better than MROQS, relatively close to STT. In case 4, all rules except MROQS can manage to complete all the loads arriving in two shifts. In remaining cases system is highly loaded and MROQS dominates STT as expected. In these cases, PARAMETRIC and DYNAMIC are the most successful rules. Fig. 4 depicts the situation when the number of AGVs is increased to ﬁve making AGVs less scarce. As expected, while this improves the situation for the ﬁrst three cases where the AGV sub-system is critical, it does not

71

Fig. 3. Throughput levels for layout A (4 AGVs).

Fig. 4. Throughput levels for layout A (5 AGVs).

help with cases 5, 6 and 7 where the processors are the scarce resources. On the whole, PARAMETRIC and DYNAMIC rules seem to be very robust, always performing the best or very close to the best. Layout B with four AGVs behaves somewhat different (Fig. 5). As Egbelu and Tanchoco (1984) indicated, the performance of STT rule is signiﬁcantly affected by the layout properties. Since closeness is the measure used to select a department for vehicle dispatching it may happen that some departments would be chosen less often than others or never chosen. Those departments will suffer abnormally long output buffer length that may eventually cause blockage. This is the situation for WS 3 in this layout. While MROQS

ARTICLE IN PRESS U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

72

Table 3 Processing data for the second job set in responsiveness tests Job type Processing sequence and time (s)

Mix (%)

F G H I J

25 25 20 10 20

WS1(400)-WS3(700)-WS4(520) WS2(520)-WS4(400)- WS5(640) WS2(560)-WS3(440)-WS5(350)-WS1(680) WS3(480)-WS1(360)-WS2(720) WS1(640)-WS4(560)-WS5(440)

Table 4 Throughput comparison under varying demand Fig. 5. Throughput levels for layout B (4 AGVs). Average throughput

performs nearly the same in both layouts, the performance of STT is severely impaired for layout B. PARAMETRIC and DYNAMIC rules are still very robust except Case 1, where weights signiﬁcantly favor the travel time component. This brings into mind, incorporation of another component, statistic or parameter which can detect the existence of a workstation with signiﬁcantly disadvantaged location, as a further study. 3.2. Test for responsiveness In order to test the responsive capability of the suggested algorithms a change of workload and ﬂow pattern is introduced in the middle of the simulation run. After discarding the ﬁrst 5 h as the transient period, each simulation experiment lasts 24 h with 10 replications. During the ﬁrst 12 h, the set of parts in Table 2 are produced with processing times divided by two (Case 1). In the second half, a different set of parts as shown in Table 3 are produced. Layout A is used with four AGVs, an AGV speed of 1 m/s and loading/ unloading time of 30 s. For the PARAMETRIC rule new weights are introduced at the end of 12 h. Here, to examine the signiﬁcance of the parametric and dynamic weights another strategy that employs equal weights (0.50) statically in the additive dispatching function is also introduced. This is referred as EQUAL WEIGHT in Table 4, which summarizes the results. The results show that DYNAMIC and PARAMETRIC rules are signiﬁcantly better than MROQS and EQUAL

MROQS EQUAL WEIGHT PARAMETRIC DYNAMIC STT

Std. Dev

90% CI LCL

UCL

301.1 322.0

3.929 7.196

298.823 317.829

303.377 326.171

334.3 337.4 359.2

6.019 5.317 5.574

330.811 334.318 355.969

337.789 340.482 362.431

WEIGHT. STT is the best performer in this scenario because of its dominance during the ﬁrst 12 h. The responsive behavior of the rules can best be examined in Fig. 6 which presents the average hourly output. It should be noted that although the new set of jobs start arriving at the beginning of the 13th hour, it takes a while for them to reach their downstream workstations and to change the job composition on the shop ﬂoor. For the static rules STT, MROQS and EQUAL WEIGHT this time lag depends on the performance of the dispatching rule during the ﬁrst phase. A sharp decrease in the output rate is observed for STT at the end of the 13th hour after which it settles at its new level, while it takes longer for a similar decrease to occur for MROQS and EQUAL WEIGHT. However, for the PARAMETRIC rule the effect of the new weights is observed at the beginning of the 13th hour, causing an immediate but gradual decrease, and then after some ﬂuctuation output rate settles a new level slightly higher than STT. For the DYNAMIC rule on the other hand, the smoothing procedure tracks the change

ARTICLE IN PRESS U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

73

Average Output Rate 24.00 20.00 16.00 12.00 8.00 4.00 0.00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 time (hours) DYNAMIC

MROQS

PARAMETRIC

EQUAL WEIGHT

STT

Fig. 6. Average output rate in tests for responsiveness.

Average Weights 1.00 0.90 0.80 0.70 0.60 0.50 0.40 0.30 0.20 0.10 0.00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 time (hours) DYNAMIC

PARAMETRIC

Fig. 7. Average weights WTt in tests for responsiveness.

in the job composition resulting in a better response. Fig. 7 is the plot of the average normalized weights WTt. 3.3. Comparison with an existing multi-attribute rule The same experimental setting as in Section 3.2 is also used to compare the performance of the

DYNAMIC rule to that of the multi-attribute dispatching rule proposed by Kim and Hwang (1999). As stated earlier, Kim and Hwang employ three attributes which are combined in product form as fD fS/fA, where fD and fS are based on normalized WIP inventory levels in the incoming buffer of the destination workstation and the outgoing buffer of the source workstation, respectively and fA is the travel distance. The parameters

ARTICLE IN PRESS 74

U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

used in fD and fS are updated using historical information. The ﬁrst set of experiments is conducted with the input and output buffer capacities of workstations as in Table 1. The results summarized in Table 5 show that the DYNAMIC rule outperforms Kim and Hwang’s heuristic. Since in Kim and Hwang’s heuristic, the parameter used in fD is designed with the underlying assumption of equal buffer capacities for all workstations, the experiments are also repeated for the case where all buffer capacities, both input and output, are equal to four. The results for this case are also given in Table 5 where it can be observed that the DYNAMIC rule still performs signiﬁcantly better than Kim and Hwang’s heuristic. These results actually indicate a very important phenomenon regarding input buffers. In Kim and Hwang’s heuristic, input buffer starvation criterion is incorporated in such a way to favor any input buffer which is underutilized relative to others, regardless of the bottlenecks in the system. However, although input buffers of bottleneck workstations should not be allowed to starve, it is not clever to prioritize workstations with low demand on this basis. Hence, it may be concluded that incorporating input buffer related criteria requires speciﬁc care; otherwise they may lead into loss of robustness. So, although the results do not exclude the possibility that our rule might be improved by means of a carefully designed third criterion involving input buffer status, they demonstrate that the DYNAMIC rule is still very robust even without one.

4. Conclusion The main aim of this paper is to discuss both the value and possible ways of incorporating responsiveness in automated guided vehicle dispatching, rather than just proposing yet another AGV dispatching rule. The experimental setting is designed such that the critical resource in the system switches among transportation and processing subsystems, posing the challenge of responding such switches and remaining robust for different system characteristics. Although STT and MROQS were presented 20 years ago, they represent two basic ‘pure’ criteria, and still do perform competitively under given conditions— critical transportation subsystem and critical processing subsystems, respectively—as shown in our experiments as well as elsewhere. Therefore, they can be considered as a ‘base’ of comparison actually for all other dispatching rules, especially on account of robustness, and this also the reason why they are used as the building blocks of our decision rule. This study demonstrates the importance of identifying the critical resources when dispatching AGVs and applying a responsive decision procedure so that critical resources are well utilized. Multi-attribute dispatching seems to be a natural way to deal with a complicated manufacturing system with a number of critical resources. Our simulation study reveals that the proposed rules achieve this to a great extent. The criticality of a resource can be deﬁned as a measure which is positively correlated to the probability that the resource becomes a bottleneck resource in the system. New indices to represent

Table 5 Throughput comparison of two multi-attribute heuristics under varying demand Average throughput

DYNAMIC (variable buffer) Kim and Hwang (variable buffer) DYNAMIC (all buffer sizes=4) Kim and Hwang (all buffer sizes=4)

337.4 311.6 324.7 315

Std. dev

5.317 11.955 4.448 6.749

90% conﬁdence interval LCL

UCL

334.318 304.670 322.121 311.088

340.482 318.530 327.279 318.912

ARTICLE IN PRESS U. Bilge et al. / Int. J. Production Economics 100 (2006) 65–75

the criticality of the processing and transport resources in a manufacturing system are proposed in this paper. Interestingly, the performance of both responsive strategies are very close to each other in nearly all cases, which shows that the parametric indices and the dynamic statistics selected in the two approaches are consistent with each other. Obviously, selection of appropriate attributes, parameters, statistics and the procedure to compute the weights play a very important role, and the approach described in this paper is just one example among the many possible. The proposed AGV dispatching rules are not only robust and effective on their own account, but they also reveal the merit of incorporating responsiveness into decisions on material ﬂow control and justify further research in this direction.

Acknowledgements The work reported in this paper is supported by Bog˘azic- i University Research Fund under Grant No: 01S107, and by State Planning Organization under Grant No: 01K120310.

References Bilge, U¨., Alp, A., Aydin, B., Esenduran, G., O¨ztu¨rk, Z., Varol, N., 2002. Multi-attribute responsive dispatching for AGVs, Proceedings of the Second International Conference on Responsive Manufacturing, Gaziantep, Turkey, pp. 806–811. Bilge, U¨., Draman, M., Dogˇan, D., 2000. An object oriented test-bed for design and real-time control of AGV systems, Proceedings of Second Workshop on Production Planning and Control, Mons, Belgium, pp. 128–134.

75

Egbelu, P.J., 1987a. Pull versus push strategy for automated guided vehicle load movement in a batch manufacturing system. Journal of Manufacturing Systems 6, 209–221. Egbelu, P.J., 1987b. The use of non-simulation approaches in estimating vehicle requirements in an automated guided vehicle based transport system. Material Flow 4, 17–32. Egbelu, P.J., Tanchoco, J.M.A., 1984. Characterization of automatic guided vehicle dispatching rules. International Journal of Production Research 22, 359–374. Han, M.H., McGinnis, L.F., 1989. Control of material handling Transporter in automated manufacturing. IIE Transactions 21, 184–190. Kim, S.H., Hwang, H., 1999. An adaptive dispatching algorithm for automated guided vehicles based on an evolutionary process. International Journal of Production Economics 60–61, 465–472. Kim, C.W., Tanchoco, J.M.A., 1993. Operational control of a bidirectional automated guided vehicle system. International Journal of Production Research 31, 2123–2138. Kim, C.W., Tanchoco, J.M.A., Koo, P.H., 1999. AGV dispatching based on workload balancing. International Journal of Production Research 37, 4053–4066. Klein, C.M., Kim, J., 1996. AGV dispatching. International Journal of Production Research 34, 95–110. Sabuncuog˘lu, I., Hommertzheim, D.L., 1992a. Experimental investigation of FMS machine and AGV scheduling rules against the mean ﬂow-time criterion. International Journal of Production Research 30, 1617–1635. Sabuncuog˘lu, I., Hommertzheim, D.L., 1992b. Dynamic dispatching algorithm for scheduling machines and automated guided vehicles in a ﬂexible manufacturing system. International Journal of Production Research 30, 1059–1079. Taghaboni, F., 1997. A value-added approach for automated guided vehicle task assignment. Journal of Manufacturing Systems 16, 24–34. Tan, K.K., Tang, K.Z., 2001. Vehicle dispatching system based on Taguchi-tuned fuzzy rules. European Journal of Operational Research 128, 545–557. Tanchoco, J.M.A., Egbelu, P.J., Taghaboni, F., 1987. Determination of the total number of vehicles in an AGV-based material transport system. Material Flow 4, 33–51. Yim, D.S., Linn, R.J., 1993. Push and pull rules for dispatching automated guided vehicles in a ﬂexible manufacturing system. International Journal of Production Research 31, 43–57.