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.
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.
Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.
Each topic is linked to an index of publications on that topic.