An algorithm using Lagrangean relaxation and decomposition for solving a capacitated lot-sizing problem. (8th January 2010)

• Record Type: Journal Article
• Authors: Cheng, Chun-Hung; Madan, Manohar S.; Gunasekaran, Angappa; Yip, Ka-Yun
• Is Part Of: International journal of mathematics in operational research. Volume 2:Number 2(2010)
• Page Start: 205
• Page End: 232
• Publication Date: 2010-01-08
• Subjects: production planning -- capacitated lot-sizing -- CLS problem -- Lagrangean relaxation -- decomposition schemes -- sub-gradient optimisation -- manufacturing industry; Operations research -- Mathematical models -- Periodicals; Operations research -- Mathematics -- Periodicals; Decision making -- Mathematical models -- Periodicals; 658.4033
• Languages: English
• ISSNs: 1757-5850

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.