An efficient solution to the simple assembly line balancing problem type 1 using iterated local search

The Assembly Line Balancing (ALB) problem involves dividing total assembly operations into tasks and assigning them to workstations so that each workstation has approximately equal times and precedence constraints are met. The most fundamental and well-studied model in ALB is called Simple ALB Problem Type 1 (SALBP-1), which aims to minimize the number of loaded stations given a fixed cycle time. SALBP-1 is proven to be NP-hard and thus its efficient solution is challenging. In this paper, we developed an Iterated Local Search (ILS) algorithm customized for obtaining high-quality and feasible solutions to SALBP-1 by minimizing the number of assembly stations. We tested our method on 270 benchmark problems from Talbot's, Scholl's, and Otto's datasets, as well as on a real antenna assembly case, and compared the results with nine algorithms from the literature. Analyses showed that the ILS outperformed other algorithms by reaching or improving the best-known upper-bound solutions in 269 of the 270 instances within lower computational runtimes. Key components that contribute to the success of the ILS include the way the initial solution is selected, innovative shallow and deep task assignment implementation, and the diversity of neighborhood generating operators (including the novel Float Shift operator), which help the algorithm to converge toward feasible solutions and achieve minimal values for the objective function. The proposed method enables designers and engineers to design more efficient assembly lines and reduce production lead times and overall costs.