混合离散粒子群算法求解机器人装配线平衡问题  

Hybrid discrete particle swarm algorithm for robotic assembly line balancing problem

作　　者：张灿然 窦建平[1] 王帅 王平远 Zhang Canran;Dou Jianping;Wang Shuai;Wang Pingyuan(School of Mechanical Engineering,Southeast University,Nanjing 211189,China)

机构地区：[1]东南大学机械工程学院,南京211189

出　　处：《东南大学学报（自然科学版）》2023年第2期349-355,共7页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金资助项目(51575108);数字化制造装备与技术国家重点实验室开放基金资助项目(DMETKF2021009)。

摘　　要：以最小化总成本为目标,将一组工序和机器人分配至工作站上的问题称为面向成本的机器人装配线平衡问题(cRALBP),为了解决此NP难问题,提出一种混合离散粒子群优化(HDPSO)算法.首先,对于给定工序,设计动态规划方法直接获取工序对应的最优机器人分配方案,从而缩小搜索空间,提高算法的全局寻优能力.然后,提出一种新的算法框架,其通过融合路径重连加强算法的局部搜索能力,并通过汉明距离评估解之间的差异,选择采用多片段交叉算子或者片段变异算子进行粒子更新,取代随机选择算子的方法,从而实现算法全局搜索和局部搜索的平衡.将所提出的HDPSO算法与最新的粒子群、人工鱼群算法在144个算例上进行对比,验证了HDPSO算法的有效性和优越性.The problem of assigning a group of tasks and robots to workstations with the objective of minimizing the total cost is called the cost-oriented robotic assembly line balancing problem(cRALBP).To solve the NP-hard problem,a hybrid discrete particle swarm optimization(HDPSO)algorithm is proposed.First,for a given task permutation,the dynamic programming is designed to directly obtain the optimal robot allocation corresponding to the task permutation,so as to reduce the search space and improve the global search ability.Then,a novel algorithm framework is proposed,which employs the path-relinking to strengthen the local search ability,and uses Hamming distance for evaluating the differences between solutions instead of the random operator selection method to decide whether to choose multi-fragment crossover operator or fragment mutation operator for updating,and thus the balance between global search and local search of the algorithm is achieved.The HDPSO algorithm is compared with the latest PSOs and the artificial fish swarm algorithm on 144 cases to verify the effectiveness and superiority of HDPSO algorithm.

关 键 词：机器人装配线平衡问题 粒子群优化 动态规划 路径重连 

分 类 号：TH162[机械工程—机械制造及自动化] TP391[自动化与计算机技术—计算机应用技术]