UN ALGORITMO GENéTICO HíBRIDO Y UN ENFRIAMIENTO SIMULADO PARA SOLUCIONAR EL PROBLEMA DE PROGRAMACIóN DE PEDIDOS JOB SHOP↓UM ALGORITMO GENéTICO HíBRIDO E UM ESFRIAMENTO SIMULADO PARA SOLUCIONAR O PROBLEMA DE PROGRAMA??O DE PEDIDOS JOB SHOP

摘要

La programación de pedidos para el problema de producción Job Shop (JSP), catalogado como NP-Hard, ha constituido un reto para la comunidad científica, debido a que alcanzar una solución óptima a este problema se dificulta en la medida que crece en número de máquinas y trabajos. Numerosas técnicas, entre ellas las metaheurísticas, se han empleado para su solución, sin embargo, su eficiencia, en cuanto a tiempo computacional, no ha sido muy satisfactoria. Por lo anterior y para contribuir a la solución de este problema, se planteó el uso de un enfriamiento simulado propuesto (ESP) y de un algoritmo genético mejorado (AGM). Para el AGM se implementó una estrategia de enfriamiento simulado en la fase de mutación, que permite al algoritmo intensificar y diversificar las soluciones al mismo tiempo, con el fin de que no converja prematuramente a un óptimo local. Los resultados mostraron que los algoritmos propuestos arrojan buenos resultados, con desviaciones alrededor de los mejores valores encontrados que no superan el 5 % para los problemas más complejos.↓A programa??o de pedidos para o problema de produ??o Job Shop (JSP), catalogado como NP-Hard, tem constituído um desafio para a comunidade científica, devido a que alcan?ar uma solu??o ótima a este problema se dificulta na medida em que cresce em número de máquinas e trabalhos. Numerosas técnicas, entre elas as metaheurísticas, foram empregadas para sua solu??o, no entanto, sua eficiência, em quanto a tempo computacional, n?o há sido muito satisfatória. Pelo anterior e para contribuir à solu??o deste problema, prop?s-se o uso de um esfriamento simulado proposto (ESP) e de um algoritmo genético melhorado (AGM). Para o AGM se implementou uma estratégia de esfriamento simulado na fase de muta??o, que permite ao algoritmo intensificar e diversificar as solu??es ao mesmo tempo, com o objetivo de que n?o convirja prematuramente a um ótimo local. Os resultados mostraram que os algoritmos propostos arrojam bons resultados, com desvios ao redor dos melhores valores achados que n?o superam 5 % para os problemas mais complexos.