Title: A Lagrangean relaxation approach for capacitated lot sizing problem with setup times

Authors: Chun-Hung Cheng; Manohar S. Madan; Jaideep Motwani; Ka-Yun Yip

Addresses: Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Room 607 William Mong, Engineering Building, Shatin, NT, Hong Kong ' Management Department, University of Wisconsin-Whitewater, Whitewater, WI 53190, USA ' Department of Management, Seidman College of Business, Grand Valley State University, 301 West Fulton, Suite 409C, Grand Rapids, MI 49504, USA ' Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Room 607 William Mong, Engineering Building, Shatin, NT, Hong Kong

Abstract: In this research, we consider a production planning problem that determines the production timings and quantities for multiple products over a finite number of periods without violating capacity constraints. This problem is commonly referred to as the capacitated lot sizing (CLS) problem. We develop a model that explicitly considers setup times for products and different types of production capacities such as regular time and overtime. We develop a heuristic based on Lagrangian relaxation to solve this CLS problem. Computational results show that our algorithm gives reliable results while comparing solution values to lower bounds.

Keywords: production planning; capacitated lot sizing; setup times; Lagrangean relaxation; production capacities.

DOI: 10.1504/IJOR.2013.056686

International Journal of Operational Research, 2013 Vol.18 No.3, pp.272 - 303

Published online: 29 Jul 2014 *

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