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.
Disassembly, disassembly line balancing, combinatorial optimization, complexity theory, product recovery
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.
Society of Photo-Optical Instrumentation Engineers
Gupta, Surendra M. and McGovern, Seamus M., "Computational complexity of a reverse manufacturing line" (2006). . Paper 30. http://hdl.handle.net/2047/d10009942
Click button above to open, or right-click to save.