Research On Ant Colony Algorithm For Assembly Line Balancing Problems

The decision problem of optimally partitioning the assembly works among the stations to achieve some objective is known as the assembly line balancing problem (ALBP). Balancing assembly line can shorten the production cycle, and improve production efficiency, which is of important practical significance. On the other hand, it is a typical NP-hard problem, and the research of effective algorithm for it has important theoretical significance.The methods for solving ALBP are mainly classified into three groups:heuristic approach, exact method and meta-heuristic algorithm. The first method can efficiently solve problem, but its effectiveness is difficult to guarantee; the second one is suitable for solving the exact solution of small-scale examples, but it is inefficient for solving the large-scale problems. Meta-heuristic algorithm is relatively balanced in effectiveness and efficiency. So it becomes the mainstream algorithm for solving ALBP. Among many meta-heuristic algorithms, ant colony optimization algorithm becomes an important development for solving ALBP, because of the high similarity between the traversal solution process and the assembly design process.An improved ant colony optimization is proposed to address the type2of the simple assembly line balancing problem (SALBP-2).(1) A novel heuristic factor:the number of release tasks, is introduced to select tasks. Among the candidate tasks, if a task is assigned to station, many tasks will be released to be the candidate task, this task should be chosen with priority to increase the diversity of ant colony.(2) A task selection strategy and an assignment mechanism are proposed to assign tasks, which is rational and effective for balancing the global optimization and the local optimization. The selection strategy is applied to calculate the selection weights of candidate tasks, which in view of the global optimization, yet the assignment mechanism is emphasized to optimize the current station, which belongs to the local optimization.(3) Two pheromones are defined to describe the combination relationship between stations and tasks and that among tasks in the same station, considering the contribution of global information and local information, respectively. The latter can adaptively combine tasks. The computational results indicate the better effect of the proposed algorithm for solving SALBP-2and the type1of the simple assembly line balancing problem (SALBP-1).Analysis the balance characteristic of ALBP, a station ant colony algorithm (SACO) is proposed to address SALBP-2.(1) The objective of SACO is decomposed to each station, and approach the global optimization through each local optimization.(2) A bound strategy is proposed to increase/decrease the lower bound/upper bound of station times according to the current best solution, and narrow the variation range of all station times.(3) An elite copy strategy is applied to randomly select one from the current superior ants (Elite Ants), and copy its partial solution to replace the one, which is not satisfied the constraints of bound strategy. The computational results show that SACO can obtain the optimal of most instances, and all obtained results are better than those of other existing meta-heuristic algorithms, including the proposed ACO. Three strategies are also applied to address SALBP-1. Computational results demonstrate that the algorithm is effective for solving SALBP-1.An improved ACO is also proposed to address the type2of two-sided assembly line balancing problem (TALBP-2).(1) A novel formulation is introduced to calculate the heuristic weight. In the formulation, two new heuristic factors:the side of candidate tasks and the idle time of them are introduced. The one-sided task can be chosen in greater probability according to the first factor, thus keeping more either-tasks to the following stations. The second one can make the chosen tasks are no longer limited to the tasks, whose idle time is0or the minimum. Two factors can increase the diversity of optional tasks.(2) A determination rule of station direction is proposed to make two-sided station time increase at the same speed as possible, which can improve the balance between the accompany stations and decrease the idle times caused by imbalance of two stations.(3) A bound strategy with variable-step and a new lower bound rule of station times are introduced in the task assignment mechanism. Three ideal tasks with different priority are defined to choose the suitable ideal task combination for the current station. Computational results verify the validity of proposed approaches.