Greedy algorithm for disassembly line scheduling

Seamus M. McGovern, Northeastern University
Surendra M. Gupta, Northeastern University

Article comments

Originally published in the Proceedings of the 2003 IEEE International Conference on Systems, Man, and Cybernetics, Washington, DC, October 2003

Abstract

Remanufacturing, recycling, and disposal recovery operations require the performance of disassembly activities. The disassembly line is the best choice for automated disassembly of returned products, however, finding the optimal balance is computationally intensive with exhaustive search quickly becoming prohibitively large. In this paper, a greedy algorithm is presented for obtaining optimal or near-optimal solutions to the disassembly line balancing problem. The greedy algorithm is a first-fit decreasing algorithm further enhanced to preserve precedence relationships. The algorithm seeks to minimize the number of workstations while accounting for hazardous and high demand components. A hill-climbing heuristic is then developed to balance the part removal sequence. Examples are considered to illustrate the methodology. The conclusions drawn from the study include the consistent generation of optimal or near-optimal solutions, the ability to preserve precedence, the speed of the algorithm and its practicality due to the ease of implementation.