Comprehensive review and evaluation of heuristics and meta-heuristics for two-sided assembly line balancing problem

Heuristics and meta-heuristics proposed for TALBP-II are comprehensively reviewed.A set of encoding schemes and decoding procedures is summarized.New objective functions and an iterative search mechanism are developed.Eighteen meta-heuristics are evaluated on a set of benchmark problems.New best and optimum solutions of TALBP-II test problems are also achieved. This paper presents a comprehensive review and evaluation of heuristics and meta-heuristics for the two-sided assembly line balancing problem. Though a few reviews have been presented, some latest methods are not included and there is no comparison of the meta-heuristics in terms of their performances. Furthermore, since various kinds of encoding schemes, decoding procedures and objective functions have been applied, the results cannot be generalized and the published comparison might be unfair. This paper contributes to knowledge by comparing the published methods, ranging from well-known simulated annealing to recent published iterated local search, and evaluating the six encoding schemes, 30 decoding procedures and five objective functions on the performances of the meta-heuristics meanwhile. The experimental design approach is applied to obtain valid and convincing results by testing algorithms under four termination criteria. Computational results demonstrate that the proper selection of encoding scheme, decoding procedure and objective function improves the performance of the algorithms by a significant margin. Another unique contribution of this paper is that 15 new best solutions are obtained for the large-sized type-II two-sided assembly line balancing problem during the re-implementation and evaluation of the meta-heuristics tested.