Computational complexity of finding Pareto efficient outcomes for green lot-sizing models
W. van den Heuvel, H.E. Romeijn, D. Romero Morales
Nowadays companies try to reduce their carbon footprint, not only to comply with targets, but also as a demonstration of corporate social responsibility. Bearing in mind this environmental awareness, the choice of a production plan can be modeled as a Bi-Objective Economic Lot-Sizing problem, in which we aim to minimize the total lot-sizing costs including production and inventory holding costs, as well as minimizing the maximum production and inventory emissions across blocks of given length. In this paper, we identify non-trivial problem classes for which this problem is polynomially solvable. On the other hand, if we relax any of the parameter assumptions, we show that (except for one case) finding a single Pareto efficient outcome is an NP-hard task in general. That means that our complexity results are (almost) tight. Finally, we shed some light on the computational complexity of the task of describing the Pareto frontier.
Keywords: carbon emissions, lot-sizing, bi-objective, Pareto efficient outcomes, complexity analysis