Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty

In this paper, we consider the two-stage minimax robust uncapacitated lot-sizing problem with interval uncertain demands. A mixed integer programming formulation is proposed. Even though the robust uncapacitated lot-sizing problem with discrete scenarios is an NPNP-hard problem, we show that it is polynomial solvable under the interval uncertain demand set.

► We consider two-stage minimax robust uncapacitated lot-sizing problem.
► A mixed integer programming formulation of the robust counterpart is proposed.
► We show that it is polynomial solvable under the interval uncertain demand set.
► A dynamic programming algorithm is developed.