Lotsizing with backlogging and start-ups: the case of Wagner-Whitin costs

We examine the uncapacitated single-item lotsizing problem with backlogging and start-up costs where Wagner-Whitin costs are assumed. We generalize some theoretical results obtained in [5] for the polyhedral description of the convex hull of feasible solutions for models that can be viewed as particular cases of the one treated in this paper (models without start-up costs and models where backlog is not allowed). In the presence of Wagner-Whitin costs (which satisfy p(t) + (h) over tilde(t)(+) - p(t+1) greater than or equal to 0, for 0 less than or equal to t less than or equal to n - 1, and p(t+1) + (h) over tilde(t)(-) - p(t) greater than or equal to 0, for 1 less than or equal to t less than or equal to n, where p(t), (h) over tilde(t)(+) and (h) over tilde(t)(-) are the unit production, storage and backlogging costs; in the case that unit production costs are constant over time, the Wagner-Whitin assumption corresponds to non-negative holding costs and backlogging costs) we present a linear extended formulation with O(n) variables and O(n(2)) constraints. By projection, we obtain a linear formulation in the original space of variables with an exponential number of constraints. (C) 1999 Elsevier Science B.V. All rights reserved.