AN ARBORESCENT NETWORK FORMULATION AND DUAL ASCENT BASED PROCEDURE FOR THE 2-STAGE MULTIITEM DYNAMIC DEMAND LOTSIZE PROBLEM

Traditional approaches for modeling and solving dynamic demand lotsize problems are based on Zangwill's single-source network and dynamic pr ogramming algorithms. In this paper, we propose an arborescent fixed-c harge network (ARBNET) programming model and dual ascent based branch- and-bound procedure for the two-stage multi-item dynamic demand lotsiz e problem. Computational results show that the new approach is signifi cantly mote efficient than earlier solution strategies. The largest se t 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 s olved in 85.65 CPU seconds. Similar results verify the superiority of the new approach for handling backlogged demand. An additional advanta ge of the algorithm is the availability of a feasible solution, with a known worst-case optimality gap, throughout the problem-solving proce ss.