The economic lot-sizing problem with an emission capacity constraint

Mathijn J. Retel Helmrich, Raf Jans, Wilco van den Heuvel and Albert P.M. Wagelmans

European Journal of Operational Research, 2015, vol. 241, issue 1, 50-62

Abstract: 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 NP-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.

Keywords: Integer programming; Approximation scheme; Lot-sizing; Carbon emissions (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714005335
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:241:y:2015:i:1:p:50-62

DOI: 10.1016/j.ejor.2014.06.030

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().