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.


Originally published in the Proceedings of the SPIE International Conference on Environmentally Conscious Manufacturing VI, Boston, Massachusetts, pp.1-12, October 1-3, 2006


Disassembly, disassembly line balancing, combinatorial optimization, complexity theory, product recovery

Subject Categories

Production engineering





Publication Date


Rights Information

Copyright 2006, Society of Photo-Optical Instrumentation Engineers


This paper was published in Proceedings of SPIE (Volume 6385) and is made available as an electronic reprint with permission of SPIE. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper are prohibited.

Rights Holder

Society of Photo-Optical Instrumentation Engineers

Click button above to open, or right-click to save.

Included in

Engineering Commons