43- #1094 UN NUEVO ALGORITMO GENETICO PARA RESOLVER EL PROBLEMA DE FLEXIBLE JOB SHOP

Resumo

La programación de operaciones es uno de los
problemas más críticos en la planeación y gestión de
procesos de manufactura. La complejidad para
encontrar la mejor programación depende del ambiente
de producción de las máquinas, las restricciones
propias del proceso y los indicadores de rendimiento
(Wang, Du, & Ding, 2011). Uno de los problemas más
importantes en esta área es el Flexible Job Shop
Scheduling Problem (FJSSP) que es una extensión del
Job Shop (JS) clásico; en el FJSSP una operación
puede ser procesada en una maquina dado un grupo
disponible de estas (Ben Hmida, Haouari, Huguet, &
Lopez, 2010).

Dada la dificultad de encontrar una solución exacta
para el FJSSP (Garey, Johnson, & Sethi, 1976) se
formula un desarrollo por medio de un método
metaheurístico: un algoritmo genético. Se propone una
representación del cromosoma novedosa con dos sub
- cadenas que codifican tanto la asignación de una
máquina como un número entero que sirve como
operador de desempate en la asignación de
operaciones. La selección de cromosomas para el
espacio de reproducción sigue los métodos de ranking
lineal y torneo de tamaño n. Para el entrecruzamiento
se adopta un operador de cruce múltiple aleatorio y
como estrategia de mutación se reorganiza la sub cadena

de números enteros del cromosoma. Como
criterio de parada se define el número de generaciones
simuladas.

El rendimiento del algoritmo propuesto se mide con las
instancias desarrolladas y presentadas por
Brandimarte (Brandimarte, 1993) que se encuentran
disponibles en OR Library (Mastrolilli, n.d.) con objetivo: 

minimización del makespan. Se compara con otros
autores los resultados obtenidos.

Se pudo demostrar que una codificación correcta del
cromosoma, una adecuada aplicación y combinación
de estrategias en operadores como selección, cruce y
mutación y una selección aleatoria de población inicial
conllevan a buenos resultados computacionales y
experimentales en el FJSSP.