Abstract: To solve the type I two-sided assembly line balancing problem with multiple constraints whose objective is minimizing the number of station,a multi-objective mathematical model was constructed,and a hybrid fruit fly algorithm was proposed.In the algorithm,the generation process of fruit fly was divided into three stages:encoding,decoding and assignment.A task assignment method oriented to all constraints was proposed,and a pre-assignment mechanism and a reset mechanism were designed.In the iterative search stage,the idea of neighborhood transformation was introduced,and various insertion and crossover operators were designed to construct neighborhoods for local search.In addition,a fitness function with minimizing the weighted idle time was proposed as an auxiliary function for optimization.Finally,comparative experiments were designed based on several benchmark cases of different sizes,and results showed that the proposed hybrid fruit fly algorithm could effectively solve the type I two-sided assembly line balancing problem with multiple constraints and has certain superiority.

Key words: two-sided assembly line balancing, multiple constraints, fruit fly optimization algorithm, neighborhood transformation

摘要： 为求解以最小化工位数为目标的第Ⅰ类多约束双边装配线平衡问题,构建多目标数学模型,并提出混合果蝇算法的求解算法。在算法设计中,将果蝇个体的生成过程分为编码、解码和分配3个阶段,提出面向全部约束的作业分配方法,设计了预分配机制和重置机制;在迭代搜索阶段,引入邻域变换思想,设计多种插入和交叉算子构建邻域进行局部搜索;此外,算法提出最小化加权空闲时间作为适应度函数辅助寻优。最后基于多个不同规模的标杆算例设计了对比实验,实验结果表明所提混合果蝇算法能有效求解第Ⅰ类多约束双边装配线平衡问题,且具有一定的优越性。

关键词: 双边装配线平衡, 多约束, 果蝇算法, 邻域变换