Yves Pochet

Title:
Single item lot-sizing with non-decreasing capacities

Abstract:
We consider the single item lot-sizing problem with non-decreasing capacities over time.
When the cost function is non-speculative or Wagner-Whitin (for instance, constant unit production costs and non-negative unit holding costs), and the production set-up costs are non-increasing over time, it is known that the
minimum cost lot-sizing problem is polynomially solvable (polynomial time dynamic programming algorithm).

For the lot-sizing problem with constant capacities over time and Wagner-Whitin costs, a compact linear programming formulation of the problem is also known. This formulation is based on a mixing set relaxation and reformulation
of the stock minimal solutions for this problem.

In this talk, we show how to extend this result to the problem with non-decreasing capacities over time.
We provide an improved LP formulation for this lot-sizing problem, which is built from an appropriate mixing set relaxation of this problem. When the cost function satisfies the above conditions, we prove that this linear programming relaxation suffices to solve the lot-sizing problem to optimality.

We illustrate the use and efficiency of this improved LP formulation on some test problems, with/without Wagner-Whitin costs, with non-decreasing and arbitrary capacities over time.