Abstract

The two-sided assembly line balancing problem type-II (TALBP-II) is of major importance for the reconfiguration of the two-sided assembly lines which are widely utilized to assemble large-size high-volume products. The TALBP-II is NP-hard, and some assignment restrictions in real applications make this problem much more complex. This paper provides an integer programming model for solving the TALBP-II with assignment restrictions optimally and utilizes a simple and effective iterated greedy (IG) algorithm to address large-size problems. This algorithm utilizes a new local search by considering precedence relationships between tasks in order to reduce the computational time. In particular, a priority-based decoding scheme is developed to handle these assignment restrictions and reduce sequence-dependent idle times by adjusting the priority values. Experimental comparison among the proposed decoding scheme and other published ones demonstrates the efficiency of the priority-based decoding. A comprehensive computational comparison among the IG algorithm and other eight recent algorithms proves effectiveness of the proposed IG algorithm.

1. Introduction

A two-sided assembly line consists of a set of sequential mated-stations connected by the material handling system. It is widely used to produce large-size high-volume products, such as cars, trucks, and automobiles. An example of two-sided assembly lines is shown in Figure 1. Both sides are utilized for performing a set of tasks. A pair of face-to-face stations like station and station is called a mated-station and one of them is the companion of the other. The idle time on each station can be divided into two types: sequence-dependent idle time such as idle time behind task 1 [1] and the remaining idle time existing at the rear of the last task such as idle time behind 3.

Figure 1 

A typical example of two-sided assembly line.

Compared with the traditional one-sided assembly line, the two-sided assembly line balancing problem (TALBP) is more complex due to the existence of restrictions on the operation direction. Some tasks have to be operated on a predefined side of the line, while others can be allocated to any side of the line. Thus, the task preferred directions can be classified into three types, namely, L (left), R (right), and E (either). In summary, there are three restrictions that need to be satisfied, including the precedence restriction, cycle time restriction, and direction restriction.

Besides these basic restrictions, other assignment restrictions which exist in real applications need to be considered, including zoning restriction, synchronous restriction, positional restriction, distance restriction, and resource restriction [2]. In this paper, we focus on zoning restriction, synchronous restriction, and position restriction which are usually found in real applications. The zoning restriction can be divided into two types: positive zoning restriction and negative zoning restrictions. Positive zoning restriction means that some tasks need to be assigned to the same station while negative zoning restriction prohibits some tasks being allocated to the same mated-station [3]. Synchronous restriction restricts two operators to perform a pair of tasks simultaneously on both sides of the same mated-station for collaboration [4]. The positional restriction indicates that certain tasks need to be allocated on predetermined stations or mated-stations [1].

The TALBP, so far as the objectives are concerned, can be divided into two versions: TALBP-I that minimizes the number of stations with a given cycle time, and TALBP-II that minimizes the cycle time for given mated-stations. The TALBP-I is more appropriate for the first-time installation of the assembly line, while the TALBP-II is proper for the reconfiguration of the assembly line [5]. Note that the TALBP-II is more complex than the TALBP-I, since the cycle time is unknown and needs to be optimized.

To our knowledge, limited papers considered the TALBP-II [2, 6–8] even though the TALBP-II is of major importance in industry [5, 7]. In addition, no paper introduces decoding schemes for the TALBP-II with assignment restrictions. To enhance research on the TALBP-II with assignment restrictions, this paper proposes a simple and effective iterated greedy (IG) algorithm. In particular, this algorithm proposes a new priority-based decoding in which the assignment restrictions are satisfied by adjusting the priority values. The IG algorithm is a local search method, and it has obtained excellent results for some discrete optimization problems [9–13]. This research is the first attempt to adopt this IG algorithm for the TALBP-II with assignment restrictions.

The organization of this paper is introduced as follows. Section 2 presents the recent method for TALBP-II and assignment restrictions. The mathematical model for TALBP-II with assignment restrictions is described in Section 3. The decoding scheme for TALBP-II with assignment restrictions is explained in Section 4. The improved IG algorithm is introduced in Section 5. Section 6 demonstrates the effectiveness of IG by comparison with other well-known methods. Finally, the conclusions are given in the last section.

2. Literature Review

The two-sided assembly line balancing has become an active field of research since the two-sided assembly line balancing problem (TALBP) was first introduced by Bartholdi [14]. The TALBP can be divided into TALBP-I that minimizes the number of stations and TALBP-II that minimizes the cycle time.

Most attention is paid to the TALBP-I, and exact, heuristic, and meta-heuristic methods have been applied. Exact methods include station-oriented enumerative algorithm [15] and branch-and-bound algorithms [16, 17]. Heuristic methods include the group assignment procedure [18] and the enhanced priority-based heuristic [19]. Additional research was based on meta-heuristic methods, and they are a genetic algorithm [1], a tabu search algorithm [20], a bee algorithm [21], simulated annealing algorithms [22–24], particle swarm optimization algorithms [25, 26], and a hybrid honey bee mating optimization [27] and multineighborhood based path relinking [28].

As for the TALBP-II, Kim et al. [6] adopted a mathematical model and utilized a genetic algorithm. Purnomo et al. [2] also proposed a genetic algorithm to handle the TALBP-II with assignment restrictions. Purnomo and Wee [7] proposed a harmony search algorithm to address multiobjective TALBP-II. More recently, Lei and Guo [8] proposed a variable neighborhood search and they developed a new method to determine the allocated sides of the tasks by utilizing a side string. Tang et al. [29] developed a discrete artificial bee colony algorithm and they also provided some methods to reduce the idle times on two-sided assembly lines. Except for Purnomo et al. [2], all the other papers ignore the assignment restrictions in real application. And Purnomo et al. [2] did not exhibit the detailed decoding procedure, but the detailed decoding procedure is very important for the replication of the method.

Now we focus on additional contributions dealing with assignment restrictions. Apart from the above literature of Purnomo et al. [2], all the researches belong to TALBP-I. Kim et al. [1] focused on positional restrictions. Baykasoglu and Dereli [3], Özbakir and Tapkan [21], and Purnomo and Wee [7] considered zoning restrictions. Simaria and Vilarinho [4] considered the zoning and synchronism restrictions. Tapkan et al. [30, 31] handled the positional restrictions, zoning restrictions, and synchronism restrictions. Yuan et al. [32], Wang et al. [33], Li et al. [34], and Tang et al. [35] also employed different methods to handle the above three restrictions. Tuncel and Aydin [36] considered additional assignment restrictions as an industrial assembly system in practice. Among these researches, few papers presented their decoding schemes except for a similar decoding scheme by four papers [32–35]. Yet this decoding method ignores the reduction of sequence-dependent idle times in the decoding procedure and the methods to deal with assignment restrictions can be possibly improved.

From the literature review, it is observed that only one paper deals with TALBP-II with assignment restrictions and no detailed encoding procedure for TALBP-II with assignment restrictions is presented. Therefore this paper focuses on the TALBP-II with assignment restrictions by utilizing a new algorithm and also provides new decoding schemes to handle assignment restrictions and reduce sequence-dependent idles by adjusting the priority values.

3. Mathematical Model for TALBP-II with Assignment Restrictions

3.1. Problem Assumptions

(1)A single model is taken into account and the travel time between stations is ignored.(2)Precedence diagrams are known and deterministic.(3)The task with a positional restriction should be assigned to the predefined station.(4)The tasks in the positive zoning restriction should be assigned to the same station.(5)The tasks in the negative zoning restrictions are prohibited to be allocated to the same mated-station.

3.2. Mathematical Model

In the TALBP-II, minimizing the cycle time is the widely used objective [6] and we employ it in this paper. Based on the research by Kim et al. [6] and Purnomo et al. [2], the other constraints are listed as follows:, ,

Constraint (1) is the occurrence restriction which guarantees that each task must be allocated to only one side of a mated-station. Constraint (2) is the precedence restriction which is usually found in the assembly line balancing problem. Constraints (3)–(5) consider the sequence-dependent finishing time of tasks. For a pair of tasks , if they are allocated to the same mated-station and task is an immediate successor of task , then constraint (3) becomes active and it is reduced to . For a pair of tasks , if they are allocated to the same station and have no precedence relationships, then constraints (4)-(5) become active. If task is allocated earlier than task , then and constraint (4) is reduced to . Otherwise, and constraint (5) is reduced to . Constraint (6) is the cycle time restriction which ensures that each task is finished within cycle time. Constraint (7) is the positional restriction which makes sure that task is assigned to station . Constraint (8) is the positive zoning restriction which ensures that tasks ,   are operated on the same station. Constraint (9) is the negative zoning restriction which forbids tasks ,   being assigned to the same mated-station. Constraints (10)-(11) are the synchronous restrictions. Constraint (10) ensures that task and task have the same starting time and constraint (11) ensures that task and task are allocated to the two sides of a mated-station.

3.3. New Objective Function for Evolution

The general objective of TALBP-II is minimizing the cycle time [6], which also means minimizing the total idle times, including the sequence-dependent idle time and the remaining idle time existing at the rear of the last task. Nevertheless, in experiments, a large number of gained solutions by the meta-heuristics have the same cycle time and the meta-heuristics cannot determine the best one among these solutions, causing their poor performance. Thus, this paper proposes the following objective based on the fitness function in Özbakir and Tapkan [21] to distinguish the solutions: where and are the completion time of the last task and the sum of task times on station , respectively, and , , , are coefficients which need to be determined. The first part in fitness function minimizes the remaining idle time, the second part aims at minimizing the sequence-dependent idle time, and the third and fourth parts balance the remained idle time and the sequence-dependent idle time on each station.

4. Encoding and Decoding Scheme for TALBP-II with Assignment Restrictions

In the TALBP-II, the number of mated-stations is fixed and the station-oriented encoding and decoding are widely utilized [1, 2]. Due to the utilization of two sides of a mated-station, both the sequence of allocating tasks and the side allocating a task need be determined to obtain a feasible solution. Kim et al. [6] utilize a heuristic method to allocate tasks and this method ignores the sequence-dependent idle times in the decoding process, which may result in an amount of idle time and a large cycle time. The priority-based encoding and decoding [22], on the contrary, allocate the tasks based on the priority values of the tasks and the sequence-dependence idle times can be reduced by the adjustment of the priority values which can be achieved by the meta-heuristics. In this paper, we develop a new priority-based encoding and decoding based on the work of Khorasanian et al. [22].

The proposed priority-based decoding first selects the side of the current mated-station and then selects a task based on the priority values. Also, the task assignment rule is embedded into the decoding schemes to balance the workload and reduce sequence-dependent idle times. In contrast to the work of Yuan et al. [32] and Li et al. [34], new methods that deal with positional restriction and positive zoning restriction are proposed. All these task assignment rules and the decoding schemes are introduced as follows.

4.1. Initial Priority Values Adjustment

In the proposed priority-based decoding, all the initial priority values are limited to a range of . Taking the well-known RPW heuristic [37] as example, the initial task priority values are equal to the sum of processing times of a task and its successors. We first sort all the tasks in a decreasing order of the priority values to obtain a task permutation and then calculate priority values for tasks as follows: where is the sequence of task in the task permutation and is the number of tasks. This equation makes the former tasks in the task permutation have higher priority values. Since the task permutation is obtained in decreasing order of the initial priority values, the task with the largest initial priority values also has the largest priority value after priority values adjustment. Since some metaheuristic algorithms update the task permutations in the search process, such as simulated annealing [22], (13) can also transfer the task permutation into priority values.

4.2. Task Assignment Rule

The task assignment rule is applied to reduce the sequence-dependent idle time and reduce the workload deviation. First, we seek to reduce the sequence-dependent idle time by boosting the priorities of tasks without generating sequence-dependent idle times. Then we try to balance the workload on each station by boosting the priority values of tasks whose finishing times on the station are within a range , where is average workload which can be calculated with . In this way, we try to make the workload on each station vary within and the deviation is thus reduced.

Step 1. Calculate priority values for all the tasks.

Step 2. Set when task satisfies cycle time, direction, and precedence restrictions while or satisfies only direction and precedence restrictions while .

Step 3. If and task in the assignable task set can begin at the earliest start time of the current station, then .

Step 4. If and the finishing time of task in the assignable task set is in , then .

Step 5. After Step 4, there are three conditions: task cannot be allocated when ; task can be allocated and its priority is not boosted when ; task can be allocated and its priority is boosted when .

In Step 2, only direction and precedence restrictions need to be satisfied while , which make sure that we can acquire a feasible solution. After Step 2, task can be assigned only when and task violates at least one of the above restrictions when . In Step 4, the tasks whose finishing times are within have higher priorities for the sake of undertaking some sequence-dependent idle time and holding more workload.

4.3. Improved Positional Restriction Handling

Yuan et al. [32] and Li et al. [34] ignore the positional restriction during the decoding process. This paper improves their decoding by preventing the tasks in the positional restriction being assigned to the former mated-station. In addition, if the current station is the predetermined station , the priority of the task is increased. To achieve the above goal, we define the matrix in (14) and the remaining values are set to zero. Then, the propriety of task is updated with expression (15):

After adjusting the priorities, when the former mated-station is the current mated-station, and task cannot be assigned. If the current mated-station is the predetermined station, the priority of task is boosted to increase the possibility of finding a solution which satisfies the positional restriction. If the current mated-station is the latter mated-station, then the priority of task remains unchanged for the sake of gaining a feasible solution.

4.4. Improved Positive Zoning Restriction Handling

Yuan et al. [32] and Li et al. [34] allocate the task in the positive zoning restriction as a whole and at an unchangeable sequence to a station. This paper improves their method by assigning the tasks in the positive zoning restriction one by one, which helps reduce sequence-dependent idle time. For this purpose, the relationship matrix among tasks is defined, and the initial values are set by following expression (16) and the remaining ones are set to zero:

For task , if , its priority is updated as follows:where is the number of tasks that have been allocated to station and is the th task on station . With this adjustment, if there is at least one task in the positive zoning restriction allocated to station , then the priorities of other tasks are boosted.

4.5. Decoding Scheme for the TALBP-II with Assignment Restrictions

The procedure of the decoding scheme is introduced as follows.

Step 1. Set the initial cycle time .

Step 2. Open a new mated-station.

Step 3. Choose a side with greater capacity of the current mated-station. If the capacities of both sides are equal, select the left side by default.

Step 4. Update the priority values with task assignment rule.

Step 5. If task ,  , is not in the negative zoning restriction, go to Step 5. Else, if and the other task has been allocated to the current mated-station, then .

Step 6. If , then .

Step 7. If , then .

Step 8. If task ,  , is not in the synchronous restriction, go to Step 8. Else, if tasks ,   in synchronous restriction can be assigned, then assign the two tasks and go to Step 10; otherwise, and go to Step 9.

Step 9. If no task whose priority value is larger than one exists, select another side and execute Steps 2–7. If no tasks can be assigned to either side, go to Step 2; else, select the task with the largest priority and allocate the tasks to the selected station, and then go to Step 10.

Step 10. If some tasks are still not assigned, go to Step 3; if all the tasks are allocated, go to Step 11.

Step 11. Choose the largest finishing time of the stations as the current cycle time and update the initial cycle time.

In this procedure, Step 4 considers the cycle time, direction, and precedence restrictions. Steps 5, 6, 7, and 8 deal with negative zoning restrictions, positional restrictions, positive zoning restrictions, and synchronous restrictions, respectively. After executing Steps 4–8, the task can be assigned only if . Note that the initial cycle time is set to   (); then the cycle time is updated if the current cycle time is better than the incumbent one with . Therefore, the cycle time is reduced gradually.

4.6. Cost Function

In the decoding scheme, the synchronism restriction and negative zoning restriction are satisfied while positive zoning restriction and positional restrictions may be violated. Therefore, the two factors are considered in the cost function as follows: where and are the number of the violated positional restrictions and the number of the violated positive zoning restrictions and and are the penalty coefficients. and should be large enough to obtain a solution which satisfies all the restriction, and thus and are both set equal to 1000.

5. Iterated Greedy Approach for TALBP-II with Assignment Restrictions

The iterated greedy (IG) algorithm is a local search method and it is can be regarded as a simple approach with less sophisticated parameters than other hybrid algorithms [38]. Despite its simplicity, the IG algorithm has shown promising results for different scheduling problems.

IG starts with constructing a high performing initial solution. Then random destruction is proposed to remove some tasks and reconstruction is utilized to reinserts these tasks back. After reconstruction, a different solution can be obtained and then the acceptance criterion is applied to determine whether the incumbent can be substituted. Optionally, after the acceptance criterion phase, a local search procedure aims at finding better solutions locally. The random destruction, reconstruction, acceptance criterion, and local search together make up a loop. The procedure of IG for TALBP-II with assignment restrictions is explained as follows.

5.1. Initialization with Modified NEH Heuristic

The NEH heuristic [39] has been shown to be effective for the flow shop scheduling problem, but it has been not applied to the TALBP-II, which can be regarded as a special flow shop scheduling problem. This paper develops a modified NEH (mNEH) for TALBP-II explained as follows.

Step 1. Generate an initial task permutation    with RPW heuristic [37].

Step 2. Remove the 2nd task from and obtain the solution by inserting it into position 1. Then the better one is selected.

Step 3. Remove the remaining tasks ,  , and obtain the best solution by inserting it to all the positions before its incumbent.

The mNEH differs from the original NEH in two aspects: the well-known ranked positional weight in assembly line balancing is proposed to gain initial task permutation; the tasks are not inserted one by one and the following parts of the task permutation are maintained, guaranteeing that a feasible solution can be obtained each time. It is worth noting that the mNEH heuristic finds much better solutions than just using the RPW heuristic. The difference is so clear that no statistical test is needed to prove the effectiveness of the proposed mNEH heuristic.

5.2. Improved Local Search

The insert operator is selected as the neighbor structure after checking the swap operator and insert operator. Based on the work of Ruiz and Stützle [38], a local search is developed and shown in Algorithm 1. In Algorithm 1, a task is removed from the current position and inserted into all the possible positions. The new generated schedule will replace the incumbent one when an improvement can be achieved. The entire procedure iterates until no improvement can be achieved.

The local search of Algorithm 1 aims at finding a local optimum, but it may lose the local optimum since some tasks may not be tested, and it requires a lot of computational time due to inserting a task in all the possible positions. To overcome the first drawback, all the tasks are selected in a given permutation . Initial experiments show that the best permutation performs better than a random task permutation, and thus the best permutation is selected as the referred permutation. As for the second drawback, the key point is eliminating invalid repetitions of the decoding while preserving the ability of finding the best permutation obtained by inserting a selected task in all possible positions. After checking the solutions of inserting a task in all possible positions, we can see that a lot of solutions have some fitness. In fact, some new task permutation may conflict with the precedence restriction, and this kind of task permutations corresponds to a task permutation satisfying precedence restriction, which indicates that the new task permutation conflicted with the precedence restriction is not needed. Therefore, the improved local search inserts a task into a new position only when it follows all its predecessors and precedes all its successors [22]. The improved local search is depicted in Algorithm 2.

5.3. Destruction, Reconstruction, and Acceptance Criterion

In order to escape local optima, destruction and reconstruction are applied to obtain a new solution. Then, the acceptance criterion is utilized to determine whether the new solution replaces the incumbent. In the destruction phase of Ruiz and Stützle [38], some randomly selected tasks are removed from the incumbent solution and inserted into a task list which consists of removed tasks. We introduce a small modification in which the tasks are moved to the back of the task permutation, which makes sure that each task permutation can acquire a feasible solution. And in the reconstruction phase, the back tasks are reinserted into the former stations one by one. Once a new solution is obtained after the destruction, reconstruction, and local search phases, the acceptance criterion is adopted to check whether this one is acceptable. We employ the acceptance criterion similar to the one suggested by Pan et al. [10] and the constant temperature is calculated with . The procedure of IG is explained in Algorithm 3.

Note that the number of removed tasks and the parameter are important parameters and need to be determined. A large may result in a completely new solution while a small cannot help the algorithm escape from a local optimum. Similarly, a large may accept poor-quality solutions, while a small can result in no acceptance of new solutions.

6. Computational Results

The computational tests are carried out to prove the effectiveness of the priority-based decoding schemes for TALBP-II with assignment restrictions and the high performance of the improved IG algorithm. All the benchmark problems with different cycle times are solved, which range from small-size problems, P9, P12, P16, and P24, to large-size problems, P65, P148, and P205. P9, P12, and P24 are taken from Kim et al. [1]. P16, P65, and P205 are taken from Lee et al. [18]. P148 from Bartholdi [14] is modified just like Kim et al. [6]. As for the TALBP-II with assignment restrictions, the additional restrictions are generated for the study and they are listed in Table 1. For the coefficients, ,  ,  ,  , in the objective function, , , , and are checked and are chosen. Since the sizes of different problems differ from each other, we set the elapsed CPU time  ms as a termination criterion for all cases and is set to 15.

6.1. Evaluation of the Proposed Priority-Based Decoding Scheme

This section tests the performance of the proposed priority-based decoding scheme by comparing it with the reported ones. There are two components to be considered: the performance of the priority-based decoding on the TALBP-II and the performance of the new methods to deal with assignment restrictions.

For the first component, two genetic algorithms (GA) with different decoding schemes are compared and all the algorithms have the same parameters. They are GA1 with the station-oriented decoding scheme [6] and GA2 with the proposed decoding scheme. All the large-size problems are tested and each case runs 20 times. The average relative deviation index (RDI) for each case is utilized for comparison and the RDI can be calculated using the following expression: where, is the fitness obtained by one running and and are the best fitness and worst fitness of 40 individuals for a same case, respectively.

In order to check whether there is statically significant difference between the two decoding schemes, we use the parametric test, but these RDI values show a strong deviation from the normality, which is caused by the difference of the benchmark problems. Therefore, we propose a nonparametric Wilcoxon matched-pairs signed rank test. In addition, all results of the decoding schemes are transferred in the following way: the best result is assigned to rank 1 while the worst result is marked with rank 2. The analysis shows there is a significant difference between the two decoding schemes with values close to zero and the means plot with 95% minimal significant confidence intervals is depicted in Figure 2. It can be seen that the average rank for GA2 with the proposed decoding is 1, which proves the superiority of the proposed decoding scheme.

Figure 2 

Mean plot of average ranks with 95% confidence intervals.

In fact, the original station-oriented decoding scheme cannot reduce the sequence-dependent idle time effectively since it only uses a heuristic method. The proposed priority-based decoding, on the contrary, takes the sequence-dependent idle times and the balance of the stations into account, which can further reduce the idle times on the stations.

For the method to deal with assignment restrictions, we also utilized two genetic algorithms: GA3 with the published method of dealing with assignment restrictions in Yuan et al. [32] and Li et al. [34] and GA4 with the proposed method of dealing with assignment restrictions. Based on the computational test, the GA4 outperforms the GA3 for all the cases; namely, the improved method outperforms the original one. Also, there is statically significant difference between the two algorithms. There are mainly two reasons leading to the high performance of the new method of dealing with assignment restrictions: new positional restriction handling increases the possibility of finding a solution which satisfies positional restriction and new positive zoning restriction handling can reduce the sequence-dependent idle time caused by assigning the tasks in positive zoning restriction together.

6.2. Calibration of the Iterated Greedy Algorithm

In this part, we calibrate the iterated greedy algorithm and determine in the destruction phase and in the acceptance criterion. All the possible combinations of the two factors are tested and the full factorial design is listed as follows:(i): 4 levels (4, 8, 12, 16);(ii) : 4 levels (0.1, 0.5, 1, 5).

Since different problems are involved, we select the best combination for each problem. Taking the largest-size problem, P205 [18], as an example, the calibration procedure is introduced as follows. To guarantee the validity of the calibration, 5 cases for P205 are solved and average results of each case are recorded. After finishing all the experiments, we also propose the RDI to measure the solutions. Then, the average RDI value of each case is proposed for statistical analysis. The algorithm is coded in C++ programming language with Microsoft Visual Studio 2012 which is running on a set of personal computers with Intel® Core2™ CPU 2.33 GHZ, 3.036 GB RMA.

After carrying out all the runs, the analysis of variance (ANOVA) technique [40] is utilized to analyze the date, after checking the independence of the residuals, homogeneity of variance, and normality of the residuals. For ANOVA results, there is a statistically significant difference among the different levels if the value of one factor is less than a predetermined number ( is set equal to 0.05). Table 2 reports the results for RDI values, and has a statistically significant effect on RDI at the 95.0% confidence. And the mean plots for the factors and are depicted in Figure 3. According to the ANOVA results, we choose at first and, then, the value of is fixed and is chosen.

Figure 3 

Mean plot for the factors and for the IG ANOVA calibration experiment.

Notice that it is more convenient to divide all the problems into several groups and decide the parameters for each group. This paper selects the parameters for each problem due to different performance of an algorithm on different problems, and the homogeneity of variance and normality of the residuals are violated if we calibrate the parameters for several problems together.

6.3. Performance Comparison among Algorithms

This section aims at showing the effectiveness of the IG on TALBP-II and TALBP-II with additional restrictions. The IG is compared with several recent algorithms: a tabu search algorithm (TS) [20], a simulated annealing algorithm (SA) [22], a late acceptance hill-climbing algorithm (LAHC) [32], a two-ant colony optimization algorithm (2-ANTBAL) [4], a particle swarm optimization algorithm with negative knowledge (PSONG) [25], a genetic algorithm (GA) [1], a teaching-learning-based optimization algorithm (TLBO) [34], and a bee optimization algorithm (BA) [21]. In order to show the superiority of the improved local search, IG with LS1 is marked with IG1 and the improved IG with LS2 is marked with IG2. All the algorithms are calibrated with the same procedure in Section 6.2, and all the parameters and the code in C++ language are available upon request from the authors.

Since the IG algorithms have not been applied to the TALBP-II without additional restrictions, we first compare the performances of these algorithms on the TALBP-II without additional restrictions. All the cases are solved for 20 times, and the average results on 14 small-size cases are reported in Table 3. The optimal solution (OPT) is also included which can be obtained by General Algebraic Modeling System 23.0 (GAMS)/CPLEX. It can be observed from Table 3 that all the algorithms can find the optimal solution in each run. Computational results demonstrate the effectiveness of the proposed IG2 for small-size problems.

As for the large-size problem, the average RDI value of each case is reported in Table 4 and the best cycle time of each case is shown in Table 5. In Table 4, we observe that three local search algorithms, TS, SA, and LAHC, do not obtain satisfactory results, while the IG2 as a local search method can still gain remarkable results. In particular, the IG2 acquires the best RDI values for almost all the largest cases and its average RDI is only 4.1%. Specifically, the IG2 outperforms the TS, SA, and LAHC for 24, 24, and 24 cases, respectively. As for swarm-based algorithms, the PSONG and 2-ANTBAL obtain remarkable results. Table 5 shows the best result by each algorithm with twenty runs. The lower bound (LB) of the cycle time [6] and the best solutions by a neighborhood genetic algorithm (n-GA) [6] is also reported. Contrary to the results on the average results, the local search algorithms can obtain better results than swarm-based algorithms partly. IG2 outperforms the compared algorithms regarding the best solutions for most cases and it improves the results by n-GA for 17 cases. Among all 25 large-size cases, IG2 outperforms TS, SA, and LAHC for 20, 11, and 15 cases.

Based on the above computational results, we can draw the following conclusions. First, some swarm-based algorithms cannot obtain satisfying results on the best solutions since they lack the ability of strong local search. Second, the local search methods, TS, SA, and LAHC, perform worse than population-based methods on the average results. Third, the destruction and reconstruction phase are an effective method to escape from local optima, which is confirmed by the superiority of the IG2 over TS, SA, and LAHC about the average results. Fourth, the new local search is proved efficient by the superiority of the IG2 over the IG1.

In order to confirm that the IG2 is statistically better than the compared ones for the average results, we also carry out statistical analysis. Since the normality of the average RDI values is violated, we carry out a nonparameter Friedman rank-based test [41]. In addition, the results of different algorithms are transferred so that the best result is marked with a rank of 1 and the worst result on the average RDI is with 10 since there are 10 algorithms. The results of the analysis show that the values for the average ranks are close to zero, which indicates there is a statistically significant difference among the average ranks of these compared algorithms. And we also depict the means plot with 95% minimal significant difference confidence intervals in Figure 4 for further studying the difference.

Figure 4 

Means plot of the ranks of the average solutions with 95% confidence level.

As you see, a total of 10 algorithms are compared. If ordering these algorithms from the best ranking to the worst ranking, an order of algorithms can be achieved: IG2, PSONG, 2-ANTBAL, TLBO, BA, GA, IG1, LAHC, TS, and SA. As stated above, the local search algorithms, SA, TS, and LAHC, are statistically worse than the swarm-based algorithms. Still, as a local search method, the IG2 is statistically better than all the compared algorithms on the average results. According to these results, it is suggested that the proposed IG2 statistically outperforms all the compared algorithms.

As for TALBP-II with additional restrictions, we also utilize all the algorithms to solve the TALBP-II with additional restrictions. The computational results are also analyzed with statistical techniques and these algorithms show similar results on the TALBP-II without additional restrictions. In fact, only the decoding schemes of the algorithms are slightly changed, and other parts of the algorithms remain unaltered. For simplification, we only show the best results by IG2 in Table 6.

For small-size problems, the results by IG2 are compared with optimal results by GAMS and the runs are interrupted when the optimal solution is discovered. For large-size problems, the results of TALBP-II with additional restrictions are compared with those of TALBP-II without additional restrictions. As can be seen in Table 6, the IG2 and GAMS can both find optimal solutions for all the small-size problems (P9, P12, P16, and P24). But for P24, GAMS needs much more computational time and IG2 can find the optimal solutions for small-size problems within 1 second. As for the large-size problems, GAMS cannot solve them owing to the tremendous compute. However, IG2 as an effective metaheuristic can also find promising results. Taking the P205 as an example, you can see that the IG2 can find the same best cycle time for the TALBP-II with additional restrictions as that for TALBP-II without additional restrictions. All the computational results suggest the superior performance of IG2 for TALBP-II with additional restrictions.

7. Summary and Conclusion

In this paper, a simple and effective iterated greedy (IG) algorithm is developed for the two-sided assembly line balancing problem type-II (TALBP-II) with assignment restrictions. The NEH heuristic is modified for TALBP-II as the initialization procedure. A new local search with referred permutation is developed, and acceleration by eliminating the insert operator that conflicted with precedence restrictions is developed to speed up the search process while preserving the ability of finding a local optimum.

A new priority-based decoding scheme is also proposed to reduce sequence-dependence idle time, balance the workload, and deal with assignment restrictions. To be specific, the task assignment rules are embedded into the decoding scheme to reduce sequence-dependent idle time and balance the workload on each station. A new method to deal with the positional restriction increase the possibility of finding a feasible solution by preventing assigning the tasks with positional restriction to the former mated-station of the predetermined one. And a new method to deal with positive zoning restriction is applied to further reduce the sequence-dependent idle time by allocating the tasks with positive zoning restriction separately.

Computational studies are carried out to demonstrate the superiority of the developed priority-based decoding scheme and the effectiveness of the proposed IG algorithm. The priority-based decoding scheme is compared with published ones, and computational results show that the priority-based decoding scheme can reduce the sequence-dependent idle times, balance the workload, and deal with assignment restrictions effectively. The computational results of IG on the TALBP-II are compared with those of eight recent algorithms, and the IG obtains superior results on both the average results and the best results, which prove its strong local search and the remarkable ability of escaping from local optima. As for the TALBP-II with additional restrictions, IG can find all the optimal solutions for small-size problems and also obtain promising results for large-size problems.

Future research can apply the IG algorithm to solve other complex assembly line balancing problems, such as the mixed-model assembly line. The priority-based encoding and decoding, especially the methods to reduce idle times and deal with assignment restrictions, may be modified to address other two-sided assembly line problem.

Notations

Competing Interests

The authors declare that they have no competing interests.

Acknowledgments

This research work is funded by the National Natural Science Foundation of China (Grant nos. 51275366 and 51305311).