In this thesis we study the use of so-called sandwich functions for lot-sizing problems. A sandwich function is a function that replaces the objective function of an optimisation problem in such a way that the original objective function is bounded by this function and a scalar multiple of this function from below and above, respectively. We start by pointing out some places in the literature where this method has been used before. We then provide an analysis of sandwich functions for two well known cost functions, the modified all-unit discount cost function and the stepwise cost function. Finally, several applications of this method to existing lot-sizing problems are presented. Amongst these applications is a $2$-approximation algorithm for the lot-sizing problem with demand time windows and stepwise cost, which is strongly $\\mathcal{NP}$-hard when order splitting is not allowed. To the best of our knowledge, this is the first constant factor approximation algorithm for this problem.

Heuvel, W. van den
hdl.handle.net/2105/45901
Econometrie
Erasmus School of Economics

Molendijk, A.L. (2019, February 19). Sandwich functions for the lot-sizing problem. Econometrie. Retrieved from http://hdl.handle.net/2105/45901