Improved Artificial Bee Colony Algorithm for Disassembly Line Balancing Problem

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 multi-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 to verify 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.