1. ¹Graduate School of Logistics, Inha University, Incheon, Korea
2. ²Hanyang University, Seoul, Korea
3. ³Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland

Correspondence: H-J Kim, Graduate School of Logistics, Asia Pacific School of Logistics, Inha University, 253 Yonghyun-dong, Nam-gu, Incheon, 402-751, Republic of Korea. E-mail: hwa-joong.kim@inha.ac.kr

Work carried out while at Swiss Federal Institute of Technology at Lausanne.

Received February 2006; Accepted November 2007; Published online 20 February 2008.

Abstract

This paper considers a production planning problem in disassembly systems, which is the problem of determining the quantity and timing of disassembling end-of-use/life products in order to satisfy the demand of their parts or components over a planning horizon. The case of single product type without parts commonality is considered for the objective of minimizing the sum of setup and inventory holding costs. To show the complexity of the problem, we prove that the problem is NP-hard. Then, after deriving the properties of optimal solutions, a branch and bound algorithm is suggested that incorporates the Lagrangean relaxation-based upper and lower bounds. Computational experiments are performed on a number of randomly generated problems and the test results indicate that the branch and bound algorithm can give optimal solutions up to moderate-sized problems in a reasonable computation time. A Lagrangean heuristic for a viable alternative for large-sized problems is also suggested and compared with the existing heuristics to show its effectiveness.