Abstract

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.

Authors
Awi Federgruen and Michal Tzur
Format
Journal Article
Publication Date
Journal
Naval Research Logistics

Full Citation

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
vol.
40
, (January 01, 1993):
459
-
478
.