Faculty Research University of Michigan Business School I k I, ", Transfer Batth Sizing in Flexible Manufacturing -Systems J Andre Longevin Ecoie Polytechnriqu d- Montreal -...; f-. Diane Riopel Ecole Polytechnique de Montrea! Kathryn, E. Stecke University of Mihigan Business School Working Paper 98-021R * -- a 1 A

TRANSFER BATCH SIZING IN FLEXIBLE MANUFACTURING SYSTEMS Andre Langevin Department of Mathematics and Industrial Engineering tcole Polytechnique de Montr6al Diane Riopel Department of Mathematics and Industrial Engineering tcole Polytechnique de Montreal Kathryn E. Stecke School of Business Administration The University of Michigan Abstract This paper presents methods to determine the optimal transfer batch sizes of" various part types between two machines so as to minimize the sum of the total relevant costs. Information required includes the expected production requirements, the operations' processing times, the travel times, the inventory carrying costs, and other information. The total relevant cost components include material handling, pallet, holding, and machine costs. The structure developed is relevant to an activity-based costing system. Scheduling is optimized so as to attain a good machine utilization. Mathematical programs are developed to minimize total costs subject to the appropriate constraints. Finally, comparisons to other possible and typical methods of transfer batch sizing are done in order to show the relevance of the new proposed methods. Keywords: Transfer Batch Sizing, Material Handling, Flexible Manufacturing System, Cost Analysis, Optimization

1. Introduction Given the production requirements and the processing times of operations, this paper presents a method to determine the transfer batch sizes of various part types between two machines so as to minimize the sum of the total relevant costs. Comparisons to other methods of transfer batch sizing are done. A major contribution of this paper is that all of the relevant costs that should be taken into account are considered. The method presented herein considers explicitly the indirect costs, which are traditionally taken care of by means of a global percentage added to the direct costs. Our approach is more akin to activity-based costing schemes. At the same time, we also optimize the scheduling of the parts in order to obtain good machine utilization. The problem that we study consists of a two-stage production sub-system that processes one or two part types. The results found here could also be applied as a heuristic to two-machine subsets of larger systems. There are orders for r1 parts of type i. The sub-system is a flow shop, i.e., each part has to be processed on both machines in the same order. All orders are available at time zero. Parts are put on pallets in a preparation station and carried to the first machine for processing, then to the second machine, and finally back to the preparation station. We initially consider that the material handler is an automated guided vehicle system (AGVS). However, the subsequent analysis holds for any intermittant materials handler, such as lift trucks, conveyors, and trains of trays. The problem studied here applies to flexible manufacturing systems (FMSs), where a make-to-order setup is implemented. A system such as the one considered can 1

be found at the Laboratoire Universitaire de Recherche en Production Automatis6e (L.U.R.P.A.) in Ecole Normale Sup6rieure de Cachan, France, a university laboratory of research in automated production. They constructed in the later eighties a two-machine FMS consisting of a milling center and a turning machine. The two machines are supplied by two AGVs carrying tools and parts from a manual preparation station where they are set up for processing. In this FMS, machining time is offered to external clients. Another eight-machine FMS like the type considered here is the Sundstrand/Caterpillar line in Peoria, Illinois. There are many FMSs with multiple parts on several fixture types. The methods proposed here can help to determine the appropriate number of parts that should be on a fixture. The system can be schematized as in Figure 1. There are two machines, M1 and M2, with the input station (I) and the output station (0) of the manual preparation station. Some related material handling literature includes Egbelu', which uses a dynamic programming-based heuristic algorithm to estimate the completion time of the requirements of a single part type. A sensitivity analysis is performed to observe the effect of changes in completion time due to changes in: (1) the transfer batch size, (2) the material-handling time, (3) the transfer batch preparatory time, and (4) the processing times of the operations. The model applies to the planning of production of parts of a single type through a multi-stage production system. However, this approach does not determine the optimal transfer batch sizes for part types. Potts and Baker2, Trietsch and Baker3, and Baker and Jia4 solve a similar problem: to split an order into different transfer batch sizes in order to minimize the 2

maximum completion time. These authors consider optimizing the transfer batch sizes with or without intermittent idling of machines. Queues are allowed at the machines. Bakers considers setup times for a two machine flow shop. Glass et al.6 provide an analysis of lot streaming for a single order in three-stage production processes (for flow shops, job shops, and open shops). At each stage, the order is split into s batches. The authors propose algorithms to minimize makespan. Mahadevan and Narendran7 present an integer programming formulation for the problem of finding the optimal transfer batch size and the number of AGVs required to avoid both bottleneck situations as well as gross under-utilization of AGVs at the FMS design phase. Askin and Madhavanur5 examine a flow shop where workers are responsible for both machine operation and material handling. An efficient algorithm computes the cycle time for a single part type and this algorithm is used to help determine the optimal number of equal-sized transfer batches. Finally, these results are extended and tested for a flow shop producing multiple part types. Kim et al.9 solve a transfer batch scheduling problem for a two-stage flow shop with identical parallel machines at each stage. They suggest a rule similar to Johnson's to minimize makespan. Smunt et al.'0 investigate transfer batch sizing for both stochastic job and flow shops using performance measures of mean flow time and standard deviation of mean flow time. They found that the number of transfer batches is more important than the exact form of splitting. 3

The previous papers may have considered a single cost component or none at all. We try to consider all relevant costs for the transfer batch size decision. In this paper, we believe that the decision on how to split the order should be based not only on the completion time and the limited transporter capacity as in Trietsch and Baker3, but also on all other relevant costs. The makespan affects costs and the objective here is then to minimize the sum of total relevant costs. The plan of the paper is as follows. The cost components are discussed in detail in section 2. We examine the problems of determining the optimal transfer batch size for a single type of part in section 3 and for two types of parts in section 4. Comparisons to other transfer batch sizing methods are presented. Section 5 concludes and outlines some future research needs. 2. Cost Components Based on some cost discussions in Sule", Mahadevan and Narendran7, and Lee2, we consider that four different types of costs should be taken into account in the transfer batch size decision: material handling, pallet, holding, and machine costs. The underlying idea is that all used services (i.e., moving) have to be paid for and hence charged to the specific order. The percentage of indirects costs may vary from one order to another according to the actual required services. The detailed analysis of costs presented hereafter allows an evaluation of the amounts to be charged to each order. This information can then be used in activity-based cost accounting schemes. Activitybased costing ideas are useful for the cost categories that we identify here. Some useful related discussion can be found in Cooper13 and Koltai et al.'4. For our evaluation 4

purposes, it is not necessary to consider the fixed costs as step functions. It is sufficient to allocate the fixed costs (overhead costs) to the appropriate material handling or machine costs. (See Cooper and Kaplan'5 and Koltai et al.14.) The system parameters are summarized in Table 1. There are two machines. Let N be the number of part types and r1 is the required number of parts of type i, for i=1 to N. For each part type i, the number of parts required r, and the processing times pqi for a part on machine j are given. Let u, be the maximum number of parts of type i that can fit on a pallet. The AGVs travel from the preparation station to machine 1 in time tM1, then from machine 1 to machine 2 in time tMI,2, and finally back to the preparation station in time t^,.. Table 1 System Parameters. R number of round trips N number of part types r,: number of parts of type i required, i = 1,...,N p,j processing time of a part of type i on machine j tiMI travel time from the input station to machine 1 tMI.M2 travel time from machine 1 to machine 2 tM20 travel time from machine 2 to the output station MH$ charged cost of the handling equipment to the transfer batch per round trip Hi$ inventory holding cost per time unit for a part of type i P$ set-up cost per pallet + utilization cost per pallet Pi$ value of a part of type i M$ hourly machine rate I % of inventory value per time unit ul: upper bound on the number of parts of type i that can fit on a pallet 5

The decision variables are k, the transfer batch size for part type i. The parameters related to costs are: MH$, the charged cost of the handling equipment per trip; P$, the pallet cost; Hi$, the inventory holding cost, and M$, the hourly machine rate. We can express the total cost as: Total Cost = Material Handling Cost + Pallet Cost + Holding Cost + Machine Cost. We now discuss each of the cost components in turnm.The material handling cost accounts for the fixed and variable operating costs to use the material handler. It can be evaluated using the number of round trips (R) times the service cost of the handling equipment for one trip (MH$). This service cost may be estimated considering the maintenance, energy, depreciation over its life period, and system operators' salary (Sule11). Material Handling Cost = R x MH$. The pallet cost evaluates the expenses associated with the preparation and utilization of the handling containers. In the machining industries, the handling containers are pallets on which parts are positioned for (perhaps automated) pick-up and drop-off. The pallet cost is composed of fixed and variable components. The fixed component is the number of round trips, R, (corresponding to the number of pallet loads processed) times the pallet set-up and utilization cost (P$). Mahadevan and Narendran7 propose these types of costs in their model reviewed in section 1. The variable cost is the number of parts times the handling cost per part. The sum of the variable costs is a constant and thus may be eliminated from the model. The preparation cost can then be written: 6

Pallet Cost = R x P$. The holding cost corresponds to the opportunity cost (lost interest) of the capital required for the work-in-progress. The holding cost for a part of type i (Hi$) is calculated by multiplying the percentage of the inventory value per time unit with the value of the part. The duration (i.e., makespan, the total time in the system for all parts of all part types) is a function of the particular part type parameters, such as the processing times. Holding Cost = duration x Ei (Hi$ x ri). The machine cost corresponds to the time during which the machines cannot be used to process anything else. It is given by the duration times the hourly machine rate (M$). Rather than duration, this should be the actual machining time. For the purposes of this paper, these are both the same. In our first case, we schedule a single part type. In the second case, we consider two part types. As long as we don't schedule additional production, the duration is equal to the actual machining time. This $ per hour machine cost can be calculated based either on the cost of the available or on the cost of the used resources (see Cooper and Kaplan15). There are several ways to calculate this cost (see, for example, Hakala16 and Koltai17). Also, Lee12 shows how to evaluate this rate over the machine's anticipated life. Machine Cost = duration x M$. There is a relationship between the transfer batch size and the machine costs. The lead time, duration, and WIP costs change. The duration then impacts the machine costs. The material handling costs and the machine costs can be similar in scale. When they are not, one will dominate. Holding costs may be either signifiant or neglible. 7

Some parts in process can cost thousands of dollars. When neglible, other cost components will then dominate. Next, we specify the cost components for the first situation considered, one part type, in Section 3. 3. Optimum Transfer Batch Size for a Single Type of Part A characteristic of the system considered here is that there are no buffers at the machines: a pallet has to be carried away before another pallet can be brought in to a machine. We have a sufficient number of AGVs and pallets. 3.1 Cost Analysis We now determine k1, the number of parts to be moved on each pallet. As r, is the total number of parts to process, the number of pallet round trips, R, is given by rrj/kl. In what follows, we assume that r,/k, is integer. The cost components are as follows. Material handling cost = (r/kl) x MH$ Pallet cost = (r1/k1) x P$ Holding cost = duration x r, x H1$ Machine cost = duration x M$. To calculate the duration, one must consider two cases: CASE a: If p1 2 P2, then: duration = t,. + rp, + tM,, + klp2 + t.0 This corresponds to the time to carry the first pallet to the first machine (t, M), plus the production time for all of the parts on the first machine (rapl), plus the time to move 8

the last pallet from machine 1 to machine 2 (tm,.m2), plus the time to process the last pallet on the second machine (k,p2), and finally the time to bring the last pallet to the output stage (t2,0). We assume that the time to transfer the pallet between the machine and the AGVs is negligible. See Figure 2 for a schematic of this. CASE b: If p, < P2, then: duration = t,M + k1p, + tM.M2 + riP2 + t2,. This is analogous to the first case except that the processing time on machine 1 is smaller. See Figure 3. 3.2 Cost Optimization The total cost function can now be written as follows. CASE a: If p,: p2, then TOTAL COST(k1) = (r,/k1) MH$ + (r1/k1) P$ + (t,,M + rip, + tM1M2 + klP2 + to) r1Hl$ + (tMi + r,p, + tM,.2 + k1P2 + tM.o) M$. CASE b: If p, < p2, then TOTAL COST(kI) = (r,/k,) MH$ + (r,/k1) P$ + (t, + k,p + tMl,2 + r,2 + tM2o) r1H1$ + (t,M, + k1,p + t,,M2 + rqP2 + to) M$. Both can be simplified by aggregating the constant terms as follows: TOTAL COST(k1) = A/k, + Bk, + C, whereA=r,(MH$+P$), B=p,(r,Hl$+M$), and C=(tM,,+ttmM2+rp2+t0)(riH1i$+M$). TeThese B and C are the constants for Case b, in which pi<p2. For Case a, where p1 p2, B and C can be derived similarly. 9

To find the optimal solution, one has only to find the value k, for which the derivative of the Total Cost function is null: d(TOTAL COST)/d(k1) = - A/k2 + B = 0. => k1 = (A/B)12. The TOTAL COST function is a convex function when k1 > 0. Hence ki is a minimum. If k, isn't integer, one has to look at LkJ and Fk,1' to find the best integer solution. Let k,~PT be the best integer solution. If k1 is integer, then kPT = k,. The optimal number of parts on a pallet is given by min {u,, k1OP"}, where u, is the maximum number of parts that can fit on a pallet. 3.3 Experimental Design and Results Tests have been performed to demonstrate the utility of this new method to determine transfer batch sizes. We let the cost parameters assume different values corresponding both to real cases as well as the literature. Some examples of these tests are now provided. We have done about 500 test comparisons (Crepel et al.'1) both to study the influence of the cost parameters on the optimal solution as well as to compare these results with the following two other possible methods of transfer batch sizing: a) determining the transfer batch size to equal either the number of parts to be produced or the maximum number that can fit on a pallet, i.e., k = min (u,, r1 }, (a traditional and typical approach to material handling... this is thought to minimize AGV purchase costs); 10

b) determining the transfer batch size to equal one (similar to a just-in-time approach). We present next a sampling of the tests. For the following examples the processing times are: p, = 3 minutes and P2 = 5 minutes. Parameters are: (1) For the material handling cost (MH$): Buying cost of an AGVS: $100,000 Life time: 5 years Maintenance: $1.50 per hour Energy: $10 for 8 hours Distance: 9,750 feet per day Wages: $3 per hour (the system operator is paid $30 per hour and takes care of 10 vehicles) Exchange time: 15 seconds Total round trip: 780 feet Speed: 104 feet per minute 2) For the pallet cost (P$) Preparation time: 10 minutes Wages: $10 per hour Multi-purpose pallet cost: $1 (3) For the holding cost (H1$) Price of part: $100 Interest rate: $0.10/$ per part per year (4) For the machine cost (M$) Machinery rate: $50 per hour per machine. For these costs: MH$ = $8.14, P$ = $2.67, H1$ = $0.003472, M$ = $100. With this particular system data, and for production requirements increasing from 10 to 1000 parts, the total cost function is developed as described previously. For each case, the optimal transfer batch size is calculated and provided in Table 2. Also contained in Table 2 are the total costs of always transferring one part at the time (JIT) 11

and the cost of transferring all the required parts at once. For each value of r, the optimal batch size and the corresponding optimal total cost are presented in bold. Table 2 Results for One Part Type. l r || I E10 15 50 80 100 200 500 1000 k 4.65 5.69 10.39 13.13 14.68 20.72 32.60 45.71 LkJ 4 5 10 13 14 20 32 45 Cost of LkJ 142.06 192.51 519.86 788.52 965.29 1835.01 4416.39 8766.33 rkl 5 6 11 14 15 21 33 46 Cost of rkl 141.66 192.11 519.95 788.79 965.16 1834.90 4416.36 8766.28 (1) 11.5% 10.6% 7.8% 6.4% 5.6% 4.2% 2.8% 2.0% (2) 3.8% 3.5% 2.6% 2.1% 1.9% 1.4% 0.9% 0.7% (3) 0.0% 0.0% 0.2% 0.2% 0.3% 0.7% 1.6% 3.3% (4) 84.7% 85.9% 89.4% 91.3% 92.2% 93.7% 94.7% 94.0% Cost of k=1 208.13 302.22 961.23 1526.64 1903.85 3793.17 9494.95 19108.29 Cost of k=r 155.84 220.92 676.96 1068.75 1330.38 2643.89 6639.07 13477.53 (1) Percentage of the material handling cost on the total cost (2): Percentage of the pallet cost on the total cost (3): Percentage of the holding cost on the total cost (4): Percentage of the machine cost on the total cost The proportion of the four costs included in the production cost was calculated. As can be seen in Table 2, the total production cost computed for the optimal transfer batch size is, for any values of the parameters, always smaller than the costs obtained with the other two proposed methods of transfer batch sizing. However, the difference is significant mostly when there is a large number of parts to be produced (more than 200 parts) and there is a small pallet cost. Nonnegligible savings can be accrued by the methods proposed here when large production requirements are needed. 12

The largest cost component, regardless of the number of parts required to be produced, is the machine cost (see Table 2). All of the other costs are smaller, and their relative proportions vary with the numbers of parts to produce. In general, the inventory cost can account for up to 7%, the material cost for up to 15%, and the pallet cost for up to 9%. Considering only the pallet, material handling, and inventory costs, the material handling cost represents more than 50% for small and medium production requirements (10 to 200 parts) but less than 35% for large batch sizes (500 to 1000 parts). This is true in case of a low pallet cost and long machining time. The higher the pallet cost is, the higher this percentage becomes. The results demonstrated here are surprisingly robust. Similar results have been observed for over 500 cost structures (see Crepel et al.18). 4. Optimum Transfer Batch Size for Two Types of Parts When the master production plan indicates that two types of parts have to be processed within a certain time horizon, one cannot just apply the method described in section 3 to each type. The scheduling is more complicated because of the two part types. The scheduling method affects total duration. Scheduling should also now be optimized to maximize the machine utilizations. Again, each part must be processed first on machine 1 (flow shop). In some cases, because of morphological issues, it is impossible to combine two types of parts on the same pallet. It may also be possible that the two processes may require too many tools to be stored in the tool magazines at the same time. Under these 13

conditions, there may be no advantage in interrupting the processing of the parts of one type to produce some of the other. This is a nonpreemptive case and is the case considered here. In this nonpreemptive case, the optimal order (w.r.t. system utilization) in which the parts are processed can be determined by Johnson's algorithm. In the following, the type of parts to be processed first according to Johnson's algorithm is defined as type 1. Some additional notation required is as follows. r: number of parts of type 1 required (given); r2: number of parts of type 2 required (given); k,: number of parts of type I in a transfer batch (to be determined); k2: number of parts of type 2 in a transfer batch (to be determined). Then we have r,/k, (r/k2) = number of round trips for parts of type 1 (type 2). 4.1 Cost Analysis The four types of costs discussed in Section 2 have to be considered. They become: Material handling cost = (r1/k1 + r2k2) x MH$ Pallet cost = (r1/k1 + r/k2) x P$ Holding cost = duration x (rH1$ + r2H2$) Machine cost = duration x M$. With the parts of type 1 scheduled first according to Johnson's algorithm, then either p,, or p2 is the minimum of all pij. To derive the duration, we proceed as in the first problem, i.e., we use charts like Figure 1 to develop the formulae for all possible 14

cases of the ordering of the pij. The formulae are presented in Table 3 and are more complex than in the first problem because of the possibility that the last pallet is not full. If we assume that r1/k, is integer, the formulae for the duration reduce to the following four (depending on the value of the parameter 6 in Table 3). Case A: If the longest processing time (LPT) is on the second machine, there are two subcases: Al1: If rp1 + k 2P 21 5 kp,1 + rp12, then duration = k1pl + rIp12 + r2P2 + t, (1) where t = tiM + t1,M2 + tM2, (time for a round trip). A2: If rp1, + k 2P 21; k,p,, + rjP12, then duration = rp,1 + k2p21 + r2p= + t. (2) Case B: If the LPT is on the first machine, there are again two subcases: B1: If r2P21 + k2P2 2 k1p12 + r2p2, then duration = r1p,1 + r2p2, + k2Ip + t. (3) B2: If r2P21 + k k 2 k, + r2p22, then duration - r1p11 + k1P12 + r2P22 + t. (4) Note that when rtpl + k2p22 = k1pl, + r^1p2 (Subcases Al and A2), equation (1) = equation (2). Similarly, when r2p21 + k2p= = k1p, + r2p22 (Subcases A3 and A4), equation (3) = equation (4). 15

Table 3 Duration Formulae for Two Types of Parts. CASES DURATION FORMULAE with pn, c SPT _ 6 max 0 r.11 + - - ir } P1~Pi12Pn~P21r + L r/k2 J kp21 + k2p2 + (r2modulo k2) p22 P I S2;P21PP22 k~P + rl12 + r, + r dP 6 = max { o, rp,, + k2,p, - kp,, - r,p12 } P"5P12;Pz2pP2' __P,, + L r2k2 J kP2. + k2p2 + (r2 modulo k=) P2 Pl ~P21 5P2P12 klp + r P2 + 62.....~~~~~~6. _=mx-,a- '. - r,2 kip } ~p11 SP~~22!~P2I~5P1,2 Wk,p,, +,12 + r222 + d d = max { o, rp, + k22, - k,p,, - r1p,2 } Pl P22P2;P2 1 rk k + P12,1 o k) + r 2,p + 6 = max (, rmax, + r2p21-o L I r k2p J k P12p- r,P,2- k,p,, }) 12 P225;P21Pi;P2,P12 kp,, + rPr12 + rp + 6 = max { o, rp11 + k2P, - k1p, - rp12 } p~ CASES.... + + (.m P22 P215P2iPl, P1L rlk, J k rp,, + kp,2 (rt modulo k,) P.2 + r2P + I__________________ < = max {o. rp,, + ro2, - Lr, lk J ktp,, - k,p,2 - (r, modulo k,) p,,2} _pn;p2^p,^p,1..,,,...... +p,,. + d p22:5.IJ5P2:5P2 12 + rp2rp + - max (o, rp,, + k2 - kp,, - r,p,,2 } P2.P.2.P25P.1 rp,, + r__ (r,2 modul.o k) p, P;P22Pi25P5P21 r:p + r2 + (r2 modulo k2) p= |_______________________P22_ max {o, ripl + r kP21 - kp - rPl2 }P PP22;PnPi2SP2. rsp1 + r2p= + (r2 modulo k~) Pz 16

4.2 Cost Optimization The next step consists of formulating a mathematical program to evaluate the optimal k, and k2. Table 4 summarizes the objective functions (C(k,,k2)) and the constraints for the four possible cases. Table 4 Mathematical Models to Minimize Total Costs. 0 Case] C (ic, k) Constraints A1 (MH$ + P$)(r1/k, + r2/k2) + rlp, + k2p2, k1,p, + rp (k1p,, + rp1 + r2p,2 + r t) 1 ~ k, U *(r,H$ + rH$, + M$) I_ 1 s k2, ~ u, A2 (MH$ + P$)(r1/k1 + r2/k2) + rp, + k2P21; k1p11 + rp, (rp,, + k2p21 + r2p2 + t) 1 k, < u |*(rH$, + rH$,+M$) I1 I k,, u, B1 (MH$ + P$)(r,/k, + r2/k2) + r2p21 + k2p22 k,2 + r2P22 (rp11 + k,p12 + r2p22 + t)1 k, u, * (r,H$, + rH$+M$) 1 Is k2: B2 (MH$ + P$)(r,/k1 + rJk2) + r2P21 + k2P22 kip12 + r2p2 (r1pi1 + r2p21 + k2p= + t) I k, u, * (r,H$, + r2H$2 + M$) I k u, We now explore in detail, Case A1, i.e., when the duration = k,p,, + rp,1 + r2p2 + t. We want to find the values of k, and k2 that minimize the total cost. We have the following mathematical program: 17

Problem (P1) min C (k,, k) = (MH$ + P$) -+ +k kl k= + (k1p,, + rp,2 + r2P22 + )(H1$r, + H2$r2 + M$) subject to rp1 + k2p21, i k1p1 + r1P12 (5) 1 ~; k1 ~ u, (6) 1 k5 k2 u2, (7) where C(k,, k2) is the total cost when the transfer batch sizes are k, and k2. Recall that u, and u2 are the maximum numbers of parts of each type that can fit on a pallet. The feasible solution set (S) to Problem (P1) is a convex and bounded polygon, and the objective function is convex over this polygon. Because Ck = - (MH$ + P$) < 0 for all k2 a2 k2 the optimum is necessarily on the upper border of the solution set S. The upper border consists of all points (k,, k2) such that k = max{k: (k,, k) E S}. ac (M$ - P$) r We have that + p 11 (Hl$r, + H2$r2 + M$) = 0, ak, k 2 18

>k- (MH$ + P$) r, p,1 (Hl$r, + H2$r2 + M$) So if (MH$ + P$)r, (8) p, (Hf$r, + H2$r2 + M$) ' 2 satisfies equations (5 - 7), then it is the optimum solution, (k,*, k2*). Otherwise, the optimum is located at one of the vertices of the solution polygon S or possibly on the line segment defined by equation (5). If the optimum is not given by equation (8), then the possible solutions of Problem (P1) (shown in Figure 4) are: u(k )Pl + rP2 - rlPl- (9) (k,, k2) = u1, '11 p1 111 (9) P21 or rPll + U2P21 - rP12 u2 (10) or 11 J (U, u2) (11) or (1, u2) (12) or 1 P11 + rP2, - r P11 P (13) P21 19

or riP1 + P21 - rP12 1 (14) Pnl One has to check which of these points satisfies equations (5 - 7) and gives the best solution. One has also to check for a possible optimum on the edge of the solution polygon S corresponding to equation (5). (This could happen if, at one point of the segment, the gradient of C(k,,k2) is orthogonal to the segment). To find the optimum, the objective function has to be expressed in terms of k, only (using equation (5)). Then its derivative is evaluated at the two ends of the line segment. If they are of different signs, there is an optimal solution between the two, which can be found by a dichotomic search along the segment. Figure 4 illustrates all possible cases of Problem (P1) for Case A1. A similar analysis can be performed for Cases A2, B1, and B2. Table 5 presents a summary of the results. Then when the LPT of the operations is on the second machine (Case A) and (k^1A, k2A) and (k,2, k2*2) ar e thelocal optimum solutions for Cases A1 and A2, respectively, then the global optimal solution is simply the lower cost of the two. In other words, the optimum transfer batch sizes are: (k;, k2) = argmin { C (kI, kJ: [(k1, k =(k A', kA ) or (k,. k/)l}. A similar analysis holds for Case B. 20

Table 5 Possible Optimal Points for the Four Cases. ".-~,,, _.. -, --- "-~.,..'.-~.-~ ---- -_.. Il Case Al Case A2 Case 81 Case B2 ^t1M | $)r N fS | - opt J.. ( +. solution P,1(rH$S + H2$ + +) ' u |, p2(rH1l$ +rH2$+$ ) NP(rH$+r2 + + 2$+M$), u U, u 1 P (rHI$ +r H2$ +M$) (1, u) (u,1) (1 3) (U1. 1) i(U U2) (I U) (U, 2)( (u, u2) otherwise, feasible, one of u 1P124P + 23 ( + -r p2 these U., UzPn+r2Ptart.a1) U1 U1p r2 + p3- r. p1, (U / U1 u112. + 'I PI Pa vertices of P) P''1 ) P2 p) the solution polygon s P^+rP -ru ) ( (1 ptl+ -rp2 | (P)| p 2 rp22-r2p2 ) on the edge defined by the first on the edge defined by the first on the edge defined by the on the edge defined by the first constraint of Case Al constraint of Case A2 first constraint of Case 81 constraint of Case B2 theI rIorio s~~ ~otutton ~ a~c ytefrt ontecs eie ytefrt nteeg eie yteo te dedfndb h i p~~~olyg~to (BeA osten fCseA ibonstri o a B nten f S 8.. A 21

4.3 Experimental Results Extensive testing of the method presented in the section 4.2 has been conducted using various values for the parameters and are reported in Marcoux et al.19. We present a sample of the results in Table 6. In this example, the values of the parameters are the same as those used in section 3.3, except for the following: P1$ = $50, P2$ = $50, p1 = 8 minutes, p12 = 20 minutes, P21 = 10 minutes, and p22 = 25 minutes. The upper bounds on the number of parts of each type that can fit on a pallet is set equal to 25. Table 6 Results for Two Types of Parts..~.. if...,,,,,.......,....... 11 Optimal solution 11 Integer Solution 11 Cost($) of k1,k2= r^i2 r r. r2 | Case k, k2 Cost($) k, k2,1 r,,r 10 10 A1 2.847 10.000 852.12 3 10 994.8 920.26 10 15 A1,A2 2.920 14.336 1061.39 3 14 1257.35 1128.77 15 15 Al 3.486 15.000 1245.3 3 15 1478.23 1362.31 15 25 A1,A2 3.550 20.840 1664.53 4 21 2003.49 1779.50 25 15 Al 4.501 15.000 1605.92 4 15 1920.10 1829.53 25 25 Al 4.500 25.000 2023.22 4 25 2445.49 2246.87 50 50 A1 6.361 25.000 3963.38 6 25 4865.89 4460.96 100 100 Al 8.989 25.000 7824.86 9 25 9716.47 8900.64 100 200 A1 8.981 25.000 12069.75 9 25 14998.94 13104.50 200 100 Al 12.701 25.000 11288.58 13 25 14161.20 13606.91 200 200 A1 12.690 25.000 15546.58 13 25 19456.69 17826.00 500 500 A1 19.962 25.000 38924.00 20 25 48989.82 44970.11 1000 1000 A 25.000 25.000 78829.22 25 25 99253.32 91437.06 22

Conclusions similar to those presented in section 3.3 can be drawn for this two part types problem. Material handling costs are nonnegligible. They account for up to 7% of the total costs and if we consider only the pallet, inventory, and material handling costs, the material handling cost accounts for up to 85%. Much savings can be obtained by choosing the appropriate transfer batch size instead of strategies such as transferring one part at a time (JIT) or all of the required parts at once. 5. Conclusions Methods to determine optimal transfer batch sizes between two machines are developed for several simple cases. All relevant cost components are considered. For two part types, optimal scheduling is done to maximize machine utilizations. Mathematical programs are developed to minimize the sum of the relevant costs. Comparisons to other methods of transfer batch sizing show the usefulness of considering costs. These costs could be part of an activity-based cost accounting system. Also, the methodology should be applicable to different cost elements and assumptions, which leads to a robust methodology. Other possible uses of the methods are for operational purposes, in allocating costs to make such transfer decisions. The methods should also be useful for design purposes, in determining the appropriate number of AGVs to buy. Methods are presented here for two part types and two machines. These methods can also serve as heuristics for larger problems, in particular, when there are 23

more than two machines. The methodology may be applied to a larger class of more complex problems in the future. Another extension to consider is when more than one part type at a time can be transported. This possibility is a function of the fixturing capabilities, tool magazine capacities, tooling requirements, and relative sizes and weights of the part types. Methods also need to be developed when there are many part types to be processed. In all cases, costs and utilizations should be considered. When relevant, due dates also need to be included. Acknowledgements The first two authors would like to acknowledge the NSERC Program as well as the FCAR Program which supported in part this work. Kathy Stecke would like to acknowledge a Research Grant from the Center for International Business Education as well as a Summer Research Grant from the Business School of The University of Michigan. This research was done in part while Kathy visited at GERAD in Montreal. The authors would especially like to thank the three referees for their careful reading, comments, and suggestions. 24

REFERENCES 1. P.J. Egbelu, "Batch Production Time in a Multi-stage System with Materialhandling Consideration," International Journal of Production Research (v29, n4, 1991), pp695-712. 2. C.N. Potts and K.R. Baker, "Flow Shop Scheduling with Lot Streaming," Operations Research Letters (v8, 1989), pp297-303. 3. D. Trietsch and K.R. Baker, "Basic Techniques for Lot Streaming," Operations Research (v41, n6, 1993), pp1065-1076. 4. K.R. Baker and D. Jia, "A Comparative Study of Lot Streaming Procedures," Omega (v21, n5, 1993), pp561-566. 5. K.R. Baker, "Lot Streaming in the Two Machine Flow Shop with Setup Times," Annals of Operations Research (v57,1995), ppl-11. 6. C.A. Glass, J.T.N. Gupta, and C.N. Potts, "Lot Streaming in Three-stage Production Processes," European Journal of Operational Research (v75, n3, 1994), pp378-394. 7. B. Mahadevan and T.T. Narendran, "Determination of Unit Load Sizes in an AGVbased Material Handling System for an FMS," International Journal of Production Research (v30, n4, 1992), pp909-922. 8. R.G. Askin and D. Madhavanur, 'The Effect of Operator-Based Material Handling on Optimal Transfer Batch Size," Proceedings of the 5th Material Handling Research Colloquium, Phoenix, Az (1998), pp1-14. 9. J.-S. Kim, S.-H. Kang, and S.M. Lee, 'Transfer Batch Scheduling for a Two-Stage Flowshop with Identical Parallel Machines At Each Stage," Omega (v25,n5, 1997), pp547-555. 10. T.L. Smunt, A.H. Buss, and D.H. Kropp, "Lot Splitting in Stochastic Flow Shop and Job Shop Environments," Decision Sciences (v27,n2, Spring 1996), pp215 -238. 11. D.R. Sule, "Manufacturing Facilities: Location, Planning and Design," (PWS-Kent Publishing Company, Boston, MA, 1988). 12. R.J.V. Lee, "Design Considerations of Automated Guided Vehicles in a Cellular Manufacturing Environment," International Journal of Operations & Production Management (v13, nl, 1993) pp35-55. 25

13. R. Cooper, "Cost Classification in Unit-based and Activity-based Manufacturing Cost Systems," Journal of Cost Management (Fall, 1990), pp4-14. 14. T. Koltai, S. Lozano, and F. Guerrero, and L. Onieva, "A Flexible Costing System for Flexible Manufacturing Systems Using ABC," Working Paper (n97-1, 1997 Technical University of Budapest, Department of Industrial Management, Hungary). 15. R. Cooper and R.S. Kaplan, "Activity-based Systems: Measuring the Costs of Resource Usage," Accounting Horizons, (September, 1992), pp1-13. 16. G. Hakala, "Measuring Costs with Machine Hours", ManagementAccounting (v67, n10, 1985), pp57-61. 17. T. Koltai, "Fixed Cost Oriented Bottleneck Analysis with Linear Programming," Omega (v23, n1, 1995), pp89-95. 18. S. Crepel, A. Langevin, S. Meslier, and D. Riopel, "Lot de transfert: etude du cas d'un type de pieces sur deux machines," Technical Report (EPM/RT-93/24, Departement de genie industriel, Ecole Polytechnique de Montreal, 1993). 19. N. Marcoux, A. Langevin, and D. Riopel, D., "Lot de transfert: etude du cas de deux types de pieces sur deux machines, Technical Report (G-95-1 1, GERAD, Ecole des Hautes Etudes Commerciales, Montreal, 1995). 26

FIGURES Figure 1: A Two-Machine FMS Figure 2: Chart Demonstrating the Total Time in the System for One Part, Case a: p, P2 Figure 3: Chart Demonstrating the Total Time in the System for One Part, Case b: p, < P2 Figure 4 All Possible Cases for Subcase Al 27

BIOGRAPHIES Dr. Andr6 Langevin is Professor in the Department of Mathematics and Industrial Engineering at Ecole Polytechnique, Montreal, Quebec, Canada. He holds a B.Sc. in Mathematics from UQAM, Montr6al, Qu6bec, Canada. He received a M.Sc.A. in Industrial Engineering and a Ph.D. in Operations Research from Ecole Polytechnique, Montreal, Quebec, Canada. His research interests encompass logistics, distribution and mathematical optimization. His articles have appeared in International Journal of Production Research,lnternational Journal of Flexible Manufacturing Systems, Transportation Science, Networks, INFOR, and other journals. Dr. Diane Riopel is an Associate Professor in the Department of Mathematics and Industrial Engineering at Ecole Polytechnique, Montreal, Qu6bec, Canada. She holds a B.Eng. and a M.Sc.A. in Industrial Engineering. She received a doctorate in Industrial Engineering from Ecole Centrale de Paris, France. Her interests are in the area of facility layout, material handling, warehousing, and logistics. Her articles have appeared in International Journal of Production Economics, International Journal of Production Research, International Journal of Flexible Manufacturing Systems, International Journal of Engineering Design and Automation, INFOR, and other journals. Dr. Kathryn E. Stecke is the Jack D. Sparks/Whirlpool Corporation Research Professor in Business Administration at the School of Business Administration at The University of Michigan. She received an M.S. in Applied Mathematics, and an M.S. and Ph.D. in Industrial Engineering from Purdue University. She has authored numerous papers on various aspects of FMS planning and scheduling in numerous journals including The FMS Magazine, Material Flow, International Journal of Production Research, European Journal of Operational Research, lIE Transactions, IEEE Transactions on Enineering Management, Annals of Operations Research, Performance Evaluation, Management Science, Operations Research and several proceedings and book contributions. She is the Editor-in-Chief of the International Journal of Flexible Manufacturing Systems. She is a member of INFORMS, SME, and IFIP Working Group 5.7. 28

E - I Z b i 7 - -~ - - ~ --- vx- ii. - -- ~ -~- ~ — ~ — -— '

I U) E E........ C14.................... I E; I m IQ~t I I, X{ * 0 Je Co - C Qi itSi ~ C ~a. - it - ~// ~ /n -2 2 ~,r.. - ~ -. - ~:N.. / r ~ r q ~ Ir 0 I 1 ~ - -

__ __ ___ _I__ __ _I ___ __ _ _ ___ _____ ____ __ __ _ _ I_ ___ __ _~ __ _ __ 1_1 _ _ I M1 M2 O i.. ~.. \ ^ \ ~ \ \ \ X \ \ \:....... I; e;:.1 1 ' _ ' 4' kp;: l- -- ^- * - ~- ^***** ** **: * --- k-^ -lf....... f..,................................ kp, \ kipi kipi kp, \ ~ \ \ \:: \ * \ \ \ I 1 * 0 *.... I I I * a * * *....................... e ~~ ~ ~ ~rl~ ~~~ *. -* weFs,,***,.*.1 _ \-' -.......... -... ^ --- "P2........ \:.\ \ \: \. ) P2 k-p2 IPkiP22:...... \ s \. e' tlM1I tM1,M2 _.d _t.. riP2 tM2,0 _.. _1. - _ I I _ — O- _ _ ppll I _ time -.. ---- -- Travel Time Processing Time

I I~ I I -I ~ ~ kel U 2 (11) U 2: e (8) (9) (13) I II. 1 U1 k I 1 Ul k 1 k2A U - 2I i (8) (11) I 'i12) I i I I k2A U2; i 1 + I 1 Ui k - - 1. U1 k2A 2; i 1 -:feasible solution set: upper border of the solution set *: possible optimal solutions 1 u1 k (#): equation number a _ _I ~ ____.II rl