UN ENFOQUE BASADO EN JUMPING GENE GENETIC ALGORITHM PARA EL JOB-SHOP SCHEDULING PROBLEM

MARIANO FRUTOS; RICARDO CASAL; RAFAEL CORRAL; NANCY LÓPEZ

Termas de Chillán

Congreso; VIII Congreso Chileno de Investigación Operativa; 2009

Universidad del Bío-Bío

El Job-Shop Scheduling Problem (JSSP) consiste en secuenciar tareas conformadas por múltiples operaciones en las diferentes máquinas involucradas en el proceso productivo, con el fin de satisfacer las distintas exigencias que presenta este último. El JSSP posee un rango de aplicación muy amplio en diferentes áreas del conocimiento. En este artículo, se propone un Multi-Objective Evolutionary Algorithm (MOEA), que opera en base a Jumping Gene Genetic Algorithm (JGGA) para darle solución a este problema. Se han abordado instancias Mono-objetivo y Multi-objetivo para verificar su eficiencia. En este estudio, se realiza un análisis estadístico detallado de los resultados obtenidos con JGGA. Además, se comparó este algoritmo con respecto a un Memetic Algorithm (MA), también propuesto por los autores, el cual se enmarca dentro del procedimiento Non-Dominated Sorting Genetic Algorithm (NSGAII). Otras meta-heurísticas que se tuvieron en cuenta para este análisis comparativo fueron: Artificial Immune System (AIS), Taboo Search (TS), Genetic Algorithm (GA) y Greedy Randomized Adaptive Search Procedures (GRASP). Los resultados indican que el algoritmo presentado es una alternativa viable para resolver el JSSP, dada la calidad de las soluciones obtenidas. Sus únicos contendientes serios, entre las meta-heurísticas comparadas, son MA, AIS y TS.