A path-relinking approach for a bi-criteria disassembly sequencing problem

The first crucial step of product recovery is disassembly. Some product disassembly is almost always needed in remanufacturing, recycling, and disposal. Since disassembly tends to be expensive, disassembly sequence planning becomes important in minimizing resources (time and money) invested in disassembly and maximizing the level of automation. A disassembly sequence plan (DSP) is a sequence of disassembly tasks, which begins with a product to be disassembled and terminates in a state where all of the parts of interest are separated. The decision version of the problem of finding the optimal DSP is an NP-complete problem and therefore complex and challenging to solve. Often one has to resort to heuristic and metaheuristic techniques for solving such problems. In this paper, we seek a DSP that addresses two criteria in order. First, we look for a sequence, the cost of which is close to our cost aspiration. Second, we look for a sequence that prioritizes some selected parts to be disassembled as early as possible. We propose a greedy randomized adaptive search procedure (GRASP) and path-relinking-based heuristic methodology specifically developed to solve such bi-criteria type of disassembly problem. An example is considered to illustrate the implementation of the methodology. Conclusions drawn include the consistent generation of near-optimal solutions, the ability to preserve precedence, the superior speed of the metaheuristic, and its practicality due to its ease of implementation. (c) 2007 Elsevier Ltd. All rights reserved.