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.