Estudo sobre as operações críticas no agendamento de tarefas em sistemas produtivos do tipo job shop
DOI:
https://doi.org/10.33448/rsd-v11i5.28035Palavras-chave:
Busca local; Caminho Crítico; Scheduling; Manufatura; Planejamento do processo.Resumo
Este trabalho estuda o problema clássico de agendamento da produção em job shop para minimização do makespan. Devido à natureza combinatória e complexidade computacional desse problema, o uso de técnicas metaheurísticas aliadas a métodos de busca local é bastante difundido por possibilitar resultados satisfatórios em um tempo computacional viável. Em geral, os métodos de busca local se baseiam em permutações empíricas das operações que compõe o caminho crítico de uma solução, as chamadas operações críticas, o que demanda o cálculo do caminho crítico para cada uma das soluções geradas no processo de busca. Além de elevar o custo computacional da busca local, tal abordagem promove permutações de operações que não resultam em qualquer melhoria da solução. Este trabalho investiga a distribuição das operações críticas nas máquinas e a correlação entre essa distribuição e características estatísticas dos problemas. O objetivo é estimar máquinas que concentram operações críticas e identificar características que possam contribuir para definição de métodos de busca local que não dependam do cálculo do caminho crítico a cada solução. Experimentos computacionais com instâncias usuais da literatura mostram que há uma concentração de operações críticas em algumas máquinas e, em alguns casos, uma correlação positiva significativa entre essa concentração e os tempos médios de processamento das operações, o que pode fornecer subsídios para criação de métodos de busca local computacionalmente mais eficientes.
Referências
Aarts, E., & Lenstra, J. K. (Eds.). (1993). Local Search in Combinatorial Optimization. Princeton University Press. https://apps.crossref.org/coaccess/coaccess.html?doi=10.2307%2Fj.ctv346t9c
Abdullahi, M., Ngadi, M., & Abdulhamid, S. (2016). Symbiotic organism search optimization based task scheduling in cloud computing environment. Future Generation Computer Systems, 56, pp. 640-650. https://doi.org/10.1016/j.future.2015.08.006
Akram, K., Kamal, K., & Z. A. (2016). Fast simulated annealing hybridized with quenching for solving job shop scheduling problem. Applied Soft Computing, 49, pp. 510-523. https://doi:10.1016/j.asoc.2016.08.037
Amirghasemi, M., & Zamani, R. R. (2015). An effective asexual genetic algorithm for solving the job shop scheduling problem. Computers & Industrial Engineering, 83, pp. 123-138. https://doi:10.1016/j.cie.2015.02.011
Asadzadeh, L. (2015). A local search genetic algorithm for the job shop scheduling problem with intelligent agents. Computers & Industrial Engineering, 85, pp. 123-138. https://doi:10.1016/j.cie.2015.04.006
Balas E, V. A. (1998). Guided local search with shifting bottleneck for job shop scheduling. Management Science, 44, pp. 262-275. Fonte: https://www.jstor.org/stable/2634500
Beasley, J. E. (1990). OR-Library. http://people.brunel.ac.uk/~mastjjb/jeb/info.html
Bierwirth, C., & J., K. (2017). Extended GRASP for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective. European Journal of Operational Research, 261(3), pp. 835-848. https://doi:10.1016/j.ejor.2017.03.030
Blazewicz, J., Domschke, W., & Pesch, E. (1996). The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 1, N.93, pp. 1-33. https://doi.org/10.1016/0377-2217(95)00362-2
Bueno, A., Godinho Filho, M., & Frank, A. G. (2020). Bueno, A.; Godinho Filho, M.; Frank, A. G. (2020). Smart production planning and control in the Industry 4.0 context: A systematic literature review. Computers & Industrial, 149. https://doi:10.1016/j.cie.2020.106774.
Burgy, R., & Bulbul, K. (2018). The job shop scheduling problem with convex costs. European Journal of Operational Research., 268 (1), pp. 82-100. https://doi:10.1016/j.ejor.2018.01.027
Çalis, B., & Bulkan, S. (2015). A research survey: review of AI solution strategies of job shop scheduling problem. Journal of Intelligent Manufacturing, 26(5), pp. 961-973. https://doi:10.1007/s10845-013-0837-8
Chan, F. T., Wong, T. C., & Chan, L. Y. (2008). A Genetic algorithm-based approach to job shop scheduling problem with assembly stage. In 2008 IEEE International Conference on Industrial Engineering and Engineering Management (pp. 331-335). Singapore: IEEE. https://doi:10.1109/IEEM.2008.4737885
Cruz-Chávez, M. A. (2014). Neighbourhood Generation mechanism applied in simulated annealing to job shop scheduling problems. International Journal of Systems Science, pp. 2673-2685. https://doi:10.1080/00207721.2013.876679
Dell’Amico, M., & Trubian, M. (s.d.). Applying tabu-search to job-shop scheduling problem. 41, pp. 231-252. https://doi.org/10.1007/BF02023076
Freitag, M., & Hildebrandt, T. (2016). Automatic design of scheduling rules for complex manufacturing systems by multi-objective simulation-based optimization. CIRP Annals-Manufacturing Technology, 65 (1), pp. 433-436. https://doi.org/10.1016/j.cirp.2016.04.066.
Fuchigami, H. Y., Moura, M. A., & Branco, F. J. (2017). Modelos Matemáticos para Programação Job Shop com Tempos de Configuração Independentes de Sequência. Revista Produção Online, 17 (1), pp. 245-267. https://doi:10.14488/1676-1901.v17i1.2504.
Goldberg, D. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
Gonçalves, J. F., Mendes, J. J., & Resende, M. G. (2005). A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research,, 167, pp. 77-95. https://doi:10.1016/j.ejor.2004.03.012
Grabowski, J., & Wodecki, M. (2005). A very fast tabu search algorithm for job shop problem. In book: Metaheuristic optimization via memory and evolution; tabu search and scatter search. Em A. B. Rego C, & A. Rego C. (Ed.), Metaheuristic optimization via memory and evolution; tabu search and scatter. Kluwer Academic Publishers. https://doi:10.13140/2.1.2986.6880
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press. Ann Harbor.
Jain, A. S., Rangaswamy, B., & Meeran, S. (2000). New and “stronger” job-shop neighbourhoods: A focus on the method of Nowicki and Smutnicki (1996). Journal of Heuristcs, 6, pp. 457-480. https://doi:10.1023/A:1009617209268
Kong, W., Lei, Y., & Ma, J. (2016). Virtual machine resource scheduling algorithm for cloud computing based on auction mechanism. Optik-International Journal for Light and Electron Optics, 127 (12), pp. 5099-5104. https://doi:10.1016/j.ijleo.2016.02.061
Kuhpfahl, J., & Bierwirth, C. (2016). A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective. omputers & Operations Research, 66, pp. 44-57. https://doi:10.1016/j.cor.2015.07.011
Lawrence, S. (1984). Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Tese (Doutorado em Administração Industrial) - Carnegie-Mellon University, Pittsburgh.
Lenstra, J. K., Rinnooy Kan, A. H., & Brucker, P. (1977). Complexity of machine. Em E. J. P.L. Hammer (Ed.), Annals of Discrete Mathematics. 1, pp. 343-362. Elsevier.
Li, K., Zhang, X., Leung, J.-T., & Yang, S. (2016). Parallel machine scheduling problems in green manufacturing industry. Journal of Manufacturing Systems, 38, pp. 98-106. https://doi:10.1016/j.jmsy.2015.11.006
Li, X., Peng, Z., Du, B., Jun, G., Wenxiang, X., & Zhuang, K. (2017). Hybrid artificial bee colony algorithm with a rescheduling strategy for solving flexible job shop scheduling problems. Computers & Industrial Engineering, 113, pp. 10-26. https://doi:10.1016/j.cie.2017.09.005
Liu, W., Liang, Z., Ye, Z., & Liu, L. (2016). The optimal decision of customer order decoupling point for order insertion scheduling in logistics service supply chain. International Journal of Production Economic, 175, pp. 50-60. https://doi:10.1016/j.ijpe.2016.01.021
Lu, H., Shi, J., Fei, Z., Zhou, Q., & Mao, K. (2018). Analysis of the similarities and differences of job-based scheduling problems. European Journal of Operational Research, 270 (3), pp. 809-825. https://doi:10.1016/j.ejor.2018.01.051
Mahmud, S., Abbasi, A., Chakrabortty, R. K., & Ryan, M. J. (2021). Multi-operator communication based differential evolution with sequential Tabu Search approach for job shop scheduling problems. Applied Soft Computing, 108, pp. 1-15. https://doi:10.1016/j.asoc.2021.107470
Mati, Y., Dauzre-Prs, S., & Lahlou, C. (2011). A general approach for optimizing regular criteria in the job-shop scheduling problem. European Journal of Operational Research, 212, pp. 33-42. https://doi:10.1080/00207721.2013.876679
Matsuo, H. D., Suh, C., & Sullivan, R. (1988). Controlled search simulated annealing method for general job shop scheduling problem. Working Paper, Department of Management, The University of Texas at Austin, Austin, TX.
Mattfeld, D. C., & Bierwirth, C. (2004). n efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research, 155 (3), pp. 616-630. https://doi:10.1016/S0377-2217(03)00016-X
Michalewicz, Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. 3rd revised and extended. Berlim, Springer-Verlag.
Mirshekarian, S., & Sormaz, D. N. (2016). Correlation of Job-Shop Scheduling Problem Features with Scheduling EfÞciency. Expert Systems With Applications, 62, pp. 131-147. https://doi:10.1016/j.eswa.2016.06.014
Mitchell, T. M. (1997). Machine Learning (16 ed.). New York: McGraw-Hill.
Muminu, O. A., & A., A. (2016). inimizing the weighted number of tardy jobs on multiple machines: A review. Journal of Industrial & Management Optimization, 12 (4), pp. 1465-1493. https://doi:10.3934/jimo.2016.12.1465
Nowicki, E., & Smutnicki, C. (1996). A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 42 (6), pp. 797-813. https://www.jstor.org/stable/2634595
Parente, M., Figueira, G., Amorim, P., & Marques, A. (2020). roduction scheduling in the context of Industry 4.0: review and trends. International Journal of Production Research, 58 (17), pp. 5401-5431. https://doi:10.1080/00207543.2020.1718794
Pérez, E., Posada, M., & Herrera, F. (2012). Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling. Journal of Intelligent Manufacturing, 23, pp. 341-356. https://doi:10.1007/s10845-010-0385-4
Pinedo, M. L. (2016). Scheduling: Theory, Algoritms, and Systems (5a ed.). Springer. https;//doi:10.1007/978-3-319-26580-3
Pongchairerks, P. A. (2019). A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem. Complexity, 2019, pp. 1-11. https://doi:10.1155/2019/8683472
Ponsich, A., & Coello, C. A. (2013). A Hybrid Differential Evolution Tabu Search Algorithm for the Solution of Job-Shop Scheduling Problems. Applied Soft Computing, 13 (1), pp. 462-474. https://doi:10.1016/j.asoc.2012.07.034
Tamssaouet, K., Dauzère-Pérès, S., & Yugma, C. (2018). Metaheuristics for the Job-Shop Scheduling Problem with Machine Availability Constraints. Computers and Industrial Engineering, 125, pp. 1-8. https://doi:10.1016/j.cie.2018.08.008
Tang, H., Chen, R., Li, Y., Peng, Z., Guo, S., & Du, Y. (2019). Flexible job-shop scheduling with tolerated time interval and limited starting time interval based on hybrid discrete PSO-SA: An application from a casting workshop. Applied Soft Computing, 78, pp. 176-194. https://doi:10.1016/j.asoc.2019.02.011
Van Laarhoven, P. E. (1992). Job shop scheduling by simulate annealing. Institute for Operations Research and the Management Sciences, 40, n.1, pp. 113-125. https://www.jstor.org/stable/171189
Wall, M. (1996). GAlib: A C++ library of genetic algorithm components. Mechanical Engineering Departament, Massachussetts Institute of Technology. Fonte: http://lancet.mit.edu/ga/dist/
Wang, B., Wang, X., Lan, F., & Pan, Q. (2018). A hybrid local-search algorithm for robust job-shop scheduling under scenarios. Applied Soft Computing, 62, pp. 259-271. https://doi:10.1016/j.asoc.2017.10.020
Wang, X., Wang, B., Zhang, X., Xia, X., & Pan, Q. (2021). wo-objective Robust Job-Shop Scheduling with Two Problem-Specific Neighborhood Structures. Swarm and Evolutionary Computation, 61, p. 100805. https://doi:10.1016/j.swevo.2020.100805
Wu, Z., Sun, S., & Yu, S. (2020). Optimizing makespan and stability risks in job shop scheduling. Computers and Operations Research, 122, p. 104963. https://doi:10.1016/j.cor.2020.104963
Yamada, T. (2003). Studies on metaheuristics for jobshop and flowshop scheduling problems. PhD dissertação Kyoto University. http://www.kecl.ntt.co.jp/as/members/yamada/YamadaThesis.pdf
Yamada, T., & Nakano, R. (1997). Job shop scheduling. IEE Control Engineering Series, 55, pp. 134-160. https://www.kecl.ntt.co.jp/as/members/yamada/galbk.pdf
Yang, J., Sun, L., Lee, H. P., Qian, Y., & Liang, Y. C. (2008). Clonal Selection Based Memetic Algorithm for Job Shop Scheduling Problems. Journal of Bionic Engineering, 5 (2), pp. 111–119. https://doi:10.1016/S1672-6529(08)60014-1
Zhang, J., Ding, G., Zou, Y., Qin, S., & Fu, J. (2019). Review of job shop scheduling research and its new perspectives under Industry 4.0. Journal of Intelligent Manufacturing, 30, pp. 1809–1830. https://doi:10.1007/s10845-017-1350-2
Zhang, R., & Wu, C. (2011). An artificial bee colony algorithm for the job shop scheduling problem with random processing times. Entropy, 13 (9), pp. 1708–1729. https://doi:10.3390/e13091708
Zhang, R., Song, S., & Wu, C. (2013). A hybrid differential evolution algorithm for job shop scheduling problems with expected total tardiness criterion. Applied Soft Computing, pp. 1448–1458. https://doi:10.1016/j.asoc.2012.02.024
Zhang, R., Song, S., & Wu, C. (2013(b)). A hybrid artificial bee colony algorithm for the job shop scheduling problem. International Journal of Production Economics, 141((1)), pp. 167-178. https://doi:10.1016/j.ijpe.2012.03.035
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2022 Jonathan Farias Bordignon; Luis Carlos Caparroz dos Santos; Marilda Fátima de Souza da Silva; Fabio Henrique Pereira
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
Autores que publicam nesta revista concordam com os seguintes termos:
1) Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
2) Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
3) Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.
