The authors develop a simple O(nlogn) 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. The authors 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(nlogn) or O(n) for the above-mentioned subclasses of the general model.
