Hybrid Formulation of the Multi-Item Capacitated Dynamic Lot Sizing Problem

HTML  XML Download Download as PDF (Size: 296KB)  PP. 503-513  
DOI: 10.4236/ajor.2015.56039    3,765 Downloads   4,654 Views  

ABSTRACT

It is shown that when backorders, setup times and dynamic demand are included in capacitated lot sizing problem, the resulting classical formulation and one of the transportation formulations of the problem (referred to as CLSP_BS) are equivalent. And it is shown that both the formulations are “weak” formulations (as opposed to “strong” formulation). The other transportation version is a strong formulation of CLSP_BS. Extensive computational studies are presented for medium and large sized problems. In case of medium-sized problems, strong formulation produces better LP bounds, and takes lesser number of branch-and-bound (B&B) nodes and less CPU time to solve the problem optimally. However for large-sized problems strong formulation takes more time to solve the problem optimally, defeating the benefit of strength of bounds. This essentially is because of excessive increase in the number of constraints for the large sized problems. Hybrid formulations are proposed where only few most promising strong constraints are added to the weak formulation. Hybrid formulation emerges as the best performer against the strong and weak formulations. This concept of hybrid formulation can efficiently solve a variety of complex real life large-sized problems.

Share and Cite:

Verma, M. and Kumar Sharma, R. (2015) Hybrid Formulation of the Multi-Item Capacitated Dynamic Lot Sizing Problem. American Journal of Operations Research, 5, 503-513. doi: 10.4236/ajor.2015.56039.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.