Share Email Print
cover

Proceedings Paper

Computational complexity of a reverse manufacturing line
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

Disassembly has recently gained attention in the literature due to its role in product recovery. Disassembly activities take place in various recovery operations including remanufacturing, recycling, and disposal. The disassembly line is the best choice for automated disassembly of returned products. It is therefore important that the disassembly line be designed and balanced so that it works as efficiently as possible. However, finding the optimal balance is computationally intensive with exhaustive search quickly becoming prohibitively large, even for relatively small products, due to exponential growth. In this paper, complexity theory is reviewed and used to prove that the DISASSEMBLY LINE BALANCING PROBLEM is NP-complete, unary NP-complete, and NP-hard, necessitating specialized solution methodologies, including those from the field of combinatorial optimization.

Paper Details

Date Published: 9 October 2006
PDF: 12 pages
Proc. SPIE 6385, Environmentally Conscious Manufacturing VI, 638501 (9 October 2006); doi: 10.1117/12.686371
Show Author Affiliations
Seamus M. McGovern, National Transportation Systems Ctr., U.S. Dept. of Transportation (United States)
Surendra M. Gupta, Northeastern Univ. (United States)


Published in SPIE Proceedings Vol. 6385:
Environmentally Conscious Manufacturing VI
Surendra M. Gupta, Editor(s)

© SPIE. Terms of Use
Back to Top