A novel variable neighborhood strategy adaptive search for SALBP-2 problem with a limit on the number of machine’s types

This paper presents the novel method variable neighbourhood strategy adaptive search (VaNSAS) for solving the special case of assembly line balancing problems type 2 (SALBP-2S), which considers a limitation of a multi-skill worker. The objective is to minimize the cycle time while considering the limited number of types of machine in a particular workstation. VaNSAS is composed of two steps, as follows: (1) generating a set of tracks and (2) performing the track touring process (TTP). During TTP the tracks select and use a black box with neighborhood strategy in order to improve the solution obtained from step (1). Three modified neighborhood strategies are designed to be used as the black boxes: (1) modified differential evolution algorithm (MDE), (2) large neighborhood search (LNS) and (3) shortest processing time-swap (SPT-SWAP). The proposed method has been tested with two datasets which are (1) 128 standard test instances of SALBP-2 and (2) 21 random datasets of SALBP-2S. The computational result of the first dataset show that VaNSAS outperforms the best known method (iterative beam search (IBS)) and all other standard methods. VaNSAS can find 98.4% optimal solution out of all test instances while IBS can find 95.3% optimal solution. MDE, LNS and SPT-SWAP can find optimal solutions at 85.9%, 83.6% and 82.8% respectively. In the second group of test instances, we found that VaNSAS can find 100% of the minimum solution among all methods while MDE, LNS and SPT-SWAP can find 76.19%, 61.90% and 52.38% of the minimum solution.