多约束双边装配线平衡的改进万有引力搜索算法

Improved gravitational search algorithm for two-ided assembly line balancing problem with multiple constraints

双边装配线具有结构紧凑、生产高效的特点,广泛用于汽车等大型产品的装配中。在双边装配线中除了要满足装配线中基本的约束外,还需要考虑一些特定的约束,包括方向约束、区域约束、位置约束和协同约束等。应用随机键编码方法,将万有引力搜索算法(Gravitational Search Algorithm,GSA)的连续型编码转换为具有离散特性的任务序列。针对多种并存的约束,通过方向和多约束集调整,明确各约束间的逻辑关系,简化解码流程。融合局部搜索算法调整邻域结构,构造一种改进的万有引力搜索算法(Improved Gravitational Search Algorithm,IGSA),增加种群多样性,避免陷入局部最优。最后通过算例验证了改进的万有引力搜索算法的有效性。

Two-sided assembly lines are broadly used in plants which produce large-sized high-volume products such as automobiles due to its characteristic of compact size and high efficiency. Besides the fundamental constraints, some specific constraints including direction constraints, zoning constraints, positional constraints and synchronous constraints should be taken into consideration when balancing the two-sided assembly lines. The random-keys encoding scheme is applied to convert the continuous positions of the Gravitational Search Algorithm （GSA） into the discrete task sequence. Considering that one task may be involved in more than one constraint, the directions and constraints of all tasks are adjusted uniformly and hence the decoding process is largely simplified. While the GSA searches the global space, the neighborhood structure is hired to search the local space, so as to achieve the intensification and diversification of the population concurrently. The experimental results show that the Improved Gravitational Search Algorithm（IGSA） is efficient and effective in solving the given problem.