Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs

A.J.D. Lambert

    Research output: Contribution to journalArticleAcademicpeer-review

    59 Citations (Scopus)
    2 Downloads (Pure)


    Disassembling complex products is formally approached via network representation and subsequent mathematical modeling, aimed at selecting a good or optimum sequence of disassembly operations. This is done via heuristics, metaheuristics or mathematical programming. In contrast with heuristics and metaheuristics, which select a near-optimum solution, mathematical programming guarantees the selection of the global optimum. This problem is relatively simple if the disassembly costs can be assumed sequence independent. In practice, however, sequence dependent disassembly costs are frequently encountered, which causes NP-completeness of the problem. Although methods, e.g., based on the two-commodity network flow approach, are available to solve this constrained asymmetric Traveling Salesperson problem rigorously, this requires the introduction of integer variables. In this paper, a modification of the two-commodity network flow approach is proposed, which reduces the number of integer variables. This is applied to product structures that can be represented by a disassembly precedence graph. It is demonstrated that use of integer variables is completely avoided by iteratively solving a binary integer linear programming problem. This appears to be more efficient than solving the corresponding integer linear programming problem. It is demonstrated, on the basis of some cases, that this method might provide the exact solution of problems with increased complexity compared to those discussed so far in the literature. This appears particularly useful for evaluating heuristic and metaheuristic approaches. Keywords: Assembly planning; Disassembly planning; Mathematical programming; Network; Traveling salesperson problem; Optimization
    Original languageEnglish
    Pages (from-to)538-549
    JournalOmega : The International Journal of Management Science
    Issue number6
    Publication statusPublished - 2006


    Dive into the research topics of 'Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs'. Together they form a unique fingerprint.

    Cite this