求解拆卸线平衡问题的改进人工蜂群算法

Improved Artificial Bee Colony Algorithm for Disassembly Line Balancing Problem

大规模拆卸线平衡问题(disassembly line balancing problem,DLBP)是NP完全问题.为克服传统算法求解DLBP搜索过于随机、易于早熟,且求解难度随任务规模的增加呈指数级增长等不足,构建了基于最小化工作站、均衡负荷、尽早拆卸有危害和高需求零部件的DLBP多目标优化模型,在此基础上,提出了改进人工蜂群算法.该算法包括以下4个阶段:在初始解生成阶段,引入危害指标和需求指标,提升算法收敛性能;在雇佣蜂搜索阶段,采取可变步长搜索策略,增加对较优解的搜索深度,加速淘汰劣解;在观察蜂搜索阶段,采用常规搜索与蠕动搜索相结合的混合搜索策略;在侦察蜂搜索阶段,构造了基于分布估计的搜索策略,引导搜索过程.应用本文算法对70个测试问题进行求解,其中65个求得了最优解,寻优率为92.86%;对10个任务实例求得最优解的需求指标为9 730个,比蚁群算法减少了360个;52个任务实例的开启工作站数目、平滑率和拆卸成本3项指标均取得了更优的结果,求解较大规模问题的性能显著提升.

The disassembly line balancing problem （DLBP） has been mathematically proved to be NP-complete. The search processes of traditional algorithms for DLBP are so random that they tend to get local optimum due to DLBP＇ s exponential time complexity for large scale cases. To overcome the shortcomings of traditional algorithms, an improved artificial bee colony （ABC） algorithm was proposed based on a muhi-objective optimization model for the DLBP, where the main objectives to achieve are to minimize the number of workstations, equilibrate workload, and remove hazardous and high-demand components as early as possible. This algorithm includes four phases. In the initial solution generation phase, the hazardous index and demand measure are used to improve the convergence property of the algorithm. In the employed bee phase, a variable step length search strategy is introduced to take a further search for better solutions and speed up the elimination of inferior solutions. In the onlooker bee phase, a hybrid search strategy that combines the traditional search with the disturbance search is adopted. In the scout bee phase, a search strategy based on estimation of distribution is constructed. The proposed algorithm was applied to solve 70 test cases toverify its validity. As a result, optimal solutions were obtained for 65 cases and the optimization rate is 92.86%. In addition, the algorithm was applied to solve a 10-task case and a 52-task case. The results show that the demand measures to obtain the optimal solution for the 10-task case are 9 730, which is 360 less that by ant colony optimization; meanwhile, better solutions for the balance rate, number of workstations and cost are obtained for the 52-task case. Compared to the traditional ABC algorithm, the improved algorithm has a significantly superior performance in solving large-scale DLBPs.