THE FIRST PROJECT

ALHAMDULILLAH IT IS PROJECT ENGINEERING IN BEKASI WEST JAVA 22-24 JANUARI 2009



Line Balancing in the Real World Emanuel Falkenauer Optimal Design Av. Jeanne 19A boîte 2, B-1050 Brussels, Belgium+32 (0)2 646 10 74 E.Falkenauer@optimaldesign.comAbstract: Line Balancing (LB) is a classic, well-researched OperationsResearch (OR) optimization problem of significant industrial importance. It is one of those problems where domain expertise does not help very much: whatever the number of years spent solving it, one is each time facing an intractable problem with an astronomic number of possible solutions and no real guidance on how to solve it in the best way, unless one postulates that the old way is the best way. Here we explain an apparent paradox: although manyalgorithms have been proposed in the past, and despite the problem’s practical importance, just one commercially available LB software currently appears to be available for application in industries such as automotive. We speculate that this may be due to a misalignment between the academic LB problemaddressed by OR, and the actual problem faced by the industry.Keyword: Line Balancing, Assembly lines, Optimization 1 Introduction Assembly Line Balancing, or simply Line Balancing (LB), is the problem of assigning operations to workstations along an assembly line, in such a way that the assignment be optimal in some sense. Ever since Henry Ford’s introduction of assembly lines, LB has been an optimization problem of significant industrial importance: the efficiencydifference between an optimal and a sub-optimal assignment can yield economies (or waste) reaching millions of dollars per year. LB is a classic Operations Research (OR) optimization problem, having been tackled by OR over several decades. Many algorithms have been proposed for the problem. Yet despite the practical importance of the problem, and the OR efforts that have been made to tackle it, little commercially available software is available to help industry in optimizing their lines. In fact, according to a recent survey by Becker and Scholl (2004), there appear to be currently just two commercially available packages featuring both a state of the art optimization algorithm and a user-friendly interface for data management. Furthermore, one of those packages appears to handle only the “clean” formulation of the problem (Simple Assembly Line Balancing Problem, or SALBP), which leaves only one package available for industries such as automotive. This situation appears to be paradoxical, or at least unexpected: given the huge economies LB can generate, one would expect several software packages vying to grab a part of those economies. It appears that the gap between the available OR results and their dissemination intoday’s industry, is probably due to a misalignment between the academic LB problemCopyright © 200x Inderscience Enterprises Ltd.
--------------------------------------------------------------------------------
Page 2
Emanuel Falkenauer addressed by most of the OR approaches, and the actual problem being faced by the industry. LB is a difficult optimization problem (even its simplest forms are NP-hard – see Garey and Johnson, 1979), so the approach taken by OR has typically been tosimplify it, in order to bring it to a level of complexity amenable to OR tools. While this is a perfectly valid approach in general, in the particular case of LB it led to somedefinitions of the problem that ignore many aspects of the real-world problem. Unfortunately, many of the aspects that have been left out in the OR approach are in fact crucial to industries such as automotive, in the sense that any solution ignoring (violating) those aspects becomes unusable in the industry.In the sequel, we first briefly recall classic OR definitions of LB, and then review how the actual line balancing problem faced by the industry differs from them, and why a solution to the classic OR problem may be unusable in some industries. 2 OR Definitions of LB The classic OR definition of the line balancing problem, dubbed SALBP (Simple Assembly Line Balancing Problem) by Becker and Scholl (2004), goes as follows. Given a set of tasks of various durations, a set of precedence constraints among the tasks, and a set of workstations, assign each task to exactly one workstation in such a way that no precedence constraint is violated and the assignment is optimal. The optimality criterion gives rise to two variants of the problem: either a cycle time is given that cannot be exceeded by the sum of durations of all tasks assigned to any workstation and the number of workstations is to be minimized, or the number of workstations is fixed and the line cycle time, equal to the largest sum of durations of task assigned to a workstation, is to beminimized.Although the SALBP only takes into account two constraints (either the precedence constraints plus the cycle time, or the precedence constraints plus the number of workstations), it is by far the variant of line balancing that has been the most researched. We have contributed to that effort in Falkenauer and Delchambre (1992), where we proposed a Grouping Genetic Algorithm approach that achieved some of the bestperformance in the field. The Grouping Genetic Algorithm technique itself was presented in detail in Falkenauer (1998). However well researched, the SALBP is hardly applicable in industry, as we will see shortly. The fact has not escaped the attention of the OR researches, and Becker and Scholl (2004) define many extensions to SALBP, yielding a common denomination GALBP (Generalized Assembly Line Balancing Problem). Each of the extensions reported in their authoritative survey aims to handle an additional difficulty present inreal-world line balancing. We have tackled one of those aspects in Falkenauer (1997), also by applying the Grouping Genetic Algorithm.The major problem with most of the approaches reported by Becker and Scholl(2004) is that they generalize the simple SALBP in just one or two directions. The real-world line balancing, as faced in particular by the automotive industry, requires tackling many of those generalizations simultaneously.
--------------------------------------------------------------------------------
Page 3
Line Balancing in the Real World 3 What Differs in the Real World? Although even the simple SALBP is NP-hard, it is far from capturing the true complexityof the problem in its real-world incarnations. On the other hand, small instances of the problem, even though they are difficult to solve to optimality, are a tricky target for line balancing software, because small instances of the problem can be solved close tooptimality by hand. That is however not the case in the automotive and related industries (bus, truck, aircraft, heavy machinery, etc.), since those industries routinely feature assembly lines with dozens or hundreds of workstations, and hundreds or thousands of operations. Those industries are therefore the prime targets for line balancing software. Unfortunately, those same industries also need to take into account many of the GALBP extensions at the same time, which may explain why, despite the impressive ORwork done on line balancing, only one commercially available software seems to be currently available for those industries. We identify below some of the additional difficulties (with respect to SALBP) that must be tackled in a line balancing tool, in order to be applicable in those industries. 3.1 Do Not Balance But Re-balance Many of the OR approaches implicitly assume that the problem to be solved involves a new, yet-to-be-built assembly line, possibly housed in a new, yet-to-be-built factory. To our opinion, this is the gravest oversimplification of the classic OR approach, for inpractice, this is hardly ever the case. The vast majority of real-world line balancing tasks involve existing lines, housed in existing factories – in fact, the target line typically needs to be rebalanced rather than balanced, the need arising from changes in the product or the mix of models being assembled in the line, the assembly technology, the available workforce, or the production targets. This has some far-reaching implications, outlined below. 3.2 Workstations Have Identities As pointed out above, the vast majority of real-world line balancing tasks involve existing lines housed in existing factories. In practice, this seemingly “uninteresting” observation has one far-reaching consequence, namely that each workstation in the line does have its own identity. This identity is not due to any “incapacity of abstraction” onpart of the process engineers, but rather to the fact that the workstations are indeed not identical: each has its own space constraints (e.g. a workstation below a low ceiling cannot elevate the car above the operators’ heads), its own heavy equipment that cannotbe moved spare huge costs, its own capacity of certain supplies (e.g. compressed air), itsown restrictions on the operations that can be carried out there (e.g. do not place welding operations just beside the painting shop), etc. 3.3 Unmovable Operations and Zoning Constraints The need to identify workstations by their position along the line (rather than solely bythe set of operations that would be carried out there) is illustrated by the typical need ofline managers to define unmovable operations and zoning constraints. An operation is
--------------------------------------------------------------------------------
Page 4
Emanuel Falkenauer marked as unmovable if it must be assigned to a given workstation. This is usually due tosome kind of heavy equipment that would be too expensive to move elsewhere in the shop. Zoning constraints are a generalization of unmovable operations: they express the fact that an operation can only be assigned to a given (not necessarily contiguous) subsetof the workstations in the line. A typical example are operations that require the vehicle to be elevated above the operators: such operations can only be assigned to workstations with enough space to contain the elevated vehicle. Zoning constraints are typical in the automotive industry – any algorithm to be applied there must support them. 3.4 Cannot Eliminate Workstations Since workstations do have their identity (as observed above), it becomes obvious that a real-world LB tool cannot aim at eliminating workstations. Indeed, unless the eliminated workstations were all in the front of the line or its tail, their elimination would create gaping holes in the line, by virtue of the other workstations’ retaining of their identities, including their geographical positions in the workshop. Also, it is often the case thatmany workstations that could possibly be eliminated by the algorithm are in factnecessary because of zoning constraints. 3.5 Need to Equalize Loads Since eliminating workstations cannot be the aim of the optimization of the line, as pointed out above, it is the equalization or smoothing (indeed “balancing”) of the workload among workstations that should be the practical aim of LB. It is worth noting that the classic objective of minimization of the cycle time, i.e. minimization of the maximum lead time over all workstations, is not necessarily the sameobjective as load equalization. The aim of the latter usually translates into minimizationof the squared differences between workstation loads, which means that a small increase in the maximum lead time may yield a substantial reduction in load disbalance, i.e. a better equalization of workload. The important practical point to be made here, is that the line’s cycle time is almost always given by the company’s marketing that sets production targets. The maximumcycle time set by marketing cannot of course be exceeded by the line (otherwise the production target would not be met), but it is typically useless to reduce the line’s cycle time below that value. In this context then, minimizing the cycle time is only required as long as it exceeds the target – once that objective is met, equalization of the workload should be pursued instead. 3.6 Multiple Operators In many industries, in particular automotive, the product being assembled is sufficientlyvoluminous to allow several operators to work on the product at the same time. Since thatpossibility does exist, not exploiting it would lead to unnecessarily long assembly lead times, implying a reduced productivity. It is therefore often the case that several operators are active on the product simultaneously. Once a workstation features more than one operator, the workstation’s lead time ceases to be a simple sum of durations of all operations assigned to it. First of all, the workstation as a whole will need the time equal to the lead time of its “slowest” operator
--------------------------------------------------------------------------------
Page 5
Line Balancing in the Real World to complete all operations assigned to the workstation. Needless to say, since operationsare indivisible chunks of work, this is certainly not equal to the sum of durations divided by the number of operators. More importantly though, the precedence constraints that nearly always exist among the operations assigned to a workstation, may introduce gaps of idle (waiting) time between operations, whenever an operator needs to wait for another one to finish a task. These gaps significantly reduce the efficiency of the workstation and must obviously be reduced as much as possible. This transforms the initially trivial computation of a workstation’s lead-time (i.e., a simple sum of operation durations) into a full-fledged scheduling problem. The problem is further significantly more complicated in presence of multi-operator operations and/or ergonomic constraints, as described below. 3.7 Multi-operator Operations Assembly of large products such as cars sometimes requires the collaboration of severaloperators to carry out an operation. A typical example of such multi-operator operation is the mounting of bumper on a car: the part is typically large and heavy and requires two operators, one at each end of the bumper (i.e. on the left and on the right of the car), to mount it.It would be conceivable to have a second operator assigned to that bumper operation alone, but that would be obviously very inefficient, because for all other operations the operator would be idle. It is therefore desirable to make that operator carry out other operations as well. That, however, significantly complicates the scheduling of operations within the workstation: all the operators in the workstation must be kept as busy as possible, must execute the operations in compliance with the precedence constraints, andmust be made available at the same time to carry out multi-operator operations. 3.8 Ergonomic Constraints (Operator Positions) 3.8.1 Workstation level A major difficulty in assembly of large products is that they are too bulky to be moved (elevated, rotated) easily. They are therefore kept in a given position during the whole stay in the workstation, i.e. for all the operations the workstation has been assigned. On the other hand, the large size of the products makes it impossible to carry outcertain operations unless the product is positioned in a certain way. For instance, in order to mount the exhaust system on a car, the car must be elevated - otherwise the operator would have to crawl under the car, making the operation extremely inefficient and tiring. Also, there are situations where the access to the product is limited. For example, a workstation can perform operations taking place on the left or the right of the car, but notboth. In other situations, the working position is imposed from the outset. For instance, when the conveyor is close to a wall on the right side in a workstation, the workstation can only be assigned operations that take place on the left side of the car. These considerations give rise to workstation-level ergonomic constraints (WLECs):• Each operation is defined to be performed in a defined WLEC, or ‘ANY’ • Each workstation is assigned a defined WLEC, or ‘ANY’ • If a workstation has a defined WLEC, then it can be only assigned operations with the same WLEC, or ‘ANY’
--------------------------------------------------------------------------------
Page 6
Emanuel Falkenauer • If a workstation has the ‘ANY’ WLEC, then it can “acquire” any defined WLEC by the operations it is assigned, but all of them must share the sameWLEC or have the ‘ANY’ WLEC. These rules simply ensure compatibility between the workstation, the operations it is assigned, and the operations among themselves. For instance, if a workstation is assigned an operation that requires the car to be elevated, then all the other operations assigned tothat workstation must be compatible with that position, otherwise they could not be carried out (since the car will be elevated in the workstation, to make the first operationfeasible). The possibility to assign the undefined (‘ANY’) WLEC to a workstation is crucial: many modern assembly lines are highly flexible, giving the line manager the possibility not to impose all WLECs a priori but, rather, have it selected by the algorithm in the way that makes the line the most efficient. Naturally, there may be more than one kind of WLECs at play simultaneously, inwhich case all of them must be satisfied on all workstations in any valid solution. For instance, a typical set of WLECs in the automotive industry includes the following three kinds:• Side (left, right, front, back, or ‘ANY’) • Elevation (low, mid, high, or ‘ANY’) • Tilt (tilted, not tilted, or ‘ANY’). 3.8.2 Operator level As we have observed in section 3.6 above, there are often several operators working on a large product at the same time. There are, however, certain restrictions that are typicallyimposed on the operations assigned to a workstation and their scheduling within the workstation, in order to avoid counterproductive “clashes” among operators. First, it is usually forbidden to have two operators working at the same time in the same spot on the product. For example, during the time an operator is fixing the interior rear-view mirror in a car, it is usually forbidden to have another operator fixing the audio player, because both operators would occupy the cabin of the car at the same time, and there is not enough space in the cabin for both of them. Second, the line manager often seeks to avoid unproductive travel of operators fromone spot on the product to another, as it significantly reduces the efficiency of the workstation and hence of the whole line. This means that an operator can be “fixed” to a given spot on the product (say “front-left”) and can only perform operations that take place there. These considerations give rise to operator-level ergonomic constraints (OLECs):• Each operation is defined to be performed in a defined OLEC, or ‘ANY’ • Each operator in a workstation is defined to work in a defined OLEC, or ‘ANY’. Note that if there are several operators in a workstation, it will have several different OLECs • If an operator in a workstation has a defined OLEC, then it can only be assigned (by the within-workstation scheduling) operations of the sameOLEC, or operations with the ‘ANY’ OLEC • If an operator in a workstation has the ‘ANY’ OLEC, then it can be assigned operations with any OLEC – he or she can therefore change its working place. However, in any case,
--------------------------------------------------------------------------------
Page 7
Line Balancing in the Real World • In any workstation, no two operations with the same defined OLEC can be scheduled to overlap in time, as this would result in a “clash” betweenseveral operators working in the same spot on the product at the same time. 3.8.3 Additional complexity According to our experience, any software aiming to solve line balancing in automotive and related industries must support the ergonomic constraints described above. Indeed, a solution where, for instance, the exhaust system should be mounted at the sameworkstation as the sunroof, is simply infeasible, as the car cannot be elevated both in the high and the low position at the same time. A solution where the left floodlight should be mounted at the same time as the left front blinker is probably infeasible as well, because the two operators would be occupying each other’s workspace. However, as pointed out above, the ergonomic constraints very significantly increase the level of difficulty of the line balancing problem. Indeed, • Workstations with the ‘ANY’ WLEC make NP-hard even the mere problemof finding an assignment of WLECs to these workstations that is feasibleunder the precedence constraints among operations with defined WLECs. For instance, if an operation with the elevation WLEC “high” is preceded by an operation with “low”, itself preceded by a “high” operation, then anyfeasible solution must feature two “high” workstations with a “low” workstation in between• OLECs may significantly constrain the within-workstation scheduling, creating idle times in many schedules. This makes the search for workstations with little idle time far more difficult. Also, multi-operator operations with OLECs defined for each of its operators can be difficult to assign, as they require the presence of all the OLECs in a single workstation.3.9 Multiple Products 3.9.1 Multi-product Line Balancing on Average In today’s time of ever more personalized (customized) products, assembly lines assembling just one product are extremely rare. This is especially true for the automotive industry, where numerous variants of the same car, or even different cars, are routinelyassembled on the same line. A line balancing tool for automotive and related industries must therefore support multiple products on the line. In a multi-product line, an operation may be carried out on only a subset of the products assembled in the line. For instance, suppose that two products, A and B, are assembled on the line: operations that must be carried out on A but not on B, will only beperformed when an A is actually being assembled, and vice-versa. This is often taken into account by the obvious approach of replacing operation durations by their average durations over the whole production, and balancing the line as if it assembled just one product. However, this “balancing of average durations” isfundamentally flawed in presence of multi-operator workstations. Indeed, the objective of the balancing is to obtain a line that would be well balanced on average, which implies that we need to compute the average lead time of each workstation. The “balancing of average durations” is based on the (correct) observation that the average of sums of durations is equal to the sum of averages. Yet as pointed out
--------------------------------------------------------------------------------
Page 8
Emanuel Falkenauer in section 3.6 above, with multiple operators per workstation, the lead time is not a simple sum of operation durations, but the result of a full-fledged within-workstation scheduling. Since the average of lead times obtained by within-workstation scheduling for each product is not necessarily equal to the lead time obtained by within-workstationscheduling of operations of average durations, the premise behind the “balancing of average durations” does not hold and the approach is flawed: the resulting lead times would most probably not reflect reality. In short, in order to obtain the true average workstation lead times, the lead times must be computed separately for all the products being assembled, with true operation durations, and only then averaged according to the respective product percentages. 3.9.2 Peak Time Reduction As pointed out above, even the simple balancing on average becomes difficult in presence of multiple operators in workstations, but the difficulties do not stop there. One of the major difficulties in running a multi-product assembly line is coping with “rare” products, i.e. products that are assembled relatively seldom. Suppose for instance, that a given product C represents only 10% of the totalproduction. Consequently, C weighs only 10% in the average of workstation lead times. With such a small percentage, the influence of the product in the line balancing on average can easily be diluted to a point where it is neglected. However, suppose that the operations pertaining to assembly of C are assigned in such a way that they induce a workstation’s lead time triple the line’s cycle time. Such an assignment would cause an inordinate amount of time being spent in that workstation each time C would be assembled, and would probably lead to a long stoppage of the whole line once in everyten products assembled – clearly a disastrous performance. One way of avoiding these problems is to take into account the peak time at each workstation, i.e. the maximum lead time over all products. These peak times must be keptat a reasonable level, which can only be achieved by taking them into account in the optimization, together with the average balance. Becker and Scholl (2004) call thisapproach “horizontal balancing”. 3.10 Drifting Operations While “rare” products are a difficulty that must be dealt with by taking peak times intoaccount, extremely long yet “rare” operations are a different kind of nuisance. In manyassemblies, in particular in the automotive industry, some operations take so long and are sufficiently “rare” that they are split over several consecutive workstations. Consider for instance the not-so-distant past when CD audio players were a rarity in a car. In that time, the technology was not very advanced either, so mounting the CD player required a very long assembly time, a multiple of the line’s cycle time. The standard way of dealing with that kind of operation is to split it over several consecutive workstations. The idea is simple: at the end of the cycle time on the first workstation to which the operation is assigned, the operation continues while the product enters the nextworkstation, where it is taken up by another operator – in other words, the operation drifts into the next workstation. This is possibly repeated into a third workstation, etc. In another variant of drifting, the operator drifts with the operation, i.e. he or she visits several consecutive workstations. When the operation is finished, the operator leaves the product and walks back to the workstation where the operation begun. If the
--------------------------------------------------------------------------------
Page 9
Line Balancing in the Real World operation is indeed sufficiently “rare”, all of this can be achieved before the next productrequiring the operation enters its first workstation. For instance, an operation that pertains to only one in every three products being assembled on the line, could drift over a total of up to three workstations, provided the products are sequenced consequently. Needless to say, handling drifting operations represents an additional difficulty in a line balancing algorithm. This is particularly the case when ergonomic constraints (see section 3.8 above) are being handled as well, as assigning a drifting operation to a workstation directly influences the ergonomic constraints on the successive workstations the operation will drift into. Nevertheless, drifting operations are quite pervasive inautomotive and related industries, so a tool intended for those industries should be able tohandle them. 4 Summing Up 4.1 Complexity of the Problem and Time Requirements The conclusions in section 3 stem from our extensive contacts with automotive and related industries, and reflect their true needs. Other “exotic” constraints may apply inany given real-world assembly line, but a line balancing tool for those industries must be able to handle at least those aspects of the problem. This is very far from the “clean” academic SALBP, as well as most GALBP extensions reported by Becker and Scholl (2004). In fact, such a tool must simultaneously solve several NP-hard problems:• Find a feasible defined replacement for all undefined (‘ANY’) ergonomic constraints on workstations, i.e. one compatible with the ergonomicconstraints and precedence constraints defined on operations, as well as zoning constraints and possible drifting operations • Solve the within-workstation scheduling problem on all workstations, for allproducts being assembled on the line • Assign the operations to workstations to achieve the best average balance, while keeping the peak times at a manageable level. Clearly, the real-world line balancing problem described above is extremely difficultto solve. This is compounded by the size of the problem encountered in the targetindustries, which routinely feature assembly lines with dozens or hundreds of workstations with multiple operators, and hundreds or thousands of operations. Yet in order to be practically usable, a tool solving the problem must nevertheless be very fast. This is because the line manager has many possibilities of imposing a prioriany of the constraints discussed above. This enables them to fashion the line to their exactneeds in an iterative process, where the influence of an a priori choice is assessed byevaluation of the resulting line. Needless to say, the algorithm needs to offer short response times (minutes) to make that iterative process practically feasible. The uncanny difficulty of the problem, and the practical need to solve it quickly, may explain why just one commercially available software, OptiLine, appears to be available. OptiLine uses the Grouping Genetic Algorithm (GGA) proposed by Falkenauer (1998), to solve the problem with all the aspects discussed above while supplying high-quality solutions in short computation times. We cannot give a detailed description of the GGA
--------------------------------------------------------------------------------
Page 10
Emanuel Falkenauer technique here, for obvious space reasons – the interested reader should consult the Falkenauer (1998) book. 4.2 The advantage of the Grouping Genetic Algorithm The GGA used in OptiLine has a fundamental advantage over other methods in handling this kind of complex problems, which may explain its success. Since the optimization itself is performed by gradual improvement through exchange of information between various solutions to the problem (as is the case in any Genetic Algorithm), the GGA has the “liberty” of constructing the various solutions under the sole constraint of feasibility (i.e. compliance with the numerous constraints), without much regard to their quality. This is in stark contrast to constructive methods that must care for the quality of the solution, as well as its feasibility, during the very process of its construction. This gives the GGA the advantage of extreme flexibility: as long as feasible solutions can be found, whatever their quality, the GGA will deliver. That flexibility makes it possible to take into account constraints as diverse and as difficult to satisfy as those identified above. 5 Conclusions We have identified a number of aspects of the line balancing problem that are vital inindustries such as automotive, yet that have been either neglected in the OR work on the problem, or handled separately from each other. According to our experience, a line balancing tool applicable in those industries must be able to handle all of themsimultaneously. That gives rise to an extremely complex optimization problem. The complexity of the problem, and the need to solve it quickly, may explain why there appears to be just one commercially available software for solving it, namely OptiLine by Optimal Design. More information on OptiLine, including its rich graphic user interface, is available at http://www.optimaldesign.com/OptiLine/OptiLine.htm.References 1 Becker C. and Scholl, A. (2004) `A survey on problems and methods in generalized assembly line balancing', European Journal of Operations Research, in press. Available on-line at http://dx.doi.org/doi:10.1016/j.ejor.2004.07.023. Journal article. 2 Falkenauer, E. and Delchambre, A. (1992) `A Genetic Algorithm for Bin Packing and Line Balancing', Proceedings of the 1992 IEEE International Conference on Robotics and Automation, May 10-15, 1992, Nice, France. IEEE Computer Society Press, Los Alamitos, CA. Pp 1186-1192. Conference proceedings. 3 Falkenauer, E. (1997) `A Grouping Genetic Algorithm for Line Balancing with Resource Dependent Task Times', Proceedings of the Fourth International Conference on Neural Information Processing (ICONIP’97), University of Otago, Dunedin, New Zealand, November 24-28, 1997. Pp 464-468. Conference proceedings. 4 Falkenauer, E. (1998) Genetic Algorithms and Grouping Problems, John Wiley & Sons, Chichester, UK. Book. 5 Garey M. R. and Johnson D. S. (1979) Computers and Intractability - A Guide to the Theory of NP-completeness, W.H.Freeman Co., San Francisco, USA. Book.
Assembly Line Balancing in a Clothing CompanyS. H.Eryuruk, F. Kalaoglu, *M. BaskakTextile Engineering Department,*Industrial Engineering Department,Istanbul Technical University Instanbul, TurkiyeAbstractIn this study, two heuristic assembly line balancing techniques known as the “Ranked Positional Weight Technique”, developed by Helgeson and Birnie, and the “Probabilistic Line Balancing Technique”, developed by El-Sayed and Boucher, were applied to solve the problem of multi-model assembly line balancing in a clothing company for two models. Information about definitions and solution methods related to assembly line balancing problems is given. The aim of this article is the comparison of the efficiencies of two different procedures applied for the first time to solve line balancing in a clothing company. By using both methods, different restrictions are taken into consideration and two different line balancing results are reached. The balancing results are compared with each other.Key words: assembly line, balancing techniques, multi-model assembly line, clothing company, balancing procedure efficiency.
--------------------------------------------------------------------------------
Page 2
FIBRES & TEXTILES in Eastern Europe January / March 2008, Vol. 16, No. 1 (66)9495FIBRES & TEXTILES in Eastern Europe January / March 2008, Vol. 16, No. 1 (66)The assembly line balancing problem was first introduced by Bryton in his graduate thesis. In his study, he accepted the amount of workstations as constant, the workstation times as equal for all stations and work tasks as moving among the workstations [8]. The first article was published in 1955 by Salveson [9]. He developed a 0-1 integer programming model to solve the problem.COMSOAL (Computer Method of Sequencing Operations for Assembly Lines) was first used by Arcus [10] in 1966 as a solution approach to the assembly line balancing problem. Helgeson ve Birnie [11] developed the “Ranked Positional Weight Technique”. In this method, the “Ranked Positional Weight Value” is determined. It is the sum of a specified operation time and the working times of the other operations that can not be assembled without considering the operation finished. While taking into consideration the cycle time and technological precedence matrix, the operation having the largest ranged weight is assigned to the first workstation, and other operations are assigned to workstations in accordance with their ranked positional weight value.For the multi-model assembly line, Kilbridge and Wester [12] developed a simple method to solve line balancing. In the first stage they formed an appointment table, and then they made necessary workload balance among workstations, taking into consideration precedence relationships and cycle time.Nicosio et. al. [13] studied the problem of assigning operations to an ordered sequence of non-identical workstations, which also took precedence relationships and cycle time restrictions into consideration. The aim of the study was to minimise the cost of workstations. They used a dynamic programming algorithm, and introduced several fathoming rules to reduce the number of states in the dynamic program.Kim et. al. [14] used a genetic algorithm to solve the assembly line balancing problem of how to minimise the number of workstations and cycle time, and how to maximise workload smoothness and work relatedness. A performance comparision was made between the Gas proposed and the heuristic algorithms known.n Experimental proceduresTest materialsIn this study, the production of two mo-dels: command pocket and welt pocket pants (Figure 1) were investigated to solve the problem of assembly line ba-lancing in a clothing company. Medhods usedBy using the “Ranked Positional Weight Technique” and the “Probabilistic Line Balancing Technique”, the assembly line balancing problem was solved. The solu-tion steps of these methods are explained as follows.Ranked positional weight techniqueThis heuristic method was developed by Helgeson and Birnie of the General Electric Company in 1961 [11]. In this method, the ranked positional weight value of each operation is determined. The procedures below are applied in order to assign operations to workstations.The ranked weight value of an operation is obtained by summing the operation time considered with the time of other operations that come after that in series. After all of the ranked positional weights of the operations are determined, they are arranged in decreasing order. Then tasks are assigned to each workstation starting from the task with the highest ranked positional weight. Before this the operation having the second highest ranked value should be selected from the remaining working operations in order to assign to the workstation; the precedence constraints, the operation time, the unused workstation time should be controlled. The assignment procedure is continued until one of conditions below is obtained;1. If all the operations are assigned to the stations,2. If there are no operations having either precedence or unassigned time constraints. Probabilistic line balancing techniqueIn this method, a P (predecessor elements) and F (follower elements) matrix are formed and the steps below are followed [15]:1. The line of the P matrix having zero values is selected. If there is more than one line having zero values, the operation with the highest operation time is selected (Every line corresponds to one work task). If the time of this work task is suitable, it is assigned to the workstation. 2. If the chosen work task is assigned, we go to the F matrix having the same line number and the numbers in this line are taken. Then we turn back to the P matrix and between the subsequent elements of the P matrix in the numbers taken, we write 0 value to the last work task assigned, and step 1 is repeated for the new situation. If the work task is not assigned, we turn back to step 1 in order to open a new station or select a new work task.3. Step 1 and step 2 are repeated until all the lines in the P matrix are used, taking into consideration the constraint (Enb ti ≤ T ≤ C).n Results Model 1: Command pocket pant line balancing resultsModel 1: Command pant model ranked positional weight balancing results This model has fifty-two work operations and an operation list. Its standard times, precedence relations and machine types used are listed in Table 1. After the determination of the precedence relationships between operations, a technological precedence diagram is drawn like Figure 3. Then the cycle time is calculated as shown below:C = T / PA(1)T = Total working time in a dayPA = Total production amount in a dayC = T / PA = (540 minutes × 60 seconds) / 450 piece = 72 seconds/pieceCycle time = 75 seconds (This value is assumed instead of 72 seconds/piece)The next step is the calculation of the minimum theoretical number of workstations .nmin= Max (nmin; nprobable) (2)nmin= [Σ ti/ C ]+= [2744.6 /75]+= 37(3)Figure I. Pant model; a) command pocket, b) welt pocket. a)b)
--------------------------------------------------------------------------------
Page 3
FIBRES & TEXTILES in Eastern Europe January / March 2008, Vol. 16, No. 1 (66)9495FIBRES & TEXTILES in Eastern Europe January / March 2008, Vol. 16, No. 1 (66)Table 1. Data of command pant modelFigure 2. Technological precedence diagram of the command pocket model.Table 2. Balancing Results of Ranked Positional Weight Technique for Model 1.Figure 3. Ranked positional weight table for the command pocket pant model
--------------------------------------------------------------------------------
Page 4
FIBRES & TEXTILES in Eastern Europe January / March 2008, Vol. 16, No. 1 (66)9697FIBRES & TEXTILES in Eastern Europe January / March 2008, Vol. 16, No. 1 (66)Table 3. Standard time, standart deviation and matrix values concerning command pant model.Table 4. Probabilistic line balancing results of the command pocket pant model.Table 5. Operations, ranked positional weights and machine type used for the welt pocket pant model.Table 6. Model 2: Ranked positional weight balancing results of the welt pocket pant model.
--------------------------------------------------------------------------------
Page 5
FIBRES & TEXTILES in Eastern Europe January / March 2008, Vol. 16, No. 1 (66)9697FIBRES & TEXTILES in Eastern Europe January / March 2008, Vol. 16, No. 1 (66)nprobable = The number of work tasks that have the condition of ti > (C/2 = 75/2 = = 37.5) = 33 (1,7,8,9,10,11,12,14,15,16,17,18,20,21,29,30,31,32,33,34,35,36,37,39,41,43,45,47, 48,49,50,51,52)nmin = Max (37; 33) = 37Then ranked positional weights of operations are calculated by using the method explained above and listed in a descending order, as shown in Figure 4. As a result of balancing, it is found that (n = 42) workstations are needed to balance the line. This situation is convenient for the condition (n ≥ nmin). Balancing results of the ranked positional weight technique are given in Table 2.Balancing loss is calculated:BL = (n×C – Σ ti)/(n×C)×100% == (42×75 – 2744.6)/(42×75)×100% == 12.9% (4)For this assembly line, theoritical and real line efficiency values are calculated:NTE = [Σ ti/(nmin×C)]×100% =i=1= [2744.6/(37×75)]×100% = 98.9 % (5)NLE = [Σ ti/(n×C)]×100% =i=1= [2744.6/(42×75)]×100% = 87.1 % (6)Model 1: Command pocket pant probabilistic line balancing results Table 3 shows information about the standard time, standart deviation and precedence matrix of the model. By accepting the confidence interval as being 80% and the cycle time as being C=75 seconds, we can attempt to balance to balance the assembly line. After constituting P and F matrixes, the steps below are followed:1. We start by using the first line, having only zero values in the P matrix. The first operation is assigned to the first station (t1=55.3; T1=55.3).2. We take 13 from the first line of the F matrix. It is looked to the line 13 of the P matrix. There is a value of l, this means that before 13 is assigned to any workstation, operation 1 should be made. This situation is supplied above. Operation 13 is controlled in order to assign it to a workstation.3. Z formula is used to control the suitability of operation 13 for the workstation (t13=6.6, T1=62, Z20%= -0.84):As the confidence interval is 80% (= 50% + 30%), a value corresponding to 30% (= 0.3000) is sought from the normal distribution table that the value corresponding. This value is 0.84. However, here the non-confidence value which corresponds to (1 – 80%=) 20% is sought, and this value is (Z20%= -0.84).σw.s.= √ σ12 + σ132= = √ (7.1)2 + (0.4)2= 7.11 (7)Z = (62 – 75)/7.11 = -1.82 < -0.84 (8)P(T > C) ≈ 0 < 0.2 (assignment is available).4. If there is still unused cycle time, it is sought whether or not any other work task can be assigned to the first station. If an operation can not be assigned to a station, then a new station is opened and new operations are attempted to be to assigned.Table 4 shows command pocket pant model probabilistic line balancing results of the command pocket pant model. The balancing loss and line efficiency are also calculated below:BL = (n×C – Σ ti)/(n×C)×100% == (44×75 – 2744.6)/(44×75)×100% = = 16.8%NLE = [Σ ti/(n×C)]×100% =i=1= [2744.6/(44×75)]×100% = 83.2%Model 2: Welt pocket pant line balancing resultsModel 2: Welt pant model ranked positional weight balancing results First the cycle time is calculated. Table 5 shows the operations, ranked positional weights and machine types used to produce the welt pocket pant model. C = T/PA = (540 minutes × 60 seconds) / 500 piece = 64.8 seconds/piece= 65 secondsnmin= Max (nmin; nprobable) =28The line is balanced by using (n = 34) workstations. Balancing results of the Table 7. Model 2: Welt pocket pant probabilistic line balancing results.Table 8. Line balancing results.ModelThe number of workstationTheoritical line efficiency, %Line efficiency, %Balancing loss, %Command and pocket pant-ranked positionalweight method balancing resultsn = 4298.987.112.9Command and pocket pant-probabilistic methodline balancing resuitsn = 4498.983.216.8Welt pocket pant-ranked positionalweight method balancing resultsn = 3497.980.619.4Welt pocket panl-probabilistic methodline balancing resuitsn = 3597.978.321.7
--------------------------------------------------------------------------------
Page 6
FIBRES & TEXTILES in Eastern Europe January / March 2008, Vol. 16, No. 1 (66)98Received 04.07.2006 Reviewed 21.07.2006ranked positional weight technique are given in Table 6. NTE = [Σ ti/(nmin×C)]×100% =i=1= [1781.8/(28×65)]×100% = 97.9%NLE = [Σ ti/(n×C)]×100% = i=1= [1781.8/(34×65)]×100% = 80.6%Model 2: Welt pocket pant probabilistic line balancing resultsWelt pocket pant probabilistic line balancing results are shown in Table 7. Also, line balancing loss and real line efficieny values are calculated below:BL = (n×C – Σ ti)/(n×C) == (35×65 – 1781.8)/(35×65) = 21.7%NLE = [Σ ti/(n×C)]×100% = i=1= [1781.8/(35×65)]×100% = 78.3%n ConclusionsAs a result of evaluation, it can be seen that the Ranked Positional Weight Technique gives better resuls than the Probabilistic line balancing technique, as shown in Table 8.The Ranked Positional Weight Technique is easier to apply and has higher line effi-ciencies. On the other hand, it is accepted that task times are not deterministic (variable) and work element times obey a normal distiribution with µ average value and σ standard deviation in the probabilistic line balancing technique. For this reason, when work elements are assigned to workstations, standard de-viation values of standard time values are taken into consideration. This situation enables work elements to be assigned to workstations more sensitively, and thus more reliable assembly line balancing re-sults can be obtained. In conclusion, both techniques have proven effective in get-ting successive line balancing results and it is necessary to select between them in accordance with the company’s targets.Editorial noteThis problem was also presented at the 2006 AUTEX Conference, June 11-14 2006, Raleigh NC State University.References1. Acar N. ve Eştaş S., “Kesikli Seri Üre-tim Sistemlerinde Planlama ve Kontrol Çalışmaları“, Milli Prodüktivite Yayınları: 309, Üçüncü Baskı, Mpm Endüstri Şube-si, Ankara, 1991. 2. Scholl, A., Becker, C., “A Survey on Problems and Methods in Generalized Assembly Line Balancing”, European Journal of Operational Research, Sep-tember 2004.3. Scholl, A. Becker, C., “State-of-The-Art Exact and Heuristic Solution Procedures for SimpleAssembly Line Balancing”, Eu-ropean Journal of Operational Research, 2004.4. Bukchin, J., Ezey, M., Dar-El, Rubinovitz, J., “Mixed-Model Assembly Line Design in a Make-to-Order Environment”, Com-puters&Industrial Engineering, 41 (4), pp. 405-421, 2002.5. G. Suresh, V. V. Vinod and S. Sahu, “Agenetic algorithm for assembly line balan-cing, Production. Planning and Control 7(1), pp. 38–46,1996.6. McMullen, P. R., Frazierb, G.V., “AHeuristic for Solving Mixed-Model Line Balancing Problems with Stochastic Task Durations and Parallel Stations”, ELSE-VIER Int. J. Production Economics, 51, pp. 177-190, 1997.7. Baybars, “A Survey of Exact Algorithms for The Simple Assembly Line Balancing Problem”, Management Science, 32 (8), pp. 909–932, 1986.8. Bryton, B., “Balancing of a Continuous Production Line”, M.S. Thesis, Northwe-stern University, Evanson, ILL. 1954. 9. Salveson, M. E., “The Assembly Line Balancing Problem, Journal of Industrial Engineering”, 6 (3), pp. 18-25, 1955.10. Arcus, A. L., “COMSOAL: A Computer Method of Sequencing for Assembly Li-nes”, International Journal of Production Research, 4 (4), pp. 259-277, 1966.11. Helgeson, W. P., Birnie, D. P., “Assem-bly Line Balancing Using the Ranked Positional Weight Technique”, Journal of Industrial Engineering, Vol. 12 (6), pp. 384-398, 1961.12. Kilbridge, M. D., Wester, L., “A Heuristic Method for Assembly Line Balancing”, Journal of Industrial Engineering,, Vol. 12 (4), pp. 292-298, 1961.13. Nicosia, G., Pacciarell, D. and Pacifici,A., “Optimally balancing assembly lines with Different Workstations”, Discrete Applied Mathematics, Vol. 118, Issues 1-2, 15, pp. 99-113, April 2002.14. Kim, Y. K., Kim, Y. J., Kim, Y., “Genetic Algorithms for Assembly Line Balancing with Various Objectives”, Computers & In-dustrial Engineering, Volume 30, Issue 3, pp. 397-409, 1996.15. El-Sayed, E. A., Boucher, T. O., “Analy-sis and Control of Production Systems”, Prentice Hall Inc., New Jersey, 1985..