Premium
An Arborescent Network Formulation and Dual Ascent Based Procedure for the Two‐Stage Multi‐Item Dynamic Demand Lotsize Problem
Author(s) -
Gao LiLian,
Robinson E. Powell
Publication year - 1994
Publication title -
decision sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.238
H-Index - 108
eISSN - 1540-5915
pISSN - 0011-7315
DOI - 10.1111/j.1540-5915.1994.tb00518.x
Subject(s) - dynamic programming , dual (grammatical number) , mathematical optimization , computer science , set (abstract data type) , process (computing) , duality (order theory) , algorithm , mathematics , art , literature , discrete mathematics , programming language , operating system
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.