Multi-mode capacitated lot sizing problem with periodic carbon emission constraints

Official URL: https://risc01.sabanciuniv.edu/record=b2708501_(Table of contents)

In this thesis, we investigate the single item capacitated multi-mode lot sizing problem with periodic carbon emission constraints where the carbon emission constraints define an upper bound for average emission per product produced in any period. The uncapacitated version of this problem was discussed in Absi et al. (2013) and solved in polynomial time. We prove that this generalization of the problem is NP-Hard and discuss important structural properties of optimal solutions. We develop algorithms to construct the piecewise linear total production cost functions for each period when the number of modes is fixed where mode represents the number of machines available for usage in production. This allows us to solve the problem using existing dynamic programming algorithms developed for the lot sizing problem with piecewise concave production cost functions. Additionally, we examine an extension of the problem where at most two resources can be used at any period, and produce a polynomial time algorithm to solve it when the number of resources, the cost and emission parameters, and the capacities of the resources are time-invariant.