Procedures to Analyze the Tradeoffs Between Costs of Setup and Utility Work for Automobile Assembly Lines by Ahmet Bolat Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Candace A. Yano Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 January 1989 Technical Report 89-3

PROCEDURES TO ANALYZE THE TRADEOFFS BETWEEN COSTS OF SETUP AND UTILITY WORK FOR AUTOMOBILE ASSEMBLY LINES by Ahmet Bolat Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Candace A. Yano Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 January 1989

PROCEDURES TO ANALYZE THE TRADEOFFS BETWEEN COSTS OF SETUP AND UTILITY WORK FOR AUTOMOBILE ASSEMBLY LINES Abstract In this article we address the problem of sequencing vehicles on a paced assembly line with no buffers between stations. The portion of the assembly facility that we consider has a painting operation which requires a setup whenever the color is changed, and a number of assembly stations which have capacity limitations. Because of these capacity limitations and the pacing of the assembly line, the work on some vehicles may be incomplete when the vehicle leaves a station. The amount of incomplete work is referred to as utility work. The tradeoff between setup costs and the cost of utility work arises because frequent setups permit more flexibility in sequencing vehicles, thereby reducing utility work. We have devised and evaluated rules for determining the sequence and sizes of color batches. For a prespecified color batch size, we found that a procedure that simultaneously considers the selection of color and jobs for the subsequent batch performs better than procedures in which the color pattern is decided in advance. We illustrate how this procedure can be used to analyze the tradeoff between the costs of setups and utility work.

1 Introduction Automobile companies usually offer a great variety of customer choices and options of each model such as the color, the number of doors, the type of engine, transmission and so forth. For example, Weiner (1985) states that there are potentially 2.5 million unique configurations for the Escort, Ford's subcompact car. Usually, on the average, fewer than ten units of each model are ordered. Hence, it is preferable to intermix the various models on the same assembly line rather than producing them in batches. This situation can also be observed to a more limited extent in the television, home appliance and farm equipment industries. While an automobile assembly plant can take various forms, the following is the most commonly used in the industry. There is a paced (or constant-speed) assembly line which conveys the jobs to a series workstations in the body, paint, and trim and chassis shops. All body sheet metal of an automobile is assembled, aligned and welded in the body shop. Usually computer-controlled robots, optical cameras and laser sensors are employed here and the processing times for different models are similar. However, in some applications, sheet metal stamping presses are coupled to the beginning of the line and machine downtime occurs each time the sequence switches from a two-door automobile to a four-door. Next, the car bodies are primed and painted in the paint shop. Most painting processes are highly automated; thus, except in special cases, painting with different colors require the same time. However, changeover costs are incurred each time the sequence switches from one color to another. For example, some paint and solvent is discarded each time the paint system is purged to switch colors, and 1

paint quality may temporarily decline after the switch. Then car bodies visit the trim and chassis stations where all the necessary operations for the finished product are performed. There are basically two types of stations in this part of the line. Some stations are assigned to do exactly the same operation on every job (e.g., installing the front windshield). The other type of station offers operations that are not performed on every job (e.g., installing vinyl roofs) or performed on every job but with two options (e.g., installing manual versus power window). In this type of station, we call an operation basic if it takes a shorter processing time to be completed and optional if it takes a longer time. For stations of the first type there is no sequencing problem at all. Now let us focus on the second type of station. The capacity of each station is usually established on the basis of the expected product mix. Even though it is planned that, on average, the work required by each job at a particular station can be completed within the boundaries of the station, there may be subsequences in the daily schedule which require more work than station can handle. In this case either a utility worker is assigned to finish incomplete work (which we call utility work) or the operators must perform the work more quickly and possibly perform part of the work outside the station. The latter contributes to quality degradation and reduced productivity due to unproductive travel time and interference between operators in adjacent stations. From this discussion it is clear that a sequence which minimizes both setup costs in the body and paint shops and utility work costs in the trim and chassis stations is desired. This may not be possible, however, since the assembly lines 2

employed in the assembly facilities permit only permutation sequences, i.e., the same sequence is introduced to every station. A sequence minimizing the total number of set-ups does not necessarily minimize total utility work. Therefore, these two objectives may conflict if there are correlations among options and color or body model choices. For example, if all red cars have power windows, using a long sequence of red cars, which helps to reduce set-ups, leads to considerable utility work at the window installation station. Hence, we need to sequence the jobs so that the sum of set-up and utility work costs is minimized. In the next section we survey the work related to problem of how to sequence jobs with options. 1.1 Related Literature The problem of how to sequence jobs with options on an assembly line without buffers has been well addressed in the literature. Wester and Kilbridge (1963) proposed both variable and fixed launching rate procedures to cope with the processing time differences between models. Thomopoulos (1967) discussed specific procedures to deal with a sequencing problem developed in the context of a case study taken from the automotive industry. He used a greedy algorithm which is based on minimizing the total penalty for a number of inefficiencies (operator idle time, utility work, work congestion and deficiency). The two papers above assume that the assembly line can be balanced so that each station has approximately the same processing time. Okamura and Yamashina (1979) proposed a heuristic procedure for a single station to find a sequence which minimizes the maximum distance operators must go downstream on the line from the beginning of any station. Monden (1983) 3

described a sequencing problem in an auto company for which the main goal was to keep the quantity used per hour for each part as constant as possible to facilitate just-in-time implementation. He formulated the problem as one of minimizing variations of the speed of utilizing each part. Almost all the proposed approaches mentioned above assume that the number of distinct products is small and the mix of the products is relatively stable. Thomopoulos (1967) points out that a rule of thumb employed in the automobile industry is to impose precedence constraints on the sequence of vehicles entering the assembly area. For example, (i) at most k out of each 1 consecutive jobs can have the option; and/or (ii) no more than a specified number of jobs with the option can be sequenced consecutively. The parameters for these spacing rules customarily are determined through experience. Some recent research has focused on how to implement these spacing rules. Bird (1986) used the theory of Markov chains to maximize the mean time to violation of the spacing constraints. Coffman et al. (1985) developed a greedy heuristic algorithm to minimize the total number of spacing constraints violated in the context of resequencing a few dozen jobs after the initial sequence was disturbed by an upstream repair process. In all three papers, the relation between spacing parameters and capacity utilization is not investigated and it is assumed that the spacing parameters are given. Therefore, it is not clear how to specify spacing constraint that lead to the best schedules overall. Previously we considered sequencing jobs for one station which offers two types of operations (see Bolat and Yano 1988a). We established a relationship between 4

utility work and spacing constraints, and by employing this relationship we developed a sequencing algorithm. Furthermore, we proved that algorithm is optimal under some conditions and were able to bound the error if these conditions did not hold. In a sequel (Bolat and Yano 1988b) we extended the algorithm to the multiple-station problem (sequencing jobs for trim and chassis stations only) and found that it outperforms a random sequencing algorithm and procedures implemented by two major automobile companies. In almost all of the above papers, the common goal is to generate schedules so that the capacities of the stations in the trim and chassis area are utilized as efficiently as possible. To the authors' knowledge, there is no published research on the generalized problem which includes stations with setups, such as body and paint, and multiple stations with utility work considerations. Burns and Daganzo (1985) examined a special version of the problem in which only setup costs are incurred. They first developed a very simple rank ordering algorithm which first groups the jobs by the type of operation whose set-up cost is most expensive then within each of these groups, it groups the jobs by the type of operation which is the second most expensive, and it continues in this fashion. They pointed out that the marginal savings decline as total number of groups increases. Then they included one station offering two types of options, such as a trim station, and assumed that the choices related to setup costs and the option were uncorrelated. They developed a probabilistic model to estimate the expected number of violations of a spacing constraint for this additional station. 5

1.2 Objective of This Research There appear to be gaps between the approaches presented in the literature and those implemented in practice. To date, none of the approaches has incorporated both setup costs and multiple stations with utility work (or spacing constraint) considerations. Even solution procedures used in industry do not have well-defined objective functions and constraints, and the solution procedures themselves tend to be ad hoc and myopic (no look-ahead provision). Although there has been a concerted effort to reduce setup costs, the nature of the changeovers, especially in the paint area, make it difficult to reduce setup costs to zero. Thus, there is a need for procedures that systematically considers both setup and utility costs, not only to improve current operations, but also to evaluate the economic benefit of investments in setup cost reduction. The purpose of this research is to (1) describe a generalized formulation of the Automobile Assembly Line (AAL) sequencing problem in which the objective is to minimize total cost of setup and utility work, and (2) extend the algorithm developed by Bolat and Yano (1988b) to consider setup costs. The principles and algorithms proposed here can help in evaluating benefits and costs of investments in future systems and in designing new systems. Although this paper focuses specifically on AAL systems, further research along these lines would also be applicable to mixed model assembly lines and flexible flow systems with small buffers. In the next section we formulate the generalized AAL sequencing problem and mention the optimum solution techniques available today. In section three we propose our solution approach to the problem and present experimental results. 6

We conclude with a summary and discussion in section 4. 2 Description and Formulation of the Problem We assume that there are N jobs, one paint station which requires a setup when the operation switches from one color to another, and M trim (and chassis) stations, each of which is capable of performing two types of operation, basic and optional. (We do not address sequencing issues related to body operations preceding the painting process. However, we will discuss later how these factors can be incorporated into our model.) Without loss of generality, it is assumed that in each trim station, the operation that takes longer to perform is called the optional operation. Each trim station is also allowed to perform other operations if they are required by all jobs. In this case the processing times of the original basic and optional operations are increased by the processing time of this additional operation, which may be a combination of smaller operations. Jobs arrive to stations on a conveyor which proceeds at a constant rate, and time is scaled so that a new job is introduced to each station at one time unit intervals. Jobs cannot be removed from their respective positions on the conveyor. We use the term slot to refer to a position in the sequence. We assume that in the paint station a setup is required when the operation switches from one color to another. Although, with a few exceptions, the changeover costs due to paint purges are slightly sequence-dependent, most of the costs result from discarded paint and solvent. Moreover, in many applications, it is difficult to determine these costs accurately; hence, we do not expect to be able to 7

obtain sequence-dependent cost data. Therefore, in this paper, we assume that a sequence-independent setup cost is incurred whenever a switch occurs in the paint station. We also assume that utility work is not a concern at the paint station because the application of different colors takes almost the same amount of time. We assume that all the operators in a trim station work on the same job simultaneously. Each of these stations is closed to the right and left, so work can be performed only within the limits of the station. The operators move downstream on the line, completing their respective tasks, then return upstream to meet the next job. We assume that the travel (walking) time to the next job is negligible, which although not exact, is a fairly accurate approximation when the travel time is far less than the processing time at a station, or when allowances for travel are included in the estimated processing time. We assume that there are no setup costs at trim stations. The problem is to determine a sequence which minimizes the sum of total setup cost in the paint station and total utility work costs in the trim stations. As we mentioned earlier, the model in this study allows only permutation schedules. Although a sequence specifies the arrival and departure times of the jobs, it alone does not determine the entire production schedule for trim stations because it does not specify which jobs are worked on at each point in time. However, it is shown that the schedule in which as much work as possible is done on the job in slot h before work is begun on the job in slot h + 1, constitutes a dominant set (see Yano and Rachamadugu 1987). Therefore, we will employ only one starting time and one finishing time for each job at each trim station. Also we use the same time 8

index for all stations which is analogous to each time zone (station) using one time zone (e.g., Greenwich mean time) as the point of reference. Let N = Number of jobs, M = number of trim stations, j = index for trim stations, i, I = indices for jobs, Rj = set of indices of the jobs requiring the optional operation at station j, oj = time required to complete an optional operation at station j, bj = time required to complete a basic operation at station j, Pij = processing time of job i at station j, i.e., oj if i E Rj and bj otherwise, Lj = maximum number of jobs at station j at one time, c = cost per setup in the paint station, Ci = total setup costs for assigning job i immediately after job 1, i.e., c if jobs i and I require different colors and 0 otherwise, Oj = cost of one unit time of utility work requested by station j, 1 if job i is assigned immediately after job 1, Yi = 0O otherwise. Ai = arrival time of job i at station j, Sij Fri ui. Oli - starting time for processing of job i at station j, = work termination time of job i at station j, = utility work for job i at station j, = unrestricted dummy variable for i = 0,..., N + 1. 9

The following is a mathematical programming formulation for the problem. Minimize EZ= 1 CYi Yi + EJ Oj El1(Sij - Fij) Subject to: Ai - EiO YiA = 1 i =,.., N + 1 Sij - Ai > 0 j = 1,..., M, iO..., N +1 i^-5^o Fj Yu > 0 j= 1,..., M, i = 0,..., N + 1 Fij - Ai < Lj j = 1,..., M, i =,..., N +1 - ai + (Nl + YiN I =,...,N, i =,...,N+l Yi = O orl l = O,...,N, i =l,...,N+ l Ai, Sij, Fij > 0 j 1,.., M, i = O,...,N + 1 where ai is unrestricted for i = 0,..., N + 1. This is a modified Traveling Salesman Problem with two dummy jobs, 0 and N + 1, both having a setup cost and processing time equal to zero at the paint and all trim stations, respectively. The objective function and constraints can be explained as follows. If job i is assigned immediately after job I then the setup cost will be $Cli. Hence, the first term in the above objective function gives the total setup cost of any sequence. If work terminates on job i (due to its departure from station j) before it can be completed, then some utility work is required for this job. Thus, the utility work for job i at station j is Uij = (Sij + Pij - Fij)+, and the objective is to minimize the sum of the Oi iN 1 Uijs. We can eliminate the positive part in this part of the objective function by constraining Fij < Sij + Pij. 10

Having done this, we can also eliminate the Pijs because they are constants. If job i is assigned immediately after job 1, it arrives at station j exactly one unit time after the arrival of job 1. The starting time of job i at any trim station must neither be earlier than its arrival time nor the finishing time of previous job because each station is left closed and only one job is processed at a time. The finishing time of processing on job i at station j is Fij = min (Sij + Pij, Aij + Lj), that is the earlier of the completion time and the departure time of the job. Every job must be assigned to one slot and each slot must be reserved for one job. The last inequality in the formulation prevent the solutions with subtours, i.e., subsequences that are not connected to the main sequence (Tucker et al. 1960). To illustrate how quickly the problem size grows with the number of jobs and stations, let us consider the following examples. For a 10-job and 3-trim station problem, there are 121 binary, 84 nonnegative continuous and 12 unrestricted continuous variables, and 143 integer, 108 linear and 47 nonlinear integer constraints, whereas for a 500-job and 10-trim station problem, there are 251,001 binary, 10,542 nonnegative continuous and 502 unrestricted continuous variables, and 252,003 integer, 15,060 linear and 5521 nonlinear integer constraints in the above formulation. Alternative formulations of the problem are no less complicated. The best known solution method for this mixed integer programming problem, Branch and Bound, can result in almost complete enumeration because most of the constraints are purely definitional (i.e., any sequence is feasible, although not necessarily good). Usually the daily production rate is about 1000 cars per assembly line and the number of the possible sequences to consider every day 11

is 1000!, 102400. Therefore we focus on a heuristic approach to find a "good" solution in a polynomially bounded amount of time. In the next section we present our solution approach and experimental results. 12

3 Solution Approach and Results In Bolat and Yano (1988b), we developed a very good and efficient algorithm to sequence N jobs for M trim stations so that the "minimum" total utility work is achieved. The algorithm is a heuristic branch and bound procedure that assigns a job to each position in the sequence, beginning with the first position in the sequence. It retains only the best node at each level of the branch and bound tree. The lower bound is computed as the sum of the utility work for the jobs scheduled so far and a lower bound on an approximation of the utility work for the remainder of the schedule. The procedure performs significantly better than other procedures without look-ahead provisions. If paint station offers only one color, or if cars of only one color are painted and assembled on a given day, then the Bolat and Yano algorithm (BYALG). can be used to sequence the jobs without considering this additional station. On the other hand, if cars of several colors need to be produced then we need to consider the tradeoff between cost of setups and cost of total utility work. To simplify the problem, we incorporate a color batch size as a constraint, and then analyze the effect of the size of color batches, and the pattern of colors, on total utility work cost. To identify the optimal batch size pattern (i.e., the assignment of colors to slots in the sequence) is very difficult, if it is possible at all, because it is a function of the data. For the moment let us assume that we would like to have equal color batch sizes. Furthermore, let us assume that the "best" batch size, b* is known. Now the question is how to choose the "best" color for each batch. 13

3.1 Rules For Choosing The Next Color Let us assume that we have sequenced a number of jobs and we are looking for the next "best" b* jobs. If we determine the "best" color then we can apply the BYALG to find the next "best" b* jobs. We propose the following logical procedures to choose the next color. In the first three rules, we fix a color sequence in the beginning and repeat this sequence as long as there are available jobs requiring the next color. If there is no job requiring a particular color then go to the next available color in the pattern. Fixed Decreasing Order, FIXDEC: Determine a permutation in decreasing order of the number of jobs requiring each color. (For example, let us assume that there are 100 jobs and b* = 10. Furthermore, Let us assume that 37 of these jobs require red paint, 18 of them white and 45 of them black. In this case this rule would first sequence 10 jobs requiring black then 10 red and then 10 white, then sequence 10 black, 10 red and 8 white, then 10 black and 10 red, then 10 black and 7 red and finally 5 black jobs. This method gives more flexibility at the beginning of the sequence. Fixed Increasing Order, FIXINC: Fix the sequence of colors in increasing order of number of jobs requiring the color. The idea here is to provide more flexibility at the end of the sequence. Fixed Random Order, FIXRAN: Fix a permutation of the colors randomly. In the following rule, the next color is determined during the assignment of the next b* jobs by applying BYALG. Choice Rule "BEST": For each available color, find the "best" b* jobs by 14

applying BYALG. Find the total utility work for this partial sequence plus a lower bound on the total utility work for all the remaining jobs. Then choose the color which gives the minimum of this measure per new additional job. (Near the end of the sequence the number of remaining jobs requiring a particular color may be less than b*. In this case the total cost for these jobs may be less than that of the other incumbent jobs, and hence, these jobs may be more attractive than the groups of b* jobs with other colors.) We develop an extended algorithm, EBYALG, which applies one of the rules defined earlier to determine the next "best" color and utilizes BYALG to determine the next "best" b* jobs. Initially we assume that b* is equal to 20. Usually there are capacity limitations on the number of jobs which can be processed without a setup. (Some paint systems must be purged after painting approximately 20 jobs requiring the same color because paint starts to coagulate inside the paint sprayers.) We evaluate the rules by scheduling randomly generated and real job orders. We use the same data sets as in Bolat and Yano (1988b). The random data sets have been produced by using a uniform random number generator (Law and Kelton 1982). There are 5 data sets with 1000, 2000, 4000 or 5000 jobs in each set and 14 trim stations. For each job, the type of operation at each station is assigned randomly. The probability of an option is chosen so that the expected labor utilization at each station is 100%. There are 10 different colors and each color is equally likely to be demanded by any job. The real data set was provided by a major automobile company. There are 20 data sets with 1000-job in each. 15

The options affect 12 trim stations, and there are 11 different colors. Table 1 present the average results. First of all, we have found that the "BEST" color rule always outperforms the other rules in experiments with random and real data. Secondly, in the random data case, the differences among the first three rules are not significant. This is expected because by construction of the data, (1) on the average, each color is demanded by N/10 jobs, and (2) there is no correlation between trim options and color choices. Hence, the increasing and decreasing order rules are similar to the random order rule. Similar performance for the first three rules is seen for real data. Thirdly, in the random data case, the average utility work per job obtained by implementing the "BEST" rule appears to decline as the number of jobs increases. Although the rate of decline is slower, similar behavior is observed for the other rules. Throughout the remainder of the experiments, we will use the "BEST" color rule. In the next section, we determine the b*. 3.2 Choosing The Next Batch Size Here we continue to assume equal size batches. We vary b* while using EBYALG with the "BEST" color rule to schedule the job orders. By construction of the random job orders, there is no correlation between colors and the operation types for the trim stations. Although there may be some correlation in real orders, we have always observed qualitatively similar results by using the random and real data. Therefore, we complete the study by also considering job orders having a high correlation between colors and options. We defined 20 different job types. Each job type has an assigned color (two job types per color). 16

Optional operations are assigned randomly to job types so that the fraction of job types with each optional operation is consistent with 100% labor utilization. Table 2 presents the job types. The jobs are generated by randomly selecting a job type with equal probability. On the average, each job type should be represented by N/20 jobs and each color should be demanded by N/10 jobs. To illustrate the strong correlation in this data set, let us examine the first row in Table 3.2. If a job requires the optional operation at stations 1, 2, 5, 6, 7 and 14, and the basic operations at the rest of the stations then we know that this job requires color number 1. Table 3 presents the average results of the schedules obtained by using random, real and correlated job orders. We have found that as the batch size decreases, the utility work per job decreases. This is expected because a small batch size allows more flexibility in choosing the next "best" color and jobs. This observation suggests that the batch size should be as small as possible to minimize the total utility work. However, a small batch size will increase the number of setups. Therefore, the tradeoff between total setup and utility costs needs to be considered to select the batch size. Let us assume that one hour of utility work costs $25 and one setup costs $10. Figure 1 plots total costs versus batch size for random, real and correlated data cases for 1000 jobs. For the random cases it appears that the "best" batch size is between 50 and 100 and any batch size in this range results in approximately $0.40 - $0.45 total cost per job. Furthermore, it appears that total cost increases exponentially as the batch size decreases from 50 to zero due to the effect of setup 17

costs. For real and correlated cases we observe similar results for b between 50 and 100. However, the total cost per job obtained by selecting any b* in this range is now approximately $0.80 to $1.30. The exponential decline of the total cost for batch sizes between 0 and 50 is also observed in these cases. The differences between the curves are attributable to differences in utility work. Figure 2 illustrates the relation between batch sizes and total costs for 5000-job problems. It appears that with the selected cost parameters, b* does not depend on the total number of jobs. Thus, we have found that for $25 per hour of utility work and $10 per setup the "best" policy is to set the batch size to its upper limit which is 20 here, and implement the "BEST" rule to sequence colors. It is clear, however, that there are benefits from reducing technological constraints on the batch size (e.g., coagulation problems in paint sprays), even if the setup cost cannot be reduced dramatically. The question now is how sensitive b* is with respect to changes in the cost parameters. We are mainly interested in determining reasonable cost coefficients which results in a smaller b* than we have found earlier. As Figure 1 and 2 indicate, b* decreases (increases) if the unit setup cost is decreased (increased) or if the unit utility work cost is increased (decreased). A setup cost less than $10 is usually not a realistic assumption in the automobile industry. However, unit utility cost more than $25 may be reasonable if we assume that there are some implicit quality costs. Hence, we assume that a setup costs $10 as before and a unit of utility work costs $100. We have prepared Figure 3 by using the new cost coefficients. As Figure 3 indicates, b* appears to lie between 20 and 100 for the random and 18

real data cases, and between 6 and 100 for the correlated data case. Although the lower bound on b* decreases with the new cost parameters, the upper bound remains same as before. This is expected because as Figure 1 indicates, the utility cost curve is very flat for batch sizes between 30 and 100, and hence, the total cost curve in this range takes approximately the shape of the setup cost curve regardless of the cost of a unit of utility work. The smaller lower bound in the correlated data case is the result of having a steeper utility cost curve for batch sizes between 0 and 20 than that in the random and real data cases. These results suggests that with high utility work (and associated quality) costs, the constraint of 20 jobs per batch is no longer problematic. Here, there is an opportunity to reduce total costs by reducing setup costs even if technological constraints on the color batch size cannot be relaxed. 19

4 Discussion and Summary In this paper we have devised and evaluated rules for determining the sequence and sizes of color batches for jobs on a paced assembly line. Each job represents a combination of options and a color. A sequence-independent setup cost is incurred whenever two adjacent jobs have different colors. On the other hand, long subsequences of jobs with the same color tend to increase the amount of utility work, which is work left undone when a job leaves a station. For a prespecified color batch size, we found that a procedure which considers both selection of color and jobs for the subsequent batch performs better than procedures in which the color pattern is decided in advance. We used this color and job selection procedure to analyze the tradeoff between setup costs and the cost of utility work. Technological constraints on the sequence of body models can be considered by restricting the procedure to choose from jobs that are feasible with respect to these constraints for each slot. This can lead to infeasibities near the end of the sequence, but in practice these are resolved by permitting N jobs out of a slightly larger pool of jobs to be scheduled. On the other hand, utility work considerations in the body shop can be handled in the same way as those in the trim and chassis areas. Additional research is needed to generalize these ideas to consider sequences with unequal color batch sizes, and to incorporate sequence-dependent setup costs. 20

References Bolat, A., 1988. "Generalized Mixed Model Assembly Line Sequencing Problem." Unpublished Ph. D. Dissertation, University of Michigan, Ann Arbor, MI. Bolat, A. and C. A. Yano, 1988a. "Scheduling Algorithms To Minimize Utility Work At A Single Station On A Paced Assembly Line." Technical Report 88-7, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI. Bolat, A. and C. A. Yano, 1988b. "Sequencing for Paced Assembly Lines: Objectives and Algorithms." Technical Report 88-13, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI. Bird, C.G., 1986. "Sequencing Vehicles for Assembly Under Precedence Constraints." Paper Presented at ORSA Conference, Los Angeles, CA., April 15, 1986 Burns, L.D. and C.F. Daganzo, 1985. "Assembly Line Job Sequencing Principles." Research Publication GMR-5127, General Motors Res. Lab., Warren, MI. Coffman, P.E., S.E. Hoffman and S.A. Weiner, 1985. "An O.R. View of Assembly Plant Modeling." Working Paper, Ford Motor Company. Law, A.M. and W.D. Kelton, 1982. Simulation Modeling and Analysis. McGrawHill, New York. Monden, Y., 1983. Toyota Production System. Industrial Engineering and Management Press, IIE, Atlanta. 21

Okamura, K. and H. Yamashina, 1979. "A Heuristic Algorithm for the Assembly Line Model-Mix Sequencing Problem to Minimize the Risk of Stopping the Conveyor." Int. J. Prod. Res., Vol.17, No.3, pp.233-247. Thomopoulos, N.T., 1967. "Line Balancing-Sequencing for Mixed-Model Assembly." Management Science, Vol.14, No.2, pp.59-75. Tucker, A.W, C.E. Miller and R.A. Zemlin, 1960. "Integer Programmming Formulation and Traveling Salesman Problems." J. ACM Vol.7, pp.326-329. Weiner, S., 1985. "Perspectives on Automotive Manufacturing," in The Management of Productivity and Technology in Manufacturing, edited by Paul R. Kleindorfer, Plenum Press, New York, pp.57-71. Wester, L. and M. Kilbridge, 1963. "The Assembly Line Model-Mix Sequencing Problem." Proc. of the 3rd Int. Conf. on OR, Dunod, Paris, pp.247-260. Yano, C.A. and R. Rachamadugu, 1987. "Sequencing to Minimize Workload Fluctuations in Assembly Lines with Product Options." Technical Report 87-22, University of Michigan, MI. 22

Data Number Average Utility Work Per Job (min.) of Type Jobs FIXRAN FIXDEC FIXING BEST Random 1000 0.55 0.55 0.55 0.48 Random 2000 0.42 0.42 0.45 0.38 Random 4000 0.31 0.31 0.32 0.27 Random 5000 0.30 0.30 0.31 0.26 Real 1000 1.39 1.43 1.42 1.24 Table 1: Average performances of the various color sequencing rules 23

Job Choice Optional Operation Required In Station Type Number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 X X XXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X x I X X X X X X X X X X X X X X X X X X X X X X X XXX X X X x x XXX Table 2: Types of jobs used in correlated data sets. 24

Average Utility Work Per Job (min.) Data Number Batch Size Type of Jobs 1 2 4 10 20 40 1CO Random 1000 0.146 0.206 0.300 0.412 0.480 0.544 0.748 Random 2000 0.102 0.142 0.212 0.306 0.376 0.422 0.504 Random 4000 0.082 0.118 0.160 0.224 0.274 0.308 0.376 Random 5000 0.092 0.128 0.162 0.216 0.270 0.306 0.356 Real 1000 0.453 0.574 0.825 1.151 1.241 1.326 1.524 Real 5000 0.290 0.398 0.642 1.058 1.153 1.210 1.232 Correlated 1000 0.676 0.870 1.420 2.196 2.540 2.726 2.860 Correlated 5000 0.598 0.758 1.300 2.136 2.492 2.660 2.780 Table 3: Relation between batch size and utility work for various data. 25

.0 0 L. 0 a() go0 0 65,,$l. 654321 I II s* Legend * Random o Correlated * Real *""M 4 s * " w * "^, g ". -e. ^ w~~~~~~s _.,i -r - -r n ___~.r n rnm m_~___,_ — nt 0 20 20 40 6I 1 I V I I I I 60 80 100 Batch size Figure 1: Tradeoff between setup cost and utility cost for 1000 job orders. 26

6 5: | Legend ~ at|I RRandom ~-'4 L ~ Q Correlated O. 02 2 ^4' _ I -' — I —- I I I I I I I a 0 20 40 60 80 100 Batch size Figure 2: Tradeoff between setup cost and utility cost for 5000 job orders. 27

.0 0 L 0 0 -- 0. 12108642-,i Legend * Random 0 Correlated * Real **ASW series _ftsea" - 43 — a 3 - - -- a " o "" * a o0m a" "M a* wa a a a a a a" a- 0 l^ _, _ _ _ _ _ __ --- _ _ L_ LI - — I-:__ 0 0 20 40 60 80 100 Batch size Figure 3: Tradeoff between setup cost and utility cost for higher unit utility cost. 28

g3 90504732 7534