43- #1094 UN NUEVO ALGORITMO GENETICO PARA RESOLVER EL PROBLEMA DE FLEXIBLE JOB SHOP
No Thumbnail Available
Date
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
Description
La programación de operaciones es uno de losproblemas más críticos en la planeación y gestión deprocesos de manufactura. La complejidad paraencontrar la mejor programación depende del ambientede producción de las máquinas, las restriccionespropias del proceso y los indicadores de rendimiento(Wang, Du, & Ding, 2011). Uno de los problemas másimportantes en esta área es el Flexible Job ShopScheduling Problem (FJSSP) que es una extensión delJob Shop (JS) clásico; en el FJSSP una operaciónpuede ser procesada en una maquina dado un grupodisponible de estas (Ben Hmida, Haouari, Huguet, &Lopez, 2010).
Dada la dificultad de encontrar una solución exactapara el FJSSP (Garey, Johnson, & Sethi, 1976) seformula un desarrollo por medio de un métodometaheurístico: un algoritmo genético. Se propone unarepresentació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 deoperaciones. La selección de cromosomas para elespacio de reproducción sigue los métodos de rankinglineal y torneo de tamaño n. Para el entrecruzamientose adopta un operador de cruce múltiple aleatorio ycomo estrategia de mutación se reorganiza la sub cadena
de números enteros del cromosoma. Comocriterio de parada se define el número de generacionessimuladas.
El rendimiento del algoritmo propuesto se mide con lasinstancias desarrolladas y presentadas porBrandimarte (Brandimarte, 1993) que se encuentrandisponibles en OR Library (Mastrolilli, n.d.) con objetivo:
minimización del makespan. Se compara con otrosautores los resultados obtenidos.
Se pudo demostrar que una codificación correcta delcromosoma, una adecuada aplicación y combinaciónde estrategias en operadores como selección, cruce ymutación y una selección aleatoria de población inicialconllevan a buenos resultados computacionales yexperimentales en el FJSSP.
Keywords
Problema de Flexible Job Shop, makespan, algoritmo genético, representación de cromosomas, operaciónes de mutación y cruzamiento