Title: An algorithm using Lagrangean relaxation and decomposition for solving a capacitated lot-sizing problem

Authors: Chun-Hung Cheng, Manohar S. Madan, Angappa Gunasekaran, Ka-Yun Yip

Addresses: Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, NT, Hong Kong SAR, China. ' Department of Management, University of Wisconsin – Whitewater, Whitewater, WI 53190, USA. ' Department of Decision and Information Sciences, University of Massachusetts Dartmouth, North Dartmouth, MA 02747, USA. ' Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, NT, Hong Kong SAR, China

Abstract: In this research, 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.

Keywords: production planning; capacitated lot-sizing; CLS problem; Lagrangean relaxation; decomposition schemes; sub-gradient optimisation; manufacturing industry.

DOI: 10.1504/IJMOR.2010.030817

International Journal of Mathematics in Operational Research, 2010 Vol.2 No.2, pp.205 - 232

Published online: 07 Jan 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article