Ant Colony Optimization For Solving The Assembly Line Balancing Problem

Assembly line is a widely used manufacturing system of equipment manufacturing industry today. Assembly line balancing is a process to reach equilibrium among productivity, utilizing rate of facility and market demands. One of the important problems in assembly line design and management is assembly line balancing, which has great effect on the production efficiency of the system.The ALBP is a kind of typical combination-optimization problem, belonging to the NP-hard problem type, it contains sub-problems extremely rich. According to the layout of the assembly line divided into straight and U-type line, According to the operation time divided into deterministic and stochastic assembly line, etc. Due to the complexity of the ALBP, formulating a mathematical model and solving it by traditional is not realistic for finding an optimal solution in case of real-world instances. In recent years, intelligent algorithm gain a lot of progress, Ant colony optimization is an efficient intelligent algorithm for combinatorial optimization problem, providing a new way to solve the ALBP.In this paper, though analyzing the basic idea of ACO algorithm, An adaptive ant colony optimization was proposed to solve the ALBP. According to the specific characteristics of the ALBP, we developed an method of solution constructing strategy, and proposed a better differentiation of objective function to appraisal solution quality,an improve ACO is presented by adaptive adjusted of the parameter in the algorithm, which has a good ability of searching better solution with higher convergence speed. The proposed algorithm was tested, and the experimental result indicated the effectiveness of the proposed algorithm.Then, in this paper studies another more complex ALBP stochastic U-type assembly line,the task times are stochastic in real work applications, especially in manual assembly lines, mathematical model of stochastic U-type assembly line balancing problem is built, and an effective combination of SA and ACO algorithm is proposed to solve the stochastic U-type assembly line. This hybrid algorithm incorporates metropolis acceptance criterion of SA into ACO to reduce the possibility of being trapped in local optimum. In order to evaluating the proposed hybrid algorithm, the performance of the proposed method is examined by benchmark problems taken from the literature,Computational results validate the efficiency and robustness of the proposed algorithm. Finally, we developed a system ACO-ALBP based on the idea. And we applied the system to solve the benchmark instances, the test results validate the efficiency of the system.A conclusion is given and the further research directions of ACO algorithm and ALBP are anticipated.