On stochastic lot-sizing problems with random lead times

Abstract In this paper, we consider lot-sizing problems where the costs, demands and order lead times follow a discrete-time stochastic process with finite support. Traditionally, the methods developed for such problems assume that the underlying stochastic process is stationary and homogeneous and/or that the costs, demands and lead times are independent random variables. In this paper, we assume that the stochastic process is very general, i.e., cost, demand and lead time distributions are non-stationary and are correlated. We use a multi-stage stochastic program to model this problem. Utilizing the property of an optimal solution, called the semi-Wagner-Whitin property, we propose a dynamic programming algorithm that is polynomial in the size of the scenario tree for the case where orders do not cross in time. Key words: stochastic programming, lot-sizing, semi-Wagner-Whitin property, polynomial algorithm, random lead times