Title: An improved heuristic for the Capacitated Lot-Sizing problem

Authors: Manu S. Madan, C.H. Cheng, Eric Yip, Jaideep Motwani

Addresses: Management Department, University of Wisconsin Whitewater, Whitewater, WI 53190, USA. ' Department of Systems Engineering and Engineering Management, Chinese University of Hong Kong, Shatin, NT, Hong Kong SAR, China. ' Department of Systems Engineering and Engineering Management, Chinese University of Hong Kong, Shatin, NT, Hong Kong SAR, China. ' Department of Management, Grand Valley State University, 401 W. Fulton, Grand Rapids, MI 49504, USA

Abstract: In this research, we present a heuristic for the Capacitated Lot-Sizing (CLS) problem without set-up time considerations and no backordering option. The CLS problem is formulated as a mixed integer-programming problem with an underlying fixed charge transportation problem structure. This formulation is flexible enough to handle different types of production capacity such as regular time capacity, overtime capacity and subcontracting. A heuristic that exploits the fixed charge transportation structure and trade-offs involved in lot-sizing decisions is developed for the problem. We also present a new Lower Bound Procedure for the multi-item CLS problems. We demonstrate the performance of the heuristic over a variety of test problems. The heuristic is evaluated by comparing the solution values to the lower bound values as well as to the solution values from another algorithm for similar problems.

Keywords: heuristics; capacitated lot sizing; production planning; mixed integer programming; fixed charge transportation.

DOI: 10.1504/IJOR.2010.029519

International Journal of Operational Research, 2010 Vol.7 No.1, pp.90 - 108

Published online: 30 Nov 2009 *

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