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.