An improved artificial bee colony algorithm with MaxTF heuristic rule for two-sided assembly line balancing problem

doi:10.1007/s11465-018-0518-6

Front. Mech. Eng.

2019, Vol. 14

Issue (2) : 241-253 https://doi.org/10.1007/s11465-018-0518-6

RESEARCH ARTICLE

An improved artificial bee colony algorithm with MaxTF heuristic rule for two-sided assembly line balancing problem

Xiaokun DUAN¹, Bo WU¹, Youmin HU¹(

), Jie LIU¹, Jing XIONG²

¹. School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
². School of Mechanical Engineering, Hubei Engineering University, Xiaogan 432000, China

Download: PDF(1177 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Two-sided assembly line is usually used for the assembly of large products such as cars, buses, and trucks. With the development of technical progress, the assembly line needs to be reconfigured and the cycle time of the line should be optimized to satisfy the new assembly process. Two-sided assembly line balancing with the objective of minimizing the cycle time is called TALBP-2. This paper proposes an improved artificial bee colony (IABC) algorithm with the MaxTF heuristic rule. In the heuristic initialization process, the MaxTF rule defines a new task’s priority weight. On the basis of priority weight, the assignment of tasks is reasonable and the quality of an initial solution is high. In the IABC algorithm, two neighborhood strategies are embedded to balance the exploitation and exploration abilities of the algorithm. The employed bees and onlooker bees produce neighboring solutions in different promising regions to accelerate the convergence rate. Furthermore, a well-designed random strategy of scout bees is developed to escape local optima. The experimental results demonstrate that the proposed MaxTF rule performs better than other heuristic rules, as it can find the best solution for all the 10 test cases. A comparison of the IABC algorithm and other algorithms proves the effectiveness of the proposed IABC algorithm. The results also denote that the IABC algorithm is efficient and stable in minimizing the cycle time for the TALBP-2, and it can find 20 new best solutions among 25 large-sized problem cases.

Keywords two-sided assembly line balancing problem artificial bee colony algorithm heuristic rules time boundary

Corresponding Author(s): Youmin HU

Just Accepted Date: 28 May 2018 Online First Date: 12 July 2018 Issue Date: 22 April 2019

Cite this article:

Xiaokun DUAN,Bo WU,Youmin HU, et al. An improved artificial bee colony algorithm with MaxTF heuristic rule for two-sided assembly line balancing problem[J]. Front. Mech. Eng., 2019, 14(2): 241-253.

URL:

https://academic.hep.com.cn/fme/EN/10.1007/s11465-018-0518-6
https://academic.hep.com.cn/fme/EN/Y2019/V14/I2/241

Fig.1 Two-sided assembly line

Natation	Representation
I	Set of tasks, I ={1, 2, …, I, …, n}
J	Set of mated-stations, J={1, 2, …, j, …, m}
k	Indicator for the side of stations, k=1, if the station is left side; k=2, otherwise
(j, k)	A station of mated-station j and its operation direction is k
S_L	Set of tasks assigned to a left station; $S L ⊂ I$
S_R	Set of tasks assigned to a right station; $S R ⊂ I$
S_E	Set of tasks assigned to either station; $S E ⊂ I$
P₀	Set of tasks that have no predecessors
P(i)	Set of immediate predecessors of Task i
P_a(i)	Set of all predecessors of Task i
S(i)	Set of immediate successors of Task i
S_a(i)	Set of all successors of Task i
D(i)	Set of tasks whose operations are opposite to Task i’s operation direction $D (i) = {S L if i ∈ S R S R if i ∈ S L ∅ if i ∈ S E$
K(i)	Set of all predecessors of Task i $K (i) = {{1} if i ∈ S R {1} if i ∈ S L {1, 2} if i ∈ S E$
t_i	Processing time of Task i
ft_i	Finish time of Task i
CT	Cycle time
x_ijk	x_ijk=1, if Task i is assigned to station (j, k); x_ijk=0, otherwise
z_ir	z_ir=1, if Task i is assigned earlier than Task r in the same station; z_ir=0, otherwise
ϕ	A very large positive number

Tab.1 Notations in TALBP

Fig.2 Flowchart of the IABC algorithm

Fig.3 Example of TALBP: P16

Fig.4 Encoding of a solution of P16

Fig.5 Gantt chart for a solution of P16

Fig.6 Example for the two-point crossover

Tab.2 Comparison of the parameter values for the MaxTF rule

Tab.3 Comparison of the performance for the MaxTF rule

Tab.4 Comparison of the performance for small-sized problems

Problem	Nms	LB	FFR			DABC			n-GA			IABC			Time/s
Problem	Nms	LB	Best	Mean	Std	Best	Mean	Std	Best	Mean	Std	Best	Mean	Std	Time/s
P65	4	637.4	661	665.7	1.60	645	637.4	2.69	641	643.7	0.39	640	641.4	0.34	63.375
	5	509.9	528	531.9	1.29	527	509.9	1.98	515	518.4	0.40	514	515.9	0.47	63.375
	6	424.9	436	440.3	1.30	435	444.7	2.01	432	434.8	0.52	430	432.4	0.59	63.375
	7	364.2	375	378.2	0.94	375	377.6	0.80	372	377.7	0.83	370	372.1	0.56	63.375
	8	318.7	335	338.4	1.18	334	335.9	0.44	327	334.2	0.90	324	326.7	0.72	63.375
P148	4	640.5	713	716.6	1.36	656	665.0	3.65	641	642.0	0.17	641	642.2	0.30	328.56
	5	512.4	567	568.5	0.58	523	532.5	4.42	514	514.9	0.18	514	515.1	0.33	328.56
	6	427.0	462	464.5	0.83	443	451.9	3.48	428	430.6	0.27	428	429.6	0.38	328.56
	7	366.0	395	396.6	0.43	384	387.0	1.47	368	369.2	0.21	367	367.8	0.26	328.56
	8	320.3	343	345.8	1.00	335	338.5	2.09	323	323.7	0.15	322	322.6	0.27	328.56
	9	284.7	305	306.9	0.64	299	302.2	1.80	287	289.6	0.53	286	286.7	0.35	328.56
	10	256.2	276	277.4	0.40	272	274.6	1.16	259	262.4	0.51	258	260.1	0.57	328.56
	11	232.9	248	248.8	0.29	245	249.4	1.80	237	238.5	0.42	235	236.2	0.37	328.56
	12	213.5	224	228.6	0.38	222	229.3	1.81	218	221.3	0.60	216	217.4	0.48	328.56
P205	4	2918.1	3513	3517.5	1.46	3016	3039.3	6.80	2946	2965.6	3.65	2953	2967.5	3.87	630.375
	5	2334.5	2799	2815.0	5.37	2474	2494.9	4.79	2364	2374.0	3.55	2358	2364.1	2.94	630.375
	6	1945.4	2353	2366.0	4.47	2060	2081.7	7.93	1984	2004.3	5.36	1980	1983.5	1.27	630.375
	7	1667.5	1982	1999.5	5.70	1795	1814.3	8.37	1709	1723.7	2.99	1707	1718.4	3.04	630.375
	8	1459.1	1750	1760.0	3.35	1560	1579.5	4.88	1507	1546.5	9.23	1496	1511.6	4.98	630.375
	9	1296.9	1545	1553.1	2.62	1368	1380.6	4.17	1337	1362.7	8.84	1334	1346.2	4.63	630.375
	10	1167.3	1385	1395.4	3.55	1247	1256.2	4.05	1189	1221.0	5.57	1186	1210.3	5.83	630.375
	11	1061.1	1254	1262.8	3.00	1131	1140.5	2.18	1095	1122.5	7.95	1092	1114.3	6.82	630.375
	12	972.7	1173	1176.0	1.02	1051	1066.3	6.12	1039	1061.1	3.45	1012	1027.2	4.49	630.375
	13	897.9	1064	1071.7	2.71	984	993.8	5.01	944	975.8	4.73	944	955.4	3.34	630.375
	14	833.8	998	1003.7	1.72	948	962.8	5.34	944	953.3	1.33	944	944.0	0.00	630.375

Tab.5 Comparison of the performance for large-sized problems

Fig.7 Gantt chart for the best solution of P65 with four mated-stations

Fig.8 Gantt chart for the best solution of P205 with 12 mated-stations

Fig.9 Means of the average RPD of the best solutions and 95% least significant difference intervals for different algorithms

Fig.10 Means of the average RPD of the average solutions and 95% least significant difference intervals for different algorithms

Fig.11 Convergence curve for P205 with 12 mated-stations

1	AScholl, C Becker. State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research, 2006, 168(3): 666–693 https://doi.org/10.1016/j.ejor.2004.07.022
2	CBecker, A Scholl. A survey on problems and methods in generalized assembly line balancing. European Journal of Operational Research, 2006, 168(3): 694–715 https://doi.org/10.1016/j.ejor.2004.07.023
3	S BLiu, K M Ng, H L Ong. Branch-and-bound algorithms for simple assembly line balancing problem. International Journal of Advanced Manufacturing Technology, 2008, 36(1–2): 169–177 https://doi.org/10.1007/s00170-006-0821-y
4	MAmen. An exact method for cost-oriented assembly line balancing. International Journal of Production Economics, 2000, 64(1–3): 187–195 https://doi.org/10.1016/S0925-5273(99)00057-2
5	E CSewell, S H A Jacobson. Branch, bound, and remember algorithm for the simple assembly line balancing problem. INFORMS Journal on Computing, 2012, 24(3): 433–442 https://doi.org/10.1287/ijoc.1110.0462
6	A RMendes, A L Ramos, A S Simaria, et al. Combining heuristic procedures and simulation models for balancing a PC camera assembly line. Computers & Industrial Engineering, 2005, 49(3): 413–431 https://doi.org/10.1016/j.cie.2005.07.003
7	OKilincci. A Petri net-based heuristic for simple assembly line balancing problem of type 2. International Journal of Advanced Manufacturing Technology, 2010, 46(1–4): 329–338 https://doi.org/10.1007/s00170-009-2082-z
8	Q XZheng, M Li, Y XLi, et al. Station ant colony optimization for the type 2 assembly line balancing problem. International Journal of Advanced Manufacturing Technology, 2013, 66(9–12): 1859–1870 https://doi.org/10.1007/s00170-012-4465-9
9	ZLi, I Kucukkoc, J MNilakantan. Comprehensive review and evaluation of heuristics and meta-heuristics for two-sided assembly line balancing problem. Computers & Operations Research, 2017, 84: 146–161 https://doi.org/10.1016/j.cor.2017.03.002
10	J JBartholdi. Balancing two-sided assembly lines: A case study. International Journal of Production Research, 1993, 31(10): 2447–2461 https://doi.org/10.1080/00207549308956868
11	Y KKim, Y H Kim, Y J Kim. Two-sided assembly line balancing: A genetic algorithm approach. Production Planning and Control, 2000, 11(1): 44–53 https://doi.org/10.1080/095372800232478
12	E FWu, Y Jin, J SBao, et al. A branch-and-bound algorithm for two-sided assembly line balancing. International Journal of Advanced Manufacturing Technology, 2008, 39(9–10): 1009–1015 https://doi.org/10.1007/s00170-007-1286-3
13	ABaykasoglu, T Dereli. Two-sided assembly line balancing using an ant-colony-based heuristic. International Journal of Advanced Manufacturing Technology, 2008, 36(5–6): 582–588 https://doi.org/10.1007/s00170-006-0861-3
14	UÖzcan, B Toklu. Balancing of mixed-model two-sided assembly lines. Computers & Industrial Engineering, 2009, 57(1): 217–227 https://doi.org/10.1016/j.cie.2008.11.012
15	Y KKim, W S Song, J H Kim. A mathematical model and a genetic algorithm for two-sided assembly line balancing. Computers & Operations Research, 2009, 36(3): 853–865 https://doi.org/10.1016/j.cor.2007.11.003
16	UÖzcan. Balancing stochastic two-sided assembly lines: A chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm. European Journal of Operational Research, 2010, 205(1): 81–97 https://doi.org/10.1016/j.ejor.2009.11.033
17	PTapkan, L Ozbakir, ABaykasoglu. Modeling and solving constrained two-sided assembly line balancing problem via bee algorithms. Applied Soft Computing, 2012, 12(11): 3343–3355 https://doi.org/10.1016/j.asoc.2012.06.003
18	DKhorasanian, S R Hejazi, G Moslehi. Two-sided assembly line balancing considering the relationships between tasks. Computers & Industrial Engineering, 2013, 66(4): 1096–1105 https://doi.org/10.1016/j.cie.2013.08.006
19	BYuan, C Zhang, XShao. A late acceptance hill-climbing algorithm for balancing two-sided assembly lines with multiple constraints. Journal of Intelligent Manufacturing, 2015, 26(1): 159–168 https://doi.org/10.1007/s10845-013-0770-x
20	QTang, Z Li, LZhang. An effective discrete artificial bee colony algorithm with idle time reduction techniques for two-sided assembly line balancing problem of type-II. Computers & Industrial Engineering, 2016, 97: 146–156 https://doi.org/10.1016/j.cie.2016.05.004
21	ZLi, Q Tang, L.Zhang Minimizing the cycle time in two-sided assembly lines with assignment restrictions: Improvements and a simple algorithm. Mathematical Problems in Engineering, 2016, 2016: 4536426 https://doi.org/10.1155/2016/4536426
22	QTang, Z Li, LZhang, et al. Balancing stochastic two-sided assembly line with multiple constraints using hybrid teaching-learning-based optimization algorithm. Computers & Operations Research, 2017, 82: 102–113 https://doi.org/10.1016/j.cor.2017.01.015
23	ZLi, Q Tang, LZhang. Two-sided assembly line balancing problem of type I: Improvements, a simple algorithm and a comprehensive study. Computers & Operations Research, 2017, 79: 78–93 https://doi.org/10.1016/j.cor.2016.10.006
24	MGansterer, R F Hartl. One- and two-sided assembly line balancing problems with real-world constraints. International Journal of Production Research, 2017, (3): 1–18 https://doi.org/10.1080/00207543.2017.1394599
25	DKaraboga. An Idea Based on Honey Bee Swarm for Numerical Optimization. Technical Report TR06. 2005
26	F GMohammadi, M SAbadeh. Image steganalysis using a bee colony based feature selection algorithm. Engineering Applications of Artificial Intelligence, 2014, 31: 35–43 https://doi.org/10.1016/j.engappai.2013.09.016
27	YLiu, S Liu. A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Applied Soft Computing, 2013, 13(3): 1459–1463 https://doi.org/10.1016/j.asoc.2011.10.024
28	DKaraboga, B Basturk. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm. Journal of Global Optimization, 2007, 39(3): 459–471 https://doi.org/10.1007/s10898-007-9149-x
29	UÖzcan, B Toklu. A tabu search algorithm for two-sided assembly line balancing. International Journal of Advanced Manufacturing Technology, 2009, 43(7–8): 822–829 https://doi.org/10.1007/s00170-008-1753-5
30	C LMoodie, H H Young. A heuristic method of assembly line balancing for assumptions of constant or variable work element times. Journal of Industrial Engineering, 1965, 16: 23–29
31	F MTonge. Summary of a heuristic line balancing procedure.Management Science, INFORMs, 1960, 7(1): 21–42
32	W BHelgeson, D P Birnie. Assembly line balancing using the ranked positional weight technique. Journal of Industrial Engineering, 1961, 12: 394–398

Viewed

Full text

Abstract

Cited

Shared

Discussed