MIP-Heuristics for the Capacitated Lot-Sizing with Hybrid Flow Shop Integration
Abstract
This paper proposes a two-phase approach to integrating the capacitated lot-sizing (CLSP) and hybrid flow shop (HFS). First, we construct an initial solution exploring three heuristics: relax-and-fix, LP-and-fix, and greedy. Next, we try to improve the initial solution through a fix-and-optimize heuristic that decomposes the original MIP per period. Numerical experiments show that combining the greedy heuristic with fix-and-optimize can overcome the alternatives, obtaining small gaps for most cases, even for large-size instances.
References
Araujo, K., Birgin, E., Kawamura, M., and Ronconi, D. (2021). Relax-and-fix heuristics applied to a real-world lot-sizing and scheduling problem in the personal care consumer goods industry. arXiv preprint arXiv:2107.10738.
Bitran, G. R. and Yanasse, H. H. (1982). Computational complexity of the capacitated lot size problem. Management Science, 28(10):1174–1186.
Helber, S. and Sahling, F. (2010). A fix-and-optimize approach for the multi-level capacitated lot sizing problem. International Journal of Production Economics, 123(2):247–256.
James, R. J. and Almada-Lobo, B. (2011). Single and parallel machine capacitated lotsizing and scheduling: New iterative mip-based neighborhood search heuristics. Computers & Operations Research, 38(12):1816–1825.
Lang, J. C. and Shen, Z.-J. M. (2011). Fix-and-optimize heuristics for capacitated lotsizing with sequence-dependent setups and substitutions. European Journal of Operational Research, 214(3):595–605.
Masmoudi, O., Yalaoui, A., Ouazene, Y., and Chehade, H. (2016). Multi-item capacitated lot-sizing problem in a flow-shop system with energy consideration. IFAC-PapersOnLine, 49(12):301–306.
Michael, L. P. (2008). Scheduling: Theory, Algorithms, and Systems. Springer.
Mohammadi, M. and Fatemi, G. S. (2010). Relax and fix heuristics for simultaneous lot sizing and sequencing the permutation flow shops with sequence-dependent setups. Int. Journal of Industrial Engineering and Production Research, 21(3):147–153.
Pochet, Y. and Wolsey, L. A. (2006). Production planning by mixed integer programming. Springer Science & Business Media.
Qin, W., Zhuang, Z., Liu, Y., and Tang, O. (2019). A two-stage ant colony algorithm for hybrid flow shop scheduling with lot sizing and calendar constraints in printed circuit board assembly. Computers & Industrial Engineering, 138:106115.
Ramezanian, R., Saidi-Mehrabad, M., and Fattahi, P. (2013). Mip formulation and heuristics for multi-stage capacitated lot-sizing and scheduling problem with availability constraints. Journal of Manufacturing Systems, 32(2):392–401.
Rodoplu, M., Arbaoui, T., and Yalaoui, A. (2020). A fix-and-relax heuristic for the single-item lot-sizing problem with a flow-shop system and energy constraints. International Journal of Production Research, 58(21):6532–6552.
Ruiz, R. and Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European journal of operational research, 205(1):1–18.
Sahling, F., Buschkühl, L., Tempelmeier, H., and 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.
Schimidt, T. M. P., Tadeu, S. C., Loch, G. V., and Schenekemberg, C. M. (2019). Heuristic approaches to solve a two-stage lot sizing and scheduling problem. IEEE Latin America Transactions, 17(03):434–443.
Silva, D. M. and Mateus, G. R. (2022). Formulações de precedência e fluxo em redes para o problema integrado de lot-sizing capacitado com hybrid flow shop. In Anais do LIV Simpósio Brasileiro de Pesquisa Operacional, Juiz de Fora. Galoá.
Silva, D. M. and Mateus, G. R. (2023). A mixed-integer programming formulation and heuristics for an integrated production planning and scheduling problem. In Di Gaspero, L., Festa, P., Nakib, A., and Pavone, M., editors, Metaheuristics, pages 290–305, Cham. Springer International Publishing.
Toledo, C. F. M., da Silva Arantes, M., Hossomi, M. Y. B., França, P. M., and Akartunalı, K. (2015). A relax-and-fix with fix-and-optimize heuristic applied to multi-level lotsizing problems. Journal of Heuristics, 21(5):687–717.
Bitran, G. R. and Yanasse, H. H. (1982). Computational complexity of the capacitated lot size problem. Management Science, 28(10):1174–1186.
Helber, S. and Sahling, F. (2010). A fix-and-optimize approach for the multi-level capacitated lot sizing problem. International Journal of Production Economics, 123(2):247–256.
James, R. J. and Almada-Lobo, B. (2011). Single and parallel machine capacitated lotsizing and scheduling: New iterative mip-based neighborhood search heuristics. Computers & Operations Research, 38(12):1816–1825.
Lang, J. C. and Shen, Z.-J. M. (2011). Fix-and-optimize heuristics for capacitated lotsizing with sequence-dependent setups and substitutions. European Journal of Operational Research, 214(3):595–605.
Masmoudi, O., Yalaoui, A., Ouazene, Y., and Chehade, H. (2016). Multi-item capacitated lot-sizing problem in a flow-shop system with energy consideration. IFAC-PapersOnLine, 49(12):301–306.
Michael, L. P. (2008). Scheduling: Theory, Algorithms, and Systems. Springer.
Mohammadi, M. and Fatemi, G. S. (2010). Relax and fix heuristics for simultaneous lot sizing and sequencing the permutation flow shops with sequence-dependent setups. Int. Journal of Industrial Engineering and Production Research, 21(3):147–153.
Pochet, Y. and Wolsey, L. A. (2006). Production planning by mixed integer programming. Springer Science & Business Media.
Qin, W., Zhuang, Z., Liu, Y., and Tang, O. (2019). A two-stage ant colony algorithm for hybrid flow shop scheduling with lot sizing and calendar constraints in printed circuit board assembly. Computers & Industrial Engineering, 138:106115.
Ramezanian, R., Saidi-Mehrabad, M., and Fattahi, P. (2013). Mip formulation and heuristics for multi-stage capacitated lot-sizing and scheduling problem with availability constraints. Journal of Manufacturing Systems, 32(2):392–401.
Rodoplu, M., Arbaoui, T., and Yalaoui, A. (2020). A fix-and-relax heuristic for the single-item lot-sizing problem with a flow-shop system and energy constraints. International Journal of Production Research, 58(21):6532–6552.
Ruiz, R. and Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European journal of operational research, 205(1):1–18.
Sahling, F., Buschkühl, L., Tempelmeier, H., and 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.
Schimidt, T. M. P., Tadeu, S. C., Loch, G. V., and Schenekemberg, C. M. (2019). Heuristic approaches to solve a two-stage lot sizing and scheduling problem. IEEE Latin America Transactions, 17(03):434–443.
Silva, D. M. and Mateus, G. R. (2022). Formulações de precedência e fluxo em redes para o problema integrado de lot-sizing capacitado com hybrid flow shop. In Anais do LIV Simpósio Brasileiro de Pesquisa Operacional, Juiz de Fora. Galoá.
Silva, D. M. and Mateus, G. R. (2023). A mixed-integer programming formulation and heuristics for an integrated production planning and scheduling problem. In Di Gaspero, L., Festa, P., Nakib, A., and Pavone, M., editors, Metaheuristics, pages 290–305, Cham. Springer International Publishing.
Toledo, C. F. M., da Silva Arantes, M., Hossomi, M. Y. B., França, P. M., and Akartunalı, K. (2015). A relax-and-fix with fix-and-optimize heuristic applied to multi-level lotsizing problems. Journal of Heuristics, 21(5):687–717.
Published
2023-08-06
How to Cite
SILVA, Diego Mello da; MATEUS, Geraldo Robson.
MIP-Heuristics for the Capacitated Lot-Sizing with Hybrid Flow Shop Integration. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 165-169.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230613.
