Division of Research March 1985 Graduate School of Business Administration The University of Michigan A COMPARATIVE EVALUATION OF HEURISTIC LINE BALANCING TECHNIQUES Working Paper No. 415 F. Brian Talbot The University of Michigan and James H. Patterson University of Missouri-Columbia and William V. Gehrlein University of Delaware FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the expressed permission of the Division of Research.

I I I I ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~~~~~~~~~~~~~~~~~~~~~ ----— ~~ 1*~ —~ _11~ —p -— ~9 ---~1 -~~~P

Abstract In this paper, we report on a computational experiment designed to assess the efficacy of twenty-six heuristic decision rules which group work tasks into work stations along an assembly line such that the number of work stations required is minimized. The heuristic decision rules investigated vary from simple list processing procedures that consider a single attribute of each work task for assignment, to procedures which are optimal seeking, but which have had their search terminated through the imposition of a limit on the amount of computation time that can be devoted to each search. Also included are heuristic decision rules which backtrack in an attempt to locate an improved solution, and decision rules which probabilistically search for improved solutions. Our investigation differs from those reported previously, in that the objective in balancing each line is to determine the minimum number of work stations for a given limit on the time available for assembly at each work station (the cycle time). Previous approaches have investigated the problem of determining the minimum cycle time for a given line length. We also compare the results obtained with the optimal solution for a subset of the problems investigated. Both problems which have appeared in the open literature and problems which have been solved for the first time are included. Since some of the results reported in this paper differ from those reported previously, we suggest why these differences have occurred. Guidelines are also given to those balancing industrial assembly lines on the choice of the heuristic decision rule to use whether one is attempting to obtain a minimum station balance given a limit on the time available for assembly at each work station, or whether one is attempting to minimize the time devoted to assembly at a work station given a limit on the number work stations available.

I

1. INTRODUCTION One of the problems inherent in organizing for mass production is how to group work tasks to be performed into "work packages" or work stations so as to achieve a desired level of performance. When the number of work stations or production employees is fixed, the objective is to allocate the work to be performed to the work stations in such a way that the maximum time required for assembly at any given station (i.e., the cycle time) is minimal across all feasible station balances. The optimal solution to this problem, called the Type II problem (Mastor, 1970), maximizes the output rate or the number of units that are produced for the given line length. A Type I problem, on the other hand, is characterized by a forecast of demand or a production plan dictating the output or the production rate. The objective in this problem is to detemtne the minimum number of work stations required to meet the specified production requirements. A line with fewer stations translates into lower labor costs and reduced space requirements, and hence, a more cost effective production plan. In this paper, we examine in detail the latter of these two problem types, and offer guidelines for applying our results to either one. There have been two previous investigations of the performance of various heuristic decision rules for solving the Type II assembly line balancing (ALB) problem for the case in which heuristic performance is assessed relative to the best heuristic result obtained. Mastor (1966) evaluated the performance of ten heuristic decision rules on twenty and forty task assembly problems for three different order strengths (ratio of the number of ordering relations among the tasks to be grouped into work stations to the total number of possible orderings), and for line lengths (number of work stations) ranging

-2 - from four to fifteen for the forty task problems and from three to twelve for the twenty task problems. Since the majority of the line balancing heuristics investigated by Mastor were designed to solve the Type I line balancing problem, Mastor obtained minimal cycle time balances by iteratively employing each of the evaluated techniques, increasing the cycle time in one percent increments above the lower bound cycle time until a balance was achieved for the specified number of work stations. Mastor's general conclusion is that best results are obtained by the Held et al. (1963) dynamic programming technique, although the range of experimental conditions over which this procedure was evaluated was less than for most of the other procedures. (This was due to excessive computation times being required on certain categories of problems using the dynamic programming approach. The difficulty reported by Mastor in solving certain problem types using dynamic programming is consistent with our experience with this approach, as described later. Also, Magazine and Wee (1981b) observed this same result when attempting to obtain optimal solutions to the line balancing problem using a dynamic programming procedure.) The results obtained with the Held et al. dynamic programming technique were followed closely by Arcus's COMSOAL (1963) in Mastor's investigation. Further, the range of experimental conditions over which this procedure was evaluated was not curtailed as with the Held et al. dynamic programming procedure. Dar-El (Mansoor) (1975) investigated twelve heuristic decision rules, also for Type II problems. Dar-El used fifty, one-hundred and five, and onehundred and forty task assembly problems, varied across three task precedence configurations, and four ratios of work elements per station (WEST ratios) in his evaluation. Dar-El's general conclusion is that MALB, a technique he developed (1973), which is based upon a backtracking extension to the Ranked

-3 - Positional Weight heuristic of Helgeson and Birnie (1961), gives consistently superior results to the Arcus or to the other techniques investigated. (A procedure we have found effective, a backtracking approach due to Hoffmann (1963), was not included in Dar-El's investigation.) In this paper, we report on a computational experiment designed to assess the efficacy of heuristic procedures for solving the Type I assembly line balancing problem. Heuristic decision rules that have been found effective elsewhere are included in this evaluation, as are some that are reported on for the first time. Four data sets are used to assess heuristic performance. The first data set consists of 120 computer generated problems each of which is solved for 11 cycle times, yielding 1,320 balances. The second data set consists of 12 problems which have appeared in the open literature. These 12 problems are solved for a variety of cycle times, yielding/64 balances in total. The third and fourth data sets each consist of 110 "difficult" balances. These latter problems have been generated in order to assess the performance of several of the heuristic decision rules evaluated under a "worst case" scenario. We first compare the various approaches examined to the minimum heuristic result obtained for each problem. This measure provides us with a relative measure of heuristic performance, and thus is similar to previous investigations. Then, because many of the heuristic procedures evaluated are able to determine and verify optimal solutions within the specified time limit for a subset of the problems examined, we also compare heuristic performance to the known optimal solution for this subset of problems. In so doing, we obtain an estimate of absolute performance for each of the heuristic decision rules that previous investigations have not provided.

-4 - In Section 2, each of the heuristic decision rules investigated is described. Section 3 then describes the test problems used to assess heuristic performance. In Section 4 we present the computational results. Because the results reported in Section 4 are somewhat at variance with other reported results, in Section 5 we suggest why the variability in results has occurred. We also offer guidelines for applying the heuristic decision rules to either type of line balancing problem. Concluding remarks are given in Section 6. 2. HEURISTIC LINE BALANCING TECHNIQUES INVESTIGATED In this section, each of the heuristic decision rules investigated is described. These decision rules vary from simple list processing prioritizing schemes to optimal-seeking procedures which have had the amount of time to devote to each search limited. To aid in our description of these procedures, we have placed each decision rule into one of four categories. These categories allow us to capture salient features of each approach, and to emphasize the similarities and differences among them. The first category consists of those decision rules which implement a list processing prioritizing scheme for task assignment based upon a single attribute of each assembly task. We term this category "Single-Pass Decision Rules" (Dar-El (1975)). The second category consists of decision rules which are a composite of the Single-Pass Decision Rules, or which otherwise produce multiple single-pass solutions for a given problem, selecting that solution for implementation which results in the fewest number of work stations. We include in this category the Arcus COMSOAL (1966) procedure found effective by Mastor, as well as a composite rule which selects the best of the solutions determined by our application of the single-pass decision rules included in Category I. This second category is

-5 -termed "Composite Decision Rules." Two of the procedures evaluated consist of backtracking approaches which attempt to improve upon a solution or station assignment previously obtained. These procedures are contained in a third category labeled "Backtracking Decision Rules." Procedures in this category include the Precedence Matrix, Enumeration method of Hoffmann (1963), and MALB (1973). Finally, six procedures are included which are optimizing approaches, but which have been programmed with a time limit set to restrict the time permitted for each solution. The procedures included in this category are two versions of Branch and Bound (Magazine and Wee, 1981b), two variations of Integer Programming (Talbot and Patterson, 1984), Dynamic Programming (Schrage and Baker, 1978), and MUST (Dar-El and Rubinovitch, 1979). This last category is titled, "Optimal Seeking Decision Rules." 2.1 Single-Pass Decision Rules In this category, thirteen single-pass, single attribute, priority dispatch scheduling rules such as Maximum Ranked Positional Weight (Helgeson and Birnie, 1961), Maximum Number of Immediate Followers (Tonge, 1961), Maximum Task Time First (Moodie and Young, 1965), etc., are included. The heuristic decision rules in this set include those which have been found effective elsewhere, plus two "benchmark" heuristic decision rules. Several techniques are additionally included which have been recently developed to compete against the set of established rules. Each of the decision rules included in this first category consists of a simple, computationally efficient, list-processing procedure that assigns tasks to work stations according to a task's computed priority. Operationally, in the implementation of each of these procedures, a task is first assigned a numerical priority specified by the logic of the heuristic decision rule.

-6 - Then, tasks that are both precedence and cycle-time feasible (i.e., all predecessors have been assigned to a work station and the task time is not larger than the remaining time available at the work station), are placed on an available list. The task on the available list with the highest priority is assigned first. The available list is then updated to reflect the possible addition of tasks that are now precedence feasible, and the amount of time available to be assigned to tasks in the work station is reduced by the task time of the assigned task. This process continues for a station until no more tasks can be assigned to it. The assignment process then continues to the next station, and so on, until all tasks have been assigned to some work station. When the final task has been assigned, a complete balance has been obtained. The thirteen decision rules included in our investigation are delineated in Table 1. Also included in Table 1 is the basis for determining task priority. A random rule is included in this set in order to provide a comparison with the more logically appealing decision rules. Rules which are being investigated for the first time include: MINLB, MINUB, MINSLK, MAXAVGRPW, MIN(UB/TFOL), MAX(DUR/UB), and MAX(TFOL/SLK). This set thus includes the majority of those single-pass, heuristic decision rules which have been found effective elsewhere, as well as includes several new approaches for solving this problem. 2.2 Composite Decision Rules 2.2.1 The Best of Thirteen Rule (COMPOSITE-13) The first composite decision rule evaluated selects the best solution available from Category I decision rules. Because a given decision rule does not always discriminate among tasks on an available list (for example, two or more tasks available for assignment to a work station could tie on their task

-7 - TABLE 1 SINGLE-PASS DECISION RULES Rule 1. Maximum Ranked Positional Weight 2. Maximum Total Number of Follower Tasks 3. Maximum Task Time 4. Maximum Number of Immediate Follower Tasks 5. Minimum Slack 6. Random Task Assignment 7. Minimum Lower Bound 8. Minimum Upper Bound 9. Minimum Task Number 10. Maximum Average Ranked Positional Weight 11. Minimum Upper Bound Divided by the Total Number of Followers 12. Maximum Task Time Divided by Task Upper Bound 13. Maximum Total Task Followers Divided by Task Slack Notation MAXRPW MAXTFOL MAXDUR MAXIFOL MINTSLK RANDOM MINLB MINUB MINTSKNO MAXAVGRPW MIN(UB/TFOL) MAX(DUR/UB) MAX(TFOL/SLK) Basis for Determining Task Priority RPW. = t. +. t 1 i jeSi j NS. 1 ti. 1 NIS. UBi - LBi random (uniform) LB. = [(ti + tj)/C] 1 i jiePi i UB. = N+l-[(t + t )/C] I i jeSi task number, i RPWi/(NSi+1) UBi/(NSi+1) ti/UBi NS./Slack. 1 1 C Station cycle time. N The number of tasks to be balanced into work stations. NSi(NPi) The total number of tasks which succeed (precede) task i (i.e., the number of elements of Si(Pi)). NISi(NIP.) S (P ) i i t. 1 The number of tasks which must immediately succeed (precede) task i. The set of tasks which must succeed (precede) task i. Assembly time required to complete task i. The smallest integer greater than or equal to X. [X]

-8 - times when the prioritizing scheme is based upon task duration), it is also possible to use one of the remaining twelve decision rules to break ties. Including the tie-breaker decision rules yields 156 (13 x 12) rule/tie-breaker rule combinations for solving each problem. Further, the possibility also exists to balance a given line beginning with the last task in the network and working forward, achieving what previous researchers of the line balancing problem have termed a "reverse" balance. Considering decision rule/tie-breaker rule combinations as well as balancing a line in reverse yields 312 possible decision rules for solving a given problem (13 x 12 x 2) using the thirteen heuristic decision rules described in Category I. The Best of Thirteen Rule selects the best of these 312 balances, implemented as described below. Whenever a balance is determined by any decision rule that is equal to the smallest integer greater than or equal to the sum of the task times divided by the cycle time, the optimal solution (that is, the solution requiring the minimum number of work stations) has been determined. This is because it is not possible to obtain a balance requiring fewer work stations than given by this quantity, which we refer to as the LOWER BOUND (M) on the value of a solution.1 In the implementation of the Best of Thirteen Decision Rule (as well as with all of the decision rules which follow), the procedure terminates the search for the minimum solution whenever a balance is obtained that is equal to this lower bound. The effect of this process is to eliminate unnecessary computations and, hence, to reduce the computation time required to solve many of the problems investigated. 1The quantity M = [S ti/C]+ has been termed the "theoretical minimum" number of work stations by previous researchers investigating the line balancing problem. This is an unfortunate choice of words, as a given problem may have an optimal solution in which the number of work stations exceeds the "theoretical minimum."

-9 - 2.2.2 Arcus' Biased Sampling Procedure (ARCUS) The Arcus (1966) procedure uses a biased sampling approach to generate feasible sequences of tasks for assignment to a work station. A "fit list," consisting of those tasks which can be assigned to a work station is constructed, and weights governing the probability the task will be selected for assignment to the work station are assigned to each task. Tasks so assigned are removed from the fit list, and a new fit list, consisting of the tasks which can currently be assigned to a work station is constructed. The process continues until all tasks have been assigned to some work station. A given line is then balanced several times, resulting in different assignments based upon the probabilistic selection of tasks from the fit list. To be consistent with the work of Arcus (1963), Mastor (1970), and Dar-El (1975), Arcus' Rule IX (which is the product of five separate weights) is used in our evaluation. The procedure we use is programmed to determine eighty balances for each problem, and to then select the balance requiring the fewest number of work stations. However, if a balance is obtained during execution of this procedure that is equal to the lower bound M, then the procedure terminates, yielding M as the number of work stations required. 2.3 Backtracking Decision Rules 2.3.1 Hoffmann's Enumeration Procedure (HOFFMANN-0.0) Hoffmann (1963) developed a heuristic method that assigns to each work station, in numerical order, a combination of tasks which minimizes station idle time. Starting with station one, a precedent feasible list of tasks is maintained from which the combination of tasks which will minimize station idle time is found via complete enumeration. These tasks are assigned to station one, and the process continues with station number two using an updated precedent feasible list. This procedure is repeated for each station

-10 - in numerical order, until all tasks have been assigned. Hoffmann uses a special zero-one precedence matrix and index vector to implement the enumeration process, which results in a very simple computer code, a description and FORTRAN listing of which is in his original article (1963). The Hoffmann methodology can be applied to tasks in decreasing order as well as in numerical order, which results in a second solution to a problem. In this investigation, all balances are solved in both the forward and reverse direction (where a forward balance did not determine the minimum required number of work stations, M), with the best solution being reported. 2.3.2 Hoffmann's Modified Enumeration Procedure (HOFFMANN-0.5 HOFFMANN- 1.0 HOFFMANN-2.0) Because the original Hoffmann approach considers stations in numerical order, it has a tendency to concentrate idle time in the later stations. In addition, a significant amount of computation time can be spent at those stations where the task precedence feasible list is long, and where a zero idle time solution doesn't exist or is difficult to determine. In the latter case, all feasible combinations of task assignments may have to be enumerated. In order to overcome these difficulties, Gehrlein and Patterson (1975) proposed a very slight modification to the original Hoffmann procedure: instead of determining the minimum idle time solution at each work station, determine one that is 'acceptably' close to minimum. To define acceptably close, Gehrlein and Patterson use a measure of average idle time per station, which is derived in the following manner. The quantity (M x C) gives the minimum amount of time that will be devoted to producing one unit of product. This quantity bears the following relationship to the total work content (E t ) for a given line: i i

-11 - (M x C) > Z t.. -i 1 The difference between these two quantities ((M x C) - E t ) represents the i i minimum total line idle time that will necessarily be present in any balance. This quantity divided by the minimum number of work stations required, M, yields an estimate of the average amount of idle time present in a work station. The Hoffmann procedure is thus modified by curtailing the search for the set of tasks resulting in the minimum amount of idle time for a given station whenever a subset of tasks o is found which satisfies the following relation: 0 < C - E t. < ([(C x M) - Z t.]/M) - 1 i i where the parameter 0 is varied in an attempt to obtain a balance requiring the fewest number of work stations. Gehrlein and Patterson (1975 and 1978) have shown that this slight modification to Hoffmann's original procedure can have a significant impact on reducing the amount of time devoted to each search, while simultaneously smoothing the idle time present among work stations for certain classes of line balancing problems. Further, this improvement in computation time is often achieved with no increase in the number of work stations required. Based upon previous experience in solving line balancing problems with this approach, we allow 0 to assume the values 0.5, 1.0, and 2.0, and denote these modified Hoffmann procedures by HOFFMANN-0.5, HOFFMANN-1.0, and HOFFMANN-2.0, respectively. 2.3.3 Dar-El's Line Balancing Heuristic (MALB) Dar-El developed MALB (1973) as a heuristic variant of his earlier optimal-seeking iterative procedure (1964). His optimal seeking procedure is based upon the Rank Positional Weight heuristic method of Helgeson and Birnie

-12 - (1961), enhanced with a backtracking algorithm that generates all feasible sequences of task assignments. Dar-El (1973) found that the computation time of his optimal seeking method restricted its applicability, so he sought to develop a heuristic approach that would retain most of the power of the optimal approach, without incurring its computational expense. MALB is the result of these efforts. To limit the number of sequences generated, and hence, to reduce computation time, MALB incorporates four types of heuristics that control the amount of backtracking permitted. In a comparative study (1975), Dar-El found that MALB dominated both ARCUS and the best of the ten single-pass rules he evaluated. On the basis of these results, MALB was included in the present investigation. MALB, however, was originally written to solve the Type II problem. Hence, it was necessary to modify it slightly here. Like most of the methods developed to solve Type II problems, MALB, in effect, solves a series of Type I problems. In the Type I problem the cycle time is fixed, and the minimum number of stations is sought. The Type II problem fixes the number of stations, and seeks to determine the minimum cycle time. Operationally however, MALB, and most of the other procedures, solves the Type II problem by fixing the cycle time at the theoretical minimum time (the largest task time), and determines the minimum number of stations less than a specified 'goal' number of stations, y. If no solution is found, then the cycle time is increased one time unit, and the process is repeated. The first feasible solution found with the number of work stations less than or equal to y yields the desired balance. (In general, if the procedure is optimal-seeking, then the first feasible solution is optimal. Otherwise, as with MALB, it is heuristic.) For the present investigation, instead of permitting the cycle time to increase when no feasible solution is determined, the goal y is increased by

-13 - one work station, and another attempt is made to find a feasible solution. The first feasible solution found is the minimum (heuristic) number of stations. Specifically, then, the only modification made to MALB (other than changing input and output formats) was to defeat the logic in the procedure that permits the cycle time to increase. The cycle time is fixed at the desired experimental level. Initially, y is set equal to M. If no feasible solution is determined, the value of y is increased by one station, and the process is repeated until a feasible solution is determined. 2.4 Optimal-Seeking Decision Rules The methods described in this section are included in our evaluation in order to gain insight into the benefit obtained by using optimal-seeking algorithms given a computational time constraint roughly comparable to the time required to solve a problem using the more sophisticated heuristic procedures. Clearly, given enough computation time, any optimal-seeking procedure will dominate a heuristic one. Our purpose is not to verify this fact, but to give an indication of the quality of solutions obtained for a given amount of computation time expended. All of the solution routines listed here have thus been run with an internal CPU time trap of 3.0 seconds per problem (balance). The reported solution is the minimum one obtained within the 3.0 second limit. 2.4.1 Branch and Bound Methods (MAG-1 and MAG-2) Magazine and Wee (1981b) report excellent results for the Type I line balancing problem with their branch and bound procedure. With their method, each node in the solution tree corresponds to a feasible set of task assignments to a particular work station, where all nodes at the same depth in the tree refer to the same station number. Starting with node zero (the null set), descendent nodes from a node of depth (d) are generated, which are

-14 - maximal feasible assignments of tasks to station (d+l). The branching direction, fathoming criteria, and growth rate of the tree are controlled via a number of heuristics and dominance tests incorporated into their procedure. Two decision rules of special significance used in their procedures are IUFFD (Immediate Update First Fit Decreasing), which we refer to as MAXDUR, and IUBRPW (Immediate Update Backward Recursive Positional Weight), a variation of MAXRPW. Although their branch and bound procedure incorporates a breadthfirst (versus depth-first) branching strategy, an upper bound on the solution is found at each node using one of these two heuristics for the unassigned tasks. This permits their procedure to terminate prior to verification of optimality with a given heuristic solution to a problem. To facilitate the use of this feature, they allow the user to select one of these heuristics and to specify a time limit for implementation of their approach. This is the time limit capability used in our experiments. The references to MAG-1 and MAG-2 correspond, respectively, to the use of the heuristics IUFFD and IUBRPW. 2.4.2 Integer Programming (ALBCUT and ALBHOFF) Two variations of Talbot and Patterson's (1984) integer programming procedure are included in our evaluation. The basic algorithm is a depthfirst, implicit enumeration, backtracking procedure to which various search, fathoming, and backtracking decision rules are applied. The first variation included (ALBCUT) contains network cuts (1984), where search and backtracking are controlled with the heuristic decision rule MINUB (with ties broken using MAXDUR). The second variation (ALBHOFF) also uses MINUB and MAXDUR for search and backtracking, but does not use any cut associated fathoming rules. Also, prior to enumeration, the problem is first solved with HOFFMANN-0.5, which

-15 - provides an initial heuristic starting solution and computational upper bounds. 2.4.3 Dynamic Programming (DYNAMIC) Schrage and Baker (1978) have proposed an efficient method for implementing the dynamic programming approach of Held et. al. (1963) through improved procedures for generating feasible subsets, and for labeling. Magazine and Wee (1981b) programmed and tested the Schrage and Baker approach for solving the Type I line balancing problem. Magazine and Wee concluded that their branch and bound solution procedure is preferred to dynamic programming for solving these types of line balancing problems, both with regard to computation time and computer storage required. For completeness, however, we have included the dynamic programming approach in our evaluation. 2.4.4 Multiple Solutions Technique (MUST) MUST, by Dar-El and Rubinovitch (1979), employs exhaustive enumeration to generate all solutions, or some subset of them, for solving the Type II line balancing problem. As with MALB, the Type II problem is solved as a sequence of Type I problems. The cycle time is fixed, and a "hurdle" number of work stations, y, is specified. If a feasible number of work stations cannot be found given y, the cycle time is increased one time unit, and the process is repeated. Starting with station number one, MUST generates all feasible task assignments. Redundancies are eliminated, and the remaining feasible task assignments (subsets) for this station are saved. At station two, and subsequent stations taken in numerical order, these subsets are extended by adding all feasible task assignments at a work station. Redundancies are then eliminated, and the extended subsets are saved. This process is repeated until all tasks have been assigned (all subsets are fully extended).

-16 - This exhaustive enumeration procedure results in an exponential growth in the number of subsets saved. In order to make this process manageable, MUST saves sets as a sequence of bits, and also uses circular storage buffers. Even with these storage-saving features however, MUST, unlike the other methods evaluated, is programmed to use external storage. To control the growth in the number of subsets saved, MUST contains three user-specified parameters. These can be set to permit the generation of either multiple optimal solutions, or multiple heuristic solutions. As a result of experiments by Dar-El and Rubinovitch (1979) which demonstrated that MUST dominates MALB, MUST was included in our investigation. It was modified to solve the Type I problem in the same manner as was MALB, by permitting the hurdle number of work stations y to increase by one station if a feasible solution could not be found, rather than (as with the Type II approach) increasing the cycle time by one time unit in each iteration. 3. DESCRIPTION OF PROBLEMS SOLVED In order to generalize the results of our investigation, both randomly generated problems and problems taken from the open literature are solved. The characteristics used for problem generation are based upon an examination of actual assembly line balancing problems, and are experimentally varied over a wide range of representative values. There are four data sets in total: three comprising randomly generated problems, and a fourth data set consisting of problems available in the open literature. 3.1 Main Experimental Data Set This data set contains 120 unique assembly networks, each of which is solved for 11 cycle times. Details of problem characteristics and generation schemes for these problems are described below.

-17 - 3.1.1 Problem Size Sixty 50-task and sixty 100-task assembly networks are randomly generated. These line sizes are sufficiently large to permit generalization of our results to actual line balancing problems, and are comparable in size to those used by Dar-El (1975), and are significantly larger than those examined by Mastor (1970). 3.1.2 Distribution of Task Times An investigation of actual line balancing problems appearing in the open literature suggests parameters for generating task times. These times are derived from the binomial distribution (n=30, and r=0.25), with zero duration tasks having their task times increased to one time unit. 3.1.3 Distribution of Cycle Times When the magnitude of the cycle time approaches the maximum task time in an assembly line balancing problem, the alternatives available for scheduling tasks into work stations decrease, as do the opportunities for the heuristic scheduling rule to exercise its intended logic in assigning tasks to a work station. Alternatively, as the cycle time increases relative to the maximum task time, the number of alternatives for assigning tasks to work stations increases, as does the discretionary "power" of the investigated decision rule. In order to investigate the efficacy of the heuristic decision rules evaluated over a wide range of problem types, each problem generated is solved for the cycle time equal to the maximum task time. The cycle time is then increased in 10 percent increments of the maximum task time to the closest integer equal to 10 percent, 20 percent, 30 percent, etc., above the minimum possible cycle time until eleven balances are obtained for each problem. 3.1.4 Strength of the Precedence-Ordering Relations Among Tasks The strength of the precedence-ordering relations among tasks affects the number of alternative production lines that may be established. This in turn

-18 - influences the discretionary power of the heuristic decision rule and, hence, its effectiveness. Network density, a characteristic which measures the strength of this relation, has been found to be an important factor in influencing heuristic performance in previous investigations of the line balancing problem. To define density, let W be an N x N 0-1 matrix that represents a precedence-ordering relation P. For a given element wij of W, let wij = 1 if Xi e P. (i.e., if task i precedes task j) and i.. = 0 if task i does i 1 1J i not precede task j, or X. j P.. Let d be the total number of relations contained in P, or N N d= XI I. i=l j=l ] The maximum number of relations that can be included in P is N(N-1)/2. The density of the assembly network is defined to be the ratio: D = 2d/[N(N-1)], or the ratio of the number of relations that exist to the number which could exist. The measure 1-D is the F-ratio used by Dar-El (1975), and the measure D is referred to as order strength by Mastor (1970). Values of D close to 1 indicate a highly interconnected network, and fewer alternatives available for assigning tasks to a work station. Values of D close to 0 indicate relatively fewer precedence relationships, and more opportunities for assigning tasks to a work station. In our evaluation, values of D equal to 0.2, 0.3, 0.5, and 0.8 are used for problem generation. 3.1.5 Partial-Order Generating Methods It is possible to test not only for the effect of network density on heuristic performance, but also for the effect of the method used to generate precedence-ordering relations. That is, several methods for generating a

-19 - precedence-ordering relation on a set of tasks can be devised, each resulting in the identical problem density. However, various factors of the ordering relation structure can be different for different generating methods. Three methods of generating precedence-ordering relations are investigated, and their effects on problem solution are assessed. All three methods of generating precedence-ordering relations work in the same general way. We begin to describe how each method works by recognizing that precedence-ordering relations are partial ordering relations. A binary relation P on a set X is a partial order if it is irreflexive (x.Px. for no x. in X), asymmetric (x.Px. requires not x.Px. for all x. and x. in X), and 1 '1 1 1 J transitive (if x.Pxj and xiPxk then xiPxk for all xi, x., and xk in X). Given a linear ordering relation L = xx2... XN, we wish to generate a random partial order P that is contained in L, or PC L. That is, if x.Pxj, then 1J i < j. We do not lose any generality by requiring this, because any partial order can be transformed so that if xiPxj then i < j simply by interchanging the subscripts attached to the x's. The first step in each generating process is to generate a suborder PO. Suborders are binary relations that are irreflexive and asymmetric, but not necessarily transitive. P0 is then changed to a partial order by taking the transitive closure of P0, denoted by Pt. This indicates that all necessary P relations are added so that Pt is transitive. For example, if the suborder P0 has xiP0xj and xjP0xk, it is not necessarily true that xiP0xk, since suborders are not always transitive. In forming Pt, all relations, such as xiPXk, are appended so that Pt is transitive. Since Pt is a transitive suborder, it is a partial order, and it is used as the generated partial order in network synthesis (Fishburn & Gehrlein (1974)). We now describe the three partial order generating methods used in our investigation:

-20 - Method 1: Let a be a randomly selected permutation on {1, 2,..., N}. For each j from 2 through N select a yi at random from {xo(l), x(2),..., x) Let P0 = L {[Y2Xa(2)] [x 0(2)'Y2I * [YN'Xo(N)]' [ (N)YNy]} so that P0 contains N-1 order pairs, and form the transitive closure Pt. Then Pt is made more Os 0 dense by adding q additional pairs from L-Pt The transo1* itive closure is taken after each pair is added and P results after the final transitive closure is taken. Method 2: Form P0 by taking each (i,j) pair with i < j and enter x.iPxj with probability p. The same p is used when each (i,j) pair is considered for entry into P0. Then P = P. Method 3: Form P0 by taking each (i,j) pair with i < j and enter xjwith probability (j-i) xiP xj with probability ( (Nl))k for some positive k. The same k is used when each (i,j) pair is considered for entry into P0. Then P = Pt. By examinating three distinct methods for generating the partial orders necessary to construct each network, we can assess the sensitivity of our results to the network generation scheme used. Many examples of simulation analysis can be given where the results reported are dependent on the procedure used to generate random partial orderings. (For example, see Fishburn & Gehrlein (1974) or Patterson (1976).) Hence, an examination of their effect is prerequisite to making general statements concerning the efficacy of the heuristic procedures investigated. (For a more comprehensive discussion of how the desired density measures are determined by using partial order generating methods, see Gehrlein (1980).)

-21 - 3.1.6 Main Experimental Problems Solved For each line size (50 and 100 tasks), each density (0.2, 0.3, 0.5, and 0.8), and each partial-order generating method (Method 1, Method 2, and Method 3), five line balancing problems are constructed. The density of the partial orders generated by Methods 1, 2, and 3 is controlled by the values of q, p, and k used, respectively, in each method. Each of the generated problems is then solved for cycle times equal to the largest task time, the largest task time plus 10 percent of the largest task time (rounded to the nearest integer), the largest task time plus 20 percent of the largest time (rounded to the nearest integer), etc., until the cycle time equals twice the largest task time. This yields 1,320 balances in total [(2)(4)(3)(5)(11)] in the Main Experimental Data Set. 3.2 Literature Problems A number of problems, ranging in size from 7 assembly tasks to 111 assembly tasks, were taken from the open literature to be used in this evaluation: Arcus (1963), Bowman (1960), Dar-El (1964), Heskia (1968), Jackson (1956), Jaeschke (1964), Kilbridge and Wester (1961), Merten (1967), Sawyer (1970), and Tonge (1961 and 1969). These problems also serve as the basis for determining the network generator parameters used for the main experimental data set. The cycle times used to assess heuristic performance in evaluating the procedures described are the same as those used by Talbot and Patterson (1984) in their evaluation of an integer programming algorithm for obtaining optimal solutions to this line balancing problem, with the exception of the Bowman and the Dar-El problems, which they did not include. For these latter two problems, the same cycle times as reported by the original authors were used (C = 20 for the Bowman problem, and C = 48, 62, and 94 for the Dar-El problem). For a more complete description of this data, see Talbot et. al.

-22 - (1985). Sixty-four balances were obtained using this literature data set over the range of cycle times considered. 3.3 "Difficult" Problem Set One Five 50-task and five 100-task assembly line networks with task times uniformly distributed between 1 and 10,000, and with network density equal to 0.2 were randomly generated and solved for 11 trial cycle times equal to 10,000, 11,000,..., 20,000. These balances were included in the experiment because with few precedence relations in the network and a very wide range of task times, the enumeration procedures evaluated can be expected to exhibit large increases in computation times. There are two arguments to support this notion: With an enumeration procedure, there will be fewer opportunities to terminate the search procedure at a given station before full enumeration is complete, because there are fewer sets of sums of task times that equal, or nearly equal, the cycle time. Also, with fewer precedence relationships, many more assignments are possible, resulting in an anticipated increase in the computation time required to solve a given problem. 3.4 "Difficult" Problem Set Two Preliminary experimental results using "Difficult" Problem Set One, led to the development of "Difficult" Problem Set Two. This set contains the same 110 networks as in Set One, except that all the odd task times are increased by one time unit to make them even numbers. The eleven cycle times include the largest task time and added increments of 10% of this value (to the nearest integer) up to twice the largest task time, where all even cycle times are increased by one time unit to make them odd numbers. With all problems having even task times and odd cycle times, no zero idle time station assignments of tasks or zero balance delay solutions are possible, thus

-23 - forcing enumeration methods such as HOFFMANN-O.O to completely enumerate all feasible task assignments at every work station. We emphasize that these latter two data sets were not generated to represent actual problem types such as those found in examining industrial line balancing problems. Rather, they were generated to assess "worst case" performance for several of the techniques investigated, especially those employing enumerative and backtracking approaches. 4. COMPARATIVE RESULTS 4.1 Experimental Conditions An attempt was made to solve each of the problems in all four data sets using the 26 solution procedures described in Section 3. A time limit of 3.0 CPU seconds per balance for each solution procedure was implemented as described. This is an internal time trap that excludes input time, but includes minimal computer output time per balance. All methods (with the exception of MUST) are programmed in FORTRAN and were run under the same operating system and compiler (IBM FORTRAN H OPT=2) and on the same computer, an AMDAHL 470/V8. MUST is programmed in PL1, and was run on the same AMDAHL 470/V8 using the same operating system after being compiled by the IBM PL1 optimization compiler (OPT=2). All methods, including MUST, were programmed to read from the same data set in an identical manner, and to write summary results to a common output data base. A concerted effort was made to run each program under similar operating conditions. With the exception of MALB, HOFFMANN-0.O, MUST and DYNAMIC, the methods were able to solve all problems within the time limit specified per problem. Unfortunately, neither MUST nor DYNAMIC were able to solve more than just a few of the smaller problems within this time limit. It became very clear that

-24 - their performance would be even worse on the larger problems, and it would be a misuse of a constrained computer budget to have them attempt the larger problems. Hence, they were dropped from further experimentation, leaving 24 solution methods to be evaluated. Before proceeding with the main results, an indication of the results obtained using MUST and DYNAMIC will be given to justify excluding them from further consideration. (The following are representative of our results —many more tests were run than are described here.) As mentioned in Section 2.4.4, MUST contains three user-specified parameters that control the growth of the solution space, which in turn affect computation time and solution quality. We first input the recommended parameter values as given in Table 2 of Dar-El and Rubinovitch (1979). Using these parameter values, MUST was able to solve only 27 of the 64 literature balances (the largest solved consisting of 21 tasks) within the 3.0 second time limit specified. Even with the limit doubled to 6.0 seconds per balance, only 29 of the 64 problems were solved, the largest consisting of 28-tasks. Within the 6.0 second limit, MUST was not able to solve any of the problems in either of the "Difficult" Data Sets One or Two, or any of the first 11 50-task problems in the Main Experimental Data Set. In an effort to obtain more solutions using MUST, even at the possible expense of lower quality solutions, the parameter values were all set equal to one, which would have the anticipated effect of reducing computation time and storage requirements for the algorithm. With these parameter values, MUST was able to solve 40 of the literature balances (the largest being a 30-task problem), two of the 110 balances (both 50-task) in the "Difficult" Set One, and none of the problems in the "Difficult" Set Two, within the 3.0 second time limit. A number of other tests were conducted with similar results. It

-25 - should be noted that these timing results are consistent with those of Dar-El and Rubinovitch, who report an average of 125.4 seconds per balance on an IBM 370/168 for a set of 50 to 140-task problems, for which they also report MALB required an average of 22.4 seconds on the much slower IBM 7044. The dynamic programming procedure was able to solve only the smallest 27 of the 64 literature balances within the 3.0 second time limit per balance, the largest problem being Mitchell's 21-task problem (C=39). Attempts to solve larger problems (e.g., 28-task and 45-task) also failed with a time limit of 6.0 seconds per balance. These findings are completely consistent with Magazine and Wee's results (1981b), and reinforced our decision to exclude this procedure from further evaluation. 4.2 Main Experimental Data Set Results Table 2 contains summary results for all heuristic decision rules retained, and for each data set. The first column under each data set is a relative measure of heuristic performance, the average percent above the best solution found by any method. The second column under each data set is the average percent above optimum, an absolute measure of heuristic performance. Whereas Table 2 indicates average heuristic performance, Table 3 shows the worst single result using each method. Specifically, the first column under each data set lists for each method the maximum percent above best heuristic solution determined for a single balance, and the second column lists the maximum percent above optimum. (All methods determined each balance within the 3.0 second time limit specified, except as noted in Table 2.) In order to more clearly illustrate the relationships depicted in Table 2 for the Main Experimental Data Set, Figures 1A and 1B were prepared. Figure 1A is a histogram of first column data with the heuristics grouped by category, and ranked within category. Figure 1B is a similar histogram of second

-26 - TABLE 2 Average Percent Results For All Data Sets MAIN EXPERIMENTAL DATA SET DATA SET: DIFFICULT SET ONE DIFFICULT SET TWO Above Best Above Above Best Above Above Best CRITERIA: (1) Heuristic (2) Optimum (3) Heuristic (4) Optimum (5) Heuristic SOLUTION METHOD Above Above Best Above (6) Optimum (7) Heuristic (8) Optimum I MAXRPW 2 MAXTFOL 3 MAXOUR 4 MAXIFOL 5 MINTSLK 6 RANDOM 7 MINLB 8 MINUB 9 MINTSKNO 10 MAXAVGRPW 11 MIN(UB/TFOL) 12 MAX(DUR/UB) 13 MAX(TFOL/SLK) 14 COMPOSITE-13 15 ARCUS 16 MALB 17 HOFFMANN-0.0 18 HOFFMANN-0.5 19 IIOFFMANN-1.O 20 HOFFMANN-2.0 21 MAC-I 22 MAG-2 23 ALBCUT 24 AI.BIIOFF 5.16 4.89 4.71 6.00 6.50 9.33 6.03 4.51 6.63 6.35 5.00 4.50 5.05 2.34 2.73 2.15 0.46 0.47 0.50 0.65 1.05 2.39 3.68 0.42 5.77 5.55 5.20 6.24 6.81 9.48 6.45 5.11 7.21 6.76 5.61 5.14 5.65 2.97 3.35 1.78 0.04 0.04 0.09 0.36 0.92 2.21 4.13 0}.02 4.62 4.27 4.81 3.96 5.16 10.26 5.81 3.43 8.96 5.66 4.27 4.40 4.71 0.46 2.78 0.31 1.34 3.29 3.29 3.41 0.00 0.52 0.60 0.73 4.85 4.31 4.70 3.94 5.34 10.71 6.03 3.34 9.02 5.84 4.31 4.52 4.83 0.23 2.94 0.36 1.48 3.44 3.44 3.44 0.00 0.61 0.26 0.45 4.76 4.70 4.99 4.79 5.43 9.11 5.15 3.91 7.08 5.15 4.82 4.87 4.60 1.90 2.06 2.80 1.75 1.58 1.61 2.41 0.89 2.16 3.52 1.13 4.35 4.46 5.22 4.3/ 5.20 8.32 5.19 3.75 6.95 4.93 4.51 4.88 4.22 2.47 2.00 2.40 0.65 0.15 0.39 1.68 0.26 1.34 2.92 0.01 4.43 4.22 4.72 4.59 5.09 8.96 4.94 3.40 7.04 5.09 4.30 4.59 4.26 1.65 1.75 2.78 1.42 1.61 1.56 1.96 1.09 2.27 3.22 1.10 4.33 4.(02 4.87 4.62 4.75 8.22 4.73 3.43 6.75 5.09 4.07 4.75 4.03 1.72 1.80 2.52 0.44 0.33 0.20 1.34 (. 31 1.18 3.23 0. 1 3 i I i,1 I ll 1 Number of Balances 635a 64 55 1 lob 45C a. The results for MALB are based upon b. The results for MALB are based upon c. The results for MALB are based upon HOFFMANN-0.0 are based upon 69 (out 872 balances (out of 1,320) and 431 (out of 635) that it solved. 79 (out of 110) and 30 (out of 50) balances. 80 (out of 110) and 24 (out of 45) balances. The results for of 110) and 25 (out of 45) balances, respectively. TABLE 3 Maximum Percent Results For All Data Sets MAIN EXPERIMENTAL DATA SET nTIVTITrll T CqFl nfr nTiF'Tr'll T qC'r T Wn DATA SET: LITERATURE UL!7rrL Ubu OFJL UNlr LsLrr,= —.r a L V Above Best Above Above Best CRITERIA: (1) Heuristic (2) Optimum (3) Heuristic Above Above Best Above Above Best Above (4) Optimum (5) Heuristic (6) Optimum (7) Heuristic (8) Optimum SOLUTION METHOD 1 MAXRPW 2 MAXTFOL 3 MAXDUR 4 MAXIFOL 5 MINTSLK 6 RANDOM 7 MINLB 8 MINUB 9 MINTSKNO 10 MAXAVGRPW 11 MIN(UB/TFOL) 12 MAX(DUR/UB) 13 MAX(TFOL/SLK) 14 COMPOSITE-13 15 ARCUS 16 MAB 17 HOFFMANN-0.O 18 HOFFMANN-0.5 19 HOFFMANN-1.0 20 HOFFMANN-2.0 21 MAG-1 22 MAG-2 23 ALBCUT 24 ALBHOFF 17.4 17.4 13.6 17.4 17.6 25.0 20.0 14.3 17.6 17.9 17.4 15.0 17.4 10.0 10.5 13.6 10.0 10.0 10.0 10.0 11.6 13.5 12.5 8.3 15.) 15.8 13.6 17.4 16.7 25.0 20.0 14.3 17.6 15.8 15.8 15.0 15.0 7.7 10.5 10.5 7.1 7.1 7.1 7.1 11.6 11.4 12.5 7.1 5).0 33.3 33.3 33.3 33.3 50.0 33.3 33.3 50.0 33.3 33.3 33.3 33.3 16.7 33.3 20.0 25.0 33.3 33.3 33.3 0.0 33.3 16.7 25.0 50.0 33.3 33.3 33.3 33.3 50.0 33.3 33.3 50.0 33.3 33.3 33.3 33.3 12.5 33.3 20.0 25.0 33.3 33.3 33.3 0.0 33.3 14.3 25.0 18.2 21.1 15.0 21.1 18.2 22.7 20.0 15.0 18.2 18.2 21.1 15.8 19.0 7.7 9.1 15.8 9.5 10.5 10.5 10.5 14.3 14.3 15.0 9.5 15.8 21.1 15.0 21.1 15.0 20.0 20.0 15.0 15.8 13.3 21.1 15.0 15.8 7.7 7.1 15.8 5.9 4.8 5.0 7.7 6.9 11.8 15.0 2.9 21.1 21.1 13.3 21.1 14.3 17.6 15.8 15.8 16.7 15.8 21.1 15.8 19.0 7.7 8.7 15.8 7.1 7.7 10.0 9.1 14.3 14.3 15.8 6.7 21.1 21.1 13.3 21.1 11.1 17.6 15.8 15.8 15.8 11.8 21.1 13.3 15.8 7.7 7.1 15.8 5.9 5.6 5.9 6.7 10.5 10.5 15.8 3.0 - - Number of Balances 1,320 635 64 55 110 50 110 45 NOTE: The footnotes to Table 2 also apply to Table 3.

-27 - FIGURE 1A AVERAGE PERCENT ABOVE MINIMUM ALL TWENTY-FOUR SOLUTION METHODS PERCENT 10 9 A V E R A G F. P E R C E N T A B 0 V E M N U M a 7 6 5 4 3 2 o 0 MMMMMMMMMMMM R C A H H H H M A M M A A I A A I A A A I A I I A 0 R 0 0 0 0 A t A A L X N X X N X XX N X N N N M C F F F F L B G G B D U D T U T R I L A T r 0 P U F F F F B H 1 2 C U B U F B F P F B V S S 0 O S H M m M 0 U R R 0 / 0 W 0 G L K M S A A A A F T / L T L L R K N I N N N N F U F / P 0 T N N N N B O S. E 0 0 1 2 L L I K 3 0 5 0 00 METHOD SP ------------------- LEGEND: CATEGORY SP C I- BK - O — - -- CATEGORY c E BK aiZ os FIGURE IB AVERAGE PERCENT ABOVE OPTIMAL ALL TWENTY-FOUR SOLUTION HETHODS PERCENT 1o0 A V E R A G E p E R C E N r A B 0 V E 0 p T M A L a 7 a 5 4 3 2 1 0 M M H M R C A H H H H M A M M A I A I I A 0 R 0 0 0 0 A A A N X N N N M C F P F F L B Q G o L A T T 0 P U F F F F B H 1 2 C v s s 0 0 s MM H 0 U Q L K M S A A A A F T R K N I N N N F P 0 T N N N N W. E 0 0 1 e 3 0 5 0 r A A A I A N X X X N X U 0 D T U T B U U F B F R R 0 / 0 / L T L U F / B 0 S L L K MM A A X X R I P F W 0 L METHOD CATEGORY H --- —-- SP -----------— A i- BK O --- — t-~- os — I LEGEND: CATEGORY LE D SP CLAi C BK WU^ OS

-28 - column data. As indicated in Figure 1 (A or B), the enumeration procedure of Hoffmann, or a variant of it, performs best on these problems. The original Hoffmann procedure, HOFFMANN-0.0, yields an average increase of 0.46 percent above the best heuristic solution result obtained, and an average increase of 0.04 percent above the optimal number of work stations. The Gehrlein and Patterson modification to improve computation time and idle time distribution characteristics yields only slightly larger results, as seen with HOFFMANN-0.5, -1.0, and -2.0. ALBHOFF, which begins with the HOFFMANN-0.5 solution and systematically attempts to improve upon it, has the best overall results of 0.42 percent above the best heuristic result obtained, and 0.02 percent above optimal solution on this group of test problems. ALBHOFF also found and verified the optimal solution more frequently than did any of the other optimizing methods (632 out of 635 optimal balances examined) and has the best "worst case" performance for a single balance (8.3 percent above best heuristic, and 7.1 percent above optimal, respectively). The next best results obtained are 1.06 percent above best heuristic and 0.92 percent above optimum for MAG-1. The performance of MAG-2, at more than twice the average percentage levels of MAG-1, and the much larger differences between ALBHOFF and ALBCUT, indicate the importance of the incorporated heuristics in implementing each of the optimization approaches. The primary difference between MAG-1 and MAG-2, for example, is in the use of IUFFD versus IUBRPW influencing the search strategy. Similarly, the overriding reason for the difference in performance between ALBHOFF and ALBCUT lies in the use of different initializing heuristics with each approach (HOFFMANN-0.5 versus MINUB). Although each of these methods will eventually determine the optimal solution given sufficient time and computer storage, these results suggest that the computational effort required in using these procedures as

-29 - heuristics is significantly influenced by the choice of the internal heuristic procedure employed. For the 872 balances it obtained, MALB has an average percent increase above the best heuristic result of 2.15, and an average percent increase above optimum of 1.78. These percentages are not directly comparable to the percentages for all of the other methods which are based upon the larger set of 1,320 balances. In an effort to correct for this difference, all methods were reranked on just the 872 balances that MALB obtained. This resulted in no changes in the rankings for the percent above optimum criterion. For percent above best heuristic, the ranking of MALB did not change. However, there were two pairwise exchanges: MINUB and MAX(DUR/UB) exchanged rankings, and COMPOSITE-13 and MAG-2 exchanged rankings. A more detailed examination of MALB's results indicate that both problem size and cycle time affect computational performance. Of the 448 balances not obtained, 308 are from 100-task and 140 are from 50-task problems. More striking, however, is the impact the cycle time increment has on heuristic performance. The most difficult problems for MALB, in terms of computation time, are those with cycle times in close proximity to the largest task time. A plot of balances not solved against cycle time increment looks surprisingly exponential, with 112 not solved when the cycle time equals the largest task time, 96 not solved for the first increment above the lowest cycle time, etc., decreasing to 14 not solved at twice the largest task time. In terms of solution quality, however, our results with MALB are generally consistent with Dar-El's (1975) findings that MALB yields better average results than ARCUS or a composite of the single-pass heuristics he tested. Predictably, the composite methods perform better than the single-pass heuristics in terms of average and worst case performance. Somewhat

-30 - surprising is that over all methods considered, COMPOSITE-13 has the second best worst case results, even though a number of other methods have better average results. Among the single-pass methods examined, two new heuristics, MINUB and MAXDUR/UB, slightly outperformed MAXDUR as the best of the group. The poorest average and worst case results come from the benchmark rule RANDOM, as one designing heuristics would hope. (This is not always the case, however. Davis and Patterson (1975) found for the resource-constrained project scheduling problem, that a random rule was often better than several apparently reasonable heuristics.) Although no attempt was made to number the tasks in a structured fashion during problem generation, solving the problems by assigning tasks in numerical order using MINTSKNO, our second benchmark rule, did produce slightly better solutions than when an explicit effort was made to randomly assign tasks with the RANDOM rule. This indicates the need to explicitly apply a random rule in this type of experiment, rather than rely on an 'arbitrary' surrogate. Not indicated in the tables and figures is that while certain rules produced superior results on average, or in terms of worst case results, no one procedure consistently dominated any other. All procedures, including RANDOM, are able to produce minimum, and often unique, solutions to certain problems, albeit is rare for some of them. In order to more systematically analyze the results for the Main Experimental Data Set, a randomized complete block, full factorial analysis of variance was performed.1 Assessed are the effects of the number of tasks (T), 1MALB was omitted from this analysis because of the overall size of the experiment and the consequent effect unequal cell sizes had on the analysis. The SAS statistical software system (PROC ANOVA) on an Amdahl 470/V8 computer was used to analyze these results.

-31 - network density (D), method of generating partial orders (G), number of increments above the lower bound cycle time [i.e., MAXi(ti)] (I), and heuristic solution technique (H) on line balancing performance. The response variable measured is the Percent Increase Over the Minimum Heuristic Result obtained. Those variables found to be significant in this analysis include (in order of significance): the heuristic solution technique (H) examined (r2 = 0.47), and 2 the number of increments (I) above the lower bound cycle time (r = 0.30). Variables found relatively insignificant in contributing to heuristic performmance include network density (r2 = 0.015), number of tasks in the line balancing problem (r = 0.0006), and the method used to generate random partial orders (r = 0.002). The only significant interaction effect identified is the interaction between the heuristic solution technique employed and the number of increments above the lower bound cycle time (H*I).l Thus, it appears as though heuristic performance is not contingent in a statistical sense upon these latter measures (T, D, G) of problem structure. In order to illustrate the (H*I) interaction, we include Figure 2, which is a three-dimensional histogram of the Percent Increase Above the Best Heuristic Solution for seven of the methods examined and for all eleven cycle times (C = maximum task time at Increment 1. At Increment 2, C = 110% of maximum task time, etc.). What is clear from this chart is that the average performance of each rule varies as a function of the cycle time, and in some cases by a considerable amount (by a factor of six for COMPOSITE-13). For each method, the distribution of Average Percent Above the Best Heuristic 1MAG-1 did generally (1) decline in performance when the number of tasks in an assembly network increased from fifty to one-hundred, and did generally (2) improve in performance over the other techniques examined when the density of a network increased (especially to 0.8). These results, however, were not found to be statistically significant.

-32 -FIGURE 2 AVERAGE PERCENT ABOVE MINIMUM _u.O CHa" BY ImAcmtm I i i I i I i I i i i i I I I i i i i i i I I I I I I I I 19oTo Result Obtained is low at Increment 1, then gradually rises, and then decreases (eventually to zero for all methods when C = Eti, although this latter situation is not specifically plotted in Figure 2). In an effort to better understand this relationship, the distributions of the average number of stations (instead of average percent) above best heuristic solution were also plotted to control for the fact that as C gets larger, the number of stations in a solution generally gets smaller. These distributions are very similar in appearance to those shown in Figure 2, revealing the same general types of information. In general, with both plots, one would expect there to be much less variability among the methods when the cycle time is equal to or is close to the maximum task time. This is because there are fewer opportunities to effect alternative task assignments. As the cycle time increases

-33 - beyond the maximum task time, however, there become more opportunities to effect different assignments as there are more combinations of tasks that can be feasibly assigned into each work station. This phenomenon continues until the cycle time approaches the work content of the product, in which case all methods will assign each of the tasks to the one work station required, giving zero variability in heuristic performance. One has to exercise a great deal of caution in interpreting Figure 2. It is tempting to conclude, for example, that the best performance overall is achieved by the heuristic decision rules when the cycle time is equal to the maximum task time. What is minimal when the cycle time is equal to the maximum task time is the variance in the performance of the procedures. There are simply fewer opportunities using these procedures to effect alternate balances at this cycle time. And, in fact, it is at the lower cycle times that the optimization approaches used in this evaluation (as heuristic procedures) have the greatest amount of difficulty in determining and verifying the optimality of the solutions obtained. Specifically, for only one balance out of 120 at the first increment was an optimal solution found and verified using the four approaches described, whereas 112 out of 120 optimal balances were found and verified when the cycle time was 200% (increment 11) of the maximum task time. The entire range of values for the eleven increments are (1, 6, 18, 25, 43, 68, 69, 87, 103, 103, 112). Hence, without additional verified optimal solutions at the lower cycle times, it is simply not possible to claim that all of the methods studied perform better in an absolute sense at the lower cycle time increments. Tukey's studentized range test (HSD) was used to compare the results obtained for the perorance measure Percent ncreasree Above Minimum Heuristic Result Obtained. An alpha value of 0.05 was used for reporting significant

-34 - differences. It is encouraging that using this procedure, the RANDOM rule which produced the highest mean value overall was placed into a group by itself, and the five variants of the HOFFMANN procedure which produced the lowest overall sample mean values were also grouped together. These results were identical when the performance measure became Percent Increase Over Optimal. Employment of Duncan's multiple range test and Scheffe's comparison procedure produced similar results on this group of test problems. 4.2 Literature Data Set As indicated in Tables 2 and 3, MAG-1 performed relatively best on the Literature Data Set by determining minimum balance solutions to all problems, and verified optimum solutions for 55 balances. The second best results were determined by MALB and COMPOSITE-13, for the measure Percent Increase Above Best Heuristic and Above Optimum, respectively. COMPOSITE-13, MALB, MAG-2, ALBCUT, and ALBHOFF each found 54 of the 55 verified optimum solutions. Although it is instructive to compare methods with a common set of test problems appearing in the open literature, some caution should be exercised in extrapolating percentage results from this data set. First, it is a very small sample. More important however, is the use of Percentage Increase Above Minimum Heuristic Results criterion. Over half of the balances obtained using this data have solutions consisting of less than ten stations (ranging from two stations up to 29), with only two balances containing more than 20 stations. With such small numbers in the denominator using this criterion, even a one station difference between methods often yields a large percentage increase. In contrast, this does not seem to be such a problem with the Main Experimental Data Set where solutions range from 13 to 90 stations, with over 90% distributed approximately uniformly in the 15 to 60 station range.

-35 - 4.3 "Difficult" Data Set One This data set was generated with low network density and high variability in task times to especially challenge the backtracking and optimal-seeking methods which have the best performance on the other two data sets. As can be seen from Tables 2 and 3, however, MAG-1 and the Hoffmann-based codes yield the best results on this data set, overall. 4.4 "Difficult" Data Set Two This 'pathological' data set with all even task times and odd cycle times was also created to tax backtracking and optimal-seeking methods, but specifically HIOFFMANN-O.O, which was expected to be unable to solve problems in this data set within the time limit specified. This expectation is based upon the notion that HOFFMANN-0.O uses exhaustive enumeration of task assignments unless a zero idle time solution is first found. As is shown in Tables 2 and 3, HOFFMANN-O.O was able to solve 69 of the 110 balances. However, along with MAG-1, the other Hoffmann-based procedures yield the five best average results reported. 4.5 Computer Time and Computer Storage Requirements Table 4 indicates the actual computer time and storage used by the 24 methods. The times quoted are the average seconds of CPU time required by each method to solve, or attempt to solve, all balances in each data set. For each balance, the minimum of the actual CPU time and 3.0 seconds is used. These values are summed over all balances in the data set and divided by the number of balances in the data set to obtain the times appearing in Table 4. The storage values are given in kilobytes of primary storage required. Although the values in Table 4 are accurate measurements, one should interpret them cautiously in evaluating the relative efficacy of each solution

I -36 -TABLE 4 Computat Ion Time and Amotint of Compiuter Storage Rc(ltilred to Solve I,nte Bal.ancing Problems Average CPU Time to Solve Each Balance in Each Data Seta Primary Solution Storage Procedure Main Requit redb Experimental Literature Difficult Difficult Data Set Data Set Data Set One Data Set Two 1,320 Balances 64 Balances 110 Balances 110 Balances Each SinglePass Decision 0.004 0.002 0.005 0.005 8 Rulec COMPOSITE-13 1.37 0.57 1.52 1.52 91 ARCUS 0.49 0.05 2.14 2.19 63 HOFFMANN-0.0 0.17. 0.53 1.48 8.36e 251 HOFFMANN-0.5 0.18 0.35 0.28 0.29 251 HOFFMANN-1.0 0.18 0.29 0.22 0.24 251 HOFFMANN-2.0 0.18.0.29 0.19 0.20 251 MALB 1.85 0.07 1.57 1.60 175 MAG-I 1.48 -.03 1.15 1.18 1,711 MA(G-2 1.87 0.03 1.64 1.82,711 ALBCUT 2.76 0.52 2.40 2.52 248 ALBIOFFd 1.67 0.91 1.76 1.91 172 aAMDAIIL 470/V8 CPU time, in seconds with a 3.0 second time limit per balance. FORTRAN-H Compiler used, with OPT=2. bin kilobytes. COne computer program was used to find individual single-pass results and COMPOSITE-13 results., The storage value is an estimate, however, of what would be required to code any one singlepass decision rule. dHalf-word integers are used in the HOFFMANN-0.5 subroutine in ALBHOFF. This has the effect of increasing the computation time and decreasing the storage over the standard HOFFMANN-0.5 procedure. eThe location of the internal timer in this code permitted some balances for which no solution was found to be attempted for more than 3.0 seconds in this data set. procedure. First of all, through clever programming one could reduce both storage and time requirements for any of the methods examined. Second, the methods vary in the predictability of their use of time and storage, which affects the potential expense and ease of their use. For example, it is not possible to specify precisely, and in advance, the amount of computer storage that will be required to solve a given problem with the MAG-i and MAG-2 branch and bound procedures. (This is a generic problem with branch and bound codes, and has been observed elsewhere (Patterson, 1984).) Thus, the array dimensions, and hence storage values, had to be determined by trial and error (repetitively increasing dimensions until overflows disappeared). The two codes dropped from the study, DYNAMIC and MUST also have this drawback, although MUST has been programmed to directly use external storage, which

-37 - reduces the need to a priori specify storage precisely. None of the other 22 procedures evaluated have this drawback relative to storage needs. However, all methods other than the single-pass and composite methods (and the optimum codes with time traps) have difficult-to-predict time requirements for an arbitrary balance. Within a given data set, it is fairly safe to compare the relative computation times of the methods. Across sets it is more risky, although in terms of number of tasks in each balance, the Main Experimental Data Set, and the "Difficult" Sets One and Two, are comparable. In creating the latter two data sets, it was expected that some of the methods, specifically the backtracking methods, would perform worse in terms of computation time. This is certainly true of HOFFMANN-0.0 on "Difficult" Data Set Two. In "Difficult" Data Set One, HOFFMANN-O.O is about nine times slower than it is in the Main Experimental Data Set. However, relative to all other methods on "Difficult" Data Set Two, its time performance was average. The only other method that exhibits substantially increased time per balance is ARCUS. 5.0 A Comparison of These Results with Previous Investigations There have been two previous major investigations of heuristics for solving the Type II line balancing problem [Mastor (1970) and Dar-El (1975)], but none, until the current investigation, for the Type I problem. Hence, it is difficult to make direct comparisons among these three evaluations. However, as indicated earlier, most methods for solving the Type II problem are in reality methods for solving the Type I problem that are repetitively applied to the same network with an increasing cycle time. This is certainly true for all of the methods included in our evaluation. Hence, we feel that the procedures examined will give the same relative performance for the Type II problem as they have for the Type I problem. In fact, by solving each

-38 - network using 11 increments of cycle time, we have in one sense mimicked the process needed to solve a Type II problem. The major methods included in both our evaluation and Mastor's (with Mastor's terminology given in parentheses) are MINTSKNO (Lexicographical), MAXRPW (Helgeson), MAXIFOL (Immediate Follower), RANDOM (Random), HOFFMANN-0.0 (Hoffmann), and ARCUS (Arcus). Mastor also included a version of the Held, et. al. (1963), dynamic programming procedure. In general, the poorest results obtained by Mastor were for the Lexicographical rule, followed by the singlepass decision rules. The best performance was obtained by Held et. al., followed by Arcus and Hoffmann, although the Held et. al. and Hoffmann methods were tested over a subset of his data because both methods required excessive computation times. Dar-El included MALB, ARCUS, and the best of ten singlepass heuristics (10-SP) in his comparative evaluation. The ten single-pass methods are combinations of four procedures included in our investigation, MAXRPW, MAXTFOL, MAXDUR, and MAXIFOL. Dar-El excluded Hoffmann and Held et. al. from his investigation on the basis of Mastor's observation that these methods exhibit high computation times. Overall, Dar-El found that MALB consistently gave superior results to ARCUS, and that generally, ARCUS outperformed 10-SP. All three investigations (Mastor's, Dar-El's and ours) are consistent in finding that the more complicated procedures give better solutions than the single-pass methods. Our results comparing MALB and ARCUS are not quite as conclusive as are Dar-El's. However, they are generally in agreement. More noteworthy are the differences among the results, the most important of which is the difference in the performance of HOFFMANN-O.O in our study and the Hoffmann in Mastor's investigation. In FORTRAN, many decimal fractions are imprecisely represented in the computer. When these numbers are arithmetically

-39 - manipulated (e.g., normalized) and compared, this imprecision can give logically erroneous results. Specifically, by treating task times and cycle times as decimal fractions, the test in Mastor's version of the Hoffmann procedure to determine if a station's idle time is equal to zero is very rarely met thus forcing complete enumeration at each work station using this approach. This is in fact the situation we have artificially created in "Difficult" Data Set Two with all even task times and all odd cycle times. If one feels that these types of problems are likely to occur in balancing an industrial assembly line, then he or she should probably use one of the modified versions of the Hoffmann procedure (we prefer HOFFMANN-O.5). It has been our experience, however, that these instances arise rarely in practice, and one has to go to the extreme of normalizing the task times or else constructing a data set such as given in our "Difficult" Data Set Two in order to observe the HOFFMANN-O.O procedure experiencing difficulty in deriving a satisfactory solution to a line balancing problem. The less significant differences in the individual performance of singlepass decision rules among these three investigations may be explained by the lack of explicit (or at least stated) tie-breaking rules used by Mastor and Dar-El. We have observed that the effect of the tie-breaker rule can become quite significant, and that the tie-breaker's performance is highly dependent upon the main scheduling heuristic used. This is largely because of the heuristic discretion the tie-breaker is or is not able to exercise, a concept addressed previously for the project scheduling problem (Patterson, 1976). For example, when MINTSLK is the main scheduling rule employed, there are usually numerous opportunities for the tie-breaker to exercise its influence (discretion) because several tasks available for scheduling at a given station will possess equal amounts of slack. In this instance, the tie-breaker rule

-40 - becomes the dominating heuristic because of the inability of the main heuristic to discriminate among the competing tasks for assignment to a work station. The use of a heuristic such as RANDOM, on the other hand, produces relatively fewer opportunities to break ties since it is unlikely the random numbers assigned for task priority will be equal. To illustrate this point, in Figure 3 we give the Average Percent Increase Above the Minimum Heuristic Result Obtained using the single-pass scheduling heuristics of MAXDUR, MAXIFOL, and MAXUB with the other single-pass decision rules serving as tie-breakers for the literature problems data set. Apparent in this figure is that the performance of MAXDUR varies little regardless of the tie-breaker used because it leaves little discretion to the tie-breaker. However, the performance of MAXIFOL and MAXUB are strongly influenced by the tie-breaker employed because of the large number of ties these rules produce. Figure 3 also illustrates that a tie-breaker's effectiveness is a function of the main rule it is paired with. Two rules, MAXAVGRPW and MAXTFOL/SL, have been highlighted in Figure 3 to illustrate this point. If one were to evaluate these tie-breakers using a main scheduling heuristic such as MAXDUR, then one might conclude that MAXAVGRPW isn't a very effective tie-breaker. However, when paired with MAXIFOL and MAXUB, this tie-breaker actually delivers the best results. Differences in reported results previously may have been due simply to the manner in which ties are broken, or in the order in which tasks are labeled numerically as data input. 6.0 Conclusions and Recommendations Twenty-six heuristic decision rules are evaluated in this paper, which are designed to assign tasks into work stations such that given a cycle time, or production rate, the number of stations is minimized. The procedures vary from simple list processing prioritizing schemes, which --------- ----— "-" --- -'"l"'~"`"crr'~-~"~^~"~1" —1-1 1- ~lc~"-`"-` -- — — 14

-41 - FIC(IRK 3 AVERAGE PERCENT INCREASE ABOVE MINIMUM SOLUTION LI -r TPE A T JFE FF=ROBL E M S F E FI C E N -T PE RCENT B 7 3 a - 0 - MM M M MM MMMM P- i M AAAA4TAAAA II XXXX XNNXXXNNN oRT T TUUDAO IL.TT U PFFF BE3OV JF= SS FnlOO /MFFtO KtL. / Lt- T Fq L NsK u / F= F 0 B SO 0 L. L --- MAXDUB --— t TIE BnEAKEnE MM M MM RM M MMMM MM AAAAIAAIZAIAI XXXXNNXN NX NXN ADDRUD T TUTT I L VUUPFBOF'SBeFSF'B GQFRRW MOL/OKO nF / L-KTL-NLL FP U / F= 0 W B S O L- LMA X F=A ol 1 --- — NJ,A X A V G F:R F:: W ~_t —lI MAXDJUR/US c r iw MAX PI vW NW9vm M AX F'FOL/S/ _L --- --- MINTSKNO W_ -J: I N UI __ n A 1N1 C) OM MMMMRM MMMMMM AAAAAAXAAIIXX XXXXrNXNXXNrqNMN ADDFOoDTUJT I -UT- r VtUUPF' OFBFF BBSS Q( RRWMOO 00 KIL MFETI FR L TLAL I4K FP U F/ O W B OS L. t --- M UB - eu 1 -rn MAXIFOL. 1 --- —--- MAXT — OLr- ~- MAXTFLOL I M I M IXLB - z —I* MINTSL.K _C__~_ MTIIUB/TE'OL_ -10D R ST I consider a single attribute of each work task, to optimal-seeking procedures which have had the amount of time permitted for search limited. These methods are tested on four data sets, one large set consisting of 1,320 balances, one set of problems found in the open literature, and two specially constructed sets of problems. A randomized complete block, full factorial analysis of variance was performed to assess the effects of number of tasks, network density, method of generating precedence relationships, and cycle time on heuristic performance. The results indicate that heuristic performance is not significantly affected by network structure, but that performance does vary with the magnitude of the cycle time.

-42 - In general, our evaluation demonstrates that methods exist which will give optimal or near-optimal solutions to large line balancing problems with very little computational effort. Of the pure heuristic methods, variants of Hoffmann's Precedence Matrix approach (1963), followed by Dar-El's MALB (1973), appear to be among the best procedures. Of the optimal-seeking methods, Magazine and Wee's branch and bound procedure (1981b) using the heuristic IUFFD (MAXDUR), and Talbot and Patterson's implicit enumeration procedure (1984) initialized with the Hoffmann procedure yield the best overall results. On the basis of our analysis and experience in using the computer implementations of each of these procedures, we make the following general recommendations. If one is constrained in terms of computer storage and computational speed (for example as with a personal computer), then solving the problem with HOFFMANN-0.5 first, and then improving upon it with an alwaysfeasible optimal-seeking approach such as ALBHOFF (with or without the additional cutting based rules) and using a time trap, would seem to return the best results for the effort expended. If computer storage is not a limiting factor, then MAG-1 (used with a time trap) is likely to give among the best results. To reduce the risk of not determining a good solution, multiple methods should be attempted. This is especially true for balances with cycle times close to the largest task time, which appear to be the most difficult for which to find and verify an optimal solution for a problem.

ACKNOWLEDGEMENTS The authors wish to extend their appreciation to the following individuals who assisted in the effort required to complete this evaluation: Professor Michael Magazine and Dr. Thomas Wee provided us with copies of their branch and bound computer program, their version of MALB, and their version of Schrage and Baker's dynamic programming procedure. They additionally responded to a number of questions we had about the operation of these algorithms. Professor Ezey Dar-El provided us with a copy of MUST. Ms. Kay Miller and Mr. Ronald Howren of the University of Missouri-Columbia provided much help in coding, running programs, and preparing final results for analysis. Finally, the anonymous referees gave us a number of constructive comments on earlier drafts of this paper.

.1 REFERENCES [1] Arcus, A. L. "An Analysis of a Computer Method of Sequencing Assembly Line Operations." Ph.D. dissertation, University of California, Berkeley, 1963. [2]. "COMSOAL: A Computer Method of Sequencing Operations for Assembly Lines." In Readings in Production and Operations Management, edited by E. S. Buffa. New York: John Wiley and Sons, 1966. [3] Bowman, E. H. "Assembly-Line Balancing by Linear Programming." Operations Research 8 (May-June 1960), 385-389. [4] Dar-El, E. M. (Mansoor). "Assembly Line Balancing —An Improvement on the Ranked Positional Weight Technique." Journal of Industrial Engineering 15, 2 (March-April 1964), 73-77. [5]. "MALB —A Heuristic Technique for Balancing Large Single-Model Assembly Lines." AIIE Transactions 5, 4 (December 1973), 343-56. [6]. "Solving Large Single-Model Assembly Line Balancing Problems —A Comparative Study." AIIE Transactions 7, 3 (September 1975), 302-310. [7], and Rubinovitch, Y. "MUST —A Multiple Solutions Technique for Balancing Single Model Assembly Lines." Management Science 25, 11 (November 1979), 1105-1115. [8] Davis, E. W. and James H. Patterson. "Resource-Based Project Scheduling: Which Rules Perform Best?" Project Management Quarterly, 6, 4 (December 1975), 25-31. [9] Fishburn, P. C., and Gehrlein, W. V. "Alternate Methods of Constructing Strict Weak Orders from Interval Orders." Psychometrika 39, 12 (1974), 501-16. ~. --- -— ~- -- -` —~^"lll-"~CI —~111 —1~ --- —---- XT -I-CI11 --- —---— ~ I

[10] Gehrlein, William V. "Generating Random Partial Ordering Relations." Proceedings, Northeast American Institute for Decision Sciences, Philadelphia, PA (April 1980), 119-22. [11], and James H. Patterson. "Balancing Single Model Assembly Lines: Comments on a Paper by E. M. Dar-El (Mansoor)," AIIE Transactions 10, 1 (March 1978), 109-12. [12]. "Sequencing for Assembly Lines with Integer Task Times." Management Science 21, 9 (May 1975), 1064-70. [13] Held, M., R. M. Karp, and R. Sharesian. "Assembly-Line Balancing — Dynamic Programming with Precedence Constraints." Operations Research 11, 3 (May-June 1963), 442-60. [14] Helgeson, W. P., and D. P. Birnie. "Assembly Line Balancing Using the Ranked Positional Weight Technique." Journal of Industrial Engineering 12, 6 (November-December 1961), 394-98. [15] Heskia, Heskiaoff. "An Heuristic Method for Balancing Assembly Lines." Western Electric Engineer 12, 3 (October 1968), 9-16. [16] Hoffmann, Thomas R. "Assembly Line Balancing with a Precedence Matrix." Management Science 9, 4 (July 1963), 551-62. [17] Jackson, J. R. "A Computing Procedure for a Line Balancing Problem." Management Science 2, 3 (April 1956), 261-72. [18] Jaeschke, G. "Eineallgemaine Methods Zur Losung Kombinatorisher Probleme." Ablaufund planungforschung 5 (1964), 133-53. [19] Kilbridge, M. D., and L. Wester. "A Heuristic Method of Assembly Line Balancing." Journal of Industrial Engineering 12, 4 (July-August 1961), 292-98.

[20] Magazine, M. S., and T. S. Wee. "Fast Algorithms for the Assembly Line Balancing Problem." Working Paper 149, University of Waterloo, Department of Management Science (June 1981a). [21] and. "An Efficient Branch and Bound Algorithm for an Assembly Line Balancing Problem —Part I: Minimize the Number of Work Stations." Working Paper 150, University of Waterloo, Department of Management Science (June 1981b). [22] and. "An Efficient Branch and Bound Algorithm for an Assembly Line Balancing Problem —Part 11: Maximize the Production Rate." Working Paper 151, University of Waterloo, Department of Management Science (June 1981c). [23] Mastor, Anthony A. "An Experimental Investigation and Comparative Evaluation of Production Line Balancing Techniques." Ph.D. dissertation, University of California, Los Angeles, 1966. [24]. "An Experimental Investigation and Comparative Evaluation of Production Line Balancing Techniques." Management Science 16, 22 (July 1970), 728-45. [25] Merten, P. "Assembly Line Balancing by Partial Enumeration." Ablaufund Planungforschung 8 (1967), 429-33. [26] Moodie, C. L., and H. H. Young. "A Heuristic Method of Assembly Line Balancing for Assumptions of Constant or Variable Work Element Tirmes." Journal of Industrial Engineering 16, 1 (January-February 1965). [27] Patterson, James H. "Project Scheduling: The Effects of Problem Structure on Heuristic Performance." Naval Research Logistics Quarterly 23, 1 (March 1976), 95-123.

[28]. "A Comparison of Exact Approaches for Solving the Multiple Constrained Resource, Project Scheduling Problem." Management Science 30, 7 (July 1984), 854-67. [29] Sawyer, J. F. H. Line Balancing. Washington, D.C., Machinery and Allied Products Institute, 1970. [30] Schrage, L., and K. R. Baker. "Dynamic Programming Solution of Sequencing Problems with Precedence Constraints." Operations Research 26 (May-June 1978), 444-49. [31] Talbot, F. Brian, and James H. Patterson. "An Integer Programming Algorithm with Network Cuts for Solving the Assembly Line Balancing Problem." Management Science 30, 1 (January 1984), 85-99. [32],, and William V. Gehrlein. "A Comparative Evaluation of Heuristic Line Balancing Techniques." Working Paper No. 415 (Revised), The University of Michigan Graduate School of Business, Ann Arbor, Michigan, 1985. [33] Tonge, F. M. A Heuristic Program of Assembly Line Balancing, Englewood Cliffs, NJ: Prentice-Hall, 1961. [34]. "Summary of a Heuristic Line Balancing Procedure." Management Science 7, 1 (October 1969), 21-42.

Appendix Listing of Literature Data Set Note: The format of the problems listed is as follows: 1. Problem title, number of tasks (N), cycle times. 2 - N+1. TaSk time, immediate successor tasks. One blank record separates consecutive problems. -— ~I -1--"-"-^ -'~- —* - L11111 —

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 MERTEN'S 7-ELEMENT 1 2 4 5 3 5 4 3 7 5 6 6 5 7 6 7 8 10 15 18 BOWMAN'S PROBLEM 9 11 2 17 3 4 9 56 5 6 8 7 12 8 10 9 3 9 0 JAESCHKE'S 9-ELEMENT 9 5 2 3 3 4 4 4 5 5 6 7 4 8 5 9 1 9 4 9 6 JACKSON'S 11-ELEMENT 11 6 2 3 4 5 2 6 5 7 7 7 1 7 2 8 3 9 6 10 5 11 5 11 4 20 6 7 8 10 18 7 9 10 13 14 21 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 1 1 1 112 113 114 115 116 4 2 3 3 21 9 4 5 5 21 9 6 7 4 8 8 8 14 7 9 5 10 11 12 13 1 15 3 15 1 15 5 17 18 3 19 5 16 18 3 17 13 20 5 19 2 3 7 HESKIAOFF'S 28-ELEM. 28 138 205 216 256 324 342 70 3 4 5 21 22 23 8 19 24 26 59 6 17 33 28 6 28 1 28 27 7 17 18 62 9 31 10 53 11 12 21 15 19 13 108 14 16 52 28 5 28 8 28 97 28 8 28 47 20 67 28 17 28 8 28 3 28 21 25 107 28 3 27 2 28 72 DAR-EL'S PROBLEM 4 4 38 4 5 45 11 12 6 10 7 8 8 12 9 10 10 2 10 10 11 34 11 48 62 94 SAWYER'S 8 4 7 11 19 16 10 7 2 6 30-ELEMENT 5 12 17 30 25 27 30 36 41 54 75 MITCHELL'S 21-ELEMEN 21 14 15 21 26 35 39

117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 6 7 14 8 10 9 1 26 4 24 14 15 13 5 14 12 15 20 9 22 10 20 2 18 10 19 18 16 21 24 21 22 14 23 16 27 7 25 17 26 9 27 25 28 29 7 14 30 2 KILBRIDGE & WE' 9 3 7 0 9 4 8 0 10 5 0 10 6 0 17 9 0 17 10 0 13 9 14 0 13 10 14 0 20 41 0 20 41 0 10 13 0 11 13 37 0 6 14 15 0 22 29 30 31 11 16 18 23 19 19 0 12 26 27 0 3 19 0 7 20 33 0 4 21 00 55 22 00 14 28 00 27 33 0 29 33 0 26 26 0 6 38 0 5 28 33 0 24 38. 0 4 41 0 5 41 0 7 41 0 STER 45 57 79 92 110 138 184 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 TONGE'S 70-ELEMENT 17 2 41 69 70 66 3 54 4 68 52 6 7 6 6 24 30 88 8 21 8 128 12 68 10 70 11 85 12 21 13 14 134 23 135 23 94 16 90 17 18 50 19 143 19 19 20 22 57 54 21 50 23 40 23 73 25 31 33 12 25 152 26 27 28 29 42 35 45 35 74 35 26 35 11 31 31 32 50 35 102 34 46 35 35 36 51 48 44 5 40 37 2 38 1 39 3 40 13 42 16 42 25 43 70 176 364 410 468 527 4 41 0 15 34 35 36 3 38 0 7 40 0 9 38 0 4 43 0 7 40 0 5 41 0 4 41 0 21 42 0 12 44 45 0 6 0 5 0 5 0 0 32 25 17 0 24 0 53 56 60 62 61

233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 21 50 43 45 30 46 83 47 89 50 56 49 59 50 43 1 52 26 54 44 54 121 55 38 68 22 58 7 59 16 60 32 25 65 27 63 156 64 28 65 66 67 15 26 18 72 23 27 ARCUS 1673 985 1836 973 1700 2881 2231 1040 1793 1250 700 464 500 1133 577 483 880 667 600 233 408 847 767 850 780 912 748 1863 83-ELEMENT 2 3 4 5 6 6 7 8 9 10 11 77 78 12 13 14 25 15 16 17 18 20 19 20 39 77 78 21 22 28 23 24 26 27 27 74 28 29 32 74 69 32 83 5048 5853 6842 7571 8412 889810816 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 714 30 1004 31 713 39 642 33 34 35 36 629 37 1234 77 78 1143 77 78 1266 38 39 792 40 1251 41 1310 42 43 44 75 663 77 78 494 45 1288 77 78 792 77 78 578 46 594 47 578 48 622 49 578 50 564 69 578 51 578 52 578 53 578 54 578 55 578 56 578 57 578 58 578 59 578 60 578 61 578 62 578 63 578 64 578 65 578 66 578 67 578 68 578 74 75 467 70 71 887 72 396 73 1296 73 1100 74 75 2543 76 764 76 357 77 78 701 79 1164 79 286 80 81 2100 82 450 83 1300 83 3691 ARCUS' 111-ELEMENT 1960 2 111 5755 884710027107431137817067

349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 1715 3 735 4 1715 5 6 7 8 490 39 1225 39 169 83 2252 71 1225 32 2319 11 12 1715 13 14 15 16 980 13 14 15 16 735 71 2281 22 23 24 25 2750 26 77 27 89 28 51 29 364 30 405 91 3060111 125 31 83 3429 32 33 43 69 70 3430 34 1960 82 29 35 27 36 15 37 121 38 1715 39 2127 41 1470111 4037 42 68 43 62 44 91 42 45 91 364 46 91 4998 40 1470111 2963 69 70 5689 47 68 48 49 91 18 50 10 51 81 52 5200 54 55 56 57 39 53 67 91 27111 1511.1 121111 58111 1715 69 70 125 61 62 63 4010 63 64 1470 65 91 1470 66 91 2303 67 91 9 10 17 18 19 20 21 17 18 19 20 21 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 1960 68 91 2205 69 70 4018 71 2744111 2999 72 735111 735111 735111 735111 545 77 78 3386 73 3234 91 2205 74 91 2206 75 490 76 825 77 78 91 79 3528 80 81 82 3568 83 1200 84 618 85 1470 86 91 1715 87 91 735111 1960 91 2889 88 89 91 618111 490111 735 90 490105 921105 326111 5390 92 93 94 243 95 371 95 58 95 5059 96 97 98 99100104 1225101 769102 768103 1670111 1670111 490105 202106107 203107108 202111 2744111 162109 324111 162110 121111 162111 91 58 59 60