MIP-Heuristics for the Capacitated Lot-Sizing with Hybrid Flow Shop Integration
Resumo
Este artigo propõe uma abordagem em duas fases para resolver o problema integrado de lot-sizing capacitado (CLSP) com flow shop híbrido (HFS). Constrói-se uma solução inicial explorando três heurísticas: relax-and-fix, LP-and-fix e gulosa. Em seguida, aprimora-se a solução inicial usando a heurística fix-and-optimize, que decompõe o MIP original em subproblemas menores, um por período. Experimentos numéricos mostram que combinar uma heurística gulosa com fix-and-optimize pode superar as alternativas, obtendo gaps menores para a maioria dos casos, mesmo para instâncias de grande porte.
Referências
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.
Publicado
06/08/2023
Como Citar
SILVA, Diego Mello da; MATEUS, Geraldo Robson.
MIP-Heuristics for the Capacitated Lot-Sizing with Hybrid Flow Shop Integration. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (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.
