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

Abstract

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.