An algorithm using Lagrangean relaxation and decomposition for solving a capacitated lot-sizing problem (Q961468)

Summary: We formulate and solve a type of the capacitated lot-sizing (CLS) problem. This problem is commonly found in many manufacturing settings. Unlike a typical formulation, our formulation explicitly considers different types of production capacities such as regular time and overtime. We develop a heuristic based on Lagrangean relaxation with a decomposition scheme to solve this CLS problem. Computational results show that our algorithm gives very good results while comparing to lower bounds.