EFFICIENT APPROXIMATE ALGORITHMS FOR A CLASS OF DYNAMIC LOT SIZE PROBLEMS UNDER PRODUCT SUBSTITUTION

Our investigation into the production substitution between prod-ucts is motivated by a significant issue faced by firms in practice: the effective balance of setup and substitution cost. Given that firms can adjust an oper-ation policy to lower the setup and substitution costs or both, the operation manager should also know how best to make the adjustment. Thus, in this study, we consider a class of dynamic lot sizing problems with one-way and two-way product substitution modes under durable and perishable products. According to some structural properties in an optimal solution, we devise a for-ward dynamic programming (DP) algorithm to work out the problem with two durable products in a polynomial time. Then, we develop an efficient approx-imate DP algorithm to solve the problem with multiple perishable products. Finally, on a comprehensive test bed, we gain some useful insights on the im-pact of substitution on the total costs. We also tested the effectiveness of the approximate algorithm.