An Arborescent Network Formulation and Dual Ascent Based Procedure for the Two‐Stage Multi‐Item Dynamic Demand Lotsize Problem
针对两阶段多物品动态需求批量问题，提出树状固定费用网络模型和基于对偶上升的分支定界算法，计算效率显著优于传统动态规划方法，并能在求解过程中提供已知最坏情况最优性差距的可行解。
ABSTRACT 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.