Variable Neighborhood Search Algorithm For Disassembly Line Balancing Problem

With the development of industrial economy, resources and environment problems increasingly draw public attention. Improving resource utilization, reducing environmental pollution and sustainable development have become the social consensus. There is a way to reduce the negative influence on resources and environment problems by recycling old or outdated products. Disassembly is the first step of product recovery, and the disassembly line whose efficiency will affect the subsequent process of product recovery, is the best choice for automated disassembly process with huge numbers of products. Therefore, it is important to design an efficient disassembly line, and the research about Disassembly Line Balancing Problem has important theoretical significance and practical application value.According to the character of Disassembly Line Balancing Problem, both general and mixed mathematical model were established with these optimal objectives of minimizing the number of workstations, smoothness index, hazard index, demand index. Disassembly Line Balancing Problem had been proved to be NP problem, which could be solved excellently by Variable Neighborhood Search algorithm, so a modified Variable Neighborhood Search algorithm was proposed to solve these models.There were three improvement measures for proposed algorithm:(1) The processes of the initial solution forming, a heuristic strategy based operation time, harmful information and demand information was proposed to generate feasible and optimal initial solution, with meeting the precedence relationships. (2) The structure of neighborhoods, three feasible neighborhoods were designed to avoid searching at infeasible neighborhood, which could improve search precision. (3) The strategy of local search, at the beginning of local search, instead of initial solution, an initial solution set was applied to enlarge global search range. Then, first improvement algorithm and tabu list strategy was adopted for local search, which avoid repeated searching at local space, thus improving search efficiency.Several numerical experiments with different size problems were conducted. The proposed VNS algorithm obtained optimal and feasible solutions, which proved the feasibility of proposed algorithm. Compared with other algorithms, the results showed that the proposed VNS algorithm had better performance in solution quality.The proposed VNS algorithm was applied to solve general disassembly line instance. Compared with previous solution, this algorithm obtained better objectives solution, and improved the production efficiency of disassembly line. Besides, the proposed VNS algorithm was also applied to solve mixed disassembly line instance, and this algorithm performed excellently in production efficiency and objectives balancing. Therefore, it demonstrated that the proposed VNS algorithm had better practicability, and showed the practical significance of this thesis.