CE-GA协同进化算法求解人机共同作业的U形装配线平衡问题

CE-GA Co-evolutionary Algorithm for Solving U-shaped Assembly Line Balancing Problem with Man-robot Cooperation

针对一类广泛存在的生产装配问题,建立人机共同作业的资源约束U形装配线平衡问题(ResourceconstraintU-shaped assembly line balancing problem with man-robot cooperation,RCUALBP_MRC)模型。该模型中机器人与助理均为有限资源,机器人可替代人工操作,助理可协助工人操作,优化目标为同时最小化总成本指标和最大化线效率以及负载标准差综合指标。一种用于求解RCUALBP_MRC的基于交叉熵(Cross-entropy,CE)方法与遗传算法(Geneticalgorithm,GA)的协同进化算法(CE-GACo-evolutionaryalgorithm,CE-GACEA)被提出。首先,根据问题特点,对解中工序子序列设计了一种基于工序选择因子的编码(Task selection factor based code,TSFBC)。其次,在算法的全局搜索阶段对解中工序子序列和机器人及助理子序列所确定的子空间,分别利用GA和CE的操作进行协同搜索,可丰富搜索方向并发现优质解区域;局部搜索阶段加入种群分裂-合并机制,可有效平衡算法的全局与局部搜索,改善算法性能。最后,通过在不同规模问题上的仿真试验和算法对比,验证所提CE-GACEA的有效性。

Aiming at a kind of widely existing production assembly problem,the model of the resource-constraint U-shaped assembly line balancing problem with man-robot cooperation(RCUALBP_MRC)is built.In this model,robots and assistants are limited resources,robots can replace manual operations,and assistants can assist workers in operations.The criteria are to simultaneously minimize the objective of total cost as well as maximize the integrated objective of line efficiency and load variance.Based on the cross-entropy(CE)method and genetic algorithm(GA),a co-evolutionary algorithm(CE-GACEA)is proposed for solving the RCUALBP_MRC.Firstly,according to the characteristics of problem solution,an efficient coding called the"task selection factor based code"(TSFBC)is designed for the task subsequence in solution.Secondly,in the global search phase,the operations of GA and CE are used to collaboratively search the subspaces determined by the task subsequence as well as the robot and assistant subsequence in solution,which can enrich search directions and find promising regions.In the local search phase,the split-merge mechanism of population is adopted,which effectively balances the global and local search of the algorithm and improves the performance of the algorithm.Finally,simulation experiments and comparisons on different instances demonstrate the effectiveness of proposed algorithm.