An Arborescent Network Formulation and Dual Ascent Based Procedure for the Two-Stage Multi-Item Dynamic Demand Lotsize Problem

Traditional approaches for modeling and solving dynamic demand lotsize problems are based on Zangwill's single-source network and dynamic programming algorithms. In this paper, we propose an arborescent fixed-charge network (ARBNET) programming model and dual ascent based branch-and-bound procedure for the two-stage multi-item dynamic demand lotsize problem. Computational results show that the new approach is significantly more efficient than earlier solution strategies. The largest set of problems that could be solved using dynamic programming contained 4 end items and 12 time periods, and required 475.38 CPU seconds per problem. The dual ascent algorithms averaged .06 CPU seconds for this problem set, and problems with 30 end items and 24 time periods were solved in 85.65 CPU seconds. Similar results verify the superiority of the new approach for handling backlogged demand. An additional advantage of the algorithm is the availability of a feasible solution, with a known worst-case optimality gap, throughout the problem-solving process.