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

• We design TS method for dynamic lot sizing with product returns and remanufacturing.
• A block-chain based method is introduced to generate a good initial solution.
• Neighboring operators are to shift integer variables for two kinds of set-ups.
• We evaluate our algorithm on 6480 problems and compare it with other best methods.
• Computational results demonstrate that our algorithm is a state-of-the-art method.

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.