# An Optimization Model for Assembly Line Balancing Problem with Uncertain Cycle Time

Authors: Yong Cao; Yuan Li; Qinghua Liu; Jie Zhang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

With the drastic change in the market, the assembly line is susceptible to some uncertainties. This study introduces the uncertain cycle time to the assembly line balancing problem (ALBP) and explores its impact. Firstly, we improve the traditional precedence graph to express the precedence, spatial, and incompatible constraints between assembly tasks, which makes ALBP more realistic. Secondly, we establish the assembly line balancing model under an uncertain cycle time, which is defined as an interval whose size can be adjusted according to the level of uncertainty. The objective of the model was to minimize the number of stations and the cycle time. Thirdly, we integrate the operator’s skill level into the model, and a multipopulation genetic algorithm is used to solve it. The method proposed in this study is verified by several test problems of different sizes. The results show that when the cycle time is uncertain, the proposed method can be used to obtain more reasonable results.


---

## Body

## 1. Introduction

Assembly lines are widely used in mass production, and they determine a number of indicators, such as production efficiency, production cost, and enterprise efficiency. To ensure the performance and productivity of assembly plants, there exists a well-known decision problem called the assembly line balancing problem (ALBP). The scientific solution to this problem has been a concern of researchers since 1965. ALBP allocates all assembly tasks to a certain number of stations while optimizing one or more objectives (e.g., number of workstations or cycle time) without violating certain technological, operational, and spatial constraints [1, 2]. Because of the wide usage of assembly lines, many survey papers appear in the literature [2–6]. ALBP can generally be divided into two classes: the simple assembly line balancing problem (SALBP) and the generalized assembly line balancing problem (GALBP) [1]. SALBP assumes that stations are arranged in a straight line, each assembly task has a defined time, and the assembly line produces just one product. There are four types of SALBP. SALBP-I aims to minimize the number of stations for a given cycle time of the assembly line. SALBP-II aims to minimize the cycle time for a given number of stations. SALBP-E aims to maximize the efficiency of the assembly line, where neither the number of stations nor the cycle time is given. In SALBP-F, the number of stations and the cycle time are given, and the problem is to evaluate whether the assembly line is feasible. GALBP includes all of the other problems, such as multiproduct hybrid assembly lines, U-shaped assembly lines, parallel workstations, and stochastic task durations. GALBP covers a wider area than SALBP. We focus on SALBP-I because it has been widely used in practice to minimize the number of stations for a given cycle time. A guide for the class of SALBP-1 can be seen in the literature [7].With the diversification, differentiation, and intensification of the market, assembly lines face many uncertainties, such as task time, demand, and machine failure [8–10]. These will easily disrupt the normal operation of an assembly line, cause failure of a production plan, and reduce customer satisfaction. To this end, the study of ALBP in an uncertain environment is of great significance to manufacturing companies. Assembly lines can have deterministic or stochastic cycle times [11]. The cycle time is deterministic in traditional SALBP-I [1, 12], and there is a significant gap between research and real-world applications. Researchers and industrial practitioners are working to solve SALBP-I as more realistic assembly line settings and features are considered. This study deals with SALBP-I by considering an uncertain cycle time as an important characteristic of production systems.Variation in demand has a significant impact on assembly performance. Demand for a new product can be uncertain; hence, the quantity to be produced is unknown, and the cycle time of assembly lines will be uncertain. In real-life assembly, it is easy to establish a relationship between the quantity to be produced and the cycle time of the assembly line. Therefore, to cope with uncertain demand, we must integrate an uncertain cycle time into traditional ALBP. Uncertainty in an assembly line can be represented using either a probability or a fuzzy set theory [13–15]. Probability theory enables the calculation of the chance of an event’s occurrence, and it requires information from observations associated with the event. Fuzzy set theory focuses on imprecise phenomena based on fuzzy mathematics. To encode the uncertainty, it must choose reasonable membership functions according to the knowledge of the event. Observations or knowledge of an event may be rare in practice, especially in the initial stages of product development. For example, the cycle time may be just an interval in the early design phase, and only its bounds can be predicted. An optimization model for ALBP with an interval cycle time can cope with this situation.This study proposes two mathematical models. SALBP-I with certain cycle time aims to minimize the number of stations. SALBP-I with interval cycle time adds an additional objective to traditional SALBP-I. After that, SALBP-I with interval cycle time may be a variant of SALBP-E, which aims to optimize both the number of stations and the cycle time. The two models are implemented with a multipopulation genetic algorithm. The remainder of this study is organized as follows: Section2 reviews the literature of ALBP with uncertainties. Section 3 analyzes and represents the constraints in SALBP. Mathematical models under certain and uncertain cycle times are presented in Section 4. Section 5 discusses implementation of the models. Section 6 presents computational results and their analysis. Concluding remarks and future work directions are given in Section 7.


## 2. Literature Review

Uncertainties affect the evaluation of a company’s production capacity, which will influence its decisions. Hence, to consider the uncertainty of the production environment is of great significance to establish a reliable assembly line. Researchers have studied the influence of uncertainties on ALBP.Mirzaei et al. [15] studied objective functions to minimize the number of stations, total tool purchasing cost, and cycle time. The cost of each tool and the task times are assumed to be trapezoidal fuzzy numbers to reflect their uncertainty. Hazr and Dolgui [16] integrated the interval uncertainty of operation times into ALBP and proposed a decomposition-based exact algorithm with enhancement strategies to solve large-scale ALBP. The objective is to minimize the cycle time. Gurevsky et al. [17] tackled the balancing problem for straight assembly lines where task times are not known exactly or are given by intervals. The objective is to assign tasks so as to minimize the number of workstations. A breadth-first search procedure finds the best and worst solution. Liu et al. [18] introduced the fuzzy knowledge method to ALBP to address the problem that the distribution of task time is unknown in advance. An approximate mixed-integer second-order cone programming (MI-SOCP) model was proposed to solve the problem. Li et al. [19] proposed a multiobjective optimization model and neighborhood search algorithm for ALBP considering the uncertainty of task time. The objectives are to maximize assembly line reliability and minimize cycle time. This method is suitable for situations of uncertain task times or small data. Li et al. [20] used uncertainty theory and introduced the uncertain task time as a constraint in ALBP-I. The problem was solved using a newly developed restart neighborhood search method. Dong et al. [21] established the assembly line balancing model considering interval task time and spatial constraints. The study compromised between line efficiency and equipment cost. A biobjective chance-constrained mixed 0-1 programming model was developed to simultaneously minimize the cycle time and equipment cost. Li et al. [22] proposed an assembly line balancing model considering uncertain production capacity, aiming to make the cycle time as close as possible to the normal value. The objective was to satisfy the demand in each possible scenario with the minimum labor cost for both normal shifts and overtime work. A heuristic algorithm was developed to quickly find a feasible solution. Chica et al. [23] proposed an approach to evaluate the robustness of a hybrid assembly line in terms of uncertainty of demand. Samouei et al. [24] explored ALBP considering uncertain requirements for semiautomated assembly lines, aiming to find the task allocation with the lowest configuration cost. Pereira et al. [25] proposed a robust formulation to handle uncertain operation times. A branch-and-bound algorithm was proposed to solve the model. The objective included minimizing the number of stations and the cost. It was found that an assembly line can be protected from moderate levels of uncertainty at the expense of small quantities of additional resources. Fathi et al. [26] considered stochastic task times and zoning constraints and integrated the minimization of the maximum of stations’ mean time and variance into ALBP. A mixed-integer programming (MIP) model solved ALBP. Zhang et al. [27] considered uncertain task times in type-II mixed-model ALBP. A robust optimization model was formulated to hedge against uncertainty, and a hybrid genetic algorithm was proposed to solve the problem. Fisel et al. [28] considered the potential need for adaptation in ALBP and used mixed-integer linear optimization to solve the problem. The study focused on production cost, as well as flexibility and changeability of the system. Babazadeh et al. [29, 30] proposed a biobjective fuzzy mixed-integer linear programming model to represent uncertainty in task-processing times, considering the minimization of the number of stations and the cycle time. They proposed an enhanced NSGA-II algorithm with a new repairing mechanism to solve the model [31, 32].Analysis of the literature indicates that while uncertainties in the production environment have been considered, problems remain to be solved. Research has focused primarily on the uncertainty of task times, and uncertainty of cycle times must still be discussed. This uncertainty can occur in all phases of the design, use, and evaluation of an assembly line. The cycle time may be an interval predicted in the design phase, or it may vary with orders and delivery dates. We introduce an interval of the cycle time to ALBP. An efficient algorithm to solve ALBP is of broad concern in industrial and academic circles. The scale of ALBP is generally large; hence, an efficient solution is required. We introduce a multipopulation genetic algorithm to the assembly line balancing problem.


## 3. Preprocessing of Assembly Tasks

### 3.1. Representation of Constraints between Assembly Tasks

The assembly processes of a product are decomposed into several assembly tasks, each comprising a series of actions that cannot or need not be divided further. The essence of ALBP is to assign a series of assembly tasks to a certain number of stations, while satisfying precedence constraints and specified cycle times. Precedence constraints are the most basic and important type of constraints in ALBP, reflecting the order of assembly tasks. Intuitively, assembly tasks and precedence constraints can be represented by a directed graph, called a precedence graph [33, 34]. In Figure 1, the circle represents the assembly task, and the straight line with an arrow indicates the precedence constraints. For products with complex structures (such as airplanes and cars), precedence constraints cannot fully express the relationships between assembly tasks. Spatial constraints and incompatible constraints between assembly tasks also must be considered. We introduce spatial constraints and incompatible constraints on the basis of the traditional precedence graph as follows.Figure 1
Precedence graph.There are two meanings of spatial constraints. Multiple associated assembly tasks must be completed on the same station, and there is a maximum number of assembly tasks that can be allocated to one station. In actual production, assembly tasks that have cooperative relationships or are of the same kind are usually assigned to the same station to improve efficiency. At the same time, the number of assembly tasks that can be assigned to one station is limited to ensure that each operator has sufficient space. In Figure1, the ellipse represents the spatial constraint, and the assembly tasks within it must be assigned to the same station. The figure does not show the maximum number of tasks that can be allocated to a station; this will be quantified in the assembly line balancing model.Incompatible constraints mean that some assembly tasks cannot be assigned to the same station. For example, some tasks to measure quality usually cannot be placed in the same location as other tasks. In Figure1, assembly tasks within dashed circles of the same color cannot be assigned to the same station.


### 3.2. Topological Sorting for Precedence Graph

Assembly tasks are arranged in a linear sequence on an actual assembly line, and ALBP-I is a reasonable division of assembly tasks. To guarantee the precedence constraints between assembly tasks, a topological sorting algorithm preprocesses them in the precedence graph to form a topological order.The precedence graph is a directed acyclic graph. Nodes represent assembly tasks, and directed edges represent the sequences between them. The precedence graph is represented as follows:(1)PG=V,E,fspatial,fincompatible,where V and E represent the sets of vertices and edges, respectively. If there is a directed edge e=a,b, then task a is the immediate predecessor of task b. If there is a directed path a,⋯,b∈V, then task a is the indirect predecessor of task b. fspatial represents spatial constraints. If fspatialVs=1, then there is a spatial constraint for the assembly tasks in the vertex set Vs; otherwise, there is not. fincompatible represents incompatible constraints. If fincompatibleVc=1, then the assembly task in vertex set Vc satisfies the incompatible constraint; otherwise, there is no such constraint; Vs,Vc∈V.Through the topological sorting algorithm, a linear sequencev1,v2,⋯,vn can be obtained, where n is the number of vertices in the precedence graph. This sequence is called the topological order (TO), and it reflects the sequence of assembly tasks. For example, if task v1 is the immediate or indirect predecessor of task v2, then task v1 will be in front of task v2 in the TO; that is, task v1 will be assigned to the station before v2. It should be noted that if the vertices in the vertex set Vs satisfy the spatial constraint, then Vs will be considered as a whole in topological sorting. The topological sorting algorithm constantly searches for vertices without predecessors. A vertex with no predecessor will be inserted in the TO and removed from the precedence graph. The algorithm is completed when all of the vertices are in the TO. If the TO of all of the vertices is not available, then the assembly processes represented by the precedence graph are infeasible. According to [35], the procedure of the topological sorting algorithm is presented in Algorithm 1.Algorithm 1: Pseudocode of topological sorting.
Procedure: Topological SortingInput: Precedence graph; Let n be the number of vertices; Let T=∅ be the TO of the precedence graph.Output: A nonempty TO (T).Fori=1 to ndoBeginIf every vertex has a predecessorThen the precedence graph is infeasible stop;Else pick a vertex vi which has no predecessors;T=T∪vi;Deletevi and all edges leading out of vi from precedence graphEndEndThe advantage of the topological sorting algorithm is to maximize the efficiency of task assignment. It can generate multiple topological orders. Ten topological orders of Figure1, in which the precedence constraints between tasks can always be satisfied, are presented in Table 1 . Therefore, the use of these topological orders may improve the efficiency of ALBP.Table 1
Ten topological orders of Figure1.
No.Topological orders17, 2, 26, 6, 27, 1, 9, 10, 14, 3, 25, 4, 12, 15, 19, 5, 21, 13, 8, 11, 16, 30, 18, 17, 20, 22, 23, 28, 31, 24, 2922, 26, 7, 12, 6, 9, 10, 15, 1, 27, 25, 19, 14, 21, 3, 4, 5, 13, 8, 30, 11, 16, 18, 17, 22, 20, 31, 23, 28, 24, 2931, 7, 3, 25, 12, 9, 10, 4, 2, 5, 14, 13, 15, 6, 30, 19, 8, 16, 11, 26, 17, 27, 18, 20, 31, 21, 22, 23, 28, 24, 2947, 9, 12, 1, 25, 2, 10, 6, 26, 15, 14, 19, 27, 21, 3, 4, 5, 13, 8, 16, 11, 18, 30, 17, 22, 20, 23, 31, 24, 28, 2952, 26, 27, 7, 12, 1, 25, 9, 3, 10, 6, 14, 15, 19, 21, 4, 5, 13, 30, 8, 16, 18, 11, 17, 20, 31, 22, 23, 28, 24, 2961, 7, 9, 3, 2, 4, 5, 26, 12, 10, 15, 27, 14, 19, 6, 8, 11, 21, 13, 25, 17, 16, 18, 22, 20, 30, 23, 28, 24, 29, 3177, 12, 1, 3, 4, 2, 9, 5, 6, 10, 25, 15, 26, 19, 27, 14, 13, 30, 21, 8, 11, 17, 20, 31, 16, 18, 22, 23, 24, 28, 2981, 3, 4, 5, 2, 6, 26, 8, 11, 27, 7, 9, 10, 14, 12, 15, 25, 13, 17, 16, 19, 20, 18, 21, 30, 31, 22, 23, 24, 28, 2991, 2, 6, 26, 27, 3, 7, 25, 4, 9, 5, 10, 13, 14, 30, 12, 8, 15, 11, 17, 20, 31, 16, 19, 18, 21, 22, 23, 28, 24, 29102, 1, 3, 7, 25, 9, 10, 26, 12, 15, 27, 4, 14, 5, 19, 13, 6, 21, 30, 8, 16, 11, 17, 20, 31, 18, 22, 23, 24, 28, 29


## 3.1. Representation of Constraints between Assembly Tasks

The assembly processes of a product are decomposed into several assembly tasks, each comprising a series of actions that cannot or need not be divided further. The essence of ALBP is to assign a series of assembly tasks to a certain number of stations, while satisfying precedence constraints and specified cycle times. Precedence constraints are the most basic and important type of constraints in ALBP, reflecting the order of assembly tasks. Intuitively, assembly tasks and precedence constraints can be represented by a directed graph, called a precedence graph [33, 34]. In Figure 1, the circle represents the assembly task, and the straight line with an arrow indicates the precedence constraints. For products with complex structures (such as airplanes and cars), precedence constraints cannot fully express the relationships between assembly tasks. Spatial constraints and incompatible constraints between assembly tasks also must be considered. We introduce spatial constraints and incompatible constraints on the basis of the traditional precedence graph as follows.Figure 1
Precedence graph.There are two meanings of spatial constraints. Multiple associated assembly tasks must be completed on the same station, and there is a maximum number of assembly tasks that can be allocated to one station. In actual production, assembly tasks that have cooperative relationships or are of the same kind are usually assigned to the same station to improve efficiency. At the same time, the number of assembly tasks that can be assigned to one station is limited to ensure that each operator has sufficient space. In Figure1, the ellipse represents the spatial constraint, and the assembly tasks within it must be assigned to the same station. The figure does not show the maximum number of tasks that can be allocated to a station; this will be quantified in the assembly line balancing model.Incompatible constraints mean that some assembly tasks cannot be assigned to the same station. For example, some tasks to measure quality usually cannot be placed in the same location as other tasks. In Figure1, assembly tasks within dashed circles of the same color cannot be assigned to the same station.


## 3.2. Topological Sorting for Precedence Graph

Assembly tasks are arranged in a linear sequence on an actual assembly line, and ALBP-I is a reasonable division of assembly tasks. To guarantee the precedence constraints between assembly tasks, a topological sorting algorithm preprocesses them in the precedence graph to form a topological order.The precedence graph is a directed acyclic graph. Nodes represent assembly tasks, and directed edges represent the sequences between them. The precedence graph is represented as follows:(1)PG=V,E,fspatial,fincompatible,where V and E represent the sets of vertices and edges, respectively. If there is a directed edge e=a,b, then task a is the immediate predecessor of task b. If there is a directed path a,⋯,b∈V, then task a is the indirect predecessor of task b. fspatial represents spatial constraints. If fspatialVs=1, then there is a spatial constraint for the assembly tasks in the vertex set Vs; otherwise, there is not. fincompatible represents incompatible constraints. If fincompatibleVc=1, then the assembly task in vertex set Vc satisfies the incompatible constraint; otherwise, there is no such constraint; Vs,Vc∈V.Through the topological sorting algorithm, a linear sequencev1,v2,⋯,vn can be obtained, where n is the number of vertices in the precedence graph. This sequence is called the topological order (TO), and it reflects the sequence of assembly tasks. For example, if task v1 is the immediate or indirect predecessor of task v2, then task v1 will be in front of task v2 in the TO; that is, task v1 will be assigned to the station before v2. It should be noted that if the vertices in the vertex set Vs satisfy the spatial constraint, then Vs will be considered as a whole in topological sorting. The topological sorting algorithm constantly searches for vertices without predecessors. A vertex with no predecessor will be inserted in the TO and removed from the precedence graph. The algorithm is completed when all of the vertices are in the TO. If the TO of all of the vertices is not available, then the assembly processes represented by the precedence graph are infeasible. According to [35], the procedure of the topological sorting algorithm is presented in Algorithm 1.Algorithm 1: Pseudocode of topological sorting.
Procedure: Topological SortingInput: Precedence graph; Let n be the number of vertices; Let T=∅ be the TO of the precedence graph.Output: A nonempty TO (T).Fori=1 to ndoBeginIf every vertex has a predecessorThen the precedence graph is infeasible stop;Else pick a vertex vi which has no predecessors;T=T∪vi;Deletevi and all edges leading out of vi from precedence graphEndEndThe advantage of the topological sorting algorithm is to maximize the efficiency of task assignment. It can generate multiple topological orders. Ten topological orders of Figure1, in which the precedence constraints between tasks can always be satisfied, are presented in Table 1 . Therefore, the use of these topological orders may improve the efficiency of ALBP.Table 1
Ten topological orders of Figure1.
No.Topological orders17, 2, 26, 6, 27, 1, 9, 10, 14, 3, 25, 4, 12, 15, 19, 5, 21, 13, 8, 11, 16, 30, 18, 17, 20, 22, 23, 28, 31, 24, 2922, 26, 7, 12, 6, 9, 10, 15, 1, 27, 25, 19, 14, 21, 3, 4, 5, 13, 8, 30, 11, 16, 18, 17, 22, 20, 31, 23, 28, 24, 2931, 7, 3, 25, 12, 9, 10, 4, 2, 5, 14, 13, 15, 6, 30, 19, 8, 16, 11, 26, 17, 27, 18, 20, 31, 21, 22, 23, 28, 24, 2947, 9, 12, 1, 25, 2, 10, 6, 26, 15, 14, 19, 27, 21, 3, 4, 5, 13, 8, 16, 11, 18, 30, 17, 22, 20, 23, 31, 24, 28, 2952, 26, 27, 7, 12, 1, 25, 9, 3, 10, 6, 14, 15, 19, 21, 4, 5, 13, 30, 8, 16, 18, 11, 17, 20, 31, 22, 23, 28, 24, 2961, 7, 9, 3, 2, 4, 5, 26, 12, 10, 15, 27, 14, 19, 6, 8, 11, 21, 13, 25, 17, 16, 18, 22, 20, 30, 23, 28, 24, 29, 3177, 12, 1, 3, 4, 2, 9, 5, 6, 10, 25, 15, 26, 19, 27, 14, 13, 30, 21, 8, 11, 17, 20, 31, 16, 18, 22, 23, 24, 28, 2981, 3, 4, 5, 2, 6, 26, 8, 11, 27, 7, 9, 10, 14, 12, 15, 25, 13, 17, 16, 19, 20, 18, 21, 30, 31, 22, 23, 24, 28, 2991, 2, 6, 26, 27, 3, 7, 25, 4, 9, 5, 10, 13, 14, 30, 12, 8, 15, 11, 17, 20, 31, 16, 19, 18, 21, 22, 23, 28, 24, 29102, 1, 3, 7, 25, 9, 10, 26, 12, 15, 27, 4, 14, 5, 19, 13, 6, 21, 30, 8, 16, 11, 17, 20, 31, 18, 22, 23, 24, 28, 29


## 4. Mathematical Modeling

Traditional ALBP-I aims to minimize the number of stations and corresponding task assignments and meet the fixed cycle time. It must be changed when the cycle time is uncertain. In the assembly line design phase, a company’s forecast order quantity may be in an interval; hence, it is not fixed, and the cycle time of the assembly line is also in an interval. In this case, ALBP-I must be expanded to what we call EALBP-I. The mathematical models of ALBP-I and EALBP-I are established below, and their differences and similarities are discussed.


### 4.1. Notations

The symbols used in ALBP-I and EALBP-I are defined in Table2.Table 2
Notation used in mathematical models.
SymbolDefinitionIndexi, jTask indexkStation indexnNumber of taskspOperator’s skill level; 1, 2, and 3, respectively, indicate low, medium, and high skillParameterCCycle timemNumber of stationsCmaxMaximum cycle timeCminMinimum cycle timetipTime required to complete taski when operator’s skill level is pPijPrecedence constraints between tasksi and j. Pij=1 indicates precedence constraints; otherwise, there is no precedence constraint.SCij+Spatial constraint between tasksi and j. SCij+=1 indicates tasks must be assigned to the same station; otherwise, this is not required.SCij−Incompatible constraint between tasksi and j. SCij−=1 indicates the tasks cannot be assigned to the same station; otherwise, they can.RpNumber of operators with skill levelpOmaxMaximum number of tasks that can be accommodated on a stationVariablexikBinary variable.xik=1 indicates that task i is assigned to station k.ripBinary variable.rip=1 indicates that operators with skill level p are assigned to task i.ykBinary variable.yk=1 indicates that station k is enabled.


### 4.2. Modeling under Certain Cycle Time

ALBP-I assumes that the cycle time is determined to minimize the number of stations; that is, minimal resources, such as equipment and operators, are required. The operator’s skill level is an important factor affecting the cycle time of an assembly line, and it can be dynamically adjusted and configured during operation. Therefore, in assembly line design, there is a need to combine the task assignment with the operator’s skill level to obtain the optimal solution [36]. The mathematical model of ALBP-I is as follows:(2)min∑k=1myk,subject to(3)∑i=1nxikriptip≤Cyk,∀k=1,2,⋯,m,∀p=1,2,3,(4)∑k=1mxik=1,∀i=1,2,⋯,n,(5)∑k=1mk×xik≤∑k=1mk×xjk,∀Pij=1,∀i=1,2,⋯,n,∀j=1,2,⋯,n,(6)yk+1≤yk,∀k=1,2,⋯,m,(7)xik=xjk,∀i,j∈SCij+,∀k=1,2,⋯,m,(8)xik+xjk≤1,∀i,j∈SCij−,∀k=1,2,⋯,m,(9)∑i=1nxik≤Omax,∀k=1,2,⋯,m,(10)∑i=1nrip≤Rp,∀p=1,2,(11)xik∈0,1,∀i=1,2,⋯,n,∀k=1,2,⋯,m,(12)rip∈0,1,∀i=1,2,⋯,n,∀p=1,2,3,(13)yk∈0,1,∀k=1,2,⋯,m.Constraint (3) indicates that the total task time of each station does not exceed the cycle time C. Constraint (4) indicates that each task can only be assigned to one station. Constraint (5) represents the precedence constraints between tasks. Constraint (6) indicates that each station must be continuously enabled; that is, if station k is enabled, then station k − 1 must be enabled; otherwise, there will be a discontinuity in the station index. Constraint (7) indicates that a set of tasks need to be assigned to the same station. Constraint (8) indicates that there are incompatible constraints between tasks. Constraint (9) indicates the maximum number of tasks that can be assigned to each station. Constraint (10) indicates that the number of operators assigned to a station should be less than the total number of available operators. Constraints (11)–(13) indicate that xik, rkp, and yk are binary variables.


### 4.3. Modeling under Uncertain Cycle Time

A dynamic market shows dynamic changes in the demand for products; that is, order quantities and delivery dates may be adjusted as the market changes. These differences require assembly lines to have different cycle times. To gain a competitive advantage, a company must respond promptly to these changes. To build a new assembly line to meet a new cycle time is costly. Therefore, such changes must be considered when designing an assembly line.Companies usually evaluate order quantities and forecast maxima and minima when they construct an assembly line. In this paper, the order quantity interval is converted to a cycle time interval, which is introduced in ALBP-I. Assume thatC0 is the nominal cycle time and D is the maximum change in the cycle time. The cycle time interval can be obtained as follows:(14)C∈C0−D,C0+D.The level of uncertaintyα is introduced, and the following two constraints are obtained:(15)C≤C0+αD,(16)C≥C0−αD,where α∈0,1. In the design phase of an assembly line, decision makers can choose a reasonable value of α to cope with uncertainty in the cycle time.Our goal is to find the most scientific number of stations and task assignments during the design phase of an assembly line, so that a company can best cope with the uncertainty of the cycle time. LetCmax=C0−αD and Cmin=C0+αD. We add the following constraints to the mathematical model of ALBP-I:(17)Cmin−C≤0,(18)C−Cmax≤0.The objective must then be adjusted accordingly. If (2) is used as the objective, then the calculation will always satisfy the maximum cycle time. Therefore, a new objective is proposed:(19)min∑k=1mykandminCCmin.A weighted summation method is used to convert (19) to a single objective:(20)minw1×∑k=1myk+w2×CCmin,where w1 and w2 are weight coefficients. According to (19), w2 should be greater than w1, which reflects the influence of the cycle time interval on the objective.


## 4.1. Notations

The symbols used in ALBP-I and EALBP-I are defined in Table2.Table 2
Notation used in mathematical models.
SymbolDefinitionIndexi, jTask indexkStation indexnNumber of taskspOperator’s skill level; 1, 2, and 3, respectively, indicate low, medium, and high skillParameterCCycle timemNumber of stationsCmaxMaximum cycle timeCminMinimum cycle timetipTime required to complete taski when operator’s skill level is pPijPrecedence constraints between tasksi and j. Pij=1 indicates precedence constraints; otherwise, there is no precedence constraint.SCij+Spatial constraint between tasksi and j. SCij+=1 indicates tasks must be assigned to the same station; otherwise, this is not required.SCij−Incompatible constraint between tasksi and j. SCij−=1 indicates the tasks cannot be assigned to the same station; otherwise, they can.RpNumber of operators with skill levelpOmaxMaximum number of tasks that can be accommodated on a stationVariablexikBinary variable.xik=1 indicates that task i is assigned to station k.ripBinary variable.rip=1 indicates that operators with skill level p are assigned to task i.ykBinary variable.yk=1 indicates that station k is enabled.


## 4.2. Modeling under Certain Cycle Time

ALBP-I assumes that the cycle time is determined to minimize the number of stations; that is, minimal resources, such as equipment and operators, are required. The operator’s skill level is an important factor affecting the cycle time of an assembly line, and it can be dynamically adjusted and configured during operation. Therefore, in assembly line design, there is a need to combine the task assignment with the operator’s skill level to obtain the optimal solution [36]. The mathematical model of ALBP-I is as follows:(2)min∑k=1myk,subject to(3)∑i=1nxikriptip≤Cyk,∀k=1,2,⋯,m,∀p=1,2,3,(4)∑k=1mxik=1,∀i=1,2,⋯,n,(5)∑k=1mk×xik≤∑k=1mk×xjk,∀Pij=1,∀i=1,2,⋯,n,∀j=1,2,⋯,n,(6)yk+1≤yk,∀k=1,2,⋯,m,(7)xik=xjk,∀i,j∈SCij+,∀k=1,2,⋯,m,(8)xik+xjk≤1,∀i,j∈SCij−,∀k=1,2,⋯,m,(9)∑i=1nxik≤Omax,∀k=1,2,⋯,m,(10)∑i=1nrip≤Rp,∀p=1,2,(11)xik∈0,1,∀i=1,2,⋯,n,∀k=1,2,⋯,m,(12)rip∈0,1,∀i=1,2,⋯,n,∀p=1,2,3,(13)yk∈0,1,∀k=1,2,⋯,m.Constraint (3) indicates that the total task time of each station does not exceed the cycle time C. Constraint (4) indicates that each task can only be assigned to one station. Constraint (5) represents the precedence constraints between tasks. Constraint (6) indicates that each station must be continuously enabled; that is, if station k is enabled, then station k − 1 must be enabled; otherwise, there will be a discontinuity in the station index. Constraint (7) indicates that a set of tasks need to be assigned to the same station. Constraint (8) indicates that there are incompatible constraints between tasks. Constraint (9) indicates the maximum number of tasks that can be assigned to each station. Constraint (10) indicates that the number of operators assigned to a station should be less than the total number of available operators. Constraints (11)–(13) indicate that xik, rkp, and yk are binary variables.


## 4.3. Modeling under Uncertain Cycle Time

A dynamic market shows dynamic changes in the demand for products; that is, order quantities and delivery dates may be adjusted as the market changes. These differences require assembly lines to have different cycle times. To gain a competitive advantage, a company must respond promptly to these changes. To build a new assembly line to meet a new cycle time is costly. Therefore, such changes must be considered when designing an assembly line.Companies usually evaluate order quantities and forecast maxima and minima when they construct an assembly line. In this paper, the order quantity interval is converted to a cycle time interval, which is introduced in ALBP-I. Assume thatC0 is the nominal cycle time and D is the maximum change in the cycle time. The cycle time interval can be obtained as follows:(14)C∈C0−D,C0+D.The level of uncertaintyα is introduced, and the following two constraints are obtained:(15)C≤C0+αD,(16)C≥C0−αD,where α∈0,1. In the design phase of an assembly line, decision makers can choose a reasonable value of α to cope with uncertainty in the cycle time.Our goal is to find the most scientific number of stations and task assignments during the design phase of an assembly line, so that a company can best cope with the uncertainty of the cycle time. LetCmax=C0−αD and Cmin=C0+αD. We add the following constraints to the mathematical model of ALBP-I:(17)Cmin−C≤0,(18)C−Cmax≤0.The objective must then be adjusted accordingly. If (2) is used as the objective, then the calculation will always satisfy the maximum cycle time. Therefore, a new objective is proposed:(19)min∑k=1mykandminCCmin.A weighted summation method is used to convert (19) to a single objective:(20)minw1×∑k=1myk+w2×CCmin,where w1 and w2 are weight coefficients. According to (19), w2 should be greater than w1, which reflects the influence of the cycle time interval on the objective.


## 5. Implementation of Multipopulation Genetic Algorithm

Individual properties in the population tend to be consistent after several iterations of the genetic algorithm, which causes convergence to a local solution. We propose a multipopulation genetic algorithm (MGA) for ALBP to improve the genetic algorithm.Figure2 shows the flowchart of the two-population genetic algorithm, whose basic idea is to replace the single population of the genetic algorithm with two subpopulations which evolve independently and then make an individual exchange according to rules until the optimal solution is found. The multipopulation genetic algorithm is characterized by faster convergence while maintaining population diversity. Through the extension of Figure 2, the flowchart of multipopulation genetic algorithm can be easily obtained. We introduce the main steps to solve EALBP-I using the multipopulation genetic algorithm:Step 1: Set up parameters.SubP is the number of subpopulations, PS is the number of individuals in each subpopulation, PM is the probability of mutation, PC is the probability of crossover, and MR is the migration rate.Step 2: Generate initial population. The chromosome structure has three layers. The first is the assembly task, with lengthn. The second is the cycle time, with code length 1. The third is the operator’s skill level for each assembly task, with length n. To ensure that the generated initial population always satisfies the precedence constraint, the topological sorting algorithm proposed in Section 3.2 is used to generate the initial population.Step 3: Calculate fitness values. The calculation of fitness for MGA is performed according to (19), with fitness function:(21)Fi=1fi,whereFi is the fitness value of the ith individual and fi is the value of the objective function calculated by the ith individual.Step 4: Selection operation. We use roulette to select individuals; i.e., an individual’s probability of selection is determined by the ratio of the individual’s fitness to the total fitness of all individuals.Step 5: Crossover operation. A two-point crossover method is adopted. Using the Buxey example [12], as illustrated in Figure 3(a), two crossover points are randomly generated, as defined by Cross_Point_1 and Cross_Point_2. The two parent chromosomes are divided into three parts: head, body, and tail. The gene segment, Body_1, in parent chromosome 1 can be found in parent chromosome 2. These genes are sorted by the gene sequence in parent chromosome 2. A new gene segment, Body_1_new, is generated, as illustrated in Figure 3(b), to replace Body_1 in parent chromosome 1. A new chromosome, child 1, is formed, as shown in Figure 3(c). By the same method, we can obtain another new chromosome, child 2, as illustrated in Figure 3(c). This crossover operation has the advantage that all of the tasks meet the sequence constraints. The child chromosomes are evaluated after crossover. If the fitness of a child is improved, then it is retained, and otherwise it is abandoned.Step 6: Mutation operation. We use a single-point mutation method; that is, a code in the chromosome is randomly selected, and the mutation of the selected code is performed according to a certain probability.Step 7: Population migration. This is performed according to a randomly generated migration rate. When the generated migration rate exceeds a given value, population migration is performed.Figure 2
Flowchart of multipopulation genetic algorithm.Figure 3
Example of crossover: (a) selection of crossover point, (b) crossover operation and (c) results.


## 6. Results and Analysis

We used basic data fromhttps://assembly-line-balancing.de/ to verify the validity of the proposed methods. The basic data were adapted according to the needs of this paper. Cases with task numbers 11, 21, 29, 35, 83, and 111 were selected to verify the adaptability of the proposed methods. For each problem, the operator’s skill levels (low, medium, high) were considered. The higher the skill level, the shorter the task time. The task time in the basic data was set to that of operators with high skill. This was multiplied by a factor of 1.2 or 1.1 to obtain the task time of operators with low and medium skill, respectively. At the same time, the number of operators with low skill, medium skill, and high skill was set to be 50% of the number of tasks, respectively. Omax=15. Referring to [37–39], MGA had the following initial configuration: SubP = 5, PS = 50, PM = 0.1, PC = 0.8, and MR = 0.1.The level of uncertaintyα was assumed to vary within a certain range. The α level determined the cycle time interval. The cycle time was assumed to change within C01±α. The number of stations at different α levels was calculated, as displayed in Table 3. Table 2 provides four types of results, namely, robust, regular, best, and worst. It should be noted that the robust results considered the uncertainty in cycle time, expressed as an interval. The regular results considered the normal cycle time. The best results were calculated when the cycle time reached C0+C0α. The worst result was calculated when the cycle time reached C0−C0α. As can be seen in Table 3, when the number of tasks was 11, 21, or 29, the number of stations in a robust situation was consistent with that in a regular situation for different α levels. When the number of tasks was 35, the number of stations in a robust situation was slightly larger than that in a regular situation for different α levels. When the number of tasks was 83 or 111, as α increased, the number of stations in a robust situation was equal to or larger than that in a regular situation. That is, the lower bound of the cycle time interval had an increasing influence on the number of stations as the number of tasks and α increased. As is easily seen from Table 3, as α increased, the number of stations in the best situation gradually decreased, which was due to the gradual increase of Cmax. With the increase of α, the number of stations in the worst situation increased, which was due to the gradual decrease of Cmin. However, when α≥0.4, the number of stations in the worst situation may be unsolvable.Table 3
Number of stations for different problems andα levels.
Number of tasksαC0Number of stationsRobustRegularBestWorst110.11066560.21066580.31066480.410664—0.510664—210.12066670.22066580.32066590.420664—0.520764—290.14010109110.24010108120.34010108130.44010107—0.54010107—350.150121110130.25012119—0.35012119—0.45012118—0.55012118—830.18000111110130.2800012119140.3800013119150.4800014118—0.5800014118—1110.12500077780.22500077690.325000876100.425000975120.52500097514After introducing the level of uncertaintyα, the cycle time becomes a variable that can be changed. Different numbers of stations, as well as different task and operator assignments, will output different cycle times. The cycle time at different α levels is calculated for each situation in Table 3. As shown in Table 4, the cycle time in the regular situation is basically consistent with C0, because the influence of uncertainty is not considered. For the six examples in Table 4, the cycle time of the robust situation mostly decreases as α increases. Hence, as α increases, the cycle time calculated by EALBP-I is closer to C0−C0α, as shown in Figures 4−7. For the best situation, the cycle time will increase with α, which is caused by the increase of C0+C0α. For the worst situation, the cycle time will decrease as α increases, because of the decrease of C0−C0α. However, when α≥0.4, the cycle time in the worst situation may be unsolvable, which is consistent with the results in Table 3.Table 4
Cycle times for different problems andα levels.
Number of tasksαCycle timesRobustRegularBestWorst110.199.81190.299.811.57.70.399.812.870.499.813.9—0.59.39.814.4—210.118.619.922180.219.319.924160.31919.925.8140.418.519.927.9—0.516.119.930—290.1374044360.236.84047.4320.336.8405227.90.436.34055.2—0.536.44059.6—350.147.45054.7450.246.25059.9—0.3455065—0.445.75070—0.545.45074.8—830.17456.27991.68774.77184.10.270917991.6956663620.36632.17991.610291.755710.46146.97991.611116.6—0.56219.37991.611762.8—1110.123462.724894.626791.1221250.223813.524894.629963.519954.60.320398.424894.632481.017428.30.419043.324894.634676.814975.80.518572.724894.637297.812320.7Figure 4
Cycle times for problem with 21 tasks.Figure 5
Cycle times for problem with 29 tasks.Figure 6
Cycle times for problem with 83 tasks.Figure 7
Cycle times for problem with 111 tasks.In EALBP-I, the number of stations and the cycle time are both variables. Therefore, EALBP-I is actually a variant of SALBP-E. To compare the robust situation with the other three situations, production efficiencyE is introduced. This is the reciprocal of the product of the number of stations and the cycle time; i.e., E=1/mC [40]. An important goal of assembly line design is to maximize productivity. According to Tables 3 and 4, the production efficiency is obtained for the six cases, as shown in Figures 8–13.Figure 8
Efficiency for problem with 11 tasks.Figure 9
Efficiency for problem with 21 tasks.Figure 10
Efficiency for problem with 29 tasks.Figure 11
Efficiency for problem with 35 tasks.Figure 12
Efficiency for problem with 83 tasks.Figure 13
Efficiency for problem with 111 tasks.The efficiency in the robust situation is generally the highest. As shown in Figures9 and 13, when the number of tasks is 21 and 111, the efficiency of the robust situation is the highest. In Figures 8, 10, and 12, only when α=0.3, the efficiency of the robust situation is less than that in one of the other situations. In Figure 11, when α≥0.3, the efficiency of the robust situation is higher than that in the other three situations.We take the cases with 21 tasks to validate the effectiveness of MGA. It is assumed thatα=0.1. The maximum number of iterations is set to 400. The weight coefficients in expression (20) are w1=0.2 and w2=1. The general GA [41] and MGA in this study are used to solve EALBP-I. The results are presented in Table 5. The number of stations is the same. However, the maximum assembly time calculated by MGA is 18.6 s, which is less than 19.0 s, as calculated by GA. The convergence curves of MGA and GA are presented in Figure 14. These indicate that MGA converges faster than GA.Table 5
Assembly balancing result of MGA versus general GA.
Station no.MGAStation no.GASet of tasksTotal assembly time (s)Set of tasksTotal assembly time (s)11, 3, 418.511, 2, 318.225, 717.824, 5, 618.9314, 2, 6, 2118.1321, 7, 1419.048, 9, 12, 11, 1018.648, 9, 12, 10, 1118.9515, 16, 13, 1818.6513, 15, 18, 1619.0617, 20, 1918.6617, 20, 1918.4Figure 14
Convergence curves of MGA versus general GA.


## 7. Conclusions

With fierce market competition, the assembly line is susceptible to some uncertainties, the influence of which on assembly line balancing is of concern to manufacturers. In this study, an uncertain cycle time is introduced to ALBP. Spatial and incompatible constraints are added based on the traditional precedence graph. Spatial constraints are suitable to situations where multiple assembly tasks must be assigned to the same station. Incompatible constraints are suitable to situations where two assembly tasks must be assigned to different stations. The introduction of these constraints makes ALBP more suitable to engineering practice. Two mathematical models of ALBP are established. In the first, the cycle time is fixed, and the objective is to minimize the number of stations. In the second, the cycle time is in a changeable interval, and the objective is to minimize both the number of stations and the cycle time. The level of uncertaintyα is introduced to adjust the range of the cycle time interval. In addition, operator skill is defined by three levels, and the selection of skill level is integrated into ALBP. Finally, a multipopulation genetic algorithm is used to solve our model. Six cases are analyzed in the study, each considering robust situation, regular situation, best situation, and worst situation. The research results show that the cycle time interval has a significant influence on the assembly line balancing problem. The current model is suitable to the situation of a new assembly line for a new product, in which case observations or knowledge of the cycle time may be limited. Designers can use an interval to represent the cycle time. In the future, uncertain cycle and task times will be considered in ALBP.



---

*Source: 2785278-2020-06-25.xml*