Um algoritmo híbrido busca tabu/ILS para o problema de sequenciamento da produção em ambiente open shop

Vitor Hugo Lopes Costa Lima; Bruno de Athayde Prata

doi:10.5585/exactaep.2021.11626

Autores

Vitor Hugo Lopes Costa Lima Universidade Federal do Ceará https://orcid.org/0000-0002-5447-9841
Bruno de Athayde Prata Universidade Federal do Ceará https://orcid.org/0000-0002-3920-089X

DOI:

https://doi.org/10.5585/exactaep.2021.11626

Palavras-chave:

Programação da produção, Meta-heurísticas, Otimização combinatória.

Resumo

O Open Shop Scheduling Problem (OSPP) é um ambiente no qual a produção é realizada por m máquinas, em que todas as máquinas podem realizar todas as n tarefas existentes e cada máquina possui um tempo específico para realizar cada tarefa. Tendo em vista que o OSSP é NP-hard, uma meta-heurística híbrida busca tabu/iterated local search (ILS) é proposta. Foram realizados testes computacionais em 140 instâncias disponíveis na literatura. Foram avaliadas as regras de prioridade LPT, SPT, LAPT e LTRPOM como algoritmos para construção de uma solução inicial. A função objetivo utilizada foi a minimização do makespan e o desvio percentual relativo foi a medida de desempenho adotada. Os resultados computacionais apontam para a competitividade da meta-heurística proposta nas instâncias avaliadas.

Downloads

Não há dados estatísticos.

Biografia do Autor

Vitor Hugo Lopes Costa Lima, Universidade Federal do Ceará

Estudante de Engneharia Mecânica na Universidade Federal do Ceará.

Bruno de Athayde Prata, Universidade Federal do Ceará

Graduado em Engenharia Civil pela Universidade Federal do Ceará (UFC), Fortaleza, Ceará, Brasil, em 2005. Obteve o título de mestre em Logística e Pesquisa Operacional pela UFC em 2007 e de Doutor, em Engenharia Industrial e Gestão pela Universidade do Porto (UP), Porto, Portugal, em 2011. É professor Adjunto do Departamento de Engenharia de Produção da UFC e líder do Grupo Pesquisa Operacional em Produção e Logística. Atualmente suas pesquisas se concentram em problemas de sequenciamento, com aplicações
em Logística e Gestão de Operações.

Referências

Abreu, L. R, Cunha, J. O., Prata, B. A., (2019). A genetic algorithm for scheduling open shops with sequence-dependent setup times. Computers and Operations Research. 113. DOI: https://doi.org/10.1016/j.cor.2019.104793

Anand, E., & Panneerselvam, R. (2015). Literature review of open shop scheduling problems. Intelligent Information Management, 7(1), 32-52. DOI: https://doi.org/10.4236/iim.2015.71004

Azadeh, A., Farahani, M. H., & Kalantari, S. S. (2015). Solving a multi-objective open shop problem for multi-processors under preventive maintenance. International Journal of Advanced Manufacturing Technology, 78(5-8), 707-722. DOI: https://doi.org/10.1007/s00170-014-6660-3

Bai, D., & Tang, L. (2013). Open shop scheduling problem to minimize makespan with release dates. Applied Mathematical Modeling, 37(4), 2008-2015. DOI: https://doi.org/10.1016/j.apm.2012.04.037

Bai, D., Zhang, Z. H., & Zhang, Q. (2016). Flexible open shop scheduling problem to minimize makespan. Computers & Operational Research, 67(1), 207-215. DOI: https://doi.org/10.1016/j.cor.2015.10.012

Cheng-, R., Gen, M., & Tsujimura, Y. (1996). A tutorial survey of job-shop scheduling problems using genetic algorithms-I. representation. Computers & Industrial Engineering, 30(4), 983-997. DOI: https://doi.org/10.1016/0360-8352(96)00047-2

Garey, M. R., & Johnson, D. S. (1974). Computers and intractability: a guide to the theory of np-completeness. New York: Freeman.

Glover, F., & Laguna, M. (1997). Tabu search. Norwell, MA: Kluwer Academic.

Gonzalez, T., & Sahni, S. (1976). Open-shop scheduling to minimize finish time. Journal of the Association for Computing Machinery, 23(4), 665-679. DOI: https://doi.org/10.1145/321978.321985

Hosseinabadi, A. A. R., Vahidi, J., Saemi, B., Sangaiah, A. K., & Elhoseny, M. (2019). Extended genetic algorithm for solving open-shop scheduling problem. Soft Computing, 23, 5099-5116. DOI: https://doi.org/10.1007/s00500-018-3177-y

Johnson, D. S., & Mcgeoch, L. A. (1997). The travelling salesman problem: a case study in local optimization. In Aarts, E. H. L. & Lenstra, J. K. (Eds). Local search in combinatorial optimization (Chap. 2, pp. 215-310). New York: John Wiley.

Lal, A. H., Vishnu, K. R., Haq, A. N. & Jeyapaul, R. (2019). The mean flow time in open shop scheduling. Journal of Advances in Management Research, 17(2), 251-261. DOI: https://doi.org/10.1108/JAMR-05-2019-0081

Liaw, C. -F. (1999). A tabu search algorithm for the open shop scheduling problem. Computers and Operations Research, 26(2), 109-126. DOI: https://doi.org/10.1016/S0305-0548(98)00056-2

Liaw, C. -F. (2000). A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research, 124(1), 28-42. DOI: https://doi.org/10.1016/S0377-2217(99)00168-X

Liaw, C. -F. (2014). A fast heuristic to minimize number of tardy jobs in preemptive open shops. Journal of Industrial and Production Engineering, 31(1), 27-35. DOI: https://doi.org/10.1080/21681015.2013.879395

Lourenço, H. R., Martin, O., & Stützle, T. (2002). Iterated local search. In: Glover, F. & Kochenberger, G. (Eds). Handbook of metaheuristics (pp. 321-353). Norwell, MA: Kluwer Academic Publishers.

Low, C., & Yeh, Y. (2009). Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated. Robotics and Computer-Integrated Manufacturing, 25(2), 314-322. DOI: https://doi.org/10.1016/j.rcim.2007.07.017

Martin, O., Otto, S. W., & Felten, E. W. (1991). Large-step Markov chains for the traveling salesman problem. Complex Systems, 5(3), 299-326. Disponível em: https://www.complex-systems.com/abstracts/v05_i03_a03/

Meddourene, A., Bouzouia, B., Abbou, R., & Farraa, B. B. (2019). An hybrid SA-DATC approach for JIT open-shop scheduling problem with earliness and tardiness penalties. IFCA-Paper Online, 52(13), 2396-2401. DOI: https://doi.org/10.1016/j.ifacol.2019.11.565

Naderi, B., Fatemi Ghomi, S. M. T., Aminnayeria, M., & Zandieh, M. (2010). A contribution and new heuristics for open shop scheduling. Computers & Operations Research, 37(1), 213-221. DOI: https://doi.org/10.1016/j.cor.2009.04.010

Naderi, B., Mousakhani, M., & Khalili, M. (2013). Scheduling multi-objective open shop scheduling using a hybrid immune algorithm. International Journal of Advanced Manufacturing Technology, 66(5-8), 895-905. DOI: https://doi.org/10.1007/s00170-012-4375-x

Naderi, B., Nafati, E., & Yazdani, M. (2012). An electromagnetism-like metaheuristic for open-shop problems with no buffer. Journal of Industrial Engineering International, 8(1), 1- 8. DOI: https://doi.org/10.1186/2251-712X-8-29

Naderi, B., & Zandieh, M. (2014). Modeling and scheduling no-wait open shop problems. International Journal of Production Economics, 158(1), 256-266. DOI: https://doi.org/10.1016/j.ijpe.2014.06.011

Pempera, J., & Smutnicki, C. (2018). Open Shop cyclic scheduling. European Journal of Operational Research, 269(2), 773-781. DOI: https://doi.org/10.1016/j.ejor.2018.02.021

Pinedo, M. L. (2016). Scheduling: theory, algorithms, and systems. New York: Prentice-Hall.

Prins, C. (2000). Competitive genetic algorithms for the open-shop scheduling problem. Mathematical Methods of Operations Research, 52(3), 389-411. DOI: https://doi.org/10.1007/s001860000090

Reza Hejazi, S., & Saghafian, S. (2005). Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research, 43(14), 2895-2929. DOI: https://doi.org/10.1080/0020754050056417

Sha, D. Y., & Hsu, C.-Y. (2008). A new particle swarm optimization for the open shop scheduling problem. Computers and Operations Research, 35(10), 3243-3261. DOI: https://doi.org/10.1016/j.cor.2007.02.019