A mathematical model and ant colony algorithm for multi-manned assembly line balancing problem

In real-world assembly lines, that the size of the product is large (e.g., automotive industry), usually there are multi-manned workstations where a group of workers simultaneously perform different operations on the same individual product. This paper presents a mixed integer programming model to solve the balancing problem of the multi-manned assembly lines optimally. This model minimizes the total number of workers on the line as the first objective and the number of opened multi-manned workstations as the second one. Since this problem is well known as NP (nondeterministic polynomial-time)-hard, a heuristic approach based on the ant colony optimization approach is developed to solve the medium- and large-size scales of this problem. In the proposed algorithm, each ant tries to allocate given tasks to multi-manned workstations in order to build a balancing solution for the assembly line balancing problems by considering the precedence relations, multi-manned assembly line configuration, task times, and cycle time constraints. Through computational experiments, the performance of the proposed ACO is compared with some existing heuristic on various problem instances. The experimental results validate the effectiveness and efficiency of the proposed algorithm.