Efficient approximate algorithms for a class of dynamic lot size problem under product substitution

Our motivation to study the production substitution between the products come from the firms’ practice. A significant issue to the firms is the effective balance of setup and substitution cost. Since the firms can adjust the operation policy to lower the setup and substitution costs or both, the operation manager would like to know how best to make the adjustment. Given this, we consider a class of dynamic lot sizing problems with one-way and two-way product substitution under durable and perishable products. According to some structural properties in an optimal solution, we devise a forward dynamic programming algorithm to work out the problem with two durable products in polynomial time, and develop an efficient approximate dynamic programming algorithm to solve the problem with multiple perishable products. Finally, on a comprehensive test bed, we gain some useful insights on the impact of substitution on the total costs. The effectiveness of the approximate algorithm is also tested.