A robust block-chain based tabu search algorithm for the dynamic lot sizing problem with product returns and remanufacturing

This paper studies the dynamic lot sizing problem with product returns and remanufacturing (DLRR). Given demands and returns over a planning horizon, DLRR is to determine a production schedule of manufacturing new products and/or remanufacturing returns such that demand in each period is satisfied and the total cost (set-up cost plus holding cost of inventory) is minimized. Since DLRR with general cost functions for set-ups of manufacturing and remanufacturing is NP-hard, we develop a tabu search to produce high-quality solutions. To generate a good initial solution, we use a block-chain based method where the planning horizon is split into a chain of blocks. A block may contain either a string of manufacturing set-ups, a string of remanufacturing set-ups, or both. Given the cost of each block, an initial solution corresponding to a best combination of blocks is found by solving a shortest-path problem. Neighboring operators aim at shifting integer variables for manufacturing and remanufacturing set-ups. We evaluate our algorithm on 6480 benchmark problems and compare it with other available algorithms. Computational results demonstrate that our algorithm produces an optimal solution in 96.60% of benchmark problems, with an average deviation of 0.00082% from optimality and it is a state-of-the-art method for DLRR. (C) 2013 Elsevier Ltd. All rights reserved.