Benchmarks para problemas de scheduling de máquinas paralelas idénticas con algoritmos inteligentes

Abstract

En nuestro trabajo presentamos un conjunto de benchmarks para el problema de scheduling de paralelas idénticas sin restricciones. Hemos estudiado tal problema a través de cuatro funciones objetivo: Maximum Tardiness (Tmax), Average Tardiness (Tavg), Total Weighted Tardiness (Twt) y Weighted Number of Tardy Jobs (Nwt). El conjunto de benchmarks se dividen en ocho escenarios de 125 instancias cada uno. Tales instancias del problema se construyeron en base a datos seleccionados de la OR-Library correspondientes a problemas de tardanza ponderada. Se obtuvieron los valores de los óptimos conocidos o benchmarks mediante la aplicación de reglas de despacho y heurísticas conocidas en la literatura y luego se utilizaron dos algoritmos propuestos basados en búsqueda local: uno de ellos es una variación del algoritmo Simutaled Annealing (SA-explorador), el segundo algoritmo es de Vecindarios Variables (VNS) y el tercer algoritmo basado en búsqueda poblacional conocido como Discrete Differencial Evolution (DDE).