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

Mayank Verma^*, Renduchintala Raghavendra Kumar Sharma

Department of Industrial and Management Engineering, Indian Institute of Technology Kanpur, Kanpur, India.

DOI: 10.4236/ajor.2015.56039                

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.

Keywords

Capacitated Lot Sizing, Linear Relaxation, Strong Formulation, Hybrid Formulation, Branch-and-Bound

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Florian, M., Lenstra, J.K. and Rinnooy Kan, A.G. (1980) Deterministic Production Planning Algorithms and Complexity. Management Science, 26, 669-679. http://dx.doi.org/10.1287/mnsc.26.7.669
[2]	Maes, J., McClain, J.O. and Van Wassenhove, L.N. (1991) Multilevel Capacitated Lotsizing Complexity and LP-Based Heuristics. European Journal of Operation Research, 53, 131-148. http://dx.doi.org/10.1016/0377-2217(91)90130-N
[3]	Chen, W.H. and Thizy, J.M. (1990) Analysis of Relexations for the Multi-Item Capacitated Lot-Sizing Problem. Annals of Operations Research, 26, 29-72. http://dx.doi.org/10.1007/BF02248584
[4]	Karimi, B., Fatemi Ghomi, S.M.T. and Wilson, J.M. (2003) The Capacitated Lot Sizing Problem: A Review of Models and Algorithms. Omega, 31, 365-378. http://dx.doi.org/10.1016/S0305-0483(03)00059-8
[5]	Quadt, D. and Kuhn, H. (2008) Capacitated Lot-Sizing with Extensions: A Review. 4OR, 6, 61-83. http://dx.doi.org/10.1007/s10288-007-0057-1
[6]	Kim, S.I., Han, J., Lee, Y. and Park, E. (2010) Decomposition Based Heuristic Algorithm for Lot-Sizing and Scheduling Problem Treating Time Horizon as a Continuum. Computers & Operations Research, 37, 302-314. http://dx.doi.org/10.1016/j.cor.2009.05.007
[7]	Melo, R.A. and Wolsey, L.A. (2010) Uncapacitated Two-Level Lot-Sizing. Operations Research Letters, 38, 241-245. http://dx.doi.org/10.1016/j.orl.2010.04.001
[8]	Akbalik, A. and Penz, B. (2009) Exact Methods for Single-Item Capacitated Lotsizing Problem with Alternative Machines and Piece-Wise Linear Production Costs. International Journal of Production Economics, 119, 367-379. http://dx.doi.org/10.1016/j.ijpe.2009.03.010
[9]	Manne, A.S. (1958) Programming of Economic Lot Sizes. Management Science, 4, 115-135. http://dx.doi.org/10.1287/mnsc.4.2.115
[10]	Alfieri, A., Brandimarte, P. and D’Orazio, S. (2002) LP-Based Heuristics for the Capacitated Lot-Sizing Problem: The Interaction of Model Formulation and Solution Algorithm. International Journal of Production Research, 40, 441-458. http://dx.doi.org/10.1080/00207540110081461
[11]	Pochet, Y. and Wolsey, L.A. (1988) Lot-Size Models with Backlogging: Strong Reformulations and Cutting Planes. Mathematical Programming, 40, 317-335. http://dx.doi.org/10.1007/BF01580738
[12]	Denizel, M., Altekin, F.T., Sural, H. and Stadtler, H. (2008) Equivalence of the LP Relaxations of Two Strong Formulations for the Capacitated Lot-Sizing Problem with Setup Times. OR Spectrum, 30, 773-785. http://dx.doi.org/10.1007/s00291-007-0094-3
[13]	Barany, I., Van Roy, T.J. and Wolsey, L.A. (1984) Strong Formulations for Multi-Item Capacitated Lot Sizing. Management Science, 30, 1255-1261. http://dx.doi.org/10.1287/mnsc.30.10.1255
[14]	Van Vyve, M. and Wolsey, L.A. (2006) Approximate Extended Formulations. Mathematical Programming, 105, 501-522. http://dx.doi.org/10.1007/s10107-005-0663-7
[15]	Pochet, Y. and Wolsey, L.A. (2006) Production Planning by Mixed Integer Programming. Springer.
[16]	Akartunali, K. and Miller, A.J. (2009) A Heuristic Approach for Big Bucket Multi-Level Production Planning Problems. European Journal of Operational Research, 193, 396-411. http://dx.doi.org/10.1016/j.ejor.2007.11.033
[17]	Conforti, M., Cornuéjols, G. and Zambelli, G. (2010) Extended Formulations in Combinatorial Optimization. 4OR, 8, 1-48. http://dx.doi.org/10.1007/s10288-010-0122-z
[18]	Trigeiro, W.W., Thomas, L.J. and McClain, J.O. (1989) Capacitated Lot Sizing with Setup Times. Management Science, 35, 353-366. http://dx.doi.org/10.1287/mnsc.35.3.353
[19]	Ozdamar, L. and Barbarosoglu, G. (1999) Hybrid Heuristics for the Multi-Stage Capacitated Lot Sizing and Loading Problem. Journal of the Operational Research Society, 50, 810-825. http://dx.doi.org/10.1057/palgrave.jors.2600773
[20]	Küçükyavuz, S. and Pochet, Y. (2009) Uncapacitated Lot Sizing with Backlogging: The Convex Hull. Mathematical Programming, 118, 151-175. http://dx.doi.org/10.1007/s10107-007-0186-5