An exact algorithm for two-level disassembly scheduling

Disassembly scheduling is the problem of determining the quantity and timing of disassembling used or end–of–life products while satisfying the demand of their parts or components over a given planning horizon. This paper considers the two–level disassembly structure that describes a direct relationship between the used product and its parts or components. To formulate the problem mathematically, we first suggest an integer programming model, and then reformulate it to a dynamic programming model after characterizing properties of optimal solutions. Based on the dynamic programming model, we develop a polynomial exact algorithm and illustrate it with an example problem.