THE IMPACT OF PROCESSING TIME VARIABILITY ON A SYNCHRONOUS ASSEMBLY LINE Steven J. Erlebacher Medini R. Singh Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 92-55 October 1992 Revised July 1993

Abstract We consider synchronous assembly lines where processing times are variable and incomplete jobs are reworked at the end of the line. The objective is to minimize the total expected work overload on a job. We explore patterns of variance allocation that yield the best and the worst performance. We demonstrate that an allocation which spreads the variance equally among all the stations may not be optimal and may in fact be the worst allocation. We discuss the implications of these results for assembly line design, operation, and performance improvement. 1

The assembly line has become the ultimate machine of mass production since its grand design by Henry Ford in 1913. Among factors that led to the widespread use of this mode of production are economies of scale, specialization of labor, use of automated technology, and dedicated material handling systems. However, gone are the days of Model T cars where a manufacturer could exploit the benefits of the assembly line to the fullest extent by producing exactly the same product over and over for a long period. Today, shortened product life cycles, product proliferation, and niche markets have motivated manufacturers to tailor their products to consumer preferences. The number of models of a given product and the variety of optional features available are increasing. Greater flexibility during assembly is required to accommodate this diversity. It is a common practice in many industries such as auto, household appliances, etc. to assemble several models of a product on the same line because the demand for a single model does not warrant a dedicated line or because potential sales volumes for individual models are uncertain. For example, AutoAlliance, a joint venture between Ford and Mazda, currently assembles Ford Probes, Mazda MX-6s, and Mazda 626s on the same line in Flat Rock, Michigan. Such assembly lines, known as mixed model lines, present great difficulty in balancing the work across stations. No matter how carefully tasks are grouped, these lines typically exhibit a high level of variability in processing times due to differing processing requirements across models and options. For example, assembling a four-door car has significantly more processing requirements than a two-door car. Similarly, a car with a sun-roof or a power-option-package requires additional work during assembly. The changes in model-mix and release sequence further adds to this variability. A number of other factors contribute to the increase in processing time variability both for a mixed-model as well as dedicated lines. These factors include unforeseen disruptions due to machine or tool failures, variation in worker skill and experience across different tasks, natural human variation in a repetitive manual work environment, and decline in operator speed due to fatigue, etc. Variability in processing time adversely affects the performance of an assembly line. For exam 2

pie, an increase in processing time variability tends to reduce the throughput of an asynchronous assembly line. Similarly, an increase in processing time variability leads to higher rework costs or poorer labor utilization on a synchronous assembly line. While the degradation in performance with increasing variability is only natural, the extent of this degradation is highly dependent upon where variability is increased. Two identical lines, both with the same amount of total variability, may perform quite differently depending upon how variability is distributed across various stations. This raises several interesting questions. Where should one increase the variability such that it has the least detrimental effect on the performance of the line? Equivalently, where should one decrease the variability to achieve the most improvement in performance? More generally, how should one allocate the variability across the stations such that minimum degradation in performance is achieved for a given level of overall variability? And finally, how does this allocation change as the level of overall variability increases or decreases? Answers to these questions are important for the design, planning and improvement of assembly lines. A number of researchers have explored these questions for asynchronous assembly lines i.e., lines where stations are separated by buffers. Readers are referred to an excellent survey by Baker (1992). Since the adverse effects of processing time variability can be reduced by providing buffers between stations, buffer allocation constitutes an important decision for these lines and has attracted significant attention in the literature. The interaction between buffer allocation and the allocation of processing time variance is quite complex. For this reason, most researchers assume an equal buffer allocation when exploring the allocation of processing time variability and its effect on the throughput of asynchronous lines. The seminal work of Hillier & Boling (1966), which first pointed out the bowl phenomenon, is based on both mean and variance imbalance since it considers stations that have exponentially distributed processing times. Later, researchers attempted to isolate the impact of variance allocation from the effect of mean imbalance. For example, Rao (1976) considers a three station 3

line and concludes that "for the large differences in coefficient of variation (among stations), the variability imbalance clearly plays a decisive role compared to the mean imbalance." The impact of positioning stations in an asynchronous line according to their level of processing time variabilities has been studied by Kala & Hitchings (1973), Carnall & Wild (1976), Rao (1976), Smith & Brumbaugh (1977), Wyche & Wild (1977), and El-Rayah (1979). These studies indicate that the relative positioning of stations according to the level of processing time variability does affect the throughput of the line. However, their findings are somehow inconsistent. While Carnall & Wild (1976) and El-Rayah (1979) point to the superiority of the bowl-shaped variance allocation over other variance allocation patterns, Kala & Hitchings (1973) and Smith & Brumbaugh (1977) both contradict these results. This contradiction possibly arises due to differences in the levels of preassigned variability to the stations among different papers. This leads us to a more fundamental question: how is the performance of a line affected by different patterns of allocating a total variability to the stations? This question is addressed by Lau (1992) for an asynchronous line where processing times are distributed either normally or uniformly. He investigates the impact of different variance allocation patterns on throughput while keeping the total variance constant. He finds bowl-shaped and symmetric patterns of processing time variances desirable, which can be explained by the bowl-phenomenon and the well-known reversibility property (Muth, 1979). However, Lau (1992) also points to the attractiveness of a spike-shape allocation where all (or nearly all) the variability is concentrated into only one station and all other stations have zero (or very close to zero) variability. This is a surprising result. Unfortunately, this work does not give an indication as to under what circumstances a spike-shape allocation will be better than a bowl-shaped or symmetric allocation. Finally, the allocation of higher order moments has also been considered by Lau (1986) and Lau & Martin (1987). Lau (1986) concludes for a two-station line without buffer that "one should perfectly balance the mean and the skewness of the stages' processing times, but the variance and the fourth moment need not 4

be balanced." For longer lines, Lau & Martin (1987) conclude that stations with higher positive skewness should be positioned towards the center of the line and stations with lower positive skewness should be positioned towards either the beginning or the end of the line. While the impact of variance allocation on the performance of asynchronous lines has been studied extensively, little work has been done on understanding the effects of variance allocation on synchronous lines. In fact, we are not aware of any work that explores this issue either analytically or via simulation. This is surprising considering the widespread use of synchronous lines in industry e.g. in the trim area of automotive assembly. This paper investigates the impact of processing time variability on a synchronous assembly line. In particular, we consider a line where jobs move synchronously to the next station every T time units. Processing times are normally distributed with mean processing time Ct. Should the processing at a station require longer than the cycle time T, the residual work is considered to be "overload" at the station. Our objective is to minimize the total expected work overload across all the stations. This objective is meaningful in environments where all unfinished work is completed at the end of the line and the cost of rework is proportional to the amount of unfinished work. As a first step towards understanding the impact of processing time variability on synchronous lines, this study identifies the best (and the worst) patterns of variance allocation conducive to minimizing the total work overload. Our results indicate that there are two desirable patterns of allocation: (i) equal allocation, where variability is evenly distributed among all the stations, and (ii) spike-shaped allocation, where most of the variability is concentrated into only one station and all other stations have relatively little variability. These allocation patterns are similar to those obtained by Lau (1992) for an asynchronous line based on simulation studies. Our work not only establishes the desirability of these allocation patterns analytically, but also establishes the circumstances under which each of these patterns is best. Specifically, we show that if the total amount of variability exceeds a critical level, then a spike-shaped allocation of variance is 5

optimal; otherwise, the equal allocation is optimal. As the total variability increases beyond the critical level, the spike-shape becomes more pronounced; that is, the allocation at all stations except one approaches zero. The performance of the equal variance allocation degrades rapidly as the total variability increases beyond the critical variance level. In fact, beyond a point any further increase in variability makes the equal variance allocation the worst possible allocation. In circumstances where a single spike-shape allocation is not possible, we show that it is desirable to have an allocation with as few spikes as possible. Lau (1992) notes that for asynchronous lines " the effect of variance allocation is surprisingly small, and may be ignored." However, unlike asynchronous lines where the impact of variance allocation on the performance is negligible, our results demonstrate that synchronous lines are highly sensitive to the variance allocation pattern. Moreover, the optimal allocation pattern for a synchronous line can be found extremely efficiently for any number of stations, as shown in this paper. This is in contrast to the determination of desirable allocation patterns for asynchronous line, where the computational requirements significantly increase with the number of stations. The remainder of the paper is organized as follows: The next section contains a formal statement of our model and the problem addressed. Sections 2 and 3 establish the optimal pattern of variance allocation for lines with two and an arbitrary number of stations, respectively. In Section 4, we discuss the implications of results derived in Sections 2 and 3 and their implications. Section 5 provides managerial insight based on the results. We end the paper with some final thoughts in Section 6. 1 Problem Formulation Consider a synchronous assembly line with n stations that is designed for a throughput of 1/T, i.e. jobs spend T time units at each station. Station processing times are stochastic and assumed to be 6

normally distributed with mean Mi. Since several elemental tasks, each of which take an uncertain amount of time, comprise the work at each station, the total processing time at a station tends to be normal. Normality of processing has been used and verified by many authors, including Wilhelm (1987). The average processing time at each station is kept the same so that the line is balanced. Also, union rules may preclude assigning more work to some workers than others. Suppose the line has inherent variability V, which must be allocated among the n stations. Consider a station which has been allocated variance v. The expected work overload for this station is given by f (v)- (/e- e) dt = /EZ ( T-t) - (P T - ) ( p (T)) T( = Vwhere Z (x) and P (x) are the standard normal probability density and cumulative distribution functions evaluated at x, respectively. The function f (v) is continuous and differentiable with lim f (v) = 0. For large v, f (v) T - -ir 2 A graph of f is shown in Figure 1. The problem we address is: How to allocate the total variance in such a way as to minimize the total expected work overload on a job. Mathematically this can be expressed by the following optimization problem: n (PI) Minimize F(vI, v2,,Vn) f (vi) i=1 n subject to vi = V i=1 v, 0,Vi Note that the objective can also be interpreted as the total expected work overload across all stations on any cycle. If f was convex, then the problem (Pl) would be a special case of the resource allocation problem addressed by Zipkin (1980), Luss & Gupta (1975) and others, who minimize a convex 7

nonlinear-additive objective function subject to a single linear constraint using a very efficient ranking algorithm. In fact in that case, the problem (P1) could be solved trivially since each nonlinear function is the same. Unfortunately, f (v) is not convex as can be seen by examining the second derivative of f, I (v)= 4v5/2 ((T-_L)2 _ v) Clearly f" (v) > 0 only if v < (T -,)2 and hence f is not convex. So in this sense, the problem (PI) is very different than the classical resource allocation problems. Before we explore the solution to problem (P1) for n stations, we investigate the optimal solution for a two station problem. The solution to the two station problem will provide crucial insights which will allow us to solve the n station problem. 2 Analysis of a Two Station Line For n = 2 the problem (P1) reduces to: (P1.1) Minimize F (v, v2) f (vi) + f (v2) subject to vl + v2 = V (1) Vl,V2 _ 0 We have only two decision variables and three constraints (including the non-negativity constraints). While this problem is symmetric in VI and v2, the following theorem states the optimal solution is not necessarily symmetric. Theorem 1 For the problem (P1.1) there exists a lower critical variance level V2- 2 (T - )2 8

such that the equal variance solution is optimal if and only if the total variance V < V2. Moreover, an optimal unequal variance solution either occurs at an extreme point or satisfies the equation A (Vi) = (V2) (2) where Z( ) Ax(v)= 2V. (3) This result is not intuitive. Due to the symmetric nature of problem (p1.1), a casual observer would have guessed that the equal variance solution would always be optimal. However, Theorem 1 states that this is only conditionally true. If the total variance is large enough (greater than the lower critical variance for a two station problem, V2), then an unequal variance solution is optimal. This behavior of the optimal solution is explained intuitively as follows: If an inherently large amount of variability exists, at least one station will have a significant amount of variance. Once one station has been assigned some variance, it is better to keep putting more of the variance at the same station because the effect of marginal variability on a station that already has significant variance is much less detrimental than the effect of marginal variability on a station that has little or no variance. The function A (v) plays a critical role in determining the optimal allocation. The graph of A (v) is shown in Figure 2. Clearly A (v) is unimodal and approaches 0 as v goes to infinity. Additionally, the global maximum of A (v) occurs at V = (T - A)2 = V2/2. These facts will be established later in Lemma 1. In fact, equations (1) and (2) define the first order conditions for the problem (P1.1). The intersection of A (vi) with its reflection about the line vi = V/2 gives the first order points as shown in Figures 3a and 3b. It is clear from these figures that one first order point will always be at Vl = V/2. The other first order points always appear as a symmetric pair. Whether there is one first order point or three depends on whether the point of reflection V/2 is greater than or 9

less than V as illustrated in Figures 3a and 3b, respectively. The corresponding objective functions F(vl,v2) = F (v, V - vl) are shown in Figures 3c and 3d, respectively. Note that in Figure 3d where V < 2V = V2 that the equal variance solution is the global minimum while in Figure 3c we have V > 2V = V2 and an unequal variance solution is optimal. Proof of Theorem 1: We recast problem (P1.1) as a single variable optimization problem by substituting V - vi for v2. (In what follows we drop the subscript on vi since it is the only decision variable.) The new optimization problem is given by (P 1.1') Minimize W (v, V) f (v) + f (V - v). 0<v<V The function W is the objective function from (Pl.1) with V - v substituted for V2. The first station receives v units of variance and the second station receives the remaining V - v units of variance. Differentiating W with respect to v and using equation (3) we obtain e= A (v) - (V - v). Clearly the first derivative vanishes at v satisfying A (v) = A(V - v). (4) An optimal solution to problem (Pl.1') must take one of the following two forms: 1. v = V/2, the equal variance solution, or 2. v Z V/2, an unequal variance solution. We first show that for V > V2, the equal variance solution can not be optimal. We will prove this by showing that for V > V2, the equal variance solution is a local maximum and hence can not be a global minimum. First note that v = V/2 satisfies equation (4) and as a result must be either a 10

local minimum, a local maximum, or a point of inflection. But &2W -x (~~ ) /2Z ( T- 9v2 y V5/2 2 ) /V/2 v2z(^} 5/ V2(2 -) < 0 for V > V2. Hence for V > V2 the equal variance solution is a local maximum and hence can not be a global minimum. This proves that for V > V2, an unequal variance solution is optimal. It remains to be shown that if (v*, V - v*) is an optimal unequal variance solution, then V > V2. Consider first the case when v* = 0. We show in Theorem 2 that for any V < V2, the equal variance solution dominates an extreme point solution; thus, an extreme point solution can not be optimal. As a result, if an extreme point solution (0, V) is optimal, then V > V2. Finally, consider the case when v' > 0. We must show that if (v*, V - v*) is an optimal unequal variance solution, then V > V2. In fact we will show that a more general result holds-for any unequal variance solution (v0, V - vO) satisfying the first order condition A (v~) = A (V - v0), it must be true that V > V2. Before we establish this fact, we need to demonstrate the following properties of A (v): Lemma 1 A (v) is unimodal and its mazimum occurs at v = V. Proof of Lemma 1: Observe that z (T}) ) = z( ) >'(v) =, ( c~2_ v)..... (V-v) crosses 0 only at v = V. Moreover, A' (v) > 0 for v < V and A' (v) < 0 for v > V. Hence A (v) is strictly increasing on (0, v, strictly decreasing on (V, oo), and achieves its maximum at V. Assume that v~ < V-v~ without loss of generality. For any solution (v0, V - v~) which satisfies the first order conditions, we know that A (v~) = A (V - v~) = A as shown in Figure 4. Since A (v) 11

attains its maximum at v = V, it must be true that v~ < V < V - v~. Let a = V - v~. In Appendix A we show that A ( - a) < A (V + a) for O < a < V. Since A (v) is strictly decreasing for v > V, then V - v > V + a. But V = v + (v - v) > (V - a) + (V + a) = 2V = V, and hence for any unequal variance solution (v~, V - v~), v~ > 0, that satisfies the first order conditions, it must but true that V > V2. For the case when V = V2, it can be shown that the first, second, and third derivatives of W with respect to v vanish at the equal variance solution. However the fourth derivative of W with respect v is positive and hence for V = V2 is the global minimum. U Theorem 1 gives us a simple rule for determining the nature of the optimal solution to problem (P1.1). For V < V2, the optimal solution is obtained simply by allocating the variance equally. For V > V2, an unequal variance allocation (vl,v2) satisfying equations (1) and (2) is optimal. Since the unequal variance allocation (vt, v2) always appears as a symmetric pair we will not distinguish (v2, vI) from its mirror image (vl, v2). The following conjecture claims that there is only one such pair satisfying equations (1) and (2). Conjecture 1 For any V > V2 there is a unique unequal variance allocation pair (vl, V2) satisfying the first order conditions given by equations (1) and (2). Justification of Conjecture 1: Consider Figure 5 which shows a plot of (vl + v2) as a function of A such that A (Vl) = A (v2) and vl # v2. Observe that for any A E (o, A ()) there is a unique (vl + v2). As a result for any V > V2 there can be only one unequal variance allocation (vl, v2) satisfying equations (1) and (2), ignoring (v2, vl), the symmetric counterpart. 0 Our discussion so far has focused on finding the best solution to problem (P1.1). For total variance exceeding the lower critical level V2, the equal variance allocation was found to be a bad 12

choice. The following theorem indicates that it can potentially be the worst choice. Theorem 2 For the problem (P1.1), there exists an upper critical variance level V2 > V2 such that the equal variance allocation is worse than an extreme point allocation if and only if V > V2; moreover, under Conjecture 1, the equal variance allocation is the worst allocation. The critical variance level V2 is given by V2 (: ) 3.83 (T ) where x is the unique positive solution to x + Z (x) + xP (x) = V'Z (xZ2) + 2xP (xVZ). (5) Consider F (v, V - v) as a function of v for a given V > V2. It was shown in the proof of Theorem 1 that the equal variance solution is a local maximum for this function. Whether or not it is a global maximum depends upon whether the total variance exceeds the upper critical variance level, V2, according to Theorem 2. This point is illustrated in Figures 6a and 6b which show F (v, V - v) for V2 < V < V2 and V > V2, respectively. Proof of Theorem 2: Define fEv (V) = 2f(V/2) and fEp (V) = f (V). The function fEv (V) is the work overload for the equal variance (EV) solution with total variance V while fEp (V) is the work overload for an extreme point (EP) solution with total variance V. If we let x = (T - p)/-V then the equation fEP(V) = fEV (V) reduces to equation (5). Since V > 0, and there is a one-to-one relationship between positive x and positive V, we need only find positive roots to equation (5). To show that x is the unique positive root to equation (5), we consider the equation D (V) I fEP (V) - fEV (V). Now since lim D(V) = 0+ v o 13

and lim D(V) = lim ( ) = - < 0, V-W —o + V-.oo r 2 2' there is at least one root to D(V) = 0, and therefore at least one root to equation (5). To show that there is a unique root to D(V), we show that there exists a number 3 such that D' (V) > 0 if and only if V < /. This fact guarantees that there is only one root to D (V) = 0. Now, consider the first derivative of D, (T-142 D' (v) V e - 1) (T-p)2 (T-,)2 It is clear that D'(V) > 0 if and only if e2 /V/2 > 1. But e 7 /v/2 > 1 if and only if V < f3 (T - p)2 /log 2. Thus we have shown that there is exactly one root to D (V) = 0. This in turn implies that there is exactly one root, a, to equation (5). So, fEV (V) will grow at a slower rate than fEP (V) until V = / and then fEv (V) will grow at a faster rate than fEp (V), cross fEp (V) at V2 (> f), and fEv (V), will be greater than fEP (V) thereafter. Through numerical techniques, we have found that x; 0.511, which implies that V2 m 3.83 (T - lZ)2 (Note that V2 > V2.) The result that the equal variance solution is the global maximum under Conjecture 1 when V > V2 follows from the fact that the only other possibility for the global maximum is an unequal variance solution satisfying the first order conditions or an extreme point solution. We have just shown that the equal variance solution is worse than an extreme point solution. Under Conjecture 1, only one unequal variance solution pair can satisfy the first order conditions. Since V > V2 > V2, we know by Theorem 1 that this unequal variance pair must be the global minimum. U To summarize, we have shown for the two station problem that an unequal variance solution is optimal if and only if the total variance is large enough (greater than V2). Furthermore, if the total variance is greater than V2, then the equal variance solution is worse than an extreme point solution. Additionally, under Conjecture 1, the equal variance solution is the global maximum when the total variance is greater than V2. Using these results, we now address the general case 14

of the problem (P1) with n stations. 3 Analysis of an n Station Line In this section we extend the results of the previous section for instances of the problem (P1) when there are more than two stations. We first note that the problem (P 1) has a symmetric structure. That is, if (vI, v2,.,,n) is a feasible solution to the problem (P1) with objective function value F (v, v2,...*, v,), then any permutation of (vl,v2, *,Vn) is also a feasible solution to the problem (PI) with the same objective function value. Therefore, the optimal solution will not be unique unless vi = V/n for all i. We assume (without loss of generality) that vl < v2 < < _ vn. The first order conditions for the problem (PI) are given by zT-A = OYi (6) E2v- = (7) i= Notice that equation (6) is equivalent to A(v) = A. Thus, if (v, vv, v, XA*) satisfies the first order conditions for this problem then given a "potential" A*, we need only find the vi which solve A (vi) = A* and then find combinations of the vi which satisfy equation (7). While this approach may sound easy, it is not since the equation A (v) = A* is transcendental. Instead, by using some of the properties of A (v), we will characterize the optimal solution to problem (P1). We now state our first result which characterizes a local optimum. Lemma 2 Any local optimum for the problem (P1) is such that the variance allocated to each station must take one of the two values, VI < V or Vh > V. Proof of Lemma 2: If (vt, v2, *,, Xn, ) satisfies the first order conditions, then A (vi) = A* for all i. By Lemma 1 we know that A (v) is unimodal. Thus given a value of A*, it is clear that A (v) = A* 15

has at most two solutions which we call vi and vh. Since the maximum of A(v) occurs at V, it must be true that vi < V and vh > V. O According to Lemma 2, the optimal solution is such that k of the n stations will have variance vl, and the remaining n - k stations will have variance vh. Since kvi + (n - k) Vh = V, the optimization problem (P1) can be reformulated as (P1') Minimize kf (vi) + (n - k) f ( k V subject to O < vi < - 1 <k<n-1 k integer. (P1') is a nonlinear-integer program with two decision variables-vi, the low variance level, and k, the number of stations with the low variance level. Each of the remaining n - k stations has the high variance level vh = (V - kv)/(n - k). In formulating (P1') we have excluded the possibility of k = 0, i.e. no stations with low variance and n stations with high variance, which corresponds to the equal variance solution. Instead we account for the equal variance solution by noting that for any value of k if vl = V/n then vh = V/n and we get the equal variance solution. The problem (P1') is significantly simpler than the problem (P1) since for a given value of k, the optimal value of vl can be determined using a univariate search. Let vl [k] be the value of vl that minimizes the objective function in the problem (P1') for a given k. The optimal solution to problem (P 1') can then be found by comparing the objective function value for all (k, vjl[kL) pairs. Unfortunately, for a large number of stations, this procedure becomes tedious since it must be repeated n - 1 times. The following result allows us to perform the search only once and still obtain the optimal solution. 16

Theorem 3 If an unequal variance solution is optimal to the problem (PI), then all but one station have low variance. That is, an optimal unequal variance solution is spike-shape. Proof of Theorem 3: We prove the result by contradiction. Suppose that an unequal variance solution is optimal, k stations have low variance, and k < n - 1. Form a two station subproblem by considering stations k + 1 and k + 2 in isolation. We let V(k) Vk + vk+l. Clearly V(k+l) = Vk+l + Vk+2 = 2Vh > 2V = V2. Thus by Theorem 1, an unequal variance solution is better for the two station subproblem of stations k + 1 and k + 2 considered in isolation. But if the solution to this two station subproblem can be improved, this implies that the original solution to the n station problem is not optimal. (This fact is a result due to the separability of F.) Thus we have a contradiction that k < n - 1. U The consequence of Theorem 3 is that given an instance of the problem (PI), we can determine the structure of the optimal solution. Either an equal variance solution is optimal, or a spike-shape allocation is optimal with n- 1 stations having a low variance level. In either case, to find the optimal values of the vi, we only need to apply a univariate search to problem (PI"), (P1") Minimize l (vi) = (n - 1) f (v) + f (V - (n - 1) vl) O<vVI<v/n That is, if v, is the optimal solution to (P1"), then v, = vt for i = 1,...,n - 1 and v = V - (n — 1) vt. An important question still remains to be answered. When is a spike-shape solution optimal for an n station problem? Recall that for a two station problem, an unequal variance solution is optimal if V > V2. We now give an analogous result for the n station problem. Lemma 3 For the problem (PI), there exists a lower critical variance level V-n = n (T-s )2 such that a spike-shape solution is optimal if V > Vn. 17

Proof of Lemma 3: We prove the result by contradiction. Suppose V > V, but the equal variance solution is optimal. Consider any two stations in isolation. The total variance from these two stations is 2V/n > 2V = V2. So for this two station problem considered in isolation, an unequal variance solution must be optimal by Theorem 1. But since F is separable, this means that the equal variance solution can not be optimal to the problem (PI). 0 Theorem 3 characterizes the structure of an optimal unequal variance solution as being spikeshape, but says nothing about when such a solution may be optimal. Lemma 3, on the other hand, gives a sufficient condition, V > Vn, for a spike-shape solution to be optimal. However, if V < Vn, we are unable to conclude from these two results that the equal variance solution is optimal except in the case of two stations. That is, unlike the result for the two station problem, V < Vn is not a sufficient condition for the equal variance solution to be optimal. We now explore the differences between the solutions to the two station problem and the n station problem. Consider the function p2 (V) which gives the optimal lower variance to a two station problem with variance V. That is vt = (V) implies that vj must satisfy A (v1l) = A (V - v ). The function Y2 (V) has a unique value for each V as shown in Figure 7. Consistent with Theorem 1, V2 (V) is linear with slope 1/2 (denoting the equal variance solution) for V < V2 and decreases for V > V2. Now consider all first order points which are candidates for the optimal solution to an n station problem as characterized by Theorem 3. Let n(V) be a relation that gives all v* which satisfy the first order conditions of problem (PL1"), that is A (v ) = A (V - (n - 1) v1). So, 18

p (V) =v AX(v7) = ( - (n-1) v) >==> A(v ) A((V + v) - nv) '>- v; = (n+ i(V + ). Equating v7 with Pn (V) we obtain (n (V) = pn+l (V + On (V)). By induction it is easily shown that 2pk+2(V + k p2 (V)) = 2 ()V). (8) In words this identity says that if v4 is the optimal solution to a two station problem with total variance V, then it satisfies the first order conditions to a k + 2 station problem with total variance (V + kv ). Graphs of p3 and (p4 obtained from equation (8) are also shown in Figure 7. An interesting phenomenon occurs for n > 2. The graph of Pn "bends back" at Vn implying nonuniqueness of candidate optimal solutions for a range of V just below Vn. That is, for a V in this range, there are several potential vf satisfying equation (8), each of which is pairwise optimal for all two station subproblems. The equal variance solution in this range may not be optimal. To illustrate this point consider a three station problem with cycle time T = 12, mean processing time 1p = 10 for which the critical variance is V3 = n (T - L)2 = 12. Suppose the total variance is V = 11.57. Three points satisfy the first order conditions-the equal variance solution, (11.57/3, 11.57/3,11.57/3) and two spike-shape solutions, (2.863,2.863,5.844) and (3.443,3.443,4.684). The equal variance solution is a local minimum, (3.443,3.443,4.684) is a local maximum, and (2.863,2.863,5.844) is the global minimum. For the specified T and A, the optimal solution to a two station problem has equal variance if V < V2 = 8 and has unequal variance otherwise. Notice that all pairwise combinations formed from these solutions are optimal. 19

To summarize, if V > V,, then a spike-shape solution is optimal with n - 1 stations allocated a low variance, v, and the remaining station allocated a high variance, Vh = V - (n - 1) vi. For V < in, we make no claim whether an equal or unequal variance solution is optimal. However, if an unequal variance solution is optimal, it must be spike-shape. In any case, the optimal solution can be found by solving the univariate optimization problem (P1"). While these results and the related analysis provide an answer to the question of what allocation of variance is the best, the following result, analogous to Theorem 2, indicates as to when the equal variance allocation is the worst. Theorem 4 For the problem (Pi) there exists an upper critical variance level Vn > Vn such that if V > Vn, then the equal variance allocation is worse than an extreme point allocation; moreover, under Conjecture 1, the equal variance allocation is the worst allocation. The critical variance level is given by Vn = (n- 1) V2. Proof of Theorem 4: The proof is in two parts. We first show that an extreme point solution can not be the global maximum. We then show that under Conjecture 1, an interior point, unequal variance solution can not be the global maximum. To show that an extreme point can not be the global maximum when V > Vn, we first observe that an extreme point solution has vl = 0. (Recall that we have assumed without loss of generality that vi < vi+l, i = 1,..., n - 1.) Furthermore, it must be true that v, > V/(n - 1) > V2. If we form a two station subproblem by considering stations 1 and n in isolation, then the total variance for this subproblem is greater than V/(n - 1) > V2. By Theorem 2, the equal variance solution to this two station subproblem has a larger objective function value than an extreme point solution. Since (vl, Vn) is not the global maximum to this two station subproblem, then the original extreme point solution can not be a global maximum to 20

the problem (PI). We now show that an interior point, unequal variance solution can not be the global maximum under Conjecture 1. Suppose that an interior point, unequal variance solution was the global maximum. Then by Lemma 2, it would have k stations with variance vi and n - k stations with variance vh. Since it is an unequal variance solution, 1 < k < n - 1. If vi + vh > V2, then by Theorem 2 under Conjecture 1, the equal variance solution must be the worst solution to this two station subproblem which implies that this unequal variance solution to the n station problem can not be the global maximum. We now show that vl + vh > V2. Let vl = V/n - A. Then Vh = V/n + kA/(n - k). So vi + Oh = 2V/n + (2k - n) A/(n - k). First consider the case when 2k - n < O. Then v +vh = 2V/n+ (2k - n) A/(n-k) 2V (2k-n)V V > - +,sinceA< — n (n - k) n n V (n - )1 _ --- > V2 n- k n-k > V2 Now consider the case when 2k - n > 0. Then VI +Vh = 2V/n + (2k - n) A/(n - k) >2V n 2 (n - 1) ^ > 2 n > V2 since (n-) 1 forn >2 U n The following corollary demonstrates that when the variance is sufficiently large, that placing most of the variance at as few stations as possible is a good strategy. Corollary 1 For the problem (P1), if the total variance V exceeds the upper critical variance Vn, then the optimal solution where k stations have low variance and n - k stations have high variance 21

is worse than the optimal solution where k + 1 stations have low variance and n - k - 1 stations have high variance. Proof of Corollary 1: See Appendix B. 4 Discussion and Further Implications The transition from an equal to a spike-shape allocation can be explained by considering the nature of f(v) and its effect on the resource allocation problem. If f(v) was convex, equal allocation of variance would be optimal. On the other hand, if f(v) was concave, an extreme point allocation such that one station receives all the variance, would be optimal. Recall from Section 1 that for v < V, f(v) is convex, otherwise it is concave. As a result, if the total variability is small enough such that the average variance is below V, an equal variance solution is optimal. Conversely, if the total variability exceeds this value, one station gets most of the variance due to the concavity of f for large v. However, all other stations do not get zero variance because f is not concave for small v. The result is a hybrid allocation of an extreme point and equal variance allocation, which is directly attributable to the convex-concave nature of f(v). The analysis presented in this paper characterizes the optimal structure of the allocation of variance on a synchronous assembly line based upon four parameters- n, T, A, and V. In fact, all of our results can be characterized by a dimensionless value based on these four parameters. For example, a spike-shape solution is optimal if T-t T — < ~~1- (9) Similarly, the equal variance solution is the worst solution if T V/(- 1 v/-V7(n ~< X7~ 22

where x is the solution to equation (5). The validity of our results depend not on the individual values of the parameters n,T,e, and V, but on fundamental dimensionless quantities expressed above. TIhis observation further strengthens the validity of Conjecture 1. Note that the structure of the optimal allocation depends upon, (T - [)/V/V7n, the normalized slack processing time per unit of standard deviation which can be viewed as a measure of processing flexibility. This is a fundamental quantity which governs the transition from an equal to a spikeshape allocation of variance. Hsu (1992) has devised a similar measure: a = 2(T - p)/v, called the coefficient of flexibility. This measure, which is not dimensionless, plays a fundamental role in determining the percentage of jobs requiring rework in her assembly line model. The transition from an equal to a spike-shape allocation can also be characterized using the following two important performance measures of the line: the coefficient of variation of processing time, c = /V7-n/it, and the level of worker utilization, p = t/T. Substituting T = tt/p into equation (9) yields the following condition for a spike-shape allocation to be optimal P< c. (10) P For a given coefficient of variation, there exists a critical utilization level such that any attempt to increase worker utilization beyond this level necessitates a spike-shape allocation for optimal performance. Moreover, this critical utilization level decreases as the coefficient of variability increases. If the variability is evenly spread across stations such that a spike-shape reallocation is difficult, then any effort to increase worker utilization must be accompanied by a simultaneous effort to reduce the variability in the system. An important question is whether the amount of variability in realistic assembly lines is large enough for a spike-shape solution to be optimal. It is typical in industry to strive for a utilization level of 90% or higher. For example, Harbour (1990) notes that a common goal for line worker utilization is 55 minutes per hour. According to equation (10), at a 90% utilization a spike-shape 23

solution will be optimal if the per station coefficient of variation exceeds 0.111. This is a very modest coefficient of variation. In fact, the level of variability in today's assembly lines far exceeds this value. Several reported examples in the literature use a level of variability higher than this. For example, Hillier & Boling (1979) in their study of the bowl phenomenon use values of c > 0.378. Similarly, Carnall & Wild (1976) note that c = 0.27 is a reasonable representation of published worktime distributions. Conway et al. (1988) use station processing time distributions with coefficients of variation of 0.1 and 0.3 in their study to represent levels of variability that might reasonably be encountered in practice for manual operations. In our own experience of assembly lines of the Big Three auto makers, we have found coefficients of variation larger than these values. We now consider the behavior of the optimal objective function value as a function of the total variance V. As V increases beyond Vn, v? -- 0 and v* -, V. The optimal objective function value for large values of V can be approximated as T-1C F(0,...,0, V) V - 2 That is, for high levels of variance the optimal work overload is proportional to V/V and is (relatively) independent of the number of stations in the line. As noted earlier, if the variance is sufficiently large, the equal variance solution may be the worst solution. Graphs of objective function values as a function of V are shown in Figure 8 for the optimal solution as well as the equal variance solution for T = 12, / = 10, and n = 2. Note that the basic shape of the graph of the optimal work overload is similar to that for /V". Furthermore, as the variance increases, the difference between the optimal solution and the equal variance solution becomes increasingly large. This behavior is in stark contrast to the bowl phenomenon for asynchronous lines. Most studies find that a bowl-shaped line gives a small (certainly less than five percent) improvement in throughput from a balanced line. Our analysis shows that for a synchronous line, the improvement from an equal to a spike-shape allocation of variance can be quite significant. In the limit, as V becomes large, the work overload for the equal variance solution is approximately /n; times higher than the 24

work overload for the optimal spike-shape allocation. Recall that we assumed that the processing time at each station is normally distributed. An interesting question is to what extent our results depend on this assumption. We have tried to develop similar results for other probability distributions. Initial attempts to do this work analytically for the lognormal, beta, and Weibull distributions has proved intractable. However, computational results for a number of distributions including beta, lognormal, and Weibull demonstrate that similar results hold for a more general class of distributions. 5 Managerial Insight Our model was designed to provide insight into the effect of the allocation of variability on a synchronous assembly line. The results developed from this model can be used by engineers and managers when designing synchronous assembly lines. The most important result is that when significant variability exists in a system, one should place most of the variability at one station. Clearly, this may not be possible in practice. However, Corollary 1 demonstrates that for such levels of variability it is best to place the variability at as few stations as possible. This observation is consistent with Lau's (1992) recommendation for asynchronous lines that "it is desirable (for improving throughput) if all (or nearly all) the variability can be concentrated into only one station and all other station have zero (or very close to zero) variability." We were surprised to find that auto manufacturers have arrived at similar conclusions independently. For example, Mazda assembly lines use a "Tact and Pitch" (Pahapil, 1992) approach which is analogous to a spike-shape allocation. A tact zone, or stabilization zone, constitutes a group of stations with relatively little variability. A pitch zone, or absorption zone, has station(s) that are highly variable. The goal of such a zone is to absorb the variation between different models. If an unequal variance solution is optimal, the question remains where to locate the high variance 25

station(s). Locating high variance station(s) at the end of the line has several attractive features. Clearly, these station(s) will have the largest share of work overload. Having the rework station immediately following these stations will facilitate rework and will not prevent other tasks from being completed. Similar rationale can be used in a variance reduction effort. If the total variability in the line is quite high, one is better off putting variance reduction efforts at upstream stations. A practice employed by auto manufacturers, including Honda and Saturn, is to offer vehicles with dealer installed options. In effect, the dealership can be viewed as the last station, with highly variable processing time. The assembly plant then attempts to imitate a single model assembly line with limited variability, while the dealership absorbs the variability due to options. 6 Conclusions We have analyzed the effect of variability on a synchronous assembly line where rework is done at the end of the line. Our results demonstrate that if the total variance in the system is sufficiently large, a spike-shape allocation of variance is optimal and that an equal allocation of the variance can be the worst solution. Additionally, the optimal allocation can be found using a simple univariate optimization technique. Practically, variability should be isolated at as few stations as possible. The results can guide continuous improvement efforts in variance reduction. Mathematically, the results derived here are interesting because they are applicable to a class of separable resource allocation problems with concave-convex structure. Acknowledgments We would like to acknowledge the support of the Operating Sciences Department of General Motors Research and Environmental Staff for this research. Dennis Blumenfeld, Bill Jordan, David Kim, and David Vander Veen of General Motors provided valuable assistance and feedback on this work. We would also like to acknowledge the helpful comments provided by Stephen Graves. 26

Appendices A Proof that A (V - ) < A (V + a) If 0 O<a < V = (T- 42 then XA (V + a) > (v - a) ( T-M)2 e 2(v+a) 2 Vl +aV, /-F, (T-A)2 e 2(v -- m) 2 V-aV7 a O(T-' 2 e((T- 2)(+)((T-/)2 2> T 2a(T-P)2 ) 2 e ((T )+ T- ) > 1 +a (T- I~)2 - a But _,2a(T-~)2 e ((T- L, +a)((T-) -,,) > 1 -+ -- s/ + (T- A)2) ((T-)2 - ) (T _A)2_ ) ((T _ )2 +a ((T _ )2_ a() (11) since 0 <a < V = (T- L)2. Therefore A( + a > (-a) if 2a (T- )2 4a2 (T- )4 2a ((T - p)2+ ) ((T- )2 + ) ((T ((T + )2((T - )2 )2 >1 (T _ )2 _ 4a(T - )2 ((T - )2 + a)2 ((T - /)2 - a)2 4a2(T - /)2 2a ((T _- )2 + C)2 )((T - -)2 + a)2 ((T -)2 -a)2 (T - / )2 -4a ( T - ((T) a2) + 4a2 (T - pa)4 > 4a ((T - a) T 2 + a) 2 - a a - a 0> -a3. 27

B Proof of Corollary 1 Consider the optimal solution to the problem where k stations have low variance and n - k stations have high variance. Let this solution be (1) _ (v, V(k), Vh(k, Vh(k)). k n-k Now consider v(2) which is a solution to the problem where k + 1 stations have a low variance of V*k) and n - k - 1 stations have high variance vZ(k) = (V - (k + 1)v*k))/(n - k - 1). That is, V(2) = (vj(k),k'",Vl(k) Vh(k) Vh(k)) k+l n-k-1 These two solutions have the same variance assigned to each of the first k stations. Therefore, consider the n - k station subproblem with total variance V' = V - kvWrk) formed by considering the last n - k stations of either one of these solutions. The solution to this subproblem formed from v(j) is Vlf = (Vh(k). ** h(k)) ~ J n-k The solution to this subproblem formed from v(2) is V(2) = (V()< Vh(1k),'' ' V vh(k)). n-k-l Note that v(l) is an equal variance solution to this subproblem. If we can demonstrate that the total variance for this subproblem, V', is greater than the upper critical variance level for this subproblem, then by Theorem 4 it will be true that v'(2) is a better solution to the subproblem than '(1). But, V' = V-kvI(k) > Vn-kv,(k) = (n-1)V2-kv*Ik) 28

> (n - 1)V2- kV2 = (n-k- )V2 = Vn-k Hence the total variance for the subproblem is greater than the upper critical variance for the subproblem. Therefore '() is a worse solution to the subproblem than '(2). This implies that v(') is a worse solution to the original problem than v(2), i.e. F(v(1)) > F(v(2)). Recall that v(2) is a solution which has k + 1 stations with low variance and n - k - 1 stations with high variance. If we let ) (VIk+l), (k+ V(k+l) h(k+l)) k+l n-k-I be the optimal solution to the problem with total variance V and k + 1 stations with low variance and n - k - 1 stations with high variance then it must be true that F((2)) > F(v(3)). Therefore F(v()) > F((2)) > F((3)), i.e. the optimal solution with k stations having low variance is worse than the optimal solution with k + 1 stations having low variance. o 29

References BAKER, KENNETH R. 1992. Tightly-Coupled Production Systems: Models, Analysis, and Insights. Journal of Manufacturing Systems 11, 385-400. CARNALL, C.A. AND RAY WILD. 1976. The Location of Variable Work Stations and the Performance of Production Flow Lines. International Journal of Production Research 14, 703-710. CONWAY, RICHARD, WILLIAM MAXWELL, JOHN O. MCCLAIN, AND L. JOSEPH THOMAS. 1988. The Role of Work-in-Process Inventory in Serial Production Lines. Operations Research 36, 229-241. EL-RAYAH, TARIG E. 1979. The Effect of Inequality of Interstage Buffer Capacities and Operation Time Variability on the Efficiency of Production Line Systems. International Journal of Production Research 17, 77-89. HARBOUR, JIM. 1990. 55 Minute Hours. Chilton's Automotive Industries July, 1990, 9. HILLIER, FREDERICK S. AND RONALD W. BOLING. 1966. The Effect of Some Design Factors on the Efficiency of Production Lines with Variable Operation Times. Journal of Industrial Engineering 17, 651-658. HILLIER, FREDERICK S. AND RONALD BOLING. 1979. On the Optimal Allocation of Work in Symmetrically Unbalanced Production Line Systems with Variable Operation Times. Management Science 25, 721-728. Hsu, LINA Y. 1992. The Design of an Assembly Line with Stochastic Task Times. M. S. Thesis. Alfred P. Sloan School of Management, Massachusetts Institute of Technology. KALA, R. AND G. HITCHINGS 1973. The Effects of Performance Time Variance on a Balanced Four Station Manual Assembly Line. International Journal of Production Research 11, 341-353. 30

LAU, HON-SHIANG. 1992. On Balancing Variances of Station Processing Times in Unpaced Lines. European Journal of Operational Research 56, 345-356. LA'U, HON-SHIANG. 1986. A Directly-Coupled Two-Stage Line. HIE Transactions 18, 304-312. LAU, HON-SHIANG AND G. E. MARTIN. 1987. The Effects of Skewness and Kurtosis of Processing Times in Unpaced Lines. International Journal of Production Research 25, 1483 -1492. Luss, HANAN AND SHIV K. GUPTA. 1975. Allocation of Effort Resources among Competing Activities. Operations Research 23, 360-366. MUTH, EGINHARD J. 1979. The Reversibility Property of Production Lines. Management Science Research 25, 152-158. PAHAPIL, ERIC. 1992. Tact and Pitch Line Balancing. Workshop sponsored by the Detroit Chapter of the Institute of Industrial Engineers, June 3, 1992. RAO, NORI PRAKASA. 1976. A Generalization of the 'Bowl Phenomenon' in Series Production Systems. International Journal of Production Research 14, 437-443. SMITH, L. DOUGLAS AND PHILIP BRUMBAUGH. 1977. Allocating Inter-station Inventory Capacity in Unpaced Production Lines with Heteroscedasctic Processing Times. International Journal of Production Research 15, 163-172. WYCHE, P. DE LA AND RAY WILD. 1977. The Design of Imbalanced Series Queue Flow Lines. Operational Research Quarterly 29, 695-702. WILHELM, W. E. 1987. On the Normality of Operation Times in Small-Lot Assembly Systems: A Technical Note. International Journal of Production Research 25, 145-149. ZIPKIN, PAUL H. 1980. Simple Ranking Methods for Allocation of One Resource. Management Science 26, 34-43. 31

Figures f(v) V Figure 1. Expected Work Overload, f (v). 32

.( v) V Figure 2. A (v) 33

)n(v- v ),aVl,) (a) V v 2 V \FTV., V - v,) V, Vv -V V 2 V, V F(v,, V - v,) _I a _I II (c) V 2 V V (d) 2 Figure 3. (a) and (b). A (vl) and A (v2) = A (V - vl) for V > V2 and V < V2, respectively. (c) and (d). F (v1,v2) = F(v1, V - vi) for V > V2 and V < V2, respectively. 34

mv) V+a ---- - vO~~~~~v V-vV Figure 4. A (v) for the Proof of Lemma 1. 35

VI + V2 2V Figure 5. v1 + V2 as a function of A, A (v1) = A (v2), v1 j4 V2. 36

F( v,V- v) (a) V,<V<V, v, (b) > v, Figures 6a and 6b. F(v1l,v2) = F (vi, V - v1). N.B. Vertical Axes not to the same scale. 37

51 Figure 7. ~p, (V) as a function of V. 38

Work Overload 6 5 4 3 2 1 Value of Equal Variance Solution of Optimal Solution V 50 100 Figure 8. 7 (vi*) and r (V/n) for n = 2, T = 12,/p = 10. 39