A novel mixed integer programming formulation and progressively stochastic search for capacitated lot sizing

Abstract

The capacitated multi-level lot sizing problem is to schedule a number of different items with a bill-of-materials structure over a horizon of finite periods. To advance techniques of solving this class of problems, this paper proposes a new mixed integer programming formulation. Theoretical proofs and computational tests are provided to show that this formulation is able to provide better linear programming relaxation lower bounds than a previously-proposed strong mixed integer programming formulation. Based on the new strong formulation, a progressively stochastic search approach is proposed for solving the problem. Computational results showed that the approach generates high quality solutions, especially for problems of large sizes.

Keywords

Capacitated / multi-level / lot sizing / optimization / mixed integer programming / facility location

References

[1] Absi N., Kedad-Sidhoum S.. The multi-item capacitated lot-sizing problem with setup times and shortagecosts. European Journal of Operational Research, 2008, 185(3): 1351-1374.

[2] Akartunali K., Miller A.J.. A heuristic approach for big bucket multi-level production planning problems. European Journal of Operational Research, 2009, 193(2): 396-411.

[3] Barany I., Van Roy T.J., Wolsey L.A.. Strong formulations for multi-item capacitated lot-sizing. Management Science, 1984, 30(10): 1255-1261.

[4] Belvaux G., Wolsey L.A.. Bc-prod: a specialized branch-and-cut system for lot-sizing problems. Management Science, 2000, 46(5): 724-738.

[5] Billington P., McClain J., Thomas L.. Mathematical programming approaches to capacity-constrained MRP systems: review, formulation and problem reduction. Management Science, 1983, 29(10): 1126-1141.

[6] Briskorn D.. A note on capacitated lot sizing with setup carry over. IIE Transactions, 2006, 38(11): 1045-1047.

[7] Denizel M., Altekin F.T., Sural H., Stadtler H.. Equivalence of the LP relaxations of two strong formulations for the capacitated lot-sizing problem with setup times. OR Spectrum, 2008, 30(4): 773-785.

[8] Eppen G.D., Martin R.K.. Solving multi-item capacitated lot-sizing problems using variable redefinition. Operations Research, 1987, 35(6): 832-848.

[9] Florian M., Lenstra J.K., Rinnooy Kan H.G.. Deterministic production planning: algorithms and complexity. Management Science, 1980, 26(7): 669-679.

[10] Kovacs A., Brown K., Tarim S.A.. An efficient MIP model for the capacitated lot-sizing and scheduling problem with sequence-dependent setups. International Journal of Production Economics, 2009, 118(1): 282-291.

[11] Krarup J., Bilde O.. Plant location, set covering and economic lot sizes: an O(m ⁿ) algorithm for structured problems, 1977, Basel, Switzerland: Optimierung bei Graphentheoretischen und Ganzzahligen Probleme Birkhauser Verlag 155-180.

[12] Millar H.H., Yang M.Z.. Lagrangian heuristics for the capacitated multiitem lot-sizing problem with backo-rdering. International Journal of Production Economics, 1994, 34(1): 1-15.

[13] Miller A.J., Wolsey L.A.. Tight MIP formulations for multi-item discrete lot-sizing problems. Operations Research, 2003, 51(4): 557-565.

[14] Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. John Wiley & Sons, Inc.

[15] Pochet Y., Wolsey L.A.. Lot-size models with backlogging: Strong reformulations and cutting planes. Mathe-matical Programming, 1988, 40(3): 317-335.

[16] Pochet Y., Wolsey L.A.. Solving multi-item lot-sizing problems using strong cutting planes. Management Science, 1991, 37(1): 53-67.

[17] Sahling F., Buschkuhl L., Tempelmeier H., Helber S.. Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic. Computers & Operations Research, 2009, 36(9): 2546-2553.

[18] Salomon, M. (1991). Deterministic Lot Sizing Models for Production Planning. Spinger, Inc.

[19] Simpson N.C., Erenguc S.S.. Modeling multiple stage manufacturing systems with generalized costs and capacity issues. Naval Research Logistics, 2005, 52(6): 560-570.

[20] Sox C.R., Gao Y.B.. The capacitated lot sizing problem with setup carry-over. IIE Transactions, 1999, 31(2): 173-181.

[21] Stadtler H.. Multilevel lot sizing with setup times and multiple constrained resources: internally rolling schedules with lot-sizing windows. Operations Research, 2003, 51(3): 487-502.

[22] Tempelmeier H., Derstroff M.. A Lagrangian-based heuristic for dynamic multilevel multiitem constrained lotsizing with setup times. Management Science, 1996, 42(5): 738-757.

[23] Trigeiro W., Thomas L.J., John O.M.. Capacitated lot sizing with setup times. Management Science, 1989, 35(3): 353-366.

[24] Wu, T. Shi, L., (2009), Hybrid nested partitions and relax-and-fix approach for capacitated multi-item lot sizing problem. Proceedings of 2009 IEEE/INFORMS International Conference on Service Operations, Logistics and Informatics, 359–364.

[25] Wu, T., Shi, L. (2009), A new heuristic method for capacitated multi-level lot sizing problem with backlogging. Proceedings of the Fifth Annual IEEE International Conference on Automation Science and Engineering, 483–488.

[26] Wu T., Shi L., Duffie N.A.. An HNP-MP approach for the capacitated multi-item lot sizing problem with setup times. IEEE Transactions on Automation Science and Engineering, 2010, 7(3): 500-511.

[27] Wu, T. & Shi, L. (2011). Mathematical models for capacitated multi-level production planning problems with linked lot sizes. International Journal of Production Research, published online