Efficient Reformulations for Uncapacitated and Capacitated Lot-Sizing with Substitutions and Initial Inventories

This section considers extensions of two well-known single-level lot-sizing models, namely the Wagner–Whitin Problem (WWP) and the Capacitated Lot-Sizing Problem (CLSP), that incorporate product substitution options. The literature published on lot-sizing models with substitution until now does not cover two aspects that are important in real-world production planning problems: Initial inventories are not taken into account. While these can be neglected easily without loss of generality in standard lot-sizing models by netting demands, this cannot be done if substitutions are possible, as the net demands depend on substitution decisions which are part of the optimization problem. E.g., consider a lot-sizing problem with two products A and B whose initial inventory is 60 and 20 units, respectively. In addition, assume that A can substitute B, and the gross demand for A and B in period 1 is 40 and 30, respectively. In this case one cannot say that the net demand of B in period 1 is 30 − 20 = 10, because it could be optimal due to the cost parameters and demand in subsequent periods to partially substitute B by A in period 1, so that B is not set up in period 1. In addition, no models and algorithms for lot-sizing with substitution and capacitated resources have been developed. If production bottlenecks exist, it is necessary to consider production capacities in combination with substitutions: Capacitated resources can on the one hand be the reason for substitutions, on the other hand limit the amount of substitutions (e.g., if a machine that could produce substitutes is working almost to full capacity).