Landscape Analysis and a Hybrid Iterated Local Search (HILS) for Solving Simple Assembly Line Balancing Problem type 2 (SALBP2)

The Assembly Line Balancing (ALB) problem is one of the subproblems of the Assembly Planning(AP) problem and is defined as the process of partitioning the assembly operations into a set of tasks and assigning them to assembly workstations such that all workstations approximately have equal times. The most basic model in ALB is the Simple Assembly Line Balancing Problem for type 2 (SALBP2). The mentioned problem is an NP-hard problem and thus many researchers in the field tried to find an effective and efficient solution for it. However, the fitness landscape of this problem has not been yet studied despite the existence of numerous works on solving it. In this article, different statistical correlation and distribution measures are used and calculated in order to analyze the fitness landscape of the SALBP2 problem for 44 test problems. The results reveal that the problem's landscape is approximately uniform based on the distribution of the locally optimal assembly sequences. Therefore, for obtaining an effective and efficient solution to SALBP2 a suitable Hybrid Iterated Local Search (HILS) is designated and used to solve a number of SALBP2 problems. Comparison results with the other approaches in the SALBP2 literature represent that the HILS produces the optimal or best known solutions on most problem instances, and it performs better than other algorithms.