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

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.

Palavras-chave


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

Texto completo:

PDF

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




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

Direitos autorais 2021 Exacta

Licença Creative Commons
Esta obra está licenciada sob uma licença Creative Commons Atribuição - Não comercial - Compartilhar igual 4.0 Internacional.

Tempo médio entre a submissão e primeira resposta de avaliação: 120 dias

Exacta – Engenharia de Produção

e-ISSN: 1983-9308
ISSN: 1678-5428
www.revistaexacta.org.br

Exacta  ©2022 Todos os direitos reservados.

Este obra está licenciada com uma Licença 
Creative Commons Atribuição-NãoComercial-CompartilhaIgual 4.0 Internacional