求解双边装配线第二类平衡问题的一种蚁群算法∗

摘要

Two-sided assembly line problem is more difficult than one-sided assembly line problem as the task distribution procedure. In this problem, besides the precedence constraints among tasks, the operation directions constraints of tasks and the requirement of parallel work should also be taken into consideration. The mathematical model and an ant colony algorithm were constructed to solve the Two-sided Assembly Line Balancing Problem of type-2(TALBP-Ⅱ). A hybrid ant-based search rule and a heuristic task distribu-tion rule were used in order to establish a feasible solution, global pheromone trail update and the optimum solution search strategy were considered. The feasibility of this algorithm was indicated by a case of a loader final assembly line.%双边装配线在任务分配过程中，除考虑任务先后关系约束外还需兼顾任务操作方位约束及任务操作的并行性要求。针对双边装配线第二类平衡问题提出了数学模型并构建了一种蚁群算法。此算法采用蚁群综合搜索规则、启发式任务分配规则构造一个可行解，对最优解的搜索过程提出了可行的规划方案。最后，通过为某型装载机的实例提出多组较好的平衡方案，验证了此算法的有效性。