Sage Journals: Discover world-class research

Abstract

In order to solve the simple assembly line balancing problem of type 1, an improved immune algorithm is proposed. Compared with the basic immune algorithm: (1) The similarity formula between any two antibodies is simplified in the improved immune algorithm. (2) Introducing immune adjustment, vaccine extraction, vaccination, and immune selection, the improved immune algorithm prevents population degradation. The validity of the proposed improved immune algorithm is tested by means of two computational examples with reference instances, and the results show that the proposed improved immune algorithm is an efficient approach to solve the simple assembly line balancing problem of type 1.

Keywords

Immune algorithm assembly line balancing precedence matrix smooth index termination condition

Introduction

The assembly line balancing problem (ALBP) is to determine the assignment of the tasks to an ordered sequence of stations such that each task is assigned to exactly one station, no precedence constraint is violated, and some selected performance measure is optimized.¹ The ALBP is an important issue of the manufacturing field, and it directly affects the production efficiency and the utilization of manufacturing resources.

The ALBP was first mathematically formulated by Salveson² in 1955. Because of the importance of the ALBP (especially in the manufacturing industry), it has attracted interests from a lot of scholars and engineers in the past 60 years.

Generally speaking, the ALBP is divided into two classes: simple assembly line balancing problem (SALBP) and generalized assembly line balancing problem (GALBP). The SALBP means that a single product is produced, the set of tasks are of deterministic operation times, and the set of workstations are arranged in a straight line. Meanwhile, GALBP includes all of the problems that do not belong to the SALBP class, such as mixed-model or multimodel line, parallel stations, U-shaped or two-sided lines, stochastic task times, etc. According to the objectives, the SALBP can be categorized into three types: (1) simple assembly line balancing problem of type 1 (SALBP-1): minimize the number of stations for a given cycle time which is mainly used in the design and installation phase of the assembly line. (2) SALBP-2: minimize the cycle time given the number of workstations which is mainly used to optimize and adjust the existing assembly line. (3) SALBP-E: balance the workload while both the workstation and the cycle time are optimized.

In this paper, only SALBP-1 will be considered, because it is widely used in industry to reduce number of workstations/machines/workers. These reductions lead to decrease production cost and improve the cost competitiveness of the plant.³

The remainder of the paper is organized into five sections, i.e. literature review, mathematical model of SALBP-1, the improved immune algorithm (IIA), case study and discussion, and conclusions.

In summary, the methods to solve SALBP-1 discussed in literatures can be roughly classified into three kinds: exact method, heuristic approach, and artificial intelligence method.

Sprecher⁴ presented a branch-and-bound algorithm for solving SALBP-1. The computational results indicated that the algorithm can compete with the best algorithms currently available for solving SALBP-1. Easton et al.⁵ presented two network-based algorithms for solving the SALBP-1. Computational tests indicated that these algorithms were more efficient than previous network-based methods (including dynamic programming methods) and favourably compare with branch-and-bound methods. Peeters and Degraeve⁶ presented a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition to solve SALBP-1. Computational results showed that the lower bound was equal to the best-known objective function value for the majority of the instances. Moreover, the new LP-based lower bound was able to prove optimality for an open problem. Liu et al.⁷ presented a branch-and-bound algorithm to solve SALBP-1. The proposed algorithms consisted of a constructive and two destructive algorithms. The computational results showed that the proposed algorithms are efficient. Bautista and Pereira⁸ presented a bounded dynamic programming to solve SALBP-1. The results obtained by the procedure showed that the implementation was capable of obtaining an optimal solution of 267 out of the 269 instances found in the literature. As well, it also found the best-known solution for another of the instances. Sewell and Pereira⁹ presented a branch, bound, and remember algorithm for solving SALBP-1. The algorithm combined a variety of existing methods to create a novel approach that was computationally superior to all existing exact algorithms reported in the literature. In particular, for 269 known benchmark problems, the algorithm successively found the best solutions and proved their optimality for all these problems, typically in a fraction of a second. Vila and Pereira¹⁰ presented a new exact algorithm for solving SALBP-1. The algorithm was a station-oriented bidirectional branch-and-bound procedure based on a new enumeration strategy that explores the feasible solutions tree in a non-decreasing idle time order. The tests showed that the proposed algorithm outperformed the best existing exact algorithm for solving SALBP-1, verifying optimality for 264 of the 269 benchmark instances.

Because the SALBP-1 belongs to NP-hard class of combinatorial optimization problems, the exact methods are computationally inefficient in solving large-scale problem, many researchers turn their interests to develop efficient heuristic approaches to solve SALBP-1.

Helgeson and Birnie¹¹ presented a method called the ranked positional weight technique to solve SALBP-1. Hoffmann¹² presented a procedure by applying the FORTRAN program to solve SALBP-1. The procedure led to optimal line balances by operation on a matrix of zeros and ones called a ‘Precedence Matrix’. Hackman et al.¹³ proposed a simple, fast, and effective heuristic named immediate update first-fit for the SALBP-1. The algorithm introduced heuristic fathoming as a technique for reducing the size of the branch-and-bound tree. Fleszar and Hindi¹⁴ presented a new heuristic algorithm and new reduction techniques for the SALBP-1. The new heuristic is based on the well known Hoffmann heuristic and builds solutions from both sides of the precedence network to choose the best. The computational efficiency enables it to arrive at optimal or near-optimal solutions for large-scale problem instances in less than 2 s of computing time on a PC. Kilincci and Bayhan¹⁵ developed a heuristic algorithm, P-in, based on P-invariants of PNs to solve SALBP-1. The algorithm was coded in MATLAB, and its efficiency was tested on Talbot’s and Hoffmann’s benchmark datasets according to some performance measures and classifications. Yeh and Kao¹⁶ proposed a new efficient heuristic, based on a recent bidirectional approach and the famous critical path method widely used in project management, to resolve the issue of task assignment for SALBP-1. The effectiveness of the proposed heuristic algorithm was verified by sample problems. Otto and Otto¹⁷ provided recommendations for ad hoc, i.e. without pretests, construction of priority rules and illustrated their effectiveness on the example of ALBP with resource constraints. The authors showed in a split second priority rules achieve much better results than 20–100s of an exact algorithm or a metaheuristic, and may reduce the warming-up phase of algorithms significantly.

Because of the differences among the SALBP such as the numbers of tasks, precedence relations between tasks, so far there hasn’t been a heuristic rule to ensure that all of SALBP-1 can get the optimal solution.

In recent years, numerous researchers have employed artificial intelligence method to solve SALBP-1.

Ponnambalam et al.¹⁸ proposed a multi-objective genetic algorithm to solve SALBP-1. It was found that the proposed genetic algorithm performs better in all the performance measures than the heuristics. However, the execution time for the GA was longer, because the GA searches for global optimal solutions with more iterations. In order to solve the deterministic and single-model ALB problem, Sabuncuoglu et al.¹ developed a new GA with a special chromosome structure that is partitioned dynamically through the evolution process. The results of extensive computational experiments indicated that the proposed GA approach outperforms the well known heuristics in the literature. Goncalves and De Almeida¹⁹ presented a hybrid genetic algorithm for the SALBP-1. The chromosome representation of the problem was based on random keys and the assignment of the operations to the workstations was based on a heuristic priority rule. The computation results validated the effectiveness of the algorithm. Gonçalves and De Almeida²⁰ presented a new hybrid genetic algorithm for the SALBP-1. The approach combined a heuristic priority rule, a local search procedure, and a genetic algorithm. The genetic algorithm used a random keys alphabet, an elitist selection, and a parameterized uniform crossover. The computation results validated the effectiveness of the algorithm. Yu and Yin²¹ presented an adaptive genetic algorithm to solve SALBP-1. The computational results demonstrated that the proposed adaptive genetic algorithm is an effective algorithm. Yolmeh and Kianfar²² proposed a hybrid genetic algorithm to solve SALBP-1. The computational results validated the effectiveness of the algorithm. Blum²³ proposed a hybrid ant colony optimization approach called Beam-ACO for the SALBP-1. The results showed that Beam-ACO is a state-of-the-art metaheuristic for the SALBP-1. Sulaiman et al.²⁴ presented an approach based on the ant colony optimization technique to address the SALBP-1. It introduced an approach to dynamically assign the value of priority rule or heuristic information during the task selection phase by allowing the ant to look forward its direct successors during the consideration in selecting a task to be assigned into a workstation. The computation results validated its effectiveness. Dou et al.²⁵ proposed a direct discrete particle swarm algorithms (DDPSA) to solve SALBP-1. In the presented DDPSA, a particle is a permutation of N integers that represents the feasible task sequence directly, and a new multi-fragment crossover is proposed to update the particle and maintain the feasibility of the task sequence. In order to avoid the stagnation of search in local optimum, the fragment mutation is embedded into the DDPSA. The results showed that the DDPSA is effective and powerful for the SALBP-1. Lapierre et al.²⁶ proposed a novel tabu search algorithm for solving both SALBP-1 and non-standard versions of this problem coming from real life applications. Computational results on both showed that the method was efficient. Guden and Meral²⁷ proposed an adaptive simulated annealing method to solve the real life SALBP-1 of a dishwasher producer which consisted of approximately 300 tasks, 400 precedence relations per product model. Performance of the algorithm was tested on several problem instances from the literature and found to be satisfactory. Then it was used to solve the real life problem instance considered and a better solution than the current one was obtained.

Some more detailed literature review of the ALBP can be found in the literature.^28–33

The remainder of the paper is as follows: The mathematical model of SALBP-1 is provided. The next section presents the IIA for finding the solution. Three computational examples are used to test the proposed IIA. Conclusions are given in the final section.

Mathematical model of SALBP-1

The notations that will be used throughout the paper are described in the Appendix.

Mathematical formulation

The mathematical formulation is as follows.

Objective function

Generally speaking, the objective function of SALBP-1 is to minimize the number of the workstations, i.e.

f_{1} = min m

The smooth index is adopted as the auxiliary objective function named f₂, i.e.

f_{2} = SI = \sqrt{\frac{1}{m - 1} \sum_{k = 1}^{m} (C - {ST}_{k})^{2}}

So, the objective function is

min f = w_{1} \times f_{1} + w_{2} \times f_{2} = w_{1} \times m + w_{2} \times \sqrt{\frac{1}{m - 1} \sum_{k = 1}^{m} (C - {ST}_{k})^{2}}

(1)

where w₁ and w₂ are the weighted coefficients. The value of w₁ and w₂ should be determined according to the simulation results of the specific example.

Constraint conditions

\sum_{k \in M} x_{ik} = 1, \forall i

(2)

\sum_{k \in M} k \cdot x_{ik} \leq \sum_{k \in M} k \cdot x_{jk}, \forall P' (i, j) = 1

(3)

\sum_{i \in N} x_{ik} \cdot t_{i} \leq C, \forall k

(4)

x_{ik} \in {0, 1}, \forall i, k

(5)

Equation (2) ensures that every task is assigned to one and only one workstation. Constraint (3) defines precedence relationships between tasks i and j. Constraint (4) ensures that the processing time of every workstation has not exceeded the cycle time. Constraint (5) defines the variable domains.

The IIA

Affinity

In the immune optimization algorithm, the antigens correspond to optimization problems and the antigens are usually objective function, and the antibodies correspond to the optimum solution to the problems.

The affinity between antigen and antibody corresponds to the matching between feasible solution and optimum solution which is called antibody fitness. The larger the antibody fitness is, the closer the feasible solution is to the optimum solution. The antibody fitness is calculated as shown in equation (1).

Affinity between antibodies corresponds to the similar degree between feasible solutions which is called similarity. The larger the similarity is, the more similar the feasible solutions are.

Suppose M antibodies, each antibody is composed of N genes, r species can be chosen in each genetic locus ranging from k₁ to k_r, i(j) represents the values of antibody i on the jth genetic locus (Figure 1).

Figure 1.

Allele schematic drawing.

Obviously, i(j) $\in k_{t}$ , where $1 \leq i \leq M, 1 \leq j \leq N, 1 \leq t \leq r$ .

The average information entropy of the M antibodies is defined as follows

H (M) = \frac{1}{N} \sum_{j = 1}^{N} H_{j} (M)

(6)

where

H_{j} (M)

represents the information entropy of the jth gene among the M antibodies and it is defined as follows

H_{j} (M) = \sum_{i = 1}^{r} (- p_{ij} \cdot \log_{2} p_{ij})

(7)

Therefore, equation (8) can be derived from equations (6) and (7)

H (M) = \frac{1}{N} \sum_{j = 1}^{N} \sum_{i = 1}^{r} (- p_{ij} \cdot \log_{2} p_{ij})

(8)

where

p_{ij}

represents probability that the value of the jth genetic locus is k_i among the antibody population.

If (1) the value of the jth genetic locus is k_i, and (2) the frequency that k_i occurs is $m_{ij}$ , then $p_{ij} = m_{ij} / M$ .

The similarity $S_{uv}$ between antibody $u$ and v is defined as follows

S_{uv} = \frac{1}{1 + H (2)}

(9)

where

H (2)

represents the average information entropy between antibody

u

and v.

H (2)

can be calculated by equation (8), but the process of solving

H (2)

is too complicated. It simplifies

H (2)

as follows.

$u (j) = v (j)$ means that the value of the jth genetic locus of antibody u is equal to that of antibody v, i.e. antibody u and antibody v have allele j.

$| u (j) = v (j) |$ represents the total numbers of allele j between antibody u and antibody v. Further, let $Neg = | u (j) = v (j) |$ .

$\forall j \in [1, N]$ , if $u (j) = v (j)$ , further let $u (j) = v (j) = k_{1}$ , then $m_{1 j} = 2$ , $p_{1 j} = 1$ , and $(- p_{ij} \log_{2} p_{ij}) = (- p_{1 j} \log_{2} p_{1 j}) = 0$ ;

$\forall j \in [1, N]$ , if $u (j) \neq v (j)$ , further let $u (j) = k_{1}$ , $v (j) = k_{2}$ , then $m_{1 j} = 1$ , $m_{2 j} = 1$ , $p_{1 j} = 1 / 2$ , $p_{2 j} = 1 / 2$ , and $(- p_{ij} \log_{2} p_{ij}) = (- p_{1 j} \log_{2} p_{1 j}) + (- p_{2 j} \log_{2} p_{2 j}) = 1$ .

According to equation (8), $H (2)$ can be derived as follows

H (2) = \frac{N - Neg}{N}

(10)

According to equations (9) and (10), $S_{uv}$ can be derived as follows

S_{uv} = \frac{N}{2 N - Neg}

(11)

Concentration

Antibody concentration c_i means the numbers of the antibodies similar to antibody i divided by the antibody population M, and it is defined as follows

c_{i} = \frac{1}{M} \sum_{j = 1}^{M} Q_{j}

(12)

where

Q_{j} = {1 if S_{ij} \geq λ 0 if S_{ij} < λ

, and λ means similarity threshold ranging from 0.9 to 1.

Antibody survival expectancy

In order to preserve the diversity of the antibody population and avoid premature convergence, antibody survival expectancy is used to promote and inhibit the antibody population, and the antibody survival expectancy is defined as follows

e_{i} = f_{i} \cdot c_{i}

(13)

Obviously, the antibody with low fitness or low concentration will be promoted, and that with high fitness or high concentration will be inhibited. As a result, this forms a new diversity keeping strategy.

Memory vault

Memory vault is used to save the excellent antibody and the original memory vault is usually designed by the engineers.

The IIA algorithm flow

Step 1. Setup parameters

M: the population size.

L: the number of immune adjustment.

P_i: the immune vaccination probability.

λ: the similarity threshold.

MNI: the maximum number of iterations

Step 2. Initialize

The M individuals are generated randomly. But it does not guarantee that all of the individuals meet the constraint (3). If an individual doesn’t meet the constraint (3), then the individual is invalid. In consideration of this, the following algorithm 1 presents the steps on how to convert any individual to meet the constraint (3), i.e. to meet the assembly precedence matrix.

Algorithm 1

Convert any individual to meet the assembly precedence matrix

Notations:

n is the number of tasks.

$P'$ represents the assembly precedence matrix, and $P'$ is n-order matrix.

A represents any an individual, and A is a matrix with n rows and one column.

1: for i = 1: n − 1

2: If $P' (A (i + 1, 1), A (i, 1)) = 1$ , then exchange the position of $A (i + 1, 1)$ and $A (i, 1)$ in A.

3: end

4: end

Step 3. Immune adjustment

The diversity of antibody is the important characteristic of the immune system. The solving steps of immune adjustment are described as follows.

Generating randomly L individuals;

Converting the L individuals to meet the constraint (3) according to algorithm 1;

Calculating antibody survival expectancy e_i according to formulas (13), and selecting M individuals as the (t + 1)^th generation population ${pop}^{(t + 1) *}$ from the (M + L) individuals in ascending order.

Step 4. Immunization

Immunization mainly includes two stages: vaccine extraction and vaccination.

Step 4.1 Extracting the vaccine

Because the global optimal individual P_g is close to the global optimal solution in the process of IIA, P_g is chosen as vaccine.

Step 4.2 Vaccination

Let $M_{1} = M * p_{i}$ , the symbol of x means the minimal positive integer that is greater than or equal to x.

First, M₁ individuals are selected randomly as ${pop}_{A}^{(t + 1) *}$ from ${pop}^{(t + 1) *}$ . Second, the immune vaccination operation is performed on ${pop}_{A}^{(t + 1) *}$ and P_g. The principle of immune vaccination operation is shown in Figure 2.

Select a positive integer randomly as the crossover point from 1 to $n - 1$ , where n is the gene number of chromosome, i.e. the number of tasks.

Maintain the left segment of the crossover point of parent, in vaccine delete these genes which are the same as those in the left segment of the crossover point of parent, maintain the original order of the remaining genes of vaccine to replace the right segment of the crossover point of parent, i.e. offspring is generated.

Figure 2.

The process of single point crossover.

After the immune vaccination operation, ${pop}_{A}^{(t + 1) *}$ is marked as ${pop}_{B}^{(t + 1) *}$ .

Step 5. Immune selection

The principle of immune selection is as follows.

If $f ({pop}_{A}^{(t + 1) *}) > f ({pop}_{B}^{(t + 1) *})$ , then ${pop}_{B}^{(t + 1) *}$ is selected instead of ${pop}_{A}^{(t + 1) *}$ ;

If $f ({pop}_{A}^{(t + 1) *}) \leq f ({pop}_{B}^{(t + 1) *})$ , then ${pop}_{A}^{(t + 1) *}$ is selected instead of ${pop}_{B}^{(t + 1) *}$ .

Based on the above principle, M₁ individuals are selected from ${pop}_{A}^{(t + 1) *}$ and ${pop}_{B}^{(t + 1) *}$ , and the M₁ individuals are marked as ${pop}_{C}^{(t + 1) *}$ . Then a new population ${pop}^{(t + 1)}$ is generated, i.e. ${pop}^{(t + 1)} = {pop}^{(t + 1) *} - {pop}_{A}^{(t + 1) *} + {pop}_{C}^{(t + 1) *}$ .

Step 6. Update the memory vault

The objective function of all the $M$ individuals in ${pop}^{(t + 1)}$ is calculated according to formula (1). Then the individual corresponding to the minimum value of the objective function is denoted as $P_{g}^{(t + 1)}$ . If $f (P_{g}^{(t + 1)}) \leq f (P_{g}^{(t)})$ , then $P_{g} = P_{g}^{(t + 1)}$ . Otherwise, $P_{g} = P_{g}^{(t)}$ .

Step 7. Termination condition

Generally speaking, the algorithm is stopped when it satisfies one of the following three conditions:

The number of iterations reaches a predefined number;

The objective fitness of the best individual reaches a predefined threshold;

The objective fitness of the best individual converges with the increase of iterations, so does the average value of the population’s objective fitness.

In this paper, condition 1 is selected as the termination condition of the IIA. Once condition 1 is satisfies, then the IIA goes to Step 8; otherwise, it goes to Step 3.

Step 8. Output

Output the best solution.

The pseudo-code of the IIA is shown in Figure 3.

Figure 3.

Pseudo-code of the IIA. IIA: improved immune algorithm.

Case study

The IIA was coded in MATLAB and the experimental results were obtained on a PC with 2 GHz CPU and 3 GB RAM. Referring to Goncalves and Almeida³⁴ and Zhang et al.,³⁵ the IIA had the following configuration:

The population size M equals the number of tasks in the problem.

The number of immune adjustment L is equal to $0.15 * M$ .

The immune vaccination probability P_i is equal to 0.7.

The similarity threshold $λ$ is equal to 0.91.

The maximum number of iterations MNI is equal to 3*M.

Example 1

Four classes of instances of SALBP-1 are selected to test the effectiveness of the IIA and the experimental results are presented in Table 1. The results of the IIA are compared with the ones obtained by DPSO.³⁶ For comparison purpose, the listed generation number of the best solution of IIA in Table 1 is the best one out of 10 runs for each class of instances given the cycle time.

Table 1.

Experiment results for four datasets.

Name	Number of tasks	Cycle time	Optimal number of stations	Best number of stations		Generation number of the best solution
Name	Number of tasks	Cycle time	Optimal number of stations	DPSO	IIA	DPSO	IIA
Mitchell	21	21	5	5	5	1	1
		26	5	5	5	1	1
		35	3	3	3	1	1
		39	3	3	3	1	1
Sawyer	30	30	12	12	12	1	1
		36	10	10	10	2	1
		54	7	7	7	1	1
		75	5	5	5	1	1
Tonge	70	364	10	10	10	1	1
		410	9	9	9	1	1
		468	8	8	8	1	1
		527	7	7	7	1	1
Arcus1	83	7571	11	11	11	1	1
		8414	10	10	10	1	1
		8998	9	9	9	1	1
		10816	8	8	8	1	1

DPSO: discrete particle swarm optimization algorithm; IIA: improved immune algorithm.

As can be observed in Table 1, the IIA produces the best number of stations that is as good as the DPSO. Comparing the generation number of the best solution, the IIA obtains the optimum faster than the DPSO when the name is Sawyer, the number of tasks is 30, and the cycle time is 36. The comparison results show that the IIA is effective and efficient for SALBP-1.

Example 2

The second set of test problems are 25 classes of instances of SALBP-1 selected from Yu and Yin.²¹ The cycle time is 30 units and the network is shown in Figure 4.

Figure 4.

Assembly precedence diagram for 25 tasks.

The results of the task–station assignment are shown in Table 2. Obviously, all the tasks assignment is satisfied with the assembly precedence relation of Figure 4.

Table 2.

Comparison of the assembly balancing result.

IIA			AGA²¹
Workstation number	The set of tasks	Total assembly time/s	Workstation number	The set of tasks	Total assembly time/s
1	1,3,4,2,7	29	1	1,2,3,4,6	30
2	6,8,9,11,12,13	29	2	5,7,8,9,11	29
3	5,10,14,15	28	3	10,12,13,14,15	27
4	16,17,18	27	4	16,17,18	27
5	19,20,21	30	5	19,20,21	30
6	22,23,24,25	29	6	22,23,24,25	29
SI	0.8165		0.9129

where $SI = \sqrt{\frac{1}{m - 1} \sum_{k = 1}^{m} (C - {ST}_{k})^{2}}$ , w₁ = 5,w₂ = 1.

AGA: adaptive genetic algorithm; IIA: improved immune algorithm.

It can be seen that the number of workstations calculated by IIA is the same as that by AGA, but the smooth index calculated by IiA is smaller than that by AGA. The smaller smooth index means that the processing time among workstations is closer, and this will increase the coefficient of utilization of workers and equipment. Obviously, the proposed IIA can produce better balancing effect than AGA.

Conclusions

In this research, the IIA is proposed to solve the SALBP-1 which aims to minimize the number of workstations and workstation load for a given cycle time of assembly line. The similarity formula between any two antibodies is simplified in the process of immune algorithm. The validity of the proposed IIA is tested by means of three computational examples with reference instances, and the results show that the proposed IIA is an efficient approach to solve the SALBP-1.

In the future, I plan to extend the IIA to solve other types ALBPs, such as two-sided assembly lines. Other artificial intelligence algorithm should be developed to solve the SALBP-1, such as chaotic water cycle algorithm,³⁷ chaotic artificial immune system optimization algorithm,³⁸ brainstorm optimization algorithm,³⁹ etc.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

Appendix

References

Sabuncuoglu

Erel

Tanyer

. Assembly line balancing using genetic algorithms. J Intell Manuf 2000; 11: 295–310.

Salveson ME. The assembly line balancing problem. J Ind Eng 1955; 6: 18–25.

Pitakaso

. Differential evolution algorithm for simple assembly line balancing type 1 (SALBP-1). J Ind Prod Eng 2015; 32: 104–114.

Sprecher

. A competitive branch-and-bound algorithm for the simple assembly line balancing problem. Int J Prod Res 1999; 37: 1787–1816.

Easton

Faaland

Klastorn

et al.

Improved network based algorithms for the assembly line balancing problem. Int J Prod Res 1989; 27: 1901–1915.

Peeters

Degraeve

. An linear programming based lower bound for the simple assembly line balancing problem. Eur J Oper Res 2006; 168: 716–731.

Liu

Ong

. Branch-and-bound algorithms for simple assembly line balancing problem. Int J Adv Manuf Technol 2008; 36: 169–177.

Bautista

Pereira

. A dynamic programming based heuristic for the assembly line balancing problem. Eur J Oper Res 2009; 194: 787–794.

Sewell

Jacobson

. A branch, bound, and remember algorithm for the simple assembly line balancing problem. Inf J Comput 2012; 24: 433–442.

10.

Vila

Pereira

. An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time. Eur J Oper Res 2013; 229: 106–113.

11.

Helgeson

Birnie

. Assembly line balancing using the ranked positional weight technique. J Ind Eng 1961; 12: 394–398.

12.

Hoffmann

. Assembly line balancing with a precedence matrix. Manag Sci 1963; 9: 551–562.

13.

Hackman

Magazine

Wee

. Fast, effective algorithms for simple assembly line balancing problems. Oper Res 1989; 37: 916–924.

14.

Fleszar

Hindi

. An enumerative heuristic and reduction methods for the assembly line balancing problem. Eur J Oper Res 2003; 145: 606–620.

15.

Kilincci

Bayhan

. A P-invariant-based algorithm for simple assembly line balancing problem of type-1. Int J Adv Manuf Technol 2008; 37: 400–409.

16.

Yeh

Kao

. A new bidirectional heuristic for the assembly line balancing problem. Comput Ind Eng 2009; 57: 1155–1160.

17.

Otto

. How to design effective priority rules: example of simple assembly line balancing. Comput Ind Eng 2014; 69: 43–52.

18.

Ponnambalam

Aravindan

Naidu

. A multi-objective genetic algorithm for solving assembly line balancing problem. Int J Adv Manuf Technol 2000; 16: 341–352.

19.

Goncalves

de Almeida

. A hybrid genetic algorithm for assembly line balancing. J Heuristics 2002; 8: 629–642.

20.

Gonçalves

de Almeida

. A hybrid genetic algorithm for assembly line balancing. J Heuristics 2002; 8: 629–642.

21.

Yin

. Assembly line balancing based on an adaptive genetic algorithm. Int J Adv Manuf Technol 2010; 48: 347–354.

22.

Yolmeh

Kianfar

. An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-dependent setup times. Comput Ind Eng 2012; 62: 936–945.

23.

Blum

. Beam-ACO for simple assembly line balancing. Inf J Comput 2008; 20: 618–627.

24.

Sulaiman

Choo

Chong

. Ant colony optimization with look forward ant in solving assembly line balancing problem, New York: IEEE, 2011, pp. 115–121.

25.

Dou

. A novel feasible task sequence-oriented discrete particle swarm algorithm for simple assembly line balancing problem of type 1. Int J Adv Manuf Technol 2013; 69: 2445–2457.

26.

Lapierre

Ruiz

Soriano

. Balancing assembly lines with tabu search. Eur J Oper Res 2006; 168: 826–837.

27.

Guden

Meral

. An adaptive simulated annealing method for type-one simple assembly line balancing: a real life case study. J Fac Eng Arch Gazi Univ 2013; 28: 897–908.

28.

Boysen

Fliedner

Scholl

. Assembly line balancing: which model to use when? Int J Prod Econ 2008; 111: 509–528.

29.

Tasan

Tunali

. A review of the current applications of genetic algorithms in assembly line balancing. J Intell Manuf 2008; 19: 49–69.

30.

Matondang MZ. Soft Computing in Optimizing Assembly Lines Balancing. J Comput Sci 2010; 6: 141–162.

31.

Rashid

Hutabarat

Tiwari

. A review on assembly sequence planning and assembly line balancing optimisation using soft computing approaches. Int J Adv Manuf Technol 2012; 59: 335–349.

32.

Battaia

Dolgui

. A taxonomy of line balancing problems and their solution approaches. Int J Prod Econ 2013; 142: 259–277.

33.

Sivasankaran

Shahabudeen

. Literature review of assembly line balancing problems. Int J Adv Manuf Technol 2014; 73: 1665–1694.

34.

Goncalves

de Almeida

. A hybrid genetic algorithm for assembly line balancing. J Heuristics 2002; 8: 629–642.

35.

Zhang

Liu

. Research on a kind of assembly sequence planning based on immune algorithm and particle swarm optimization algorithm. Int J Adv Manuf Technol 2014; 71: 795–808.

36.

Dou JP, Su C and Li J. A discrete particle swarm optimization algorithm for assembly line balancing problem of type 1. In: 2011 third international conference on measuring technology and mechatronics automation, Shangshai, China, 6–7 January 2011, pp.44–47. Los Alamitos, CA, USA: IEEE Computer Society.

37.

Heidari

Abbaspour

Jordehi

. An efficient chaotic water cycle algorithm for optimization tasks. Neural Comput Appl 2017; 28: 57–85.

38.

Jordehi

. A chaotic artificial immune system optimisation algorithm for solving global continuous optimisation problems. Neural Comput Appl 2015; 26: 827–833.

39.

Jordehi

. Brainstorm optimisation algorithm (BSOA): an efficient algorithm for finding optimal location and setting of FACTS devices in electric power systems. Int J Electr Power Energy Syst 2015; 69: 48–57.

An improved immune algorithm for simple assembly line balancing problem of type 1

Abstract

Keywords

Introduction

Mathematical model of SALBP-1

Mathematical formulation

Objective function

Constraint conditions

The IIA

Affinity

Concentration

Antibody survival expectancy

Memory vault

The IIA algorithm flow

Step 1. Setup parameters

Step 2. Initialize

Algorithm 1

Step 3. Immune adjustment

Step 4. Immunization

Step 5. Immune selection

Step 6. Update the memory vault

Step 7. Termination condition

Step 8. Output

Case study

Example 1

Example 2

Conclusions

Footnotes

Declaration of conflicting interests

Funding

Appendix

References