ImpactU Versión 3.11.2 Última actualización: Interfaz de Usuario: 16/10/2025 Base de Datos: 29/08/2025 Hecho en Colombia
Greedy Randomized Adaptive Search Procedure (GRASP), una alternativa valiosa en la minimización de la tardanza total ponderada en una máquina: A Valuable Alternative for Minimizing Machine Total Weighted Tardiness
^les^aEste articulo presenta los resultados experimentales obtenidos de secuenciar trabajos en una maquina, a fin de minimizar la tardanza total ponderada mediante un algoritmo GRASP. Los resultados se compararon con los valores optimos o mejores valores reportados hasta el momento para cada una de las instancias de OR-Library y se encontro una excelente relacion entre la calidad de los resultados (93% de las instancias se solucionaron con una desviacion maxima del 1% respecto a estos valores) y el esfuerzo computacional y de implementacion requerido. El algoritmo se implemento usando macros en una hoja de calculo. La fase de postoptimizacion se realizo mediante una estrategia de Busqueda Local que utilizo reglas de dominancia que, aun cuando sencillas, permitieron mejorar sustancialmente la tardanza total ponderada de las secuencias obtenidas en la fase constructiva del algoritmo.^len^aA GRASP algorithm was implemented in a common spreadsheet for single machine scheduling total weighted tardiness problem, and was tested with OR-Library instances. Results were compared with optimum or best known schedules for each instance, yielding less than 1% of difference in 93% of the cases, which results in an excellent tradeoff among results quality, computational effort and implementation easiness. Local search was performed on the post-optimization phase, based on dominancy rules, which yielded even better results with little implementation effort.^lpt^aEste artigo apresenta os resultados experimentais obtidos ao sequenciar trabalhos em uma maquina, a fim de minimizar a tardanca total ponderada mediante um algoritmo GRASP. Os resultados compararam-se com os valores otimos ou os melhores valores conhecidos ate o momento para cada uma das instâncias de OR-Library e encontrou-se uma excelente relacao entre a qualidade dos resultados (93% das instâncias solucionaram-se com um desvio maximo de 1% com respeito a estes valores) e o esforco computacional e de implementacao requerido. O algoritmo implementouse usando macros em uma planilha de calculo. A fase de pos-otimizacao realizou-se mediante uma estrategia de Busca Local que utilizou regras de dominância que, ainda que simples, permitiram melhorar substancialmente a tardanca total ponderada das sequencias obtidas na fase construtiva do algoritmo.