Algoritmo Genético Adaptativo com Chaves Aleatórias Viciadas para um Problema de Corte de Estoque Multi-Período com Custos de Setup
DOI:
https://doi.org/10.5540/03.2023.010.01.0017Keywords:
Problema de Corte de Estoque Unidimensional, Custo de Setup nos Padrões de Corte, MetaheurísticaAbstract
Este trabalho apresenta um Algoritmo Genético Adaptativo com Chaves Aleatórias Vici- adas (AGACAV) para resolver o problema de Corte de Estoque Multi-período com custos de setup nos padrões de corte. Uma aplicação determinística chamada decoder que mapeia soluções factíveis do problema é necessária para a inicialização do AGACAV. Um decoder baseado na geração de estoque por período e construção de padrões de corte é proposto e comparado com um procedimento de geração de colunas. Os métodos foram comparados em instâncias com diferentes tamanhos de itens e o resultados mostram que o AGACAV obtém melhores resultados para instâncias cujo custo de setup é maior que o custo dos objetos em estoque.
Downloads
References
J. C. Bean. “Genetic Algorithms and Random Keys for Sequencing and Optimization”. Em: ORSA Journal on Computing 6.2 (1994), pp. 154–160. doi: 10.1287/ijoc.6.2.154.
H. Ben Amor e J. M. Valério de Carvalho. “Cutting Stock Problems”. English. Em: Column Generation. Ed. por G. Desaulniers, J. Desrosiers e M. M. Solomon. Springer US, 2005, pp. 131–161.
A. Chaves, J. F. Gonçalves e L. Lorena. “Adaptive Biased Random-key Genetic Algorithm with Local Search for the Capacitated Centered Clustering Problem”. Em: Computers & Industrial Engineering 124 (jul. de 2018), pp. 331–346. doi: 10.1016/j.cie.2018.07. 031.
Antônio Augusto Chaves e L. H. N Lorena. An adaptive and near parameter-free BRKGA using Reinforcement Learning. Rel. técn. Universidade Federal de São Paulo (UNIFESP), 2021.
P. C. Gilmore e R. E. Gomory. “A Linear Programming Approach to the Cutting Stock Problema - Part II”. Em: Operations Research 11.6 (1963), pp. 863–888.
P. C. Gilmore e R. E. Gomory. “A Linear Programming Approach to the Cutting-Stock Problem”. Em: Operations Research 9.6 (1961), pp. 849–859.
J. F. Gonçalves e M. G. C. Resende. “Random-key genetic algorithms”. Em: Handbook of heuristics (2016), pp. 1–13.
J. F. Gonçalves e M.G.C. Resende. “Biased random-key genetic algorithms for combinatorial optimization”. Em: J Heuristics 17 (2011), pp. 487–525. doi: 10.1007/s10732-010-9143-1.
José Fernando Gonçalves e Mauricio G.C. Resende. “A biased random key genetic algorithm for 2D and 3D bin packing problems”. Em: International Journal of Production Economics 145.2 (2013), pp. 500–510. issn: 0925-5273. doi: https://doi.org/10.1016/j.ijpe.2013.04.019. url: https://www.sciencedirect.com/scienc/article/pii/S0925527313001837.
C. McDiarmid. “Pattern minimisation in cutting stock problems”. Em: Discrete Applied Mathematics 98.1-2 (1999), pp. 121–130.
G. M. Melega, de Araujo, S. A. e Jans, R. “Classification and literature review of integrated lot-sizing and cutting stock problems”. Em: European Journal of Operational Research 271.1 (2018), pp. 1–19.
K. C. Poldi e S. A. de Araujo. “Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem”. Em: Annals of Operations Research 238.1 (2016), pp. 497–520.
Eduardo M. Silva et al. “Formulations and theoretical analysis of the one-dimensional multiperiod cutting stock problem with setup cost”. Em: European Journal of Operational Research 304.2 (2023), pp. 443–460. issn: 0377-2217. doi: https://doi.org/10.1016/j.ejor.2022.04.023. url: https://www.sciencedirect.com/science/article/pii/S0377221722003344.
D. A. Wuttke e S. H. Heese. “Two-dimensional cutting stock problem with sequence dependent setup times”. Em: European Journal of Operational Research 265.1 (2018), pp. 303–315.
