Two-sided assembly line balancing problem of type I: Improvements, a simple algorithm and a comprehensive study. (March 2017)

• Record Type: Journal Article
• Authors: Li, Zixiang; Tang, Qiuhua; Zhang, LiPing
• Is Part Of: Computers & operations research. Volume 79(2017)
• Page Start: 78
• Page End: 93
• Publication Date: 2017-03
• Subjects: Assembly line balancing -- Two-sided assembly line -- Iterated greedy -- Local search -- Metaheuristics; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.10.006
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Many meta-heuristic methods have been applied to solve the two-sided assembly line balancing problem of type I with the objective of minimizing the number of stations, but some of them are very complex or intricate to be extended. In addition, different decoding schemes and different objectives have been proposed, leading to the different performances of these algorithms and unfair comparison. In this paper, two new decoding schemes with reduced search space are developed to balance the workload within a mated-station and reduce sequence-depended idle time. Then, graded objectives are employed to preserve the minor improvements on the solutions. Finally, a simple iterated greedy algorithm is extended for the two-sided assembly line balancing problem and modified NEH-based heuristic is introduced to obtain a high quality initial solution. And an improved local search with referenced permutation and reduced insert operators is developed to accelerate the search process. Computational results on benchmark problems prove the efficiency of the proposed decoding schemes and the new graded objectives. A comprehensive computational comparison among 14 meta-heuristics is carried out to demonstrate the efficiency of the improved iterated greedy algorithm. Highlights: Two new decoding schemes are developed and compared with existed ones. Graded objectives are developed to preserve the tiny improvements A simple and effective iterated greedy algorithm is applied and evaluated. New local search is developed to reduce repeated insert operators. All optimal solutions are obtained for the first time.