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

Document Type : Research Paper


Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran



Being one of the main subproblems of the broader Assembly Planning(AP) problem, The Assembly Line Balancing (ALB) problem 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 Simple Assembly Line Balancing Problem type 2 (SALBP2) which is proven to be NP-hard and thus its effective and efficient solution has been a challenge for the researchers in the field. However, despite the existence of numerous works on solving the SALBP2, the topology, structure, and complexity of the problem's search space (i.e., the fitness landscape) has not been studied yet. In this article, the fitness landscape of the SALBP2 problem is analyzed for 44 test problems through various distribution and correlation statistical measures, which reveals that locally optimal assembly sequences are distributed in the problem's landscape nearly uniformly. Based on this result, a suitable optimization algorithm called Hybrid Iterated Local Search (HILS) is selected and customized for obtaining effective and efficient solution to SALBP2. A number of SALBP2 problems are solved by the presented HILS and other algorithms in the SALBP2 literature. Experimental results show that the HILS outperforms other algorithms by producing the best-known or optimal solutions most of the time.