[DAK18] The single-item green lot-sizing problem with fixed carbon emissions

Conférence Internationale avec comité de lecture : EURO, July 2018, Spain,

Mots clés: Lot-Sizing, Complexity, Dynamic Programming

Résumé: This presentation is based on our paper in EJOR (Absi et al., 2016), which considers a single-item lot sizing problem with a periodic car- bon emission constraint. In each period, the carbon emission constraint defines an upper limit on the average emission per product. Di ff erent supply modes are available, each one characterized by its own cost and carbon emission parameters. The problem consists in selecting the modes used in each period such that no carbon emission constraint is violated, and the cost of satisfying all the demands on a given time horizon is minimized. This problem, introduced in Absi et al. (2013), has been shown polynomially solvable when only unit carbon emis- sions are considered. In this work, we extend the analysis to the real- istic case of a fixed carbon emission associated to each mode, in addi- tion to its unit carbon emission. We show that the resulting problem is NP-hard. Several dominant properties are presented, and two dy- namic programming algorithms are proposed. We also establish that the problem can be solved in polynomial time for a fixed number of modes when carbon emission parameters are stationary. The presenta- tion will end with a discussion on the extension of the problem to the multi-item case.


@inproceedings {
title="{The single-item green lot-sizing problem with fixed carbon emissions}",
author=" S. Dauzère-Pérès and N. Absi and S. Kedad-Sidhoum and B. Penz and C. Rapine ",
address=" Spain",