Computational complexity of a reverse manufacturing line

Seamus M. McGovern; Surendra M. Gupta

doi:10.1117/12.686371

9 October 2006 Computational complexity of a reverse manufacturing line

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

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.

Citation Download Citation

Seamus M. McGovern and Surendra M. Gupta "Computational complexity of a reverse manufacturing line", Proc. SPIE 6385, Environmentally Conscious Manufacturing VI, 638501 (9 October 2006); https://doi.org/10.1117/12.686371

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available