Abstract
This paper considers the capacitated multi-level lot-sizing problem with setup times, a class of difficult problems often faced in practical production planning settings. In the literature, relax-and-fix is a technique commonly applied to solve this problem due to the fact that setup decisions in later periods of the planning horizon are sensitive to setup decisions in the early periods but not vice versa. However, the weakness of this method is that setup decisions are optimized only on a small subset of periods in each iteration, and setup decisions fixed in early iterations might adversely affect setup decisions in later periods. In order to avoid these weaknesses, this paper proposes an extended relax-and-fix based heuristic that systematically uses domain knowledge derived from several strategies of relax-and-fix and a linear programming relaxation technique. Computational results show that the proposed heuristic is superior to other well-known approaches on solution qualities, in particular on hard test instances.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Absi, N., & Kedad-Sidhoum, S. (2007). MIP-based heuristics for multi-item capacitated lot-sizing problem with setup times and shortage costs. RAIRO. Recherche Opérationnelle, 41(2), 171–192.
Akartunalı, K., & Miller, A. J. (2009). A heuristic approach for big bucket multi-level production planning problems. European Journal of Operational Research, 193(2), 396–411.
Almada-Lobo, B., & James, R. J. W. (2010). Neighbourhood search meta-heuristics for capacitated lot-sizing with sequence-dependent setups. International Journal of Production Research, 48(3), 861–878.
Barany, I., Van Roy, T. J., & Wolsey, L. A. (1984). Uncapacitated lot sizing: The convex hull of solutions. Mathematical Programming Studies, 43(10), 22–32.
Belvaux, G., & Wolsey, L. A. (2000). Bc-prod: A specialized branch-and-cut system for lot-sizing problems. Management Science, 46(5), 724–738.
Billington, P., McClain, J., & Thomas, L. (1983). Mathematical programming approaches to capacity-constrained MRP systems: Review, formulation and problem reduction. Management Science, 29(10), 1126–1141.
Hung, Y. F., Chen, C. P., Shih, C. C., & Hung, M. H. (2003). Using tabu search with ranking candidate list to solve production planning problems with setups. Computers & Industrial Engineering, 45(4), 615–634.
Krarup, J., & Bilde, O. (1977). Plant location, set covering and economic lot sizes: An O(mn) algorithm for structured problems. In Optimierung bei Graphentheoretischen und Ganzzahligen Probleme (pp. 155–180). Basel: Birkhäuser.
Kuik, R., & Salomon, M. (1990). Multi-level lot-sizing problem: Evaluation of a simulated annealing heuristic. European Journal of Operational Research, 45, 25–37.
Mercé, C., & Fontan, G. (2003). Mip-based heuristics for capacitated lotsizing problems. International Journal of Production Economics, 85(1), 97–111.
Millar, H. H., & Yang, M. Z. (1994). Lagrangian heuristics for the capacitated multiitem lot-sizing problem with backordering. International Journal of Production Economics, 34(1), 1–15.
Ozdamar, L., & Bozyel, M. A. (2000). The capacitated lot sizing problem with overtime decisions and setup times. IIE Transactions, 32(11), 1043–1057.
Sahling, F., Buschkuhl, L., Tempelmeier, H., & Helber, S. (2009). Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic. Computers & Operations Research, 36(9), 2546–2553.
Stadtler, H. (2003). Multilevel lot sizing with setup times and multiple constrained resources: Internally rolling schedules with lot-sizing windows. Operations Research, 51(3), 487–502.
Suerie, C., & Stadtler, H. (2003). The capacitated lot-sizing with linked lot sizes. Management Science, 49(8), 1039–1054.
Tempelmeier, H., & Buschkuhl, L. (2009). A heuristic for the dynamic multi-level capacitated lotsizing problem with linked lotsizes for general product structures. OR-Spectrum, 31(2), 385–404.
Tempelmeier, H., & Derstroff, M. (1996). A Lagrangian-based heuristic for dynamic multilevel multiitem constrained lotsizing with setup times. Management Science, 42(5), 738–757.
Wu, T., & Shi, L. (2011). Mathematical models for capacitated multi-level production planning problems with linked lot sizes. International Journal of Production Research, 49(20), 6227–6247.
Wu, T., Shi, L., Akartunalı, K., & Geunes, J. (2011). An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging. European Journal of Operational Research, 214(2), 428–441.
Wu, T., Shi, L., & Duffie, N. A. (2010). An HNP-MP approach for the capacitated multi-item lot sizing problem with setup times. IEEE Transactions on Automation Science and Engineering, 7(3), 500–511.
Acknowledgements
This research was supported in part by the National Science Foundation under grant CMMI-00646697, and by the Air Force of Scientific Research under grant FA9550-07-1-0390. The authors are also thankful to two anonymous referees for their suggestions improving the presentation of the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wu, T., Shi, L. & Song, J. An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times. Ann Oper Res 196, 635–650 (2012). https://doi.org/10.1007/s10479-011-1026-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-011-1026-9