An improved heuristic for the Capacitated Lot-Sizing problem. (2nd December 2009)

• Record Type: Journal Article
• Authors: Madan, Manu S.; Cheng, C.H.; Yip, Eric; Motwani, Jaideep
• Is Part Of: International journal of operational research. Volume 7:Number 1(2010)
• Page Start: 90
• Page End: 108
• Publication Date: 2009-12-02
• Subjects: heuristics -- capacitated lot sizing -- production planning -- mixed integer programming -- fixed charge transportation; Operations research -- Periodicals; 003.05
• Languages: English
• ISSNs: 1745-7645

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.