Hybridizing ant colony optimization by beam search for the assembly line balancing problem

Abstract

The type-I Assembly Line Balancing Problem (ALBP) focuses on the task assignment process with the objective of minimizing the number of workstations for a given cycle time. With the development of complex products, the problem size and the complexity in the assembly process is increasing. In this study, we hybridize the ant colony optimization algorithm via beam search (ACO-BS) in order to solve the type-I ALBP, and we focus more on the large scale ALBP in order to suit to the industrial requirements. We test ACO-BS with benchmark instances with a time limit of 360 seconds for one run, and the results show that 95.54% of the problems can reach their optimal solutions. In addition, since we want to explore the large scale ALBP, we generate 27 instances with a total of 400 tasks (the largest number of tasks in the benchmark instances of type-I ALBP is 297) randomly basing on the complexity indicators of order strength and processing time variation. There are three levels of order strength, 0.2, 0.6 and 0.9, and the time variation is set to be at 5-15, 65-75 and 135-145 levels. Meanwhile, the processing times of the tasks usually follow a unimodal or bimodal distribution, and we generate task times to follow three kinds of distribution respectively, unimodal distribution peaking at the bottom, unimodal distribution peaking in the middle and bimodal distribution. The comparison results with solutions obtained by the priority rule demonstrate the superiority of ACO-BS in solving large scale ALBP.