The Economic Lot-Sizing Problem with an Emission Constraint

We consider a generalisation of the lot-sizing problem that includes an emission constraint. Besides the usual financial costs, there are emissions associated with production, keeping inventory and setting up the production process. Because the constraint on the emissions can be seen as a constraint on an alternative cost function, there is also a clear link with bi-objective optimisation. We show that lot-sizing with an emission constraint is NP-hard and propose several solution methods. First, we present a Lagrangian heuristic to provide a feasible solution and lower bound for the problem. For costs and emissions for which the zero inventory property is satisfied, we give a pseudo-polynomial algorithm, which can also be used to identify the complete Pareto frontier of the bi-objective lot-sizing problem. Furthermore, we present a fully polynomial time approximation scheme (FPTAS) for such costs and emissions and extend it to deal with general costs and emissions. Special attention is paid to an efficient implementation with an improved rounding technique to reduce the a posteriori gap, and a combination of the FPTASes and a heuristic lower bound. Extensive computational tests show that the Lagrangian heuristic gives solutions that are very close to the optimum. Moreover, the FPTASes have a much better performance in terms of their gap than the a priori imposed performance, and, especially if the heuristic’s lower bound is used, they are very fast.