Mixed Assembly Line Balancing

Theoretical background

Assembly lines

An AL consists of a production arrangement formed by workstations typically distributed over a movement system. The product is sequentially released from station to station, suffering changes until it reaches the final assembly station.

The assembly lines that produce identical products are call single-model line, or one-model line. When there are differences in the products, two classifications arise. The first is the multi-model line or multi-line model, which shows significant differences in production processes, and different products are manufactured in larger batches than a unit to minimize the setup impacts. The second classification is known as mixed-model line or mixed line, which is apply when there is similarity of productive process and there is no setup for process adjustment. This makes it possible to launch the products in the line in units randomly. For each model, different processing times are required, so the amount of work at the same operator in the same workstation is uneven. Cases which operator ends the job before the next cycle or not ends the job within the cycle time make AL unbalanced and efficiency is reduced. Even so, for Askin & Standridge apud Souza et al., this production system tends to be one of the most efficient, but requires reliable process and it with low variability in processing time of the workstations (in the practical application context of the methodology proposed, low variability refers to a difference less than 30% of the time variation between models). Figure 1 illustrates the above definitions, where the geometry of the figures refers to different products.

Figure 1 Assembly line types. Source: Adapted from Becker & Scholl.

In the AL design, the main issues to deal are: (i) define the cycle time; (ii) determine the number of workstations; (iii) balance the AL; and (iv) determine the models production order. Another concern of AL design is to minimize the lead time, which means reducing the gap of time between the initiation and completion of the product AL. As shorter is the lead time, greater the potential sale of products. Another premise for the proper functioning of ALs is time the station (S) does not exceed the cycle time, according to Equation 1.

$\max t_{k} \leq \max S_{j} \leq T_{c} \leq \frac{1}{D}$

where $S_j$ is the total time of station $j (j=1,...,W)$ , representing the sum of performing times tasks allocated to each station in time units; $t_k$ is the processing time of the $k^{th}$ task on time unit; k identifies the task such that $k=1,..., N; T_c$ is the time cycle and D is the product demand rate.

The cycle time ( $T_c$ ) is the time when a product is released from station to station, defined by the Equation 2.

$T_{c}=\frac{\text { available time in period p }}{\text { demand in period p }}$

The number of workstations needed to meet demand varies with the AL settings and restrictions. According Peinado and Graeml, the minimum number of workstations for ALs counting with only one operator can be estimated by Equation 3.

$\text { Number of work stations }=\frac{\sum \text { individual tasks times }}{T_{c}}$

To balance the tasks, it is essential to know precedence diagram (Figure 2). This diagram shows the order of tasks execution, respecting technological requirements or item production characteristics.

Figure 2 Exemple of precedence diagram. Source: Adapted from Becker & Scholl.

In precedence diagram, the numbers within the circles represent tasks, while the arrows joining the circles show the precedence relation. The sum of the tasks times assigned to a station is known as station time.

Each task time can be achieved by chrono-analyse among other methods. The chrono-analyse is a way of measuring the work by means of statistical methods, allowing calculating the standard time. The standard time includes a series of factors, such as operator speed, personal needs and relieving fatigue, among others; such factors can be found in specialized literature in the area. The standard time of performing tasks can also be determined by predetermined times.

The task processing times are also used to determine the production capability of a AL. Capacity is the maximum amount of items produced in the AL in a given time interval; to determine the production capacity, it is necessary to identify the bottlenecks in the AL. Therefore, the production capacity is calculated on the basis of working time available and the time of the bottleneck station, as in Equation 4.

$\text { Production capacity }=\frac{\text { Available time in period p }}{\text { Time of the bottlneck station }}$

Assembly line balancing

The Assembly Line Balance (ALB) is known as the classic problem of AL balancing, consisting in the allocation of tasks on a workstation in a way that downtime is minimized and the precedence constraints are met. The ALB allows achieve the best use of available resources so that satisfactory production rates are reached at a minimum cost. The balancing is necessary when there are process changes, such as adding or deleting tasks, change of components, changes in processing time and also in the implementation of new processes.

According to Becker & Scholl, 2006, the assembly line balancing problem can be classified into four categories, as shown in Figure 3. This classification is detailed as follows:

Figure 3 AL balancing problem classification. Source: Adapted from Ghosh & Gagnon.

i.i

DSM – Deterministic single model: This model is considered to assembly lines with only one product model, where the tasks times are known deterministically, with little tasks timing variation (as a result of easy execution and also the operators motivation). Certain efficiency criteria should be otimizated, as idle time station and line efficiency, among others; (ii) SSM – Stocastic single model: In this category, the execution times of activities have resulting human behavior variability, inability of operators, lack of motivation, complex processes and equipment with low reliability, among others; (iii) DMM - Deterministic multi/mixed model: The formulation of the DMM problems considers deterministic tasks times, but with the presence of different products manufactured on the same assembly line. In this context, aspects associated with sequencing, release rate and batch sizes become important when compared to single model lines; and (iv) SMM - Stocastic multi/mixed model: the tasks times are probabilistic. Learning impacts, skill, tasks delineation and tasks time variation are considered in this approach.

Another important classification split the line balancing problems into two categories: (i) simple assembly line balancing problems, indicating that no restrictions are relaxed; and (ii) generic balancing problems, which fit the line balancing problems that aim to solve problems with additional features.

According Van Zante-de Forkket & De Kok apud Gerhardt, the fundamental difference between a single model line balancing problem for a multi-model is the precedence diagram. Such, many authors, to develop methods to solve multi-model line balancing problems, transform the problem into single model. Two methods can be used: (i) equivalent precedence diagram, and (ii) adjusting the processing taks time.

i. i

Equivalent precedence diagramming method: Thomopoulos apud Gerhardt assumed that in a mixed line, there are several common tasks to the various models produced and, consequently, a similar set of precedence relationships. Then, the precedence diagrams combination of each individual model can be made by joining the nodes and precedence relations of the respective diagrams for each model, as exemplified by the Figures 4 and 5.

Figure 4 Precedence diagram to the model A (a) and model B (b). Source: Adapted from Gerhardt.

Figure 5 Precedence diagram equivalent models A and B. Source: Adapted from Gerhardt.

According to van Zante-de Fokkert & de Kok, the balance of AL multi-model based on equivalent precedence diagramming method can be compared to balancing single AL model. However, the allocation of tasks to workstations is performed based on the total shift time duration and not in cycle time, which is used as the basis to balancing AL single model.

i. ii

Setting task processing time method: In this method, the processing time is determined by the weighted average of k^th task common to different models, according to the Equation 5,

$\overline{t_{k}}=\sum_{m=1}^{M} p d_{m} t_{k, m}$

where

$pd_m$ is the proportion of the model m ahead the other models produced in AL,

$t_{k, m}$ represents the processing time for the k^th common task for different models and

$\overline{t_{k}}$ represents the processing time weighted average of the k^th common task to different models. An advantage of this method is that it is based on the cycle time, which makes more sense for organizing tasks in a AL (instead using it total shift time). As disadvantages, the method does not determine the sequence in which the models will be produced and does not consider different diagrams of precedence. As such, it is recommended for balancing derivatives models of a basic model, where the tasks have a processing time similar to the basic model.

In turn, Becker & Scholl emphasizes that both methods (i) and (ii) exhibit inefficiencies resulting from variations in stations processing times, which depend on the production model. Such inconsistencies may generate work overload or idle for operators.

Traditionally, two indicators are used to evaluate balancing quality AL: Balance Delay, which represents a percentage of time that the AL remains idle; and Smoothness Index (softness Index), which measures the difference between the maximum total working time between the stations and the total times of the other work stations.

Driscoll & Thilakawardana introduce alternative ways to evaluate the balance of the AL. The Line efficiency (LE) quantifies the use of AL and has aspects of economic evaluation; Balancing efficiency (BE) quantifies the tasks allocation quality for the workstations, which may consequently cause an increase in the production rate. Both indicators are dimensionless and represented using a scale from 0 to 100%, where 100% represents the best result. They are calculated according to Equations 6 and 7 respectively.

$L E=\frac{\sum_{k+1}^{N} t_{k}}{W \times T_{e}} \times 100$

$B E=\left[1-\frac{\sum_{j=1}^{W}\left|S_{j}-S_{\mathrm{av}}\right|}{W \times S_{\mathrm{aw}}}\right] \times 100$

where $s_{av}$ is the average time of workstations and W the number of workstations.

Soluctions for ALB

Considering that the ALB problem may be shown on NP-hard combinatorial optimization category, several researches have developed computational or heuristic approaches. Ghosh & Gagnon classify methods for balancing ALB as follows:

(i) Rank and Assign Methods: In these methods, tasks are sorted based on criteria or rules of priority and assigned to stations relying on an order that does not violate the relationship of precedence constraints and cycle time;

(ii) Tree Search Methods: These methods are essentially integer programming relying on the Branch & Bound method. Approaches in this category can also be termed as enumerative methods;

(iii) Random Sampling Methods: These methods randomly assign tasks to workstations in view of the precedence constraint and cycle time; and

(iv) Other methods: aggregation methods (task elements are grouped into composite tasks), Successive Approximation (a great algorithm is applied successively as a heuristic in a simpler version of the problem), and Learning Methods (based on the premise that the experience acquired minor problem solving is used to solve larger problems).

Cristo, Ponnambalam et al. and Chow highlight the following heuristics to ALB troubleshooting: Rank positional weight, Kilbridge and Wester's method, Largest set ruler. The foundations of heuristics above are now displayed.

RPW-Rank Positional Weight: this method was introduced by Hegelson and Birnie in the 60s, having generated satisfactory and fast solutions according Boctor apud Praça. Its operation consists in calculating the positional weight of each task according to the precedence diagram. The weight is the sum of the task time with the time tasks that predate it. In sequence, the positional weights should be arranged in descending order, and the tasks assigned to the workstations according to the order of the positional weight, respecting the precedence constraints. Further details on the method can be found in Chow.
Kilbridge e Wester Method (KWM): This method selection work elements to describe the station according to the column Precedence Diagramming position as shown in Figure 6. In sequence, tasks are arranged in descending order of processing time. Finally, tasks are allocated to workstations in accordance with such order, thus ensuring that the largest elements are allocated first and increasing the chance of each station time get closer to the cycle time.

Figure 6 Precedence diagram divided in column by Kilbridge and Wester method. Source: Adapted from Gerhardt & Fogliatto.

Largest Candidate Rule (LCR): This heuristic allows obtaining results in less time than the positional weights method. Initially, one should list tasks in descending order of processing time; then the task should be assigned to the workstations according to the order of the list without violating any precedence constraint or exceed the cycle time.