Assesing The Performance of Different S-Metaheuristics To Solve Unrestricted Parallel Identical Machines Scheduling Problem

• Autores: Claudia Ruth Gatica, Susana Cecilia Esquivel, Mario Guillermo Leguizamón
• Localización: Inteligencia artificial: Revista Iberoamericana de Inteligencia Artificial, ISSN-e 1988-3064, ISSN 1137-3601, Vol. 16, Nº. 52, 2013 (Ejemplar dedicado a: WASI), págs. 42-51
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen
  • English

    In this paper we present a comparative study of four trajectory or single-solution based metaheuristics (S-metaheuristics): Iterated Local Search (ILS), Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS), and Simulated Annealing (SA). These metaheuristics were considered to assess their respective performance to minimize the Maximum Tardiness (Tmax) for the unrestricted parallel identical machine scheduling (Pm) problem, which is considered an NP-Hard problem. The results obtained through experimentation show that SA was the best performing metaheuristic.

  • English

    En este trabajo se presenta un estudio comparativo de cuatro metaheurísticas basadas trayectoria o de solución única (S-metaheurísticas): Búsqueda Local Iterada (ILS), Procedimiento de Búsqueda Greedy Aleatorizado Adaptativo (GRASP), Búsqueda de Vecindario Variable (VNS), y Recocido Simulado (SA). Estas metaheurísticas fueron consideradas para evaluar su rendimiento respectivo de minimizar la Máxima Tardanza (Tmax) para el problema de planificación de máquinas paralelas idénticas irrestrictas (Pm), el cual se considera un problema NP-duro. Los resultados obtenidos mediante la experimentación demuestran que SA fue la metaheurística de mejor desempeño.