Problema del job shop utilizando algoritmos genéticos

Enviado por Crista Ojeda

FINALIDAD: OPTIMIZACIÓN DE PROCESOS INDUSTRIALES UTILIZANDO TÉCNICAS METAHEURÍSTICAS, EPECIFICAMENTE ALGORITMOS GENÉTICOS.

Resumen

Los métodos clásicos de programación de operaciones en industrias resultan poco eficaces en las plantas de producción reales ya que suponen hipótesis escasamente realistas y que difícilmente se cumplen en la práctica. Fundamentalmente, estas hipótesis están relacionadas con la consideración del entorno de fabricación como estático, pero en la vida real las instalaciones productivas están sujetas a numerosos sucesos imprevistos que, si no se tienen adecuadamente en cuenta, desembocan en planes de producción inaceptables. Por otra parte, es necesario reaccionar con premura, dada la importancia económica de los costes indirectos asociados a las interrupciones que originan. De hecho, la capacidad de reacción rápida y la flexibilidad son requisitos clave a tener en cuenta en los sistemas de control, ya que contribuyen a reducir los tiempos de flujo, mejorar las tasas de utilización y el servicio al cliente. Por consiguiente, es preciso extender los modelos de scheduling clásicos con el fin de representar la fábrica de una manera más cierta. En el siguiente trabajo, se presenta una revisión bibliográfica acerca de uno de los problemas clásicos de la optimización combinatoria y la investigación de operaciones: el Job Shop Scheduling Problem. Se define el problema formalmente y se exponen teorías de algunos autores para concluir con la más mejor técnica de resolución según el criterio del autor.

Palabras clave: Optimización combinatoria, Algoritmos genéticos, Job-shop scheduling.

Introducción

El problema de asignación de trabajos a máquinas con diferente secuencia de operación se identifica como un caso del denominado Job-Shop Scheduling Problem (JSSP), y se detalla la implementación del método de resolución utilizando un algoritmo genético. El objetivo principal de este trabajo es diseñar y programar un modelo replicable que se ajuste a la planificación de un sistema de producción de tipo Job shop, usando como base algoritmos genéticos.

En los últimos años, la comunidad científica internacional ha mostrado un creciente interés en esta nueva técnica que se fundamenta en la teoría de la evolución y que se conoce como algoritmos genéticos. Esta técnica se basa en los mecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los individuos más aptos de una población son los que sobreviven, al adaptarse más fácilmente a los cambios que se producen en su entorno.

Es de mucha importancia para las empresas de hoy en día, dar una imagen de excelente calidad en los productos ofrecidos y procesos desarrollados, cumpliendo con los plazos pactados con los clientes, responsabilidad, seriedad, entre otros aspectos de importancia; todo esto con la intención de mantenerse competitivos en un mercado que cada vez exige más sobre sus requerimientos y tiempos de entrega.

Este tipo de problemas aparecen con frecuencia en la vida real en numerosos entornos productivos y de servicios. No obstante, los algoritmos genéticos han sido aplicados con éxito en una infinidad de problemas, que van desde problemas en economía y finanzas como predicción econométricas, mercados de valores, problemas de programación, ruteo para telecomunicaciones, optimización paramétrica de elementos mecánicos, balanceo de turbinas, optimización de arquitectura de redes neuronales, coloración de mapas, etc; y en general en todo tipo de problema donde se desea encontrar un óptimo.

Algunos ejemplos son los siguientes:

a) Marcel Goic F y Carlos Caballero V. (5 Agosto, 2005); Universidad de Chile: Aplicación de algoritmos genéticos para el mejoramiento del proceso de programación del rodaje en la industria del cine independiente; modelo desarrollado para apoyar el proceso de la planificación del rodaje de películas independientes generando calendarios de filmación que permiten reducir el costo de los recursos humanos contratados y generar planes de trabajo alineados con el proceso creativo subyacente.
b) Naupari Quiroz, Raúl Esteban y Rosales Gerónimo, Gissela Katheryn (Lima-Perú 2010); Universidad Mayor de San Marcos: Aplicación de algoritmos genéticos para el diseño de un sistema de apoyo a la generación de horarios de clases para la Facultad de Ingeniería de Sistemas e Informática de la UNMSM. Se llegó a la conclusión que el modelo desarrollado encontró buenas soluciones al problema dentro del margen de error definido.
c) Javier Caballero Villarraso, Antonio R. Tabares, Francisco J. Gavilán León, Manuel Baena García, Francisco Javier Díez Vegas (Sevilla-España 2011): Aplicación de algoritmos genéticos y sistemas expertos en medicina asistencial. Aplicaciones clínicas de la inteligencia artificial. Existe una ingente producción científica relacionada con la Inteligencia Artificial en asistencia clínica y en gestión sanitaria.

Para solucionar el problema del Job Shop, se construye un modelo matemático que se adapte a los procesos productivos de la empresa y cuyo objetivo es encontrar la secuencia optima de fabricación, encontrando una solución factible que ofrezca el menor tiempo.

El presente trabajo será desarrollado en tres partes. En la primera se detalla la fundamentación del problema, describiendo teorías, ideas principales y técnicas utilizadas hoy en día. En la segunda parte se discutirán algunas de las técnicas nombradas en el primer capítulo comparándolas de acuerdo al autor que las expone. Por último, en el tercer capítulo se demostrará los resultados obtenidos de acuerdo a la confrontación de ideas que se hizo en el capítulo anterior.

CAPÍTULO I:

Fundamentación del problema

Este tipo de problemas es NP-hard (Garey y Jonson, 1979), por lo que no existe un algoritmo conocido que asegure encontrar la solución óptima en un tiempo polinomial. Por este motivo, ha sido tradicionalmente utilizado como test en la validación de nuevos algoritmos desarrollados.

Además en los últimos años, los estudios se han centrado no ya en encontrar la solución óptima del problema, sino en intentar alcanzar un abanico de soluciones óptimas todas ellas igualmente válidas por varios motivos:

Dar al ejecutor del plan más flexibilidad ante contingencias no siempre cuantificables o incorporables en el modelo del problema (averías de máquinas, roturas de stocks, etc.).
Cuando el problema es complejo o multimodal, donde mantener la diversidad en la búsqueda es necesario para no quedar atrapado en subóptimos.

Por estas razonas, hace ya 20 años surgieron los primeros estudios de multimodalidad con algoritmos genéticos de la mano de Goldberg (Goldberg y Richardson, 1987). Desde entonces han sido numerosos las aproximaciones y algoritmos desarrollados con tal fin. Entre ellos, el que ha demostrado ser de los más potentes (Sareni y Krahenbuhl, 1998; Pérez et al., 2003), es el método clearing desarrollado en el año 95.

1. Ho y Tay y en sus distintas publicaciones estudian el problema del Job Shop Flexible, proponiendo reglas de despacho que utilizan como solución inicial para una nueva metodología denominada GENACE.
2. Fattahi, Meharab y Jolai proponen un modelo matemático para el Job Shop Flexible, combinan las metaheurísticas de Tabu Search y Simulated Annealing, y para probarlo generan diez instancias pequeñas y diez instancias medianas/grandes, aunque sólo logran resolver las instancias pequeñas.
3. Algoritmos genéticos: Zhang y Gen proponen un algoritmo genético basado en escenarios múltiples, donde cada escenario corresponde a una operación y cada máquina factible a un estado.
4. El método clásico "Sharing fitness", (Goldberg y Richardson, 1987) está basado en la penalización de las áreas del espacio de búsqueda con más soluciones en la población. De esta forma, las soluciones pertenecientes a áreas densamente pobladas verán reducida su calidad con el objetivo de permitir la exploración de otras áreas menos pobladas.
5. Debido a los problemas en mantener la diversidad necesaria se modificó el proceso dando lugar al método denominado continuously updated sharing (Oei et al., 1991).
6. Basado también en el concepto de nicho, el método clearing utiliza el concepto de recursos limitados para eliminar la competencia entre soluciones que son muy diferentes (Pétrowski 1996 y 1997).

CAPÍTULO II:

Discusión del problema

1. GENACE, en la cual las poblaciones son influenciadas por reglas heurísticas y en cada generación se guía el espacio de búsqueda mediante esquemas. Otros autores también estudian las representaciones de las soluciones, para encontrar la más eficaz en términos de tiempo de cómputo y de alcanzar el mejor makespan. Este enfoque es generalizado en una publicación posterior en Ho, Tay y Lai, donde se propone una arquitectura basada en algoritmos evolutivos, un aprendizaje con teoría de esquemas y un generador de poblaciones mediante reglas de despacho compuestas.
2. Tabu Search y Simulated Annealing: Utilizando también el enfoque jerárquico, combinan las metaheurísticas de Tabu Search y Simulated Annealing, con las que concluyen que el algoritmo que resuelve el subproblema de asignación con Tabu Search y el subproblema de secuenciamiento con Simulated Annealing presenta el mejor desempeño.
3. Algoritmos genéticos: Pezzella, Morganti y Ciaschetti también proponen un algoritmo genético, pero utilizan el enfoque de localización propuesto por Kacem, Hammadi y Borne. Con ello establecen una mutación inteligente, que consiste en seleccionar una operación entre aquellas máquinas con más carga de trabajo y reasignar dicha carga a la máquina que tenga menos. Por último, la publicación más reciente corresponde a Yazdani, Zandieh y Amiri, quienes proponen un enfoque en paralelo de vecindario variable (VNS), con seis vecindarios, minimizando también el makespan.
4. Sharing fitness: El objetivo de este tipo de métodos es dividir el espacio de búsqueda en subregiones o nichos. Para ello, en la población, y para cada solución, se busca las soluciones vecinas (definidas como las que están a una distancia menor de un radio predeterminado, y que determinan el espacio geográfico que comprende su nicho). Si hay muchas soluciones en su nicho, el valor de la función de modificación será elevado y, por ello su calidad será altamente penalizada, frente a otras soluciones en cuyo nicho haya pocas o ninguna solución, por lo que su calidad apenas se verá afectada y el nicho al que pertenece tendrá más posibilidades de ser analizado en el proceso de búsqueda.
5. Continuously updated sharing: La diferencia con el método original es que en lugar de penalizar las áreas presentes en la población de partida de cada generación, se van penalizando aquellas que van siendo elegidas durante la selección. Así, la calidad de una zona en la que ya haya varios padres seleccionados se penaliza limitando la posibilidad de que, nuevamente, sus individuos sean elegidos para la población de padres. Además, se modificó el método de selección dando lugar al torneo binario restringido (restricted binary tournament). Este método utiliza un parámetro denominado tamaño de nicho máximo. Si las dos soluciones que compiten en el torneo pertenecen a nichos con un tamaño de nicho menor que, ganará aquella solución con mayor calidad. En caso contrario, ganará la que tenga mayor riesgo de desaparecer. Puntualizar que se habla siempre de la calidad modificada, y que el tamaño de nicho se refiere al número de soluciones que hay en la población de padres con una distancia menor que el radio definido hacia las soluciones involucradas en el torneo.
6. Clearing: En la naturaleza los individuos de una misma especie son los que luchan entre sí para lograr los recursos limitados existentes en la naturaleza, sin embargo esta lucha no es frecuente entre individuos de especies con muy diferentes características. Así es posible que convivan animales tan dispares como el león y la hormiga (no tienen que luchar por los mismos recursos y por ello sobreviven). La población inicial se modifica para formar otra población desde la que se hace la selección. Las soluciones de la población de partida se ordenan de mayor a menor calidad, como inicio al proceso se selecciona la primera solución de la ordenación que pasa directamente a la población. A esta primera solución se la llama dominadora puesto que no hay mejor solución que ella en la población. Después, se compara cada solución de la población inicial con la seleccionada, obteniéndose el conjunto de soluciones que pertenecen al mismo nicho. De este conjunto reservamos las k mejores soluciones (las de mayor calidad) mientras que a las restantes se les asigna una calidad nula. De esta forma, limitamos la competencia dentro del nicho. En este punto tenemos una solución en la población mantiene las N iniciales pero algunas de ellas con calidad cero. El proceso continua volviendo a seleccionar la siguiente solución de la ordenación cuya calidad sea distinta de cero. El proceso termina cuando todas las soluciones que quedan por seleccionar en la población inicial tienen calidad cero. Por último, el método implementa la siguiente forma de elitismo. De la población resultante se selecciona aquellas soluciones cuya calidad sea superior a la media de la calidad original de la población inicial.

CAPÍTULO III:

Demostración

Algoritmo Genético (GA), son métodos metaheurísticos de optimización estocástica inspirados en la evolución natural de las especies y propuestos por Holland en 1975.

Holland aprendió que la evolución era una forma de adaptación más potente, que el simple aprendizaje, y tomo la decisión de aplicar estas ideas para desarrollar Algoritmos bien adaptados para un fin determinado.

El algoritmo genético, es un proceso de cómputo que emula la forma de actuar de la evolución biológica. Como la evolución, opera sobre una población de individuos que representan las soluciones potenciales a un determinado problema. Entonces busca producir mejores individuos al combinar a los mejores existentes empleando la táctica de la "sobrevivencia del más apto" y descartando a aquellos individuos deficientes. Así, consigue producir más y mejores soluciones conforme se desarrolla el proceso.

En términos generales, se trata de procesos iterativos que, en cada etapa, mantienen una población de soluciones candidatas que satisfacen las restricciones de un problema. En cada etapa, a partir de la población actual, una nueva generación de soluciones es formada usando un conjunto de operadores, dentro de los cuales los tres más importantes son la selección, el cruce y la mutación.

Para implementar el algoritmo Genético en sistemas de organización de la producción después de identificar los parámetros, se debe seguir los siguientes pasos:

Inicialización:

Construir la población inicial, con P soluciones, de acuerdo al número de máquinas y trabajos definidos en los parámetros de entrada.

Evaluación:

Esta función, evalúa el tiempo total de ejecución, siguiendo los parámetros establecidos en la gráfica de Gantt, la cual representa un orden de los trabajos con respecto al tiempo, determinando de esta manera, la ordenación de los trabajos en las máquinas, obteniendo un tiempo óptimo de ejecución.

Selección:

La selección de los individuos de la población está limitada por el tamaño de la población y la función de aptitud (fitness). El proceso de selección se basa en la elección de los individuos más fuertes de la población, los cuales serán los candidatos a ser cruzados y por ende a generar la siguiente generación.

Para este caso se usara el método de la ruleta, el cual se basa en la aptitud de cada uno de los individuos, asignándoles mayor probabilidad a los más aptos (los de menor tiempo total de ejecución).

Cruce:

Aleatoriamente se seleccionan dos cromosomas (Padres) de la población para realizar el proceso de cruce, obteniendo de esta manera la siguiente generación (Hijos). Se repite este proceso hasta obtener el mismo número de individuos de la población inicial.

Mutación:

Se seleccionan los genes de una población y se cambian sus valores aleatoriamente teniendo en cuenta que los valores no se pueden repetir.

Conclusiones

El estudio realizado muestra la posibilidad de aplicar con éxito una técnica avanzada de optimización, como son los algoritmos genéticos y evolutivos, al problema de la programación de producción industrial. Esta característica se logra gracias a la incorporación de una heurística específica del problema en el proceso de generación de los organismos iniciales y en la mutación de organismos en sucesivas generaciones.

Es muy importante destacar que un problema que a simple vista parece tan sencillo es uno de los problemas que mayor tiempo se le ha dedicado a su estudio e investigación durante las últimas décadas. Se dieron a conocer algunas metodologías, categorizándolas según su método de resolución en técnicas de optimización y técnicas de aproximación.

El algoritmo genético planteado es eficiente para problemas pequeños, es decir, aquellos para los cuales el conjunto de solución es pequeño. A medida que el taño del problema crece el conjunto de solución también lo hace, pero de manera exponencial, dificultando la búsqueda.

Referencias bibliográficas

1. ACEVEDO ROMERO, PAOLA ANDREA Y OVIEDO MARTÍNEZ, ALEXA CATALINA. (2005). "Diseño y Programación de un algoritmo genético para la solución a un problema de asignación de trabajos para el proceso de Job Shop". Colombia: Universidad de la Sabana.
2. JIMÉNEZ CARRION, MIGUEL (2001). «Aplicación de Algoritmos Genéticos a un problema de dimensionalidad en programación Dinámica». Perú: Trabajo de Investigación.
3. JIMÉNEZ CARRIÓN, MIGUEL. (2003). "Implementación de un sistema de información para gestionar el problema de retornos tabulados utilizando algoritmos genéticos" Perú: Universidad Nacional de Piura.
4. JIMÉNEZ CARRION, MIGUEL (2010) "El arte en la construcción de los algoritmos genéticos". Perú: Trabajo de Investigación.
5. VICTOR PENA Y LILLO ZUMELZU. (2006). "Estado del Arte del Job Shop Scheduling Problem". Valparaíso, Chile: Departamento de Informática, Universidad Técnica Federico Santa María.
6. TAHA, HAMDY A. (1994). "Investigación de Operaciones, una Introducción". México: AlfaOmega.

Direcciones electrónicas:

7. http://www.sc.ehu.es/ccwbayes/docencia/mmcc/docs/temageneticos.pdf
8. http://www.scielo.cl/pdf/ingeniare/v19n1/art06.pdf
9. http://www.uelbosque.edu.co/sites/default/files/publicaciones/revistas/revista_tecnologia/volumen3_numero2/algoritmo_genetico3-2.pdf
10. http://intellectum.unisabana.edu.co:8080/jspui/bitstream/10818/5028/1/130072.pdf
11. http://www.dm.uba.ar/materias/optimizacion/2008/1/tesis.PDF

DEDICATORIA

A Dios, por el camino recorrido….

A mi hijo, Fabiano, por ser mi fuerza y templanza…

A mis padres, por su amor y apoyo…

A la vida…. Por lo aprendido y aprehendido

AGRADECIMIENTOS

Agradezco a Dios, ser maravilloso que me dio fuerza y fe para creer lo que me parecía imposible terminar.

A mi familia por ayudarme con mi hijo mientras yo realizaba investigaciones y por estar a mi lado en cada momento de mi vida.

A la Ing. Yolanda Lizana por su apoyo total desde los inicios de mi carrera de Ingeniería Informática.

Al Dr. Miguel Jiménez, que como asesor, me ha orientado, apoyado y corregido en mi labor científica con un interés y entrega que han sobrepasado, con mucho, todas las expectativas que, como alumna, deposite en su persona.

Autor:

Cristha Ojeda Monzón

CURSO: SEMINARIO DE INGENIERÍA INFORMÁTICA.

UNIVERSIDAD NACIONAL DE PIURA

FACULTAD DE INGENIERÍA INDUSTRIAL

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA

PIURA – 2014