A hybrid adaptive variable neighbourhood search approach for multi-sided assembly line balancing problem to minimise the cycle time

Multi-sided assembly line balancing problems usually occur in plants producing big-sized products such as buses, trucks, and helicopters. In this type of assembly line, in each workstation, it is possible to install several workplaces, in which a single operator performs his/her own set of tasks at an individual mounting position. In this way, the operators can work simultaneously on the same product without hindering each other. This paper considers for the rst time the multi-sided assembly line balancing problem with the objective of minimizing the cycle time, proposing a new mathematical formulation to solve small-sized instances of this problem. Besides, a metaheuristic algorithm based on variable neighborhood search hybridized with simulated annealing is developed to solve large-sized instances. The algorithm is called adaptive because of the adopted neighborhood selection mechanism. A novel three-string representation is introduced to encode the problem solutions and six dierent neighborhood generation structures are presented. The developed approach is compared to other meta-heuristics, considering some well-known in literature test instance and a real world assembly line balancing problem arising in a car body assembly line. The experimental results validate the eectiveness of the proposed algorithm.