In this talk, I will discuss the dynamic lotsizing problem. The issue is to find the optimal timing and level of production to satisfy known but varying demand over a finite time horizon. I will start by providing a small tutorial on the basic single item uncapacitated lotsize problem and its extensions. I will discuss various properties and Mixed Integer Programming formulations for this problem. Next I will discuss some of the work that I have done on applying Dantzig-Wolfe decomposition to the Capacitated Lotsize Problem with Setup Times (CLST). I will present two alternative Dantzig-Wolfe reformulations. In the first approach, the capacity constraints are the complicating constraints and the problem is split up into single-item uncapacitated lotsizing problems. In the second approach, Dantzig-Wolfe decomposition is applied to the network reformulation of the lotsizing problem. The demand constraints are now the linking constraints and the problem decomposes into subproblems per period which contain the capacity and set up constraints. A comparison is made with other lower bounds from the literature.
Groupe d’études et de recherche en analyse des décisions