Memorias Institucionales UIS

Vol. 2 No. 1 (2020): Memorias Institucionales UIS
III congreso Colombiano de Investigación de Operaciones

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

PDF (Español (España))
  • Carlos Rodrigo Ruiz Cruz,
  • Sebastián Mateo Meza Villalba
Carlos Rodrigo Ruiz Cruz
Departamento de Ingeniería Industrial, Escuela Colombiana de Ingeniería, Colombia
Sebastián Mateo Meza Villalba
Departamento de Ingeniería Industrial, Escuela Colombiana de Ingeniería, Colombia,

Published 2019-01-01

Keywords

  • Problema de Flexible Job Shop,
  • makespan,
  • algoritmo genético,
  • representación de cromosomas,
  • operaciónes de mutación y cruzamiento

How to Cite

Ruiz Cruz, C. R., & Meza Villalba, S. M. (2019). 43- #1094 UN NUEVO ALGORITMO GENETICO PARA RESOLVER EL PROBLEMA DE FLEXIBLE JOB SHOP. Memorias Institucionales UIS, 2(1). Retrieved from https://revistas.uis.edu.co/index.php/memoriasuis/article/view/10451

Abstract

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.

PDF (Español (España))

Downloads

Download data is not yet available.

References

Ben Hmida, A., Haouari, M., Huguet, M. J., & Lopez, P.
(2010). Discrepancy search for the flexible job shop
scheduling problem. Computers and Operations
Research, 37(12), 2192–2201.
https://doi.org/10.1016/j.cor.2010.03.009
Brandimarte, P. (1993). Routing and scheduling in a
flexible job shop by tabu search. Annals of Operations
Research, 41(3), 157–183.
https://doi.org/10.1007/BF02023073
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The
complexity of flowshop and jobshop scheduling.
Mathematics of Operations Research, 1(2), 117–129.
https://doi.org/10.1287/moor.1.2.117
Mastrolilli, M. (n.d.). Flexible job shop problem.
Http://Www.Idsia.Ch/~monaldo/%0Afjsp.Html.
Retrieved from
http://www.idsia.ch/~monaldo/%0Afjsp.html
Wang, J. F., Du, B. Q., & Ding, H. M. (2011). A genetic
algorithm for the flexible job-shop scheduling problem.
In Advanced Research on Computer Science and
Information Engineering (Vol. 152, pp. 332–339).
Springer, Berlin, Heidelberg.
https://doi.org/10.1007/978-3-642-21402-8_54