Revista EIA (Jul 2010)
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 A HYBRID GENETIC ALGORITHM AND A SIMULATED ANNEALING FOR SOLVING THE JOB SHOP SCHEDULING PROBLEM
Abstract
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.Job Shop Scheduling Problem (JSP), classified as NP-Hard, has been a challenge for the scientific community because achieving an optimal solution to this problem is complicated as it grows in number of machines and jobs. Numerous techniques, including metaheuristics, have been used for its solution; however, the efficiency of the techniques, in terms of computational time, has not been very satisfactory. Because of this and for contributing to the solution of this problem, a simulated annealing (SA) and an improved genetic algorithm (IGA) have been proposed. The latter, by implementing a strategy of simulated annealing in the mutation phase, allows the algorithm to enhance and diversify the solutions at the same time, in order not to converge prematurely to a local optimum. The results showed that the proposed algorithms yield good results with deviations around the best values found not exceeding 5 % for more complex problems.
