Please wait a minute...

Frontiers of Mechanical Engineering

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 DUAN1, Bo WU1, Youmin HU1(), Jie LIU1, Jing XIONG2
1. School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
2. 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 Authors: 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:  
http://journal.hep.com.cn/fme/EN/10.1007/s11465-018-0518-6
http://journal.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
SL Set of tasks assigned to a left station; SL I
SR Set of tasks assigned to a right station; SR I
SE Set of tasks assigned to either station; SE I
P0 Set of tasks that have no predecessors
P(i) Set of immediate predecessors of Task i
Pa(i) Set of all predecessors of Task i
S(i) Set of immediate successors of Task i
Sa(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)={ SLif iSR SRif iSLif i SE
K(i) Set of all predecessors of Task i
K( i)={ {1}if iS R{1} if i SL{1, 2} if iSE
ti Processing time of Task i
fti Finish time of Task i
CT Cycle time
xijk xijk=1, if Task i is assigned to station (j, k); xijk=0, otherwise
zir zir=1, if Task i is assigned earlier than Task r in the same station; zir=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
Problem m Tmc α:β = 2:8 α:β = 3:7 α:β= 4:6 α:β = 5:5 α:β = 6:4 α:β = 7:3 α:β = 8:2
Best Mean Std Best Mean Std Best Mean Std Best Mean Std Best Mean Std Best Mean Std Best Mean Std
P16 2 20.50 26 27.2 0.63 22 25.4 2.46 24 26.0 1.89 22 25.9 1.91 22 29.2 3.43 27 28.7 1.77 26 28.6 2.46
3 13.67 16 16.9 0.74 16 17.0 0.67 16 17.2 0.79 16 16.7 0.67 16 16.8 0.42 21 27.6 4.03 21 26.2 3.36
P24 2 35.00 36 38.1 2.84 37 43.0 3.92 39 43.9 2.81 45 48.3 5.76 44 48.3 5.14 44 50.1 3.57 49 52.8 2.86
3 23.33 25 26.9 2.23 25 30.7 3.34 30 32.2 4.94 32 41.9 5.90 30 34.2 3.26 30 37.2 2.57 30 37.4 2.67
4 17.50 18 19.7 2.06 20 24.5 2.92 19 24.4 2.76 26 29.4 4.99 25 27.2 2.78 25 28.8 2.62 26 33.0 6.55
P65 4 637.4 655 659.3 2.62 649 659.4 12.51 657 674.7 14.74 662 685.8 16.88 740 852.7 96.74 736 826.4 93.97 706 723.8 19.51
5 509.9 532 536.1 3.98 540 559.1 18.28 536 599.1 57.37 558 584.6 36.97 695 769.4 79.80 573 691.2 73.21 549 597.3 62.73
6 424.9 450 452.7 5.01 457 490.8 62.95 445 490.8 67.35 452 480.5 38.18 670 720.3 53.54 469 586.9 92.63 456 499.7 76.60
7 364.2 382 404.2 14.58 410 439.1 14.81 385 393.1 7.45 456 507.2 46.97 454 572.2 81.10 392 490.1 79.28 399 420.8 37.60
8 318.7 336 364.5 18.34 346 417.1 51.58 343 414.8 72.79 340 417.4 99.69 360 488.5 91.58 357 450.1 50.72 353 407.6 62.59
Tab.2  Comparison of the parameter values for the MaxTF rule
Problem m Tmc MaxT MaxF MaxRPW MaxTF Improved
rate 1/%
Improved
rate 2/%
Improved
rate 3/%
Best Mean Std Best Mean Std Best Mean Std Best Mean Std
P16 2 20.50 33 33.7 0.95 29 29.0 0.00 29 29.0 0.00 26 27.2 0.63 19.29 6.21 6.21
3 13.67 33 33.8 1.23 29 29.0 0.00 29 29.0 0.00 16 16.9 0.74 50.00 41.72 41.72
P24 2 35.00 44 53.4 4.95 36 38.7 2.31 40 41.8 2.90 36 38.1 2.84 28.65 1.55 8.85
3 23.33 34 35.9 1.20 25 27.9 3.31 26 28.3 3.53 25 26.9 2.23 25.07 3.58 4.95
4 17.50 19 23.8 3.49 19 23.9 1.91 22 25.4 2.80 18 19.7 2.06 17.23 17.57 22.44
P65 4 637.4 954 992.5 67.15 725 754.3 26.62 746 783.7 25.39 655 659.3 2.62 33.57 12.59 15.87
5 509.9 737 897.6 80.28 653 699.5 27.45 701 716.1 26.33 532 536.1 3.98 40.27 23.36 25.14
6 424.9 655 725.7 75.30 562 613.7 28.37 561 590.4 22.85 450 452.7 5.01 37.62 26.23 23.32
7 364.2 571 668.8 49.10 513 549.3 30.41 483 538.8 25.15 382 404.2 14.58 39.56 26.42 24.98
8 318.7 502 595.4 97.28 463 481.5 17.58 459 474.3 16.32 336 364.5 18.34 38.78 24.30 23.15
Tab.3  Comparison of the performance for the MaxTF rule
Problem Nms LB MIP DABC IABC
Best Mean Time/s Best Mean Time/s Best Mean Time/s
P16 2 20.50 22 22 0.16 22 22 3.84 22 22 3.84
3 13.67 16 16 0.97 16 16 3.84 16 16 3.84
P24 2 35.00 35 35 * 35 35 8.64 35 35 8.64
3 23.33 24 24 * 24 24 8.64 24 24 8.64
4 17.50 18 18 * 18 18 8.64 18 18 8.64
Tab.4  Comparison of the performance for small-sized problems
Problem Nms LB FFR DABC n-GA IABC Time/s
Best Mean Std Best Mean Std Best Mean Std Best Mean Std
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   0
  Discussed