Improved algorithms for dynamic lot sizing problems with incremental discount. (2nd January 2019)

• Record Type: Journal Article
• Authors: Fan, Jie; Wang, Guoqing
• Is Part Of: Optimization methods and software. Volume 34:Number 1(2019)
• Page Start: 139
• Page End: 149
• Publication Date: 2019-01-02
• Subjects: dynamic lot sizing -- concave piecewise linear cost -- exact algorithms -- geometric technique -- dynamic programming; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1368508
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We develop improved algorithms for the dynamic lot sizing problems with incremental discount, where the procurement cost is a concave piecewise linear function with m sections and the holding cost is linear. We decompose the problem carefully and present a new dynamic programming formulation. By using geometric techniques, we show that when m is fixed, the problem can be solved in O ( T log T ) time, and further O ( T ) time if the procurement cost is stationary.