TY - JOUR
T1 - Local search methods for type I mixed-model two-sided assembly line balancing problems
AU - Li, Zixiang
AU - Janardhanan, Mukund Nilakantan
AU - Tang, Qiuhua
AU - Nielsen, Peter
N1 - Funding Information:
This project is partially supported by National Natural Science Foundation of China under Grants 51875421 and 61803287 and the China Postdoctoral Science Foundation under Grant 2018M642928. The authors are grateful for the insightful comments by the anonymous referees which helped to improve this paper.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer-Verlag GmbH, DE part of Springer Nature.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2021
Y1 - 2021
N2 - Two-sided assembly lines are widely utilized to assemble large-sized products such as cars and trucks. Recently, these types of assembly lines have been applied to assemble different types of products due to a large variety of customer demands and strong market competition. This paper presents two simple local search methods, the iterated greedy algorithm and iterated local search algorithm, to deal with type I mixed-model two-sided assembly line balancing problems. These two algorithms utilize new precedence-based local search functions with referenced permutation and two neighborhood structures to emphasize intensification while preserving high search speed. Additionally, these local search methods are enhanced by utilizing the best decoding scheme amongst nine candidates and a new station-oriented evaluation to guide the search direction. New lower bound calculations are also presented to check the optimality of the achieved solutions. Eleven recent and high-performing metaheuristic algorithms are re-implemented to test the performance of the proposed algorithms. A comprehensive study on a set of benchmark problems demonstrates the advantages of the improvements and the superiority of the two proposed methods. Experimental results show that the proposed algorithms obtain 23 new upper bounds compared with two recently published algorithms, among which 19 cases are proven to be optimal for the first time.
AB - Two-sided assembly lines are widely utilized to assemble large-sized products such as cars and trucks. Recently, these types of assembly lines have been applied to assemble different types of products due to a large variety of customer demands and strong market competition. This paper presents two simple local search methods, the iterated greedy algorithm and iterated local search algorithm, to deal with type I mixed-model two-sided assembly line balancing problems. These two algorithms utilize new precedence-based local search functions with referenced permutation and two neighborhood structures to emphasize intensification while preserving high search speed. Additionally, these local search methods are enhanced by utilizing the best decoding scheme amongst nine candidates and a new station-oriented evaluation to guide the search direction. New lower bound calculations are also presented to check the optimality of the achieved solutions. Eleven recent and high-performing metaheuristic algorithms are re-implemented to test the performance of the proposed algorithms. A comprehensive study on a set of benchmark problems demonstrates the advantages of the improvements and the superiority of the two proposed methods. Experimental results show that the proposed algorithms obtain 23 new upper bounds compared with two recently published algorithms, among which 19 cases are proven to be optimal for the first time.
KW - Assembly line balancing
KW - Local search
KW - Metaheuristics
KW - Mixed-model production
KW - Two-sided assembly line
UR - http://www.scopus.com/inward/record.url?scp=85098741056&partnerID=8YFLogxK
U2 - 10.1007/s12293-020-00319-0
DO - 10.1007/s12293-020-00319-0
M3 - Journal article
AN - SCOPUS:85098741056
SN - 1865-9284
VL - 13
SP - 111
EP - 130
JO - Memetic Computing
JF - Memetic Computing
IS - 1
ER -