Two-phase heuristic for disassembly scheduling with multiple product types and parts commonality

Disassembly scheduling is one of the important planning problems in disassembly systems, and generally defined as the problem of determining the quantity and timing of disassembling products in order to satisfy the demand of their parts or components over a planning horizon. This paper focuses on the case of multiple product types with parts commonality for the objective of minimizing the sum of set-up, disassembly operation and inventory-holding costs, and it suggests a two-phase heuristic in which an initial solution is obtained using a linear-programming relaxation, and then improved by perturbing the initial solution using a dynamic programming algorithm with look-ahead check. Computational experiments are done on a number of randomly generated test problems and the results show that the heuristic suggested in this paper can give near-optimal solutions within a short computation time.