Estudio sobre operaciones críticas en las tareas de programación en sistemas productivos de tipo job shop
DOI:
https://doi.org/10.33448/rsd-v11i5.28035Palabras clave:
Búsqueda de ubicación; Ruta crítica; Programación; Fabricación; Planificación de processos.Resumen
Este trabajo estudia el problema de programación de la producción clásica en la tienda de empleo para minimizar a Makespan. Debido a la naturaleza combinativa y la complejidad computacional de este problema, el uso de técnicas metaheurísticas aliadas a los métodos de búsqueda locales está generalizada al permitir los resultados satisfactorios en un tiempo computacional viable. En general, los métodos de búsqueda locales se basan en permutaciones empíricas de operaciones que conforman la ruta crítica de una solución, llama a operaciones críticas, que exige el cálculo del camino crítico para cada una de las soluciones generadas en el proceso de búsqueda. Además de elevar el costo computacional de la búsqueda local, dicho enfoque promueve permutaciones de operaciones que no resultan en ninguna mejora en la solución. Este trabajo investiga la distribución de operaciones críticas sobre máquinas y correlación entre esta distribución y características estadísticas de los problemas. El objetivo es estimar las máquinas que concentren las operaciones críticas e identifican las características que pueden contribuir a la definición de métodos de búsqueda locales que no dependen del cálculo del camino crítico a cada solución. Los experimentos computacionales con instancias habituales de literatura muestran que hay una concentración de operaciones críticas en algunas máquinas y, en algunos casos, una correlación positiva significativa entre esta concentración y los tiempos de procesamiento de operaciones promedio, lo que puede proporcionar subsidios para crear métodos de búsqueda computacionalmente más eficientes.
Citas
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
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2022 Jonathan Farias Bordignon; Luis Carlos Caparroz dos Santos; Marilda Fátima de Souza da Silva; Fabio Henrique Pereira
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Los autores que publican en esta revista concuerdan con los siguientes términos:
1) Los autores mantienen los derechos de autor y conceden a la revista el derecho de primera publicación, con el trabajo simultáneamente licenciado bajo la Licencia Creative Commons Attribution que permite el compartir el trabajo con reconocimiento de la autoría y publicación inicial en esta revista.
2) Los autores tienen autorización para asumir contratos adicionales por separado, para distribución no exclusiva de la versión del trabajo publicada en esta revista (por ejemplo, publicar en repositorio institucional o como capítulo de libro), con reconocimiento de autoría y publicación inicial en esta revista.
3) Los autores tienen permiso y son estimulados a publicar y distribuir su trabajo en línea (por ejemplo, en repositorios institucionales o en su página personal) a cualquier punto antes o durante el proceso editorial, ya que esto puede generar cambios productivos, así como aumentar el impacto y la cita del trabajo publicado.
