The economic lot-sizing problem with an emission capacity constraint

• We consider a lot-sizing problem with one global constraint on carbon emissions.
• We show that this problem is NP-hard.
• We present a Lagrangian heuristic, pseudo-polynomial algorithm and FPTAS.
• Special attention is paid to an efficient implementation of the FPTAS.
• Tests show that a combination of the heuristic and FPTAS is very fast.

We consider a generalisation of the lot-sizing problem that includes an emission capacity constraint. Besides the usual financial costs, there are emissions associated with production, keeping inventory and setting up the production process. Because the capacity constraint on the emissions can be seen as a constraint on an alternative objective function, there is also a clear link with bi-objective optimisation. We show that lot-sizing with an emission capacity constraint is NPNP-hard and propose several solution methods. Our algorithms are not only able to handle a fixed-plus-linear cost structure, but also more general concave cost and emission functions. First, we present a Lagrangian heuristic to provide a feasible solution and lower bound for the problem. For costs and emissions such that the zero inventory property is satisfied, we give a pseudo-polynomial algorithm, which can also be used to identify the complete set of Pareto optimal solutions 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 actual gap than the a priori imposed performance, and, especially if the heuristic’s lower bound is used, they are very fast.