An intelligent product disassembly planning method

Disassembly sequence planning problem is a NP-hard combinatorial optimization problem. Generally, with the increasing of components number, the computational complexity of searching for good disassembly solution(s) in a large search space of disassembly solutions will be increased more. Therefore, to avoid the exploded combination, heuristic methods are often used for the goal of finding optimum solution(s) at a high efficiency. In the proposed research, we present the Disassembly Feasibility Information Graph (DFIG) to describe product's disassembly operations (sequences) information. In fact, this graph is a model of simulated all possible disassembly operations, and meanwhile, stored relevant information of operations which includes feasibility of operations and disassembly processes if these operations are feasible. Based on this graph, product's disassembly sequences planning problem could be transformed into this problem: On the DFIG, to find out a path with an optimized sum value, which starts from the Start Point, and could tour all the components of product just one time, along with the weighed, directed edges. A genetic algorithm is presented to realize the search and optimization for disassembly sequence which is symbolized as a directed path on DFIG. In the genetic algorithm, a natural way of encoding chromosome is through a sequence of disassembly operations. And due to the property of chromosome- from the start to end of chromosome, representing the sequence of disassembly operations, we use a kind of Order Crossover (OX) operator to execute the crossover process. This method can conserve the partial sequences of parents and if they are feasible in parents, they will be feasible in the children, too. Therefore, by this crossover operation, children could inherit some information of parents. In addition, after a chromosome is generated in original random creation or genetic operations, a test for feasibility of chromosome according to some precedence relations, is executed for expelling unfeasible chromosomes from population. This could improve the search and optimization process efficiently. This method combines the filling up process of DFIG graph with searching process for optimum path. That is, with the evolving process of genetic search and optimization, the DFIG is extended from root point, and new node (represent disassembly operation) filled with relevant data and information is added into. And meanwhile, the genetic search will move close to the optimum path in the process of searching. Based on these approaches, we developed a software system, a product's disassembly planning system on 3D CAD platform. And by repeated trials, these conclusions are interesting: 1. The main computation time is used for components' disassembly planning on the 3D environment, and compared with it, time used by operating process of genetic algorithm is smaller. 2. Using large scale population could realize optimized population in small generations, but not an exhausting search. 3. If constraint relationships are strong, the optimized solution(s) could be found quickly.