Um algoritmo populacional para o problema de flow shop com bloqueio e minimização do makespan

  • Ewerton Teixeira UFPB
  • Anand Subramanian UFPB
  • Hugo Harry Kramer UFPB

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.
Publicado
06/08/2023
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.