Lot-sizing with fixed charges on stocks: the convex hull

In this paper, we examine a variant of the uncapacitated lot-sizing model of Wagner–Whitin that includes fixed charges on the stocks. Such a model is natural in a production environment where stocking is a complex operation, and appears as a subproblem in more general network design problems.

Linear-programming formulations, a dynamic program, the convex hull of integer solutions and a separation algorithm are presented. All these turn out to be very natural extensions of the corresponding results of Barany et al. (Math. Programming Stud. 22 (1984) 32) for the uncapacitated lot-sizing problem. The convex hull proof is based on showing that an extended facility location formulation is tight and by projecting it onto the original space of variables.     

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 NP-hard problem, we show that it is polynomial solvable under the interval uncertain demand set.     

Lot-sizing on a tree

For the problem of lot-sizing on a tree with constant capacities, or stochastic lot-sizing with a scenario tree, we present various reformulations based on mixing sets. We also show how earlier results for uncapacitated problems involving (Q,S_Q) inequalities can be simplified and extended. Finally some limited computational results are presented.     

A single supplier–single retailer system with an order-up-to level inventory policy

We consider a two-level vendor-managed system in which external demand occurs only at a retailer and a supplier replenishes the retailer employing an order-up-to S policy over T periods. We present an O(T³) algorithm to coordinate the system when S is known. We also show that S can be optimized in O(aT³) time for an input parameter a.     

A comparative study of modeling and solution approaches for the coordinated lot-size problem with dynamic demand

In the coordinated lot-size problem, a major setup cost is incurred when at least one member of a product family is produced and a minor setup cost for each different item produced. This research consolidates the various modeling and algorithmic approaches reported in the literature for the coordinated replenishment problem with deterministic dynamic demand. For the two most effective approaches, we conducted extensive computational experiments investigating the quality of the lower bound associated with the model’s linear programming relaxation and the computational efficiency of the algorithmic approaches when used to find heuristic and optimal solutions. Our findings indicate the superiority of the plant location type problem formulation over the traditional approach that views the problem as multiple single-item Wagner and Whitin problems that are coupled by major setup costs. Broader implications of the research suggest that other classes of deterministic dynamic demand lot-size problems may also be more effectively modeled and solved by adapting plant location type models and algorithms.     

Four equivalent lot-sizing models

We study the following lot-sizing models that recently appeared in the literature: a lot-sizing model with a remanufacturing option, a lot-sizing model with production time windows, and a lot-sizing model with cumulative capacities. We show the equivalence of these models with a classical model: the lot-sizing model with inventory bounds.     

Linear-programming extended formulations for the single-item lot-sizing problem with backlogging and constant capacity

Recently, several authors [8, 10] have argued for the use of extended formulations to tighten production planning models. In this work we present two linear-programming extended formulations of the constant-capacity lot-sizing problem with backlogging. The first one applies to the problem with a general cost function and has O(n³) variables and constraints. This improves on the more straightforward O(n⁴) Florian and Klein [2] type formulation. The second one applies when the costs satisfy the Wagner-Whitin property but it has O(n²) variables and O(n³) constraints. As a by-product, we positively answer an open question of Miller and Wolsey [4] about the tightness of an extended formulation for the continuous mixing set. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The research was carried out with financial support of the Growth Project G1RD-1999-00034 (LISCOS) of the European Community. The scientific responsibility is assumed by the author.     

Note on “An efficient approach for solving the lot-sizing problem with time-varying storage capacities”

In a recent paper Gutièrrez et al. [1] show that the lot-sizing problem with inventory bounds can be solved in O(TlogT) time. In this note we show that their algorithm does not lead to an optimal solution in general.