Um algoritmo populacional para o problema de flow shop com bloqueio e minimização do makespan
Resumo
Este trabalho aborda o problema de flow shop com bloqueio para minimização do makespan. Um algoritmo populacional que utiliza um operador ruin-and-recreate juntamente de uma busca local baseada em Variable Neighbourhood Descent é proposto para o problema. Experimentos computacionais foram realizados em 120 instâncias de benchmark e o método proposto foi capaz de obter soluções competitivas quando comparadas com a literatura.Referências
Fernandez-Viagas, V., Leisten, R., and Framinan, J. M. (2016). A computational evaluation of constructive and improvement heuristics for the blocking flow shop to minimise total flowtime. Expert Systems with Applications, 61:290–301.
Graham, R. L., Lawler, E. L., Lenstra, J. K., and Kan, A. (1979). Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. In Discrete Optimization II, volume 5 of Annals of Discrete Mathematics, pages 287–326. Elsevier.
Martinez, S., Dauzère-Pérès, S., Gueret, C., Mati, Y., and Sauer, N. (2006). Complexity of flowshop scheduling problems with a new blocking constraint. European Journal of Operational Research, 169(3):855–864.
Mecler, J., Subramanian, A., and Vidal, T. (2021). A simple and effective hybrid genetic search for the job sequencing and tool switching problem. Computers & Operations Research, 127:105153.
Pan, Q.-K. and Wang, L. (2012). Effective heuristics for the blocking flowshop scheduling problem with makespan minimization. Omega, 40(2):218–229.
Röck, H. (1984). Some new results in flow shop scheduling. Zeitschrift für Operations Research, 28(1):1–16.
Ruiz, R. and Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European journal of operational research, 177(3):2033–2049.
Shao, Z., Pi, D., Shao, W., and Yuan, P. (2019). An efficient discrete invasive weed optimization for blocking flow-shop scheduling problem. Engineering Applications of Artificial Intelligence, 78:124–141.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285.
Teixeira, E. V. P. d. P., Subramanian, A., and Kramer, H. H. (2022). Uma heurística para o problema de flow shop com bloqueio e minimização do makespan. In Anais do LIV Simpósio Brasileiro de Pesquisa Operacional, Juiz de Fora, November 8–11, 2022.
Graham, R. L., Lawler, E. L., Lenstra, J. K., and Kan, A. (1979). Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. In Discrete Optimization II, volume 5 of Annals of Discrete Mathematics, pages 287–326. Elsevier.
Martinez, S., Dauzère-Pérès, S., Gueret, C., Mati, Y., and Sauer, N. (2006). Complexity of flowshop scheduling problems with a new blocking constraint. European Journal of Operational Research, 169(3):855–864.
Mecler, J., Subramanian, A., and Vidal, T. (2021). A simple and effective hybrid genetic search for the job sequencing and tool switching problem. Computers & Operations Research, 127:105153.
Pan, Q.-K. and Wang, L. (2012). Effective heuristics for the blocking flowshop scheduling problem with makespan minimization. Omega, 40(2):218–229.
Röck, H. (1984). Some new results in flow shop scheduling. Zeitschrift für Operations Research, 28(1):1–16.
Ruiz, R. and Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European journal of operational research, 177(3):2033–2049.
Shao, Z., Pi, D., Shao, W., and Yuan, P. (2019). An efficient discrete invasive weed optimization for blocking flow-shop scheduling problem. Engineering Applications of Artificial Intelligence, 78:124–141.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285.
Teixeira, E. V. P. d. P., Subramanian, A., and Kramer, H. H. (2022). Uma heurística para o problema de flow shop com bloqueio e minimização do makespan. In Anais do LIV Simpósio Brasileiro de Pesquisa Operacional, Juiz de Fora, November 8–11, 2022.
Publicado
06/08/2023
Como Citar
TEIXEIRA, Ewerton; SUBRAMANIAN, Anand; KRAMER, Hugo Harry.
Um algoritmo populacional para o problema de flow shop com bloqueio e minimização do makespan. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 180-184.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230720.
