A scatter search based heuristic for the balancing of parallel assembly lines

This paper proposes a scatter search based heuristic approach to the parallel assembly lines balancing problem where a given set of tasks must be assigned to stations while the total task time for each station could not exceed the cycle time and the precedence constraint should be abided. Since the problem is NP-hard, a scatter search based heuristic is designed to solve the problem. To the best of our knowledge, there has been no study in the literature that use scatter search solving this type of ALBP. New heuristics, improvement method and solution combination method are developed in the algorithm implementation process. Computational results of the benchmark problems indicate that the proposed method is stable and can find 15 better solutions among the total 95 test problems than the known best feasible solutions. It can also be seen that our heuristic has smaller average gap from the lower bound than the best known results in the literature.