The dynamic lot-sizing model with backlogging: A simple 0(n log n) algorithm and minimal forecast horizon procedure
Coauthor(s): Michal Tzur.
We develop a simple O(n log n) solution method for the standard lot-sizing model with backlogging and a study horizon of n periods. Production costs are fixed plus linear and holding and backlogging costs are linear with general time-dependent parameters. The algorithm has linear [O(n)] time complexity for several important subclasses of the general model. We show how a slight adaptation of the algorithm can be used for the detection of a minimal forecast horizon and associated planning horizon. The adapted algorithm continues to have complexity O(n log n) or O(n) for the above-mentioned subclasses of the general model.
Source: Naval Research Logistics
Federgruen, Awi, and Michal Tzur. "The dynamic lot-sizing model with backlogging: A simple 0(n log n) algorithm and minimal forecast horizon procedure." Naval Research Logistics 40, no. 4 (1993): 459-478.