Prof. Linwei Xin
University of Illinois at Urbana-Champaign
Talk:
Beating the curse of dimensionality in inventory problems with lead times
Abstract:
Many classical inventory models become notoriously challenging to optimize in the presence of positive lead times, since the state-space blows up and dynamic programming techniques become intractable. This includes, for example, lost sales models with positive lead times, and dual-sourcing models with positive lead time gap between the two suppliers. In this talk, we will present a new algorithmic approach to such problems, which shows that as the lead time grows large, simple policies become asymptotically optimal. These results are quite surprising, as this setting had remained an open algorithmic challenge for over forty years. In particular, we will show that a simple constant-order policy is asymptotically optimal for lost sales models with large lead times, and provide explicit bounds on the optimality gap which demonstrate good performance even for small-to-moderate lead times. We will also show that the so-called Tailored-Base Surge heuristic for dual-sourcing problems is asymptotically optimal as the lead time gap between the two sources grows large. In both cases, our results provide a new algorithmic approach to these problems, as well as a solid theoretical foundation for the good performance of these algorithms observed numerically by previous researchers. Our approach combines ideas from the theory of random walks and queues, convex analysis, and inventory control. Finally, we will talk about implementation of Tailored-Base Surge policies at Walmart.com.
