A Three-Stage Optimization Method for Assembly Line Balancing Problem

Considering the characteristics of multimodels production pattern on assembly line, the assembly line balancing problem which is non-deterministic polynomial hard becomes more challenging to complete. In this article, we propose a reformulation of simple assembly line balancing problem based on Dantzig-Wolfe decomposition. New models of the master problem and subproblems in this algorithm are built. We implement a branching rule which is suited to seeking integer solutions of the problem. A new three-stage branch-and-price algorithm is designed to accelerate the process of searching the branch-and-bound tree. Extensive computational experiments on benchmark data sets, as well as a real industry case are conducted. The numerical results validate the feasibility and effectiveness of the proposed method which performs efficiently on various cases. Effects on optimization results considering the characteristics of the instance sets are analyzed. Results show that the three-stage branch-and-price algorithm is superior to the classic branch-and-price algorithm in terms of solution quality and computing time.

SECTION I. Introduction

The production system of passenger vehicle manufacturing consists of four main areas: Press shop, Body shop, Paint shop and Assembly shop. Assembly represents the final phase in which parts are sequentially installed on the semi-finished vehicle body as it moves from one work station to the next. Fig. 1 shows the structure of main assembly line which consists of more than 300 work stations (gray squares with green borders) at Plant Tiexi, BMW Brilliance. Six models are produced in Plant Tiexi currently, and there are 2000+ parts designed to be installed on every vehicle. Planners are responsible for designing a line balancing scheme for each model of cars according to the structure of the assembly line, the production rate and work force. However, the line balancing work is done manually depending on planners’ own experiences now. These plans need to be updated often as orders change and new models are planned to be produced. Thus, the line balancing work becomes more challenging to be finished. It is crucial to design an algorithm which could solve the problem efficiently and correctly. The problem of assigning tasks to sequential stations in such a way that one or more objectives are optimized subject to some specific constraints is called the assembly line balancing problem (ALBP). The basic formulation of assembly line balancing problem, in which one worker is assigned to a work station, is known as the simple assembly line balancing problem (SALBP). SALBP can be classified into two groups: simple assembly line balancing problem type-1 (SALBP-I) and simple assembly line balancing problem type-2 (SALBP-II). In SALBP-I, the objective is to minimize the number of work stations for a given cycle time, while in SALBP-II the objective is to minimize the cycle time for a given number of work stations. SALBP-I could be applied at the stage of planning assembly process for a new vehicle before its start of production (SOP) or optimization of production cost after SOP. SALBP-II matches for the reconfiguration of the assembly line when the production rate increase or the take rate of specific car model changes during production. We study SALBP-I to deal with practical demands of automotive industry that more models are planned to be produced on one assembly line.

FIGURE 1.

Assembly line system at Plant Tiexi, BMW Brilliance Automotive.

The remainder of this article is structured as follows: Section 2 discusses research works of SALBP-I done in literature and the column generation method used in scheduling and planning area. In Section 3, we describe the objective and constraints of SALBP-I, and present a new reformulation of SALBP-I based on the Dantzig-Wolfe decomposition method. In Section 4, we develop a branch-and-price algorithm which integrates the column generation method in the frame of branch-and-bound approach to solve the mathematical model built in Section 3. In this article, a specific branching strategy is implemented in the branch-and-price algorithm. In Section 5, experiments based on benchmark data sets as well as a test for the real production case, which locates in the production area of the vehicle’s frontend pre-assembly, at one premier brand OEM’s assembly shop are conducted. Computational results are presented and analyzed Section 6. Conclusions and further research work directions are stated in the final part.

SECTION II. Literature Review

There exist a large number of models and methodologies for the assembly line balancing problem, and we will focus our review on the researches of the simple assembly line balancing problem.

Baybars [1] presented a survey of exact algorithms for the simple assembly line balancing problem. He concluded that only the enumerative techniques (i.e., branch and bound (B&B) or searching methods) had been extensively applied to SALBP-I among the four primary approaches to solve integer programming (IP) problems (cutting plane techniques, enumerative techniques, partitioning methods and group theory). Scholl and Becker [2] also reviewed the exact procedures for SALBP-I. He classified most exact solutions into two subdivisions: branch and bound (B&B) procedures and dynamic programming (DP) approaches. Charlton and Death [3] defined a general B&B method for machine scheduling. They utilized the solution of a critical path problem to yield a smallest lower bound for each iteration of the algorithm. Jackson [4] first constructed the algorithm for SALBP-I, using an unconventional DP method. Held et al. [5] also reported a new DP algorithm with the introduction of the notion of ‘feasible subsets’ and ‘feasible sequences’. Due to the severe computational and storage requirements of the DP methods, few other significant DP approaches were reported until Schrage and Baker [6] proposed an efficient method within the framework of DP approach. Queyranne [7] has also presented a hybrid DP and B&B models, suggesting that such an approach may be more efficient compared to individual DP or B&B approaches. Besides, Bockmayr and Pisaruk [8] developed a branch and cut procedure based on integer programming formulations with additional valid inequalities and constraint programming techniques. Pinnoi and Wilhelm [9], [10] also proposed branch and cut procedures for SALBP-I connected with vertical balancing as well as for more general problems. Recently, Peeters and Degraeve [11] presented a Dantzig-Wolfe type formulation of SALBP-I. Linear programming (LP) relaxation of this formulation was solved by using column generation combined with subgradient optimization. Pastor and Ferrer [12] presented an improved mathematical program to solve SALBP. They provided a more effective mathematical model by adding an additional set of constraints. An initial pre-process is implemented to calculate the range of work stations for different tasks. Vila and Pereira [13] studied the assembly line worker assignment and balancing problem using a branch, bound and remember algorithm. The branch, bound and remember algorithm utilized the characteristics of a dynamic programming method.

Intelligent algorithms are also widely used on various types of the general assembly line balancing problem. Rubinovitz and Levitin [14], Kim et al. [15] and Sabuncuoglu et al. [16] developed genetic algorithms for the SALBP. Ponnambalam et al. [17] presented a multiobjective genetic algorithm for solving the SALBP with a given cycle time. Yu and Yin [18] designed an adaptive genetic algorithm in which the probability of crossover and that of mutation are dynamically adjusted according to the individual’s fitness value. Baykasoglu [19] proposed a simulated annealing algorithm for simple assembly line balancing problems. Seyed-Alagheband et al. [20] constructed a mathematical model and a novel simulated annealing (SA) algorithm to solve the general assembly line balancing problem aiming at minimization of the cycle time with a given number of work stations. Lapierre et al. [21] stated a new tabu search algorithm (TSA) for SALBP-I and verified it with a real industrial data set. Annarongsri and Limnararat [22] presented a hybrid tabu search method, which combined the tabu search with the genetic algorithm, for the SALBP-I. Fattahi et al. [23] developed a mathematical model and ant colony optimization method for SALBP-I. Lai and Liu [24] applied an ant colony algorithm to solve the SALBP-II.

Due to the fact that SALBP is a class of NP-hard optimization problem, effective exact and heuristic procedures can only obtain feasible solutions on medium size instances. Both the number of nodes generated in branch-and-bound procedures and the computational demands of a DP method grow exponentially as the problem size increases [1]. Most exact algorithms have large computer memory requirements, since the enumerating procedures which assign tasks to stations do not strictly work stage-by-stage [2]. In general, when the number of tasks is large, all exact algorithms fail, in the sense that the CPU times grow very rapidly [1]. Thus, algorithms of SALBP for solving large-scale instances are necessary to be studied.

Column generation has proven to be one of the most successful approaches for solving large-scale integer programming (IP). Three types of column generation approaches have been used to solve problems with a huge number of columns. Rather than enumerating so many columns explicitly, these methods deal with them implicitly, generating a selected set. The master problem, which contains a part of columns of original problem’s solution, is defined as the Restricted Master Problem (RMP) in column generation.

In the Type I approach, an auxiliary model is employed to generate the set of feasible columns, and a RMP is built to optimize over those generated columns obtaining the best subset. Besides accepting columns from the auxiliary model, there is no interaction between the restricted master problem and the auxiliary model. This method was successfully applied to airline crew scheduling problems in the 1960s and 1970s [25], [26]. Type II approach of column generation includes the interaction between the restricted master problem and subproblems. The restricted master problem provides dual variable values as the coefficients of the subproblems’ objective function. These data could direct the search for improving columns in subproblems. The subproblem chooses nonbasic columns which could improve the master problem with the best reduced cost. Gilmore and Gomory [27] first devised the Type II methodology to the cutting stock (CS) problem. A comprehensive algorithm was designed to form a prototype for other applications. Gilmore and Gomory [28] also proposed further problem-specific techniques to facilitate this algorithm. Balinski and Quandt [29] first suggested formulating the vehicle routing problems with time windows (VRPTW) as a set covering problem and Cullen et al. [30] first devised a heuristic that exploited the related set partitioning form. Wilhelm [31] applied the column generation method to the assembly system design with tool changes problem. Type III column generation applied Dantzig-Wolfe decomposition [32] to the linear relaxation of an IP. The restricted master problem provides dual values to the subproblem which generates the improving column during the iteration. Appelgren [33] first used the Dantzig-Wolfe decomposition to solve the ship scheduling problem which is an IP. Appelgren [34] integrated the Dantzig-Wolfe decomposition into a branch and bound searching frame dealing with the fractional solution. Type III column generation are successfully applied in cutting stock problems. Vance et al. [35], [36] proposed a branch and price algorithm to solve the CS problem. Savelsbergh [37] presented a method of branch-and-price for the generalized assignment problem. However, few works are done with applying the branch-and-price method to SALBP-I so far.

The aim of this article is to develop a branch-and-price algorithm to solve SALBP-I. The scale of practical line balancing problem in automotive industry becomes larger than decades ago, and we analyze the feasibility and efficiency of the proposed algorithm. We reformulate a new model for Dantzig-Wolfe decomposition of the SALBP-I that maintains precedence constraints in the master problem. Thus the subproblem could be designed as a knapsack problem with side constraints which is solvable in pseudo-polynomial time [38]. In our study, we construct an efficient frame of a three-stage branch-and-price algorithm, in which a heuristic algorithm gives the initial solution in the $1^{st}$ stage, column generation procedures are integrated in the $2^{nd}$ stage and an IP model is applied to solve the SALBP-I in the $3^{rd}$ stage, that could obtain the optimal solution in relatively short time. Effective branching strategy is determined for the unique characteristic of the column generation method.

SECTION III. Problem Description and Formulation

An assembly line is the manufacturing process in which vehicle components are added to an unfinished vehicle body in a sequential manner along a serial flow line. Fig. 2 shows an example of a precedence graph of an instance with 11 tasks. The number in the node represents the task number, and the value in the bracket is operation time for each task. The bar chart in Fig. 3 displays an optimal line balancing solution for this example. Pillars of different colors are marked with the task number 1 to 11, and the height of the pillar matches the length of task’s operation time. The task assignment to the four stations is: Station$_{1}=\{1,3\}$ , Station$_{2}=\{2,5\}$ , Station$_{3}=\{4,6,7,8,9\}$ , and Station$_{4}=\{10,11\}$ . We illustrate some basic concepts used in the process of assembly production in following texts.

1. Work station: A station is the basic unit constructing an assembly line where a number of operations are performed in a fix range of area.

2. Production rate: The Production rate means the hourly output of finished vehicles on the assembly line associated with the operation or sequence of lines.

3. Cycle time: The cycle time is planned according to the production rate of an assembly line. One cycle time begins to count when a product arrives at a station, and ends until the following product enters the same station. It gives a limitation that the workload of a worker should be less than the cycle time.

4. Task: The task is the operation in an assembly process. The sum of all operations adds up to the total work content for a vehicle assembly. The time it takes to perform a task is called operation time.

5. Workload: The workload means the ratio of sum of one worker’s total operation times needed for a vehicle to the station’s cycle time.

6. Precedence relationship: Precedence relationship defines the order in which operations of tasks should follow. Precedence constrains can be summarized in a precedence graph (activity-on-arrow diagram) that shows which operation has to be completed before a specific operation can start.

7. Predecessor: Predecessor refers to the set of tasks that must be done previous to one task according to the precedence relationship.

8. Successor: Successor refers to the set of tasks that follow one task in the precedence relationship.

FIGURE 2.

Precedence graph of an instance with 11 tasks.

FIGURE 3.

Solution example of the instance set with 11 tasks.

A. Problem Statement

Based on the above explanations of special terms, we define the SALBP-I as: The purpose of SALBP-I is to obtain the optimal line balancing plan with a minimum number of stations under a given cycle time. The line balancing solution must include the assignment of all tasks in the data set.

To ensure the feasibility of line balancing solution, we seek out rules that formed in the planning work. We state the key instructions for the assembly line balancing in details below.

1) Assembly Sequence

Assembly sequence is defined as the order in which parts are installed on the vehicle. In the study of line balancing problem, the precedence relations of tasks are edited on the basis of assembly sequence. Line balancing solution should satisfy the restrictions of the precedence relations. Since the assembly sequence depends on the structure of product, some parts must be installed first before its successors. Mechanical interference between parts happens if the operation breaks the precedence restrictions which may results in a shutdown of the assembly line.

2) Allowed Workplaces

The assembly line is usually designed as a main assembly line connected with several pre-assembly lines in the assembly shop. Furthermore, the main assembly line can be partitioned into several areas with different types of the vehicle’s conveyer which are marked with different colors in the structure layout in Fig. 4. Different structures of the conveyers and hangers make it possible to assemble parts to specific place on the vehicle for the process and ergonomic reasons. Thus, some operations should be completed on the recommended area. For example, all the operations of installing parts underneath the vehicle body are distributed to the line with tilting hangers (green area in Fig. 4: the tilting line) which could lift the car vertically and adjust the tilting angle. Parts assembly of doors, cockpit and frontend are completed in the independent pre-assembly areas noted in the layout. As a result, the line balancing work in the industry practice is done independently according to the assembly line’s different areas.

FIGURE 4.

Structure of the automotive assembly shop.

3) Relations Between Tasks

Some tasks require to be done continuously without a break. Thus we create a group for this kind of tasks. Considering special process requirements, some tasks must be completed on the same station, while some operations are exclusive in one station that there must be the station gap between them. For those parts with a large size, they need two or more workers cooperate together to finish the installations. These tasks are marked as simultaneous work.

4) Guidelines of the Work Organization

All of operations are finally edited in the Standard Work Specifications (SWS) document. The list of SWS states a clear description of the tasks content and how to finish it on each station. Total working time for one worker should be less than the cycle time. Besides, the worker is not allowed to take two tasks at the same time. One task description usually includes several physical actions. The calculation of workload of the worker is based on these actions. Using the standard methods of time measurement planners could compute the accurate task time.

B. Natural Formulation of SALBP-I

The definitions of the sets, parameters, and decision variables used later in this article are presented in Table 1, Table 2 and Table 3, respectively. We describe the SALBP-I as an IP formulation:

$$\begin{align*}&Minimize~\sum \limits _{j \in J} {y_{j}}. \tag{1}\\&\textit {Subject to}~ \\&\hphantom {\textit {Subject to}~}\sum \limits _{j \in J} {{a_{ij}}} = 1\quad \forall i \in I \tag{2}\\&\hphantom {\textit {Subject to}~}\sum \limits _{i \in I} {t_{i} \cdot {a_{ij}}} \le ct \cdot {y_{j}}\quad \forall j \in J \tag{3}\\&\hphantom {\textit {Subject to}~}\sum \limits _{j \in J} {j \cdot {a_{hj}}} \le \sum \limits _{j \in J} {j \cdot {a_{ij}}} \quad \forall i \in I,~h \in P(i) \qquad \tag{4}\\&\hphantom {\textit {Subject to}~}{a_{ij}} \in \left \{{ {0,1} }\right \}\quad \forall i \in I,~j \in J \tag{5}\\&\hphantom {\textit {Subject to}~}{y_{j}} \in \left \{{ {0,1} }\right \}\quad \forall j \in J \tag{6}\end{align*}$$

TABLE 1 Definitions of the Set Symbols

TABLE 2 Definitions of the Parameter Symbols

TABLE 3 Definitions of the Variables

The objective function of the SALBP-I is to complete all tasks assignment with the minimum number of stations. Constraints set (2) ensure that all tasks in the data set are done and every task (i) in the set is assigned to one work station. Constraints set (3) define the cycle time constraint for work stations. The sum of operation time of task on one station for each vehicle should be less than the cycle time of the assembly line. Once a station has been assigned to a task, then this station will be noted as open in the solution and the value of variable $y_{j}=1$ . Constraints set (4) describe the sequence requirement for all tasks. Any preceding operation for one specific task should not be assigned to stations later than the station where its reference task locates. The predecessor’s assignment is acceptable either before or in the same station with its reference task.

C. Dantzig-Wolfe Reformulation

Dantzig-Wolfe decomposition is a standard way to decompose an integer programming model into a linear programming master problem and one or several subproblems. Dantzig-Wolfe decomposition has a close connection to column generation method. Instead of focusing on which station a particular task is assigned to, the possible plans used to design the solution for each station are regarded as variables in the new formulation.

We construct a reformulation of SALBP-I:

$$\begin{align*}&\hspace {-0.5pc}Minimize~\sum \limits _{j \in J} {y_{j}}. \tag{7}\\&\hspace {-0.5pc}\textit {Subject to}~ \\&\hspace {-0.5pc}\hphantom {\textit {Subject to}~}\sum \limits _{j \in J}^{} {\sum \limits _{k \in {T_{j}}}^{} {\lambda _{k}^{j}} m_{ik}^{j}} = 1,\quad \forall i \in I \tag{8}\\&\hspace {-0.5pc}\hphantom {\textit {Subject to}~}\sum \limits _{j \in J} {j \!\cdot \! \sum \limits _{k \in {T_{j}}}^{}\! {\lambda _{k}^{j}} m_{hk}^{j}} \!\le \!\! \sum \limits _{j \in J} {j \!\cdot \! \sum \limits _{k \in {T_{j}}}^{}\! {\lambda _{k}^{j}} m_{ik}^{j}} \quad \!\!\forall i \!\in \!I,~h \!\in \! P(i) \\ \tag{9}\\&\hspace {-0.5pc}\hphantom {\textit {Subject to}~}\sum \limits _{k \in {T_{j}}}^{} {\sum \limits _{i \in I}^{} {t_{i}} \lambda _{k}^{j}} m_{ik}^{j} \le ct \cdot {y_{j}}\quad \forall j \in J \tag{10}\\&\hspace {-0.5pc}\hphantom {\textit {Subject to}~}\lambda _{k}^{j} \in \left \{{ {0,1} }\right \}\quad \forall k \in {T_{j}},~j \in J \tag{11}\\&\hspace {-0.5pc}\hphantom {\textit {Subject to}~}{y_{j}} \in \left \{{ {0,1} }\right \}\quad \forall j \in J \tag{12}\end{align*}$$

The objective of the reformulation is still to calculate the minimum number of work stations same as the original model (1). Constraint set (8) is derived from assignment constraint set (2). Sequence constraints of set (4) are reformulated in constraint set (9). Constraint (10) determines the cycle time constraint. Also, the value of variable $y_{j}=1$ if the feasible pattern k for station j is kept in the solution.

However, there will be an extremely huge number of columns in the matrix ${m}$ when the size of task set grows larger. It is not feasible to enumerate all of the possible combinations of task assignment. We implement the column generation method to solve the reformulated model of SALBP-I in another section below. This method transforms a problem into a master problem and pricing problems for improving the tractability of large-scale problems.

D. Column Generation Method

The fact that, there are a huge number of these combinations between the tasks and stations, results in considerable variables in the original model of SALBP-I. In the column generation method, the line balancing problem is designed as two parts: the restricted master problem and the subproblem which is also called the pricing problem. The restricted master problem covers partial sets of the assignment patterns. Other solution patterns are generated through solving the subproblem.

We derive the master problem based on the D-W decomposition of the original problem model as follows.

$$\begin{align*}&\hspace {-0.5pc}Minimize~\sum \limits _{j \in J} {\sum \limits _{p \in Q} {z_{j}^{p}} } \tag{13}\\&\hspace {-0.5pc}\textit {Subject to } \\&\hspace {-0.5pc}\hphantom {\textit {Subject to }}\sum \limits _{j \in J}^{} {\sum \limits _{p \in Q}^{} {A_{ij}^{p}} z_{j}^{p}} = 1\quad \forall i \in I \tag{14}\\&\hspace {-0.5pc}\hphantom {\textit {Subject to }}\sum \limits _{j \in J}^{}\! {\sum \limits _{p \in Q}^{} {j \!\cdot \! A_{hj}^{p}} z_{j}^{p}} \!\le \! \sum \limits _{j \in J}^{}\! {\sum \limits _{p \in Q}^{} {j \cdot A_{ij}^{p}} z_{j}^{p}}\quad \!\forall i \in I,h \in P(i) \\ \tag{15}\\&\hspace {-0.5pc}\hphantom {\textit {Subject to }}~0 \le z_{j}^{p} \le 1 \tag{16}\end{align*}$$

The minimization of the station number forms as the objective function value in the master problem. The matrix $A$ consists of the current set of task distributions. Each column represents an assignment pattern of one station. A heuristic approach for solving SALBP-I is developed to obtain the initial matrix. Details will be introduced in next section.

Task assignment constraints (8) and assembly sequence constraints (9) in the reformulation of model are kept in the restricted master problem. Constraints set (14) that matches the constraints set (8) in the original formulation ensures the task assignment constraints. Constraints set (15) makes sure that original sequence constraints set (9) could still be satisfied after the reformulation.

Variables in (16) which are relaxed binary variables of (11) define the master problem as a linear programming. The restricted master problem considers only a subset of the columns. Additional columns can be generated for the RMP by solving a subproblem. To check optimality, the subproblem, also called the pricing problem, is solved to identify columns to enter the basis of the master problem’s parameter set $A$ . Then the linear programming problem is reoptimized after adding this kind of columns.

According to the theory of the simplex algorithm, a column with the negative reduced cost value can improve the current solution. Thus, we set the minimum reduced cost as objective value of the pricing problem, and the constraints inherit from constraints of the original problem. The most negative reduced cost $rc$ of a column ${j}$ in the master problem is defined as:

$$\begin{equation*}rc = Min\left ({{1 - \sum \limits _{i = 1}^{n} {\pi _{i}{x_{i}}} } }\right) = 1 - Max\sum \limits _{i = 1}^{n} {\pi _{i}{x_{i}}} \tag{17}\end{equation*}$$ where $\pi$ represents the dual cost vector consists of the dual variables of the restricted master problem.

We formulate the subproblem as a 0–1 knapsack problem with side constraints.

$$\begin{align*}&\hspace {-0.5pc}Max\left ({{\sum \limits _{i = 1}^{n} {\pi _{i}{x_{i}}} + \sum \limits _{i \in P0}^{} {\sum \limits _{h \in Pre(i)}^{} {j \cdot \mu _{i}^{h} \cdot \left ({{x_{i} - {x_{h}}} }\right)} } } }\right) \tag{18}\\&\hspace {-0.5pc}\textit {Subject to}~ \\&\hspace {-0.5pc}\hphantom {\textit {Subject to}~}\sum \limits _{i \in I} {t_{i}{x_{i}}} \le ct \tag{19}\\&\hspace {-0.5pc}\hphantom {\textit {Subject to}~}~{x_{i1}} \!+\! {x_{i3}} \!-\! {x_{i2}} \!\le \! 1\!\quad \forall i1 \in P(i2),~i3 \in {F^{*}}(i2) ~\,\qquad \tag{20}\\&\hspace {-0.5pc}\hphantom {\textit {Subject to}~}~{x_{i}} \in \left \{{ {0,1} }\right \}\quad \forall i \in I \tag{21}\end{align*}$$

The objective function is equal to searching for the minimization of the reduced cost for the master problem. The coefficients of variables in (18) are related to the dual variable values associated with constraints set (14) and (15). Parts of constraints of the knapsack problem are the same as the cycle time constraints of the original line balancing problem, namely the constraint set of (3). The cycle time value of the original problem gives a weight limit in the knapsack problem model. Another set of constraints is added to the knapsack problem: task sequence constraints (20). These constraints guarantee that solutions could satisfy the sequence constraints set (4).

The solution of the pricing problem represents one possible pattern of task assignment. The new pattern can be added into the master problem’s solution pool when its reduced cost is negative. For each station, a specific pricing problem is constructed to calculate the minimum reduced cost. Pricing problems are designed to be solved in the order of the station’s sequence. After getting an improved column, we add it into the matrix $A$ of the master problem.

SECTION IV. Three-Stage Branch-and-Price Algorithm

A. Overview of Algorithm

The three-stage branch-and-price algorithm consists of three parts of computation. The flow chart of the algorithm is illustrated in Fig. 5. In the first stage, an initial solution for the instance of SALBP-I is given applying a heuristic approach. The object value of the initial solution acts as the upper bound $Z_{best}$ in the algorithm. The lower bound in our algorithm is calculated as the simple lower bound $LB_{1}= \lceil sum(t)/ct\rceil$ . The initial solution also constructs the root node of the branch and bound tree. Details of this initial algorithm are described in the next subsection $B$ .

FIGURE 5.

Three-stage branch-and-price algorithm.

In the second stage, we implement the iteration procedure of column generation. At children nodes in the searching tree, the LP relaxation model of the line balancing problem is solved using the column generation method. We define this problem as “restricted master problem” because the initial reformulation of master problem only includes a subset of the solution. Other columns with negative reduced cost are generated iteratively by solving the pricing problems. Given the optimal dual solutions which act as the multipliers in the subproblem’s objective function, we use $Gurobi$ optimizer to solve subproblems. To identify a new column, the negative reduced cost requirement of the master problem needs to be satisfied by checking the optimal value of subproblem. We add the optimal solution into the master problem as a new column of the parameter set and repeat this iteration until the negative reduced cost no more exists.

Iterations between the master problem and the pricing problem stop when three cases happen: The first condition works if the basic solution value of the master problem reaches the lower bound $Z_{B} \le LB$ . Secondly, the iteration breaks when the reduced cost got from the new pricing problem is nonnegative $rc \ge 0$ which means that current solution of the master problem cannot be improved any more. The third condition interrupts the iteration when the value of the reduced cost $rc$ is small enough. Since the number of the work station is integer, the final result should not be smaller than the rounded up value of the basic solution value. Thus the final result will not be smaller when the reduced cost locates within a certain range $Z_{B}=\lceil Z_{B}/(1-rc)\rceil$ .

When the iteration stops, we analyze the possible result obtained at the current phase. Options should be taken under different conditions:

1. Whenever an integer solution in node $h$ is found, if $Z_{h} < Z_{best}$ , then solution of node h becomes the new incumbent solution, and the node $h$ is pruned after updating $Z_{best}$ .

2. For fractional node ${i}$ which holds $Z_{i} > Z_{best} -1$ , then node $i$ is fathomed for bounding.

3. The node with no feasible solution should also be fathomed.

4. Branching is performed on fractional node ${i}$ with a solution that $Z_{i} \leq Z_{best} -1$ .

If we cannot obtain an integer solution at the second stage, branching takes place and it generates two new children nodes in the branch-and-bound tree. In the third stage of the branch-and-price algorithm, an IP model of the Dantzig-Wolfe reformulation (7)–(12) is applied to solve SALBP-I. The parameters of the IP model are based on the columns generated in the second stage. This procedure is designed to seek integer solutions. If we achieve the optimal solution, the algorithm terminates and the final solution is updated, otherwise calculation on active nodes continues. The list of active nodes in the searching tree consists of nodes that are either not solved or solved but with fractional solutions. When no active node left in the branch-and-bound tree the algorithm terminates. The current incumbent solution becomes the final solution.

The lower and upper bounds used in the branch-and-price algorithm could improve the efficiency of tree searching. A good lower bound of optimal IP solution value decreases the iteration times of column generation as the first stopping criteria stated above. The lower bound is set to the minimum value of work station over all active nodes in this algorithm. And the upper bound value is updated according to the value of $\lceil Z_{B}\rceil$ when the column generation process finishes in the $2^{nd}$ stage and the value of IP solution in the $3^{rd}$ stage. The upper bound is the current optimal integer solution value. Nodes with the value exceeds the upper bound could be pruned without further branching. If an integer solution is obtained, this is the best feasible integer solution that can be obtained in this part of the tree, thus no more branching is needed on this node [33]. $Z_{best}$ can be updated to reduce the gap between the lower bound and the upper bound.

B. Initial Solutions

We need to determine the initial restricted master problem to start the branch-and-price algorithm. The optimal values of dual variables can be obtained through solving the initial restricted master problem. Based on these values we devise the object function of subpricing problems. Not only do we need to set an initial restricted master problem, but also at every branching node in the searching tree of the branch-and-price algorithm, an available restricted master problem has to be initialized to kick off the iteration process of column generation. A heuristic algorithm is designed to construct the initial solution of the restricted master problem in this work. The pseudo-code is described below.

Heuristic Algorithm 1 Pseudo-Code of Initial Solution

1:

while $the~Pool~not~empty$ do

2:

if $t_{i} > the~time~capacity~of~active~station~j$ then

3:

$Set\,\,a\,\,new\,\,station\,\,j+1\,\,active$

4:

end if

5:

for $task~in~Pool$ do

6:

if $L=\emptyset \,\,and\,\,R=\emptyset$ then

7:

$assign~the~current~task~to~active~station$

8:

$update~the~pool~set$

9:

end if

10:

if $L=\emptyset \,\,and\,\,R\ne \emptyset$ then

11:

$exclusive~tasks~checking$

12:

end if

13:

if $L\ne \emptyset$ then

14:

$search~tasks~for~packing$

15:

$assign~the~packing~tasks~to~active~station$

16:

$update~the~pool~set$

17:

end if

18:

end for

19:

end while

Since the branching is realized through adding constraints in the pricing problems, the initial restricted master problem should not be violent against these constraints. As the searching trees grow, the number of task pairs that should be combined or disjoint will increase in deeper layers. Thus, we need to construct the specific initial master problem which has a feasible LP relaxation at different nodes. The methodology of the heuristic algorithm for the initialization is based on the task oriented approach. Tasks in the pool, whose preceding operations are totally assigned already, will be updated during the process of solution searching. Tasks are classified into three categories after checking their feasibility of fixing to current station: Firstly, task without any related constraint pair can be assigned directly according to the current station’s time capacity. Secondly, tasks, which are included in the disjointing pair, should satisfy exclusive constraints that their exclusive tasks are not in current station. Thirdly, we must pack tasks that appear in one joining pair constraint together through grouping them as one task in later computing process. Tasks which belong to the set of middle range of the joining pair in the precedence relationships need to be packed simultaneously. New station will be created when the capacity of current station is not enough to accept any unassigned task in the pool. Searching for a feasible solution continues until the pool set is empty which means that every task has a corresponding assignment.

C. Search Strategy

The search strategy controls how to select unexplored nodes in the branch-and-bound tree. Search strategies affect the computer memory requirements and computation time of the branch-and-price algorithm. Different search strategies have specific characteristics which are suitable to variant problems. Depth-first search, breadth-first search and best-first search are three common search strategies widely used in the branch-and-bound algorithm.

Depth-first search (DFS) strategy navigates the search path in the order of relation of the current node. At current node in the branch-and-bound tree, new branching nodes generated from this node will be explored first for further study. This is realized through setting a stack to store the list of unexplored nodes. We select the top item in the stack for exploration, and then remove it after obtaining a feasible solution. Children nodes based on the branching procedure of this fractional solution are inserted on the top of that stack. Thus, in the depth-first search tree, the node which is created most recently will be calculated first.

Breadth-first search deals with the list of brand-and-bound nodes in the data structure of a queue. Contrary to the depth-first search method, breadth-first search manage the unexplored nodes in a first-in, first-out sequence. Breadth-first search runs well on unbalanced search trees since this strategy could always detect the optimal solution that is closest to the root of the tree.

Best-first search compare the values of lower bound of active nodes and select the node with smallest value as the next branching node. Best-first search is conducted by managing the active nodes list in a data structure of heap and setting the lower bound value as the key. As a result, best-first search often discover good solutions earlier in the search tree. The last strategy tested in our algorithm is called cyclic best-first search. This approach, which is originally named distributed best-first search, is a hybrid method between depth-first search and best-first search. Unexplored nodes list is divided into a group of heaps according to the depth of node in the searching tree. Cyclic best-first search picks out the smallest node from each heap to branch and takes the same operation at the next heap until all heaps are empty. Cyclic best-first search will explore the node with the best value at depth 0, then depth 1, and so on; upon reaching the deepest layer of the search tree, it will repeat the process starting from depth 0. The choice of search strategy has potentially significant consequences for the amount of computation time required for the branch-and-price procedure, as well as the amount of memory used.

SECTION V. Implementation Details

A. Branching Rules

The restricted master problem used in the column generation method is a LP relaxation model. The optimal solutions of this model are not necessarily integers when column generation iterations finish at one node. Then the branching works to create new nodes on the searching tree aiming to obtain the integer solution. In the standard branch-and-bound algorithm, branching always acts on fractional variables of the original problem. However this method cannot guarantee obtaining an optimal integer solution in the branch-and-price algorithm. Since the solutions pruned out after branching may appear again in the children nodes’ column generation process.

We apply the Ryan-and-Foster branching rule in our branch-and-price algorithm. This branching strategy is based on the following proposition.

Proposition 1:

If a basic solution to the master problem is fractional, then there exist two tasks ${l}$ and ${m}$ of the master problem such that

$$\begin{equation*}0 < \sum \limits _{j,p:A_{lj}^{p} = 1,A_{mj}^{p} = 1}^{} {z_{j}^{p}} < 1 \tag{22}\end{equation*}$$

Proof:

Consider fractional variable $z_{j}^{p}$ , Let task $l$ be any task with $A_{lj}^{p} = 1$ . Since and $z_{j}^{p}$ is fractional, there must exist another basic column with $0 < z_{j'}^{p'} < 1$ and $A_{lj'}^{p'} = 1$ . Since there are no duplicate columns in the basis, there must exist a task m such that either $A_{mj}^{p} = 1$ or $A_{mj'}^{p'} = 1$ , but not both. This leads to the following relations:

$$\begin{align*} 1=&\sum \limits _{j \in J}^{} {\sum \limits _{p \in Q}^{} {A_{lj}^{p}} z_{j}^{p}} \\=&\sum \limits _{j:A_{lj}^{p} = 1} {\sum \limits _{p:A_{lj}^{p} = 1} {z_{j}^{p}} } \\>&\sum \limits _{j,p:A_{lj}^{p} = 1,A_{mj}^{p} = 1}^{} {z_{j}^{p}} \tag{23}\end{align*}$$

The pair $l$ and $m$ gives the pair of branching constraints.

$$\begin{equation*}\sum \limits _{j,p:A_{lj}^{p} = 1,A_{mj}^{p} = 1}^{} {z_{j}^{p}} \ge 1\quad {\text {and }}\sum \limits _{j,p:A_{lj}^{p} = 1,A_{mj}^{p} = 1}^{} {z_{j}^{p}} \le 0\end{equation*}$$

We follow the structure of binary trees when act branching in the branch-and-bound tree. On the left branch tasks $l$ and $m$ are required to be covered by the same column. Thus, all feasible columns must have $A_{lj}^{p} = A_{mj}^{p} = 1$ or $A_{lj}^{p} = A_{mj}^{p} = 0$ . While tasks $l$ and $m$ are required to be covered by the different columns on the right branch, and feasible columns must have $A_{lj}^{p} = A_{mj}^{p} = 0$ or $A_{lj}^{p} =0$ , $A_{mj}^{p} =1$ or $A_{lj}^{p} =1$ , $A_{mj}^{p} =0$ . Branching constraints on the left branch equals to combining tasks $l$ and $m$ into a new task. On the right branch, tasks $l$ and $m$ are required to be disjoint. Proposition 1 implies that if no branching pair can be identified, then the solution to the master problem must be integer. The branch-and-price algorithm must terminate after a finite number of branches since there are only a finite number of pairs of tasks.

B. Knapsack Subproblem With Side Constraints

The strategy of branching in this work is preventing the fractional solution from being regenerated in the column generation process. Adding constraints set to the master problem can introduce new dual variables to the pricing problem. Thus, instead of adding the branching constraints to the variables of master problem directly, we guarantee the branching constraints through constructing and solving the pricing problem. Branching constraints can be integrated into the column generation subproblems. On the left branch we have:

$$\begin{align*}&Max\left ({{\sum \limits _{i = 1}^{n} {\pi _{i}{x_{i}}} + \sum \limits _{i \in P0}^{} {\sum \limits _{h \in Pre(i)}^{} {j \cdot \mu _{i}^{h} \cdot \left ({{x_{i} - {x_{h}}} }\right)} } } }\right) \tag{24}\\&\textit {s.t.}~ \\&\hphantom {\textit {s.t.}~}\sum \limits _{i \in I} {t_{i}{x_{i}}} \le ct \tag{25}\\&\hphantom {\textit {s.t.}~}~{x_{l}} = {x_{m}}\quad \forall l,m \in L \tag{26}\\&\hphantom {\textit {s.t.}~}~{x_{i1}} + {x_{i3}} - {x_{i2}} \le 1\quad \forall i1 \in P(i2),~i3 \in {F^{*}}(i2) \qquad \tag{27}\\&\hphantom {\textit {s.t.}~}~{x_{i}} \in \left \{{ {0,1} }\right \}\quad \forall i \in I \tag{28}\end{align*}$$

The new constraint set (26) requires that the pair of tasks $l$ and $m$ must appear together in new patterns in the left branch. As a result, fractional columns eliminated by the addition of these constraints will not be regenerated again.

Subproblems on the right branch can be formulated as:

$$\begin{align*}&Max\left ({{\sum \limits _{i = 1}^{n} {\pi _{i}{x_{i}}} + \sum \limits _{i \in P0}^{} {\sum \limits _{h \in Pre(i)}^{} {j \cdot \mu _{i}^{h} \cdot \left ({{x_{i} - {x_{h}}} }\right)} } } }\right) \tag{29}\\&\textit {s.t.}~ \\&\hphantom {\textit {s.t.}~}\sum \limits _{i \in I} {t_{i}{x_{i}}} \le ct \tag{30}\\&\hphantom {\textit {s.t.}~~}{x_{l}} + {x_{m}} \le 1\quad \forall l,m \in R \tag{31}\\&\hphantom {\textit {s.t.}~~}{x_{i1}} + {x_{i3}} - {x_{i2}} \le 1\quad \forall i1 \in P(i2),i3 \in {F^{*}}(i2) \qquad \tag{32}\\&\hphantom {\textit {s.t.}~~}{x_{i}} \in \left \{{ {0,1} }\right \}\quad \forall i \in I \tag{33}\end{align*}$$

On the right branch we add the constraint set (31) to the subproblem. This constraint will prevent columns with tasks assignments $x_{i} = x_{m} = 1$ from being generated.

SECTION VI. Computational Results

In this section, we present and analyze experiment results of the proposed algorithm. Benchmark data sets and real production data of the assembly line are employed to test the algorithm. We implement our experiments in Python 3.0 programming environment that constructs an interface with $Gurobi~7.5$ .2 optimizer. The computer on which experiments are conducted has an $Intel^{\text{@}}~Core^{TM}$ i7-3770 3.40GHz CPU and 8GB RAM memory using the $Windows~7$ operating system.

A. Benchmark Data Sets

In this part, our experiments use three referenced data sets of SALBP, which is data set of Talbot et al. [39], Hoffmann [40] and Scholl [41] respectively. The reported best-known solutions of the instances studied in these data sets provide a benchmark for numerical computations. These three data sets include a total of 25 precedence graphs. Table 4 presents characteristics of these precedence graphs.

TABLE 4 Characteristics of Precedence Graphs

The column headings in the Tables of data sets and experiment results mean as follows.

AbbreviationExpansion

Name:	name of the precedence graph.
$n$ :	the number of tasks.
$ct$ :	cycle time.
$t_{min}$ :	the minimum task time in the instance set.
$t_{max}$ :	the maximum task time in the instance set.
sum(t):	the summation of task time in the instance set.
OS:	the ‘Order Strength’ (OS) is equal to the number of all precedence relations divided by the maximum number of precedence relations.
TV:	the ‘Time Variability Ratio’ is the ratio of maximum task time to the minimum task time.
UB:	upper bound found by the heuristics used to initialize the column generation.
LB1:	lower bound which equals to $\lceil sum(t)/ct\rceil$ .
$Z^{*}$ :	best-known solution in the literature.
Nodes:	the number of nodes searched in the branch-and-bound tree.
Iterations:	the total times that the column generation procedure runs for finding the final solution.
CPU:	time needed for CPUs to solve the instance of SALBP-I problem.

The average CPU time results of the benchmark data sets are listed in Table 5. The three-stage branch-and-price algorithm outperforms $Gurobi$ optimizer for 13 of 25 data sets. $Gurobi$ optimizer calculates faster in 9 of 25 data sets. There exist 2 data sets (Barthol2 and Scholl) that the average computing time is too long to obtain the optimal solution for both $Gurobi$ optimizer and the three-stage branch-and-price algorithm. We set the limitation of average CPU time as 1000s, computing time beyond this value is noted as (−).

TABLE 5 Average Computing Time

To evaluate the effectiveness of the three-stage branch-and-price algorithm, we analyze that at which phase the optimal solution is obtained in the procedure of optimization. Statistics are listed in Table 6. Totally, the algorithm could found the optimal solution for 48.55% of the instance sets at the $1^{st}$ stage. And 21.97% of the instances sets got the optimal solution at the $2^{nd}$ stage which represents the iteration process of column generation. Finally, the added integer programming, which is the $3^{rd}$ stage in the algorithm, solved 29.48% of the instances sets optimally.

TABLE 6 Optimal Results for Different Problem Characteristics

TABLE 7 Data of Real Production Sample

TABLE 8 Optimization Results of Frontend Assembly

Additionally, the properties of the precedence graph of the instance have an impact on the operation process. The data sets are classified into three categories, the Number of Tasks (NT), the Order Strength (OS) and the Time Variability ratio (TV), depending on different characteristics to study their influence: (i): Low-NT ($0\le {NT} < 30$ ), Middle-NT($30\le {NT} < 70$ ), High-NT($70\le {NT} < 300$ ). (ii): Low-OS ($0\le {OS} < 30$ ), Middle-OS($30\le {OS} < 70$ ), High-OS($70\le {OS} < 100$ ). (iii): Low-TV($5\le {TV} < 15$ ), Middle-TV($15\le {TV} < 70$ ), High-TV($70\le {TV} < 600$ ). In sets of Low-NT, most (73.81%) instances could get the optimal solution at the $1^{st}$ stage. And that percentage decreases in Middle-NT (34.69%) and High-NT (43.90%) sets. The percentage value of optimal solutions obtained at $2^{nd}$ stage for Middle-NT (28.57%) and High-NT (23.17%) sets are more than that for Low-NT (11.90%) set. Also this trend is accordant with the percentage values of $3^{rd}$ stage. The effectiveness of $3^{rd}$ stage is higher than the $2^{nd}$ stage in all three different NT sets. As the order strength increases, the optimal solution obtained at the 1st stage becomes more. However, the percentage of optimal result getting from the $2^{nd}$ stage decreases when the order strength is high. In both Middle-OS and High-OS sets, more optimal solutions, 32.67% to 22.77% and 25.58% to 11.63%, are obtained at $3^{rd}$ stage than at $2^{nd}$ stage. Nearly half of instances obtain their optimal results at the $1^{st}$ stage in three different TV sets. The percentage of the $2^{nd}$ stage and the $3^{rd}$ stage changes little from the Low-TV to High-TV sets. The influence of the time variability ratio did not affect the operation results as much as the number of task and the order strength.

In order to assess the efficiency of the proposed three-stage branch-and-price algorithm, the numerical tests of a classic branch-and-price algorithm are done on the benchmark instance sets. We list the computational results whose upper bound is not equal to the best-known solutions in Table 9, Table 10, and Table 11. Since the solving process did not enter into the column generation procedure if the initial heuristics could find the best value of solution in a short time. Results of the classic branch-and-price algorithm and the three-stage branch-and-price algorithm are both reported.

TABLE 9 Experiments Results of Data Set of Talbot

TABLE 10 Experiments Results of Data Set of Hoffmann

TABLE 11 Experiments Results of Data Set of Scholl

Table 9 presents the results of 15 instances of the data set of Talbot. Table 10 shows the detailed results for 13 instances of the Hoffmann set. Results of 51 instances of the Scholl set are listed in Table 11.

For standard branch-and-price algorithm, there are 38 instances which did not achieve the optimal solution. Using three-stage branch-and-price algorithm, only 4 instances got the final solution with a gap of one station to the known best value. There is one instance of Gunther data set ($ct=49$ ) that obtained the optimal solution which is superior to the known best value. The three-stage branch-and-price algorithm is more effective than the standard branch-and-price algorithm, especially for the instances which belong to the High-NT set.

The three-stage branch-and-price algorithm can prune the branching nodes effectively exploring fewer nodes than the classic branch-and-price algorithm. The number of column generation iteration also decreases in the three-stage branch-and-price algorithm. These result in a shorter computing time. There are only 8 of the total instances whose CPU time consumed in the three-stage branch-and-price algorithm is longer than that of the classic branch-and-price algorithm.

B. Real Production Case

An industry case study for the frontend part assembly of vehicle on the assembly line in BMW Brilliance Automotive Ltd. is conducted to validate our algorithm. The frontend pre-assembly line consists of 12 work stations as shown in Fig. 6. As illustrated in Section 3, some parts are assembled on the pre-assembly areas in the assembly shop. After the completion of total assembly of the frontend, this part is delivered to the main assembly line for its installation on the vehicle as indicated in Fig. 4. The production pattern, for which there is one operator working on each station, is same as the model of SALBP we study. Twelve workers are assigned to this section. Apart from movement time (15 seconds) of the conveyor transiting from one station to the next station, the reference cycle time is set as 80 seconds for the operator. The data of the test instance is shown in Table 7.

FIGURE 6.

Pre-assembly line of the vehicle’s frontend part.

Current line balancing solution needs 12 workers to finish the pre-assembly work of frontend parts. Results after optimization show that the station number can decrease to 11 with the cycle time of 80s. Finally, the percentage of the total idle time of test area dropped to 7.61% from 15.31%. We also list the results of our method and that of classic branch-and-price in Table 8. Compared to the standard branch-and-price algorithm, the number of searching nodes is lesser in the three-stage branch-and-price algorithm (2 to 3), and its total iteration time is also lesser (58 to 82) which result in a faster computing time (12.884s to 37.421s).

SECTION VII. Conclusion

In this article, we have reformulated the SALBP-I applying the Dantzig-Wolfe decomposition. Sequence constraints are maintained in the model of the master problem. The three-stage branch-and-price algorithm for solving the SALBP-I is presented. Considering the nature of solutions created through the column generation process, a specific branching strategy is introduced to assure the efficiency of the optimal result searching. Details of the construction and solving the pricing problems are described.

Experiments are conducted on the standard benchmark data sets which cover a wide range of the task scale. The proposed three-stage branch-and-price algorithm obtains competitive results compared to the commercial solver. Three-stage branch-and-price algorithm is also superior to the classic branch-and-price algorithm in the terms of the efficiency of solving and the quality of solution. The analysis of the computational results shows that properties of instances have effects on the optimization algorithm. The number of tasks and the order strength has more impact on the optimization process than value of time variety ratio. A case study on one production line in BMW Brilliance Automotive Ltd. verifies the effectiveness of the proposed algorithm. Following the principle of production (‘allowed workplace’, Section_3_A2) the super-larger scale of assembly line balancing in the automotive industry can be decomposed into smaller instances of different areas. Most of these instances belong to the range of scale that the proposed algorithm can deal with. Even under complex industrial conditions, the practical application of our proposed algorithm is still feasible to improve the productivity and reduce the production cost. Although the SALBP-I is a basic issue of assembly line balancing work, insights and comprehension of the proposed method will guide further research works on more complicated instances of assembly line balancing problem.