  This paper deals with a problem of production planning, which is a version of
the capacitated single-item lot sizing problem with backordering under demand
uncertainty, modeled by uncertain cumulative demands. The well-known interval
budgeted uncertainty representation is assumed. Two of its variants are
considered. The first one is the discrete budgeted uncertainty, in which at
most a specified number of cumulative demands can deviate from their nominal
values at the same time.The second variant is the continuous budgeted
uncertainty, in which the sum of the deviations of cumulative demands from
their nominal values, at the same time, is at most a bound on the total
deviation provided. For both cases, in order to choose a production plan that
hedges against the cumulative demand uncertainty, the robust minmax criterion
is used. Polynomial algorithms for evaluating the impact of uncertainty in the
demand on a given production plan in terms of its cost, called the adversarial
problem, and for finding robust production plans under the discrete budgeted
uncertainty are constructed. Hence, in this case, the problems under
consideration are not much computationally harder than their deterministic
counterparts. For the continuous budgeted uncertainty, it is shown that the
adversarial problem and the problem of computing a robust production plan along
with its worst-case cost are NP-hard. In the case, when uncertainty intervals
are non-overlapping, they can be solved in pseudopolynomial time and admit
fully polynomial timeapproximation schemes. In the general case, a
decomposition algorithm for finding a robust plan is proposed.
