9 October 2006 Computational complexity of a reverse manufacturing line
Author Affiliations +
Proceedings Volume 6385, Environmentally Conscious Manufacturing VI; 638501 (2006) https://doi.org/10.1117/12.686371
Event: Optics East 2006, 2006, Boston, Massachusetts, United States
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.
© (2006) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Seamus M. McGovern, Seamus M. McGovern, Surendra M. Gupta, Surendra M. Gupta, } "Computational complexity of a reverse manufacturing line", Proc. SPIE 6385, Environmentally Conscious Manufacturing VI, 638501 (9 October 2006); doi: 10.1117/12.686371; https://doi.org/10.1117/12.686371

Back to Top