Capacitated lot sizing problem with periodic carbon emission constraints and multiple resources

Abstract

We study the single item capacitated lot sizing problem with multiple resources and periodic carbon emission constraints that impose an upper bound for the average emission per product produced in any period. Although the uncapacitated version of this problem can be solved in polynomial time, generalisation of the problem including the resource capacities is NP-Hard, in general. We present important structural properties for the optimal solutions of the problem. We consider the special cases with two resources and under non-speculative costs, construct the piecewise linear total production cost function when the resource capacities, and the emission and cost parameters are time-invariant, and develop a polynomial time dynamic programming algorithm (DP) to solve them. Then, we generalise the procedure to construct the total production cost function and the DP for the general setting with fixed number of capacitated resources. We test our algorithm for different problem instances, and compare it with a commercial solver and a DP available in the literature for solving the lot sizing problem with piecewise concave production cost functions. The results reveal that our DP outperforms the other one, and it performs better than the commercial solver when the number of breakpoints of the total production cost function is small.

Keywords:

• Production planning
• multi-resource capacitated lot sizing
• periodic carbon emission constraints
• complexity analysis
• dynamic programming

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

Data used in computational experiments are publicly available at https://research.sabanciuniv.edu/id/eprint/45402/1/KocaKoksalan2023-DATA.txt.

Additional information

Funding

Both authors acknowledge the support from Türkiye Bilimsel ve Teknolojik Araştırma Kurumu (TUBITAK) [grant number 218M782].

Notes on contributors

Esra Koca

Esra Koca is a faculty member in the Industrial Engineering Program at Sabancı University, Turkey. She received her Ph.D degree in Industrial Engineering from Bilkent University, Turkey, in 2015. Her research interests include development of effective solution methods for deterministic and stochastic optimisation problems, especially in production and distribution systems.

G. Irmak Koksalan

Güniz Irmak Köksalan is an industrial engineer currently working as a Senior Supply Chain Consultant at ICRON Technologies, a recognised Gartner Magic Quadrant Vendor. She completed her MSc degree in Industrial Engineering at Sabancı University, Turkey, in 2022. She specialises in supply chain operations management, with a particular focus on production planning, detailed scheduling, and blending optimisation. She is driven by a passion for solving intricate problems and is committed to advancing the field through ongoing research and practical applications.