“SOLUCIÓN DE UN PROBLEMA DE ASIGNACIÓN DE HORARIOS DE MANTENIMIENTO EN MÁQUINAS, EQUIPOS E INSTALACIONES A LA EMPRESA POWEL CONTINENTAL Ltda. MEDIANTE LA PROGRAMACIÓN DE UN ALGORITMO GENÉTICO”

JORGE ALBERTO OSPINA FALLA RAFAEL RICAURTE BERNAL

UNIVERSIDAD DE LA SABANA FACULTAD DE INGENIERIA, INGENIERIA INDUSTRIAL INVESTIGACIÓN DE OPERACIONES CHIA, COLOMBIA Lunes, 09 de Febrero de 2004

“SOLUCIÓN DE UN PROBLEMA DE ASIGNACIÓN DE HORARIOS DE MANTENIMIENTO EN MÁQUINAS, EQUIPOS E INSTALACIONES A LA EMPRESA POWEL CONTINENTAL Ltda. MEDIANTE LA PROGRAMACIÓN DE UN ALGORITMO GENÉTICO”

JORGE ALBERTO OSPINA FALLA RAFAEL RICAURTE BERNAL

Tesis de grado

Directores: JUAN CARLOS VILLAMIZAR MARIA MARGARITA CERVANTES

UNIVERSIDAD DE LA SABANA FACULTAD DE INGENIERIA, INGENIERIA INDUSTRIAL INVESTIGACIÓN DE OPERACIONES CHIA, COLOMBIA Lunes, 09 de Febrero de 2004

2

DEDICATORIA Este trabajo está dedicado a nuestros padres quienes nos brindaron todo su apoyo y comprensión durante el desarrollo de nuestras carreras y quienes fueran ejemplo de vida para nosotros.

3

RESUMEN EJECUTIVO Esta tesis propone obtener un cronograma para las actividades de mantenimiento preventivo mediante el uso de un algoritmo genético con el fin de optimizar el tiempo y costo del personal destinado a la labor de mantenimiento y cumplir con los requerimientos de mantenimiento preventivo de cada máquina, equipo e instalación en la empresa Powel Continental LTDA. La empresa Powel Continental LTDA. es una empresa dedicada a la fabricación de filtros de aire, aceite y combustible. Cuenta actualmente con 26 máquinas distribuidas por los diversos departamentos de la empresa, cada máquina cuenta con características propias de funcionamiento y de desgaste de piezas, además de tener en cuenta las exigencias para el mantenimiento preventivo en la empresa Powel Continental LTDA. dependiendo del modelo y tipo de máquina entre ellas Desgaste de piezas, Tiempo sin mantenimiento, Importancia en la producción, Cantidad de hombres / hora, Distribución de la maquinaria, Usuario responsable, Seriedad del operario y manejo que este le da a la máquina para un buen funcionamiento y con el menor desgaste posible, entre otras. Los Algoritmos Genéticos buscan generar soluciones de poblaciones que al infinito tiendan a una solución real al problema que se plantea. Durante el planteamiento y desarrollo del problema se plantearon las técnicas de los algoritmos genéticos buscando el mejor para este tipo de problema, y que en la practica resulta ser un problema de ordenamiento con múltiples restricciones; seguido del planteamiento del problema se desarrolló un programa en un lenguaje de programación (Visual Basic) para probar los resultados. Se encontró así, el mejor método de selección, cruce y mutación logrando llegar a una solución. Como los Algoritmos Genéticos operan con probabilidades de cruce y mutación que generan diferentes soluciones y varían considerablemente en su tiempo de ejecución, fue necesario entonces probar el programa para diferentes probabilidades logrando una enorme población de soluciones con diferentes parámetros en cada solución, se utiliza entonces el método de muestreo y métodos estadísticos para encontrar el modelo más eficiente que supla las necesidades de optimización en el menor tiempo posible. Se logra así entonces un modelo de Algoritmo Genético que cumple con los parámetros establecidos de evolución y proporciona una solución muy real y satisfactoria para el mantenimiento de maquinaria, equipos e instalaciones a la empresa Powel Continental LTDA. Los resultados de esta técnica muestran la factibilidad de un algoritmo genético para la optimización de un horario de mantenimiento preventivo.

4

ABSTRACT

In this thesis the results appear of applying a genetic algorithm, to organize a schedule of preventive maintenance in the company Powel continental S.A. consider own factors of each machine, such as the location, wearing down of pieces, time without maintenance, importance in the production, amount of men/hour, distribution of the machinery, number of machines, responsible user, among others. The Genetic Algorithms look for to generate populations that to the infinite tend to a real solution to the problem that considers. During the exposition and development of the problem the techniques of the genetic algorithms considered looked for the best one for this kind of problem, that in practices it turns out to be a problem of ordering with multiple restrictions; By means of the design of a software that the exposition of the problem in computacional language Visual Basic models, tests were developed to the model and by means of statistical techniques were the best parameters in those than the genetic Algorithm works being the obtained results very satisfactory.

5

CONTENIDO 1.

MARCO TEORICO .................................................................................................. 15 1.1 MANTENIMIENTO................................................................................................ 15 1.1.1 Ventajas del Mantenimiento Preventivo: ......................................................... 15 1.2 COMPUTACIÓN EVOLUTIVA ............................................................................ 16 1.3 ALGORITMOS GENÉTICOS ................................................................................ 17 1.3.1 Componentes de los algoritmos genéticos ................................................... 17 1.3.2 Cómo saber si es posible aplicar un algoritmo genético.............................. 18 1.3.3 Parámetros de los algoritmos genéticos ....................................................... 19 1.3.4 Elementos básicos de un algoritmo genético ............................................... 19 1.3.5 Codificación ................................................................................................. 20 1.3.5.1 Binaria .......................................................................................................... 20 1.3.5.2 Codificación mediante valores reales y caracteres....................................... 20 1.3.6 Método de selección..................................................................................... 21 1.3.6.1 Ruleta ........................................................................................................... 21 1.3.6.2 Escalamiento Sigma ..................................................................................... 21 1.3.6.3 Elitista .......................................................................................................... 22 1.3.6.4 Selección por rango...................................................................................... 22 1.3.6.5 Selección por torneo..................................................................................... 22 1.3.7 Cruce ............................................................................................................ 23 1.3.7.1 Cruce de punto simple.................................................................................. 23 1.3.7.2 Cruzamiento de dos puntos .......................................................................... 23 1.3.7.3 Cruce de parametrización uniforme ............................................................. 23 1.3.8 Mutación ...................................................................................................... 23 1.4 IMPLEMENTACIÓN DE UN ALGORITMO GENÉTICO................................... 24 2. SITUACIÓN ACTUAL DE LA EMPRESA ........................................................... 25 2.1 HISTORIA ............................................................................................................... 25 2.2 PROCESO DE FABRICACIÓN Y DESCRIPCIÓN DEL PROCESO .................. 25 2.3 PROCESO DE MANTENIMIENTO EN POWEL CONTINENTAL LTDA. ....... 26 2.4 CARACTERÍSTICAS DE LAS MÁQUINAS........................................................ 27 2.5 DEFINICIÓN DEL PROBLEMA. .......................................................................... 33 2.6 VARIABLES RELEVANTES ................................................................................ 36 3. SOLUCIÓN AL PROBLEMA.................................................................................. 38 3.1 COMPARACIÓN CON EL SISTEMA DE EVALUACIÓN DE TODAS LAS POSIBLES SOLUCIONES ............................................................................................. 38 3.2 MODELACIÓN DE UN ALGORITMO GENÉTICO PARA EL ÁREA DE MANTENIMIENTO EN LA EMPRESA POWEL CONTINETAL LTDA................... 38 3.3 CADENA GENÉTICA Y ALGORITMO GENÉTICO PROPUESTO .................. 39 3.3.1 Codificación del problema para un algoritmo genético ............................... 39 3.3.1.1 Codificación mediante valores reales, enteros o caracteres ......................... 39 3.3.1.2 Ejemplo 1 (codificación).............................................................................. 39 3.3.2 Funciones decodificación y objetivo........................................................... 41

6

3.3.2.1 Función decodificación ................................................................................ 41 3.3.2.2 Ejemplo 2 (Función decodificación)............................................................ 42 3.3.2.3 Función objetivo .......................................................................................... 44 3.3.2.4 Ejemplo 3 (Función Objetivo) ..................................................................... 44 3.3.2.5 Ejemplo 4 (función decodificación y función objetivo) .............................. 46 3.3.3 Método de selección..................................................................................... 50 3.3.3.1 Ejemplo 5 (Torneo y elitismo) ..................................................................... 50 3.3.4 Operadores genéticos ................................................................................... 53 3.3.4.1 Ejemplo 6 (Cruce) ........................................................................................ 54 3.3.4.2 Mutación ...................................................................................................... 56 3.3.4.3 Ejemplo 6 (Mutación) .................................................................................. 56 3.4 ALGORTMO GENÉTICO GENERAL .................................................................. 58 4. ANÁLISIS DE RESULTADOS ................................................................................ 60 4.1 PRUEBAS PRELIMINARES.................................................................................. 60 4.2 PRUEBAS FINALES .............................................................................................. 60 4.3 METODOLOGÍA UTILIZADA.............................................................................. 62 4.4 RESULTADOS OBTENIDOS ................................................................................ 63 4.4.1 Mínimo de generaciones .............................................................................. 63 4.4.2 Tamaño población........................................................................................ 64 4.4.3 Probabilidad de cruce................................................................................... 66 4.4.4 Probabilidad de mutación............................................................................. 67 4.5 PARÁMETROS EN LOS QUE MEJOR FUNCIONA EL PROGRAMA DE ALGORITMOS GENÉTICOS EN MANTENIMIENTO Y SOLUCION ARROJADA 67 4.6 UTILIZACIÓN DEL PROGRAMA CON LAS CARACTERÍSTICAS DE LA EMPRESA POWEL CONTINENTAL LTDA................................................................ 69 5. CONCLUSIONES Y RECOMENDACIONES....................................................... 72 6. BIBLIOGRAFIA ............................................................................................................... 74 Anexo A ............................................................................................................... 76 Anexo B ............................................................................................................... 87 Anexo C ............................................................................................................... 92

7

LISTA DE TABLAS Pág. Tabla 1.

Cronograma actual

35

Tabla 2.

Tabla de información 1

42

Tabla 3.

Tabla de decodificación

43

Tabla 4.

Tabla de información 2

45

Tabla 5.

Tabla de decodificación 2

45

Tabla 6.

Características de las máquinas

47

Tabla 7.

Función decodificación

49

Tabla 8.

Características de las máquinas 2

49

Tabla 9.

Tabla de decodificación 3

49

Tabla 10.

Ejemplo de aptitud

51

Tabla 11.

Ejemplo de aptitud 2

51

Tabla 12.

Ejemplo de aptitud 3

52

Tabla 13.

Ejemplo de aptitud 4

53

Tabla 14.

Ejemplo Pmuta

57

Tabla 15.

Parámetros recomendados

68

Tabla 16.

Resultados

70

8

LISTA DE FIGURAS

Pág. Figura 1.

Proceso de fabricación

25

Figura 2.

Vector evaluación

45

Figura 3.

Función objetivo

48

Figura 4.

Variación de la aptitud

59

Figura 5.

Características de las máquinas

61

Figura 6.

Ingreso de datos en el programa

68

Figura 7.

Horario

69

Figura 8.

Horario de mantenimiento en Powel Continental Ltda..

70

9

LISTA DE ANEXOS Pág. Anexo A.

76

Anexo B.

87

Anexo C.

92

10

JUSTIFICACIÓN El mantenimiento de maquinaria y equipos constituye una parte esencial en el buen comportamiento económico de Powel Continental Ltda., se pretende satisfacer las necesidades de mantenimiento de los procesos productivos incurriendo en los mínimos costos posibles. Debido a que dentro de su programa de mantenimiento de maquinaria y equipos, se debe considerar las exigencias de cada máquina y optimizar el tiempo del personal destinado para esta labor, se convierte éste en un problema complejo para la empresa. El mantenimiento de maquinaria, equipos e instalaciones como problema de toma de decisiones y de organización, pretende suministrar el nivel de existencias que permita minimizar los costos implicados en las mismas. Diariamente en la empresa se presentan problemas debido a la falta de mantenimiento o mantenimiento no oportuno del equipo de trabajo, las principales consecuencias de la falta de mantenimiento son: ¾ ¾ ¾ ¾ ¾

Demora en los tiempos de entrega Altos costos Reprocesamiento de productos Insatisfacción de los clientes Daño en las máquinas, por el excesivo desgaste de las piezas

También existen factores que intervienen en la realización de un mantenimiento de maquinaria y equipos, los cuales pueden afectar de una u otra forma la efectividad en dinero, tiempo y rendimiento de éste, las principales variables o factores a considerar y analizar son: Distribución de la maquinaria y equipos Número de maquinarias y equipos Características propias de cada máquina, equipo o instalación Desgaste de las piezas Tiempo sin mantenimiento Importancia en la producción de la empresa de acuerdo al plan maestro de producción ¾ Cantidad de horas-hombre para realizar el mantenimiento ¾ Usuario responsable de la maquinaria

¾ ¾ ¾ ¾ ¾ ¾

Estos factores se traducen principalmente en altos costos para la empresa y la asignación de horarios de mantenimiento son problemas de difícil solución

11

mediante métodos estocásticos, computacionales tradicionales.

y

de

alta

complejidad

para

sistemas

El planteamiento de horarios y distribución de tareas son en la realidad problemas de optimización combinatoria (selección del mejor horario entre diferentes combinaciones). Estas son tareas difíciles de ser resueltas computacionalmente, la mayor dificultad está en que estos procesos procuran fijar el máximo de tareas en un tiempo limitado, usando una cantidad de recursos fija, haciendo que el espacio de búsqueda de posibles soluciones sea muy grande y compleja, dando como resultado en la mayoría de las ocasiones soluciones optimas que se encuentran en un máximo o mínimo local.

12

OBJETIVOS Objetivo general ¾ Obtener un cronograma para las actividades de mantenimiento mediante el uso de AGS con el fin de optimizar el tiempo y costo del personal destinado para esta labor y cumplir con los requerimientos de mantenimiento de cada máquina, equipo e instalación. Objetivos específicos ¾ Determinar las variables relevantes del problema de mantenimiento en la empresa. ¾ Desarrollar las funciones de decodificación y evaluación de los individuos. ¾ Generar un modelo de programación computacional que simulen mediante el uso de un AGS los planteamientos de horarios y distribución de tareas de mantenimiento en maquinarias y equipos para una línea de producción. ¾ Probar el algoritmo con los requerimientos de mantenimiento de Powel Continental. ¾ Entregar el cronograma de mantenimiento preventivo para ser usado en la empresa.

13

INTRODUCCIÓN Si nos ubicamos al inicio de un turno en un centro de trabajo cualquiera, desde donde el personal operativo atiende el mantenimiento, encontramos que en su mayoría la labor del personal se divide en dos grandes tareas día a día, corregir las fallas (mantenimiento correctivo) y eliminar las causas que puedan originar una falla (mantenimiento preventivo). La ocurrencia de fallas, de la magnitud que estas sean, provocan demoras en las líneas de producción y desperfectos en los productos, por lo tanto la prioridad es atenderlas. Lógicamente, a mayor número de fallas, es necesario desviar mayor personal del mantenimiento preventivo hacia el mantenimiento correctivo. De esta forma, las fallas continúan surgiendo, por lo que es sumamente difícil llevar a cabo el trabajo programado de mantenimiento preventivo. Finalmente, el cumplimiento de los programas de producción y el mejoramiento de la calidad son los objetivos que requieren del mayor esfuerzo, pero, ¿se está cumpliendo con este objetivo? Este es el punto de partida en la búsqueda de nuevos métodos. Por tal razón se enfocará la atención en los algoritmos genéticos como disciplina para auxiliar a la empresa Powel Continental Ltda., en la optimización de sus ciclos de mantenimiento con el fin de minimizar el horario de mantenimiento para lograr así ampliar los tiempos de producción. Permitiendo a los tomadores de decisiones de la empresa probar sus hipótesis en un ambiente libre de riesgo, capturar el conocimiento de los expertos en el área de mantenimiento y transmitir dicho conocimiento al resto de la empresa con un lenguaje sencillo y claro, identificar las variables que más influencia tienen en el proceso de mantenimiento e identificar los costos de cada decisión, así como las consecuencias adicionales que cada una de ellas acarrea en los programas de producción.

14

1. MARCO TEORICO 1.1

MANTENIMIENTO

La programación de inspecciones, tanto de funcionamiento como de seguridad, justes, reparaciones, análisis, limpieza, lubricación, calibración, que deben llevarse a cabo en forma periódica en base a un plan establecido y no a una demanda del operario o usuario. Su propósito es prever las fallas manteniendo los sistemas de infraestructura, equipos e instalaciones productivas en completa operación a los niveles y eficiencia optimos. La característica principal de este tipo de Mantenimiento es la de inspeccionar los equipos, y las máquinas y detectar las fallas en su fase inicial, y corregirlas en el momento oportuno. Con un buen mantenimiento preventivo, se obtiene experiencias en la determinación de causas de las fallas repetitivas o del tiempo de operación seguro de un equipo, asi como a definir puntos débiles de instalaciones, máquinas, etc. 1.1.1

Ventajas del Mantenimiento Preventivo:

•

Confiabilidad, los equipos operan en mejores condiciones de seguridad, ya que se conoce su estado, y sus condiciones de funcionamiento.

•

Disminución del tiempo muerto, tiempo de parada de equipos/máquinas.

•

Mayor duración, de los equipos e instalaciones.

•

Disminución de existencias en Almacén y, por lo tanto sus costos, puesto que se ajustan los repuestos de mayor y menor consumo.

•

Uniformidad en la carga de trabajo para el personal de Mantenimiento debido a una programación de actividades.

•

Menor costo de las reparaciones.

15

1.2

COMPUTACIÓN EVOLUTIVA

El origen de lo que se conoce como computación evolutiva, es decir, el estudio de los fundamentos y aplicaciones de ciertas técnicas heurísticas de búsqueda basadas en los principios naturales de la evolución. Fue en las décadas de 1950 y 1960 cuando varios científicos, de modo independiente, comenzaron a estudiar los sistemas evolutivos, guiados por la intuición de que se podrían emplear como herramienta en problemas de optimización en ingeniería. La idea era evolucionar una población de candidatos a ser solución de un problema conocido, utilizando operadores inspirados en la selección natural y la variación genética natural. introdujo las “estrategias Fue Rechenberg quien, en la década de 1960 evolutivas”, método que empleó para optimizar parámetros reales para ciertos dispositivos. La misma idea fue desarrollada posteriormente por Schwefel (1975, 1977). El campo de las estrategias evolutivas ha permanecido como un área de investigación activa, cuyo desarrollo se produce, en su mayor parte, de modo independiente al de los algoritmos genéticos (aunque recientemente se ha visto como las dos comunidades han comenzado ha colaborar). Fogel, Owens y Walsh (1966), fueron los creadores de la programación evolutiva, una técnica en la cual las candidatas a soluciones a tareas determinadas, eran representadas por máquinas de estados finitos, cuyos diagramas de estados de transición se evolucionaban mediante mutación aleatoria, seleccionándose el que mejor aproximara. Una formulación más amplia de la programación evolutiva, es un campo de investigación que también continúa en activo. Estas tres áreas, estrategias evolutivas, algoritmos genéticos, y programación evolutiva, son las que forman la columna vertebral de la Computación Evolutiva, y de ellas parten los caminos hacia todos los campos de investigación inspirados en nuestros conocimientos sobre Evolución. Pero muchos otros investigadores desarrollaron su trabajo en los algoritmos para la optimización y el aprendizaje inspirados en la evolución. Sin embargo, su trabajo no ha tenido, ni con mucho, la atención que han recibido las estrategias evolutivas, programación evolutiva, y los algoritmos genéticos. Pero habría que esperar hasta que la computación electrónica se desarrollara, para poder apreciar la consolidación definitiva de la computación evolutiva. fuente: E.T.S. Ingeniería Informática - Universidad de Valladolid 2003

16

1.3

ALGORITMOS GENÉTICOS

Los algoritmos genéticos (AGs) fueron introducidos por John Holland en 1970, son métodos heurísticos de búsqueda y optimización utilizados en muchas disciplinas, tales como optimización combinatoria, aprendizaje de máquinas, procesamiento de imágenes, entre otros. Estos son inspirados en el proceso evolutivo de los seres vivos. El Algoritmo Genético de Holland era un método para desplazarse, de una población de cromosomas (bits) a una nueva población, utilizando un sistema similar a la “selección natural” junto con los operadores de cruces, mutaciones e inversión inspirados en la genética. En este primitivo algoritmo, cada cromosoma consta de genes (bits), y cada uno de ellos es una muestra de un alelo particular (0 o 1). El operador de selección escoge, entre los cromosomas de la población, aquellos con capacidad de reproducción, y entre éstos, los que sean más compatibles, producirán más descendencia que el resto. El de cruce extrae partes de dos cromosomas, imitando la combinación biológica de dos cromosomas aislados (gametos). La mutación se encarga de cambiar, de modo aleatorio, los valores del alelo en algunas localizaciones del cromosoma; y, por último, la inversión, invierte el orden de una sección contigua del cromosoma, reposicionando por tanto el orden en el que se almacenan los genes. La mayor innovación de Holland fue la de introducir un algoritmo basado en poblaciones con cruces, mutaciones e inversiones. Es más, Holland fue el primero en intentar colocar la computación evolutiva sobre una base teórica firme. Hasta hace poco, esta base teórica, fundamentada en la noción de esquemas, fue la estructura sobre la que se edificaron la mayoría de los trabajos teóricos sobre algoritmos genéticos en las décadas siguientes. "Se pueden encontrar soluciones aproximadas a problemas de gran complejidad computacional mediante un proceso de evolución simulada" Dado que el algoritmo genético opera con una población en cada iteración, se espera que el método converja de modo que al final del proceso la población sea muy similar, y en el infinito se reduzca a un sólo individuo, el cual proporcionará la respuesta óptima al problema. 1.3.1 Componentes de los algoritmos genéticos En general es aceptado que cualquier algoritmo genético para resolver un problema, debe tener cinco componentes básicos como se verá a continuación

17

1. Se necesita una codificación o representación del problema, que resulte adecuada al mismo. 2. Una manera de crear una población inicial de soluciones 3. Una función de ajuste ó adaptación al problema, también llamada función de evaluación, la cual asigna un número real a cada posible solución codificada. 4. Durante la ejecución del algoritmo, los padres (dos individuos pertenecientes a la población inicial, que son soluciones factibles del problema) deben ser seleccionados para la reproducción; a continuación dichos padres seleccionados se cruzarán generando dos hijos, nuevas soluciones al problema, sobre cada uno de los cuales actuará un operador de mutación de acuerdo con una cierta probabilidad. El resultado de la combinación de las anteriores funciones será un conjunto de individuos (posibles soluciones al problema), los cuales en la evolución del algoritmo genético formarán parte de la siguiente población. 5. Valores para los parámetros: tamaño de la población, probabilidad de aplicación de los operadores genéticos, probabilidad de cruce, probabilidad de mutación, entre otras. 1.3.2 Cómo saber si es posible aplicar un algoritmo genético La aplicación más común de los AGs ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla: ¾ Su espacio de búsqueda debe estar delimitado dentro de un cierto rango conocido. ¾ Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta. ¾ Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora. El primer punto es muy importante, y lo más recomendable es intentar resolver problemas que tengan espacios de búsqueda discretos, aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de

18

búsqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente pequeño. 1.3.3 Parámetros de los algoritmos genéticos Para identificar más apropiadamente las diferencias entre un AG y la naturaleza que faciliten la identificación, a continuación se muestra la analogía que puede existir entre un algoritmo genético y la naturaleza La analogía entre un AG y la naturaleza AG

Naturaleza

Palabra, número, vector, etc. Características del problema Valor de la característica Posición en la palabra Estructura Solución Ciclo Fuente los autores

Cromosoma Gen Alelo Locus Genotipo Individuo Generación

1.3.4 Elementos básicos de un algoritmo genético Simular un proceso evolutivo en una computadora mediante un algoritmo genético se requiere: • • • • • •

Codificar un espacio de posibles soluciones. Un mecanismo adecuado de selección de individuos. Operaciones que afecten a los “individuos” (operadores genéticos). Recombinación o cruce de individuos Mutación de individuos nuevos Una función de aptitud o función objetivo

Antes de aplicar el algoritmo debemos fijar una serie de parámetros de los cuales dependerá la eficiencia y convergencia del algoritmo. •

a = Número de alelos; en nuestro caso la mayoría de veces representaremos los individuos como cadenas enteras x= 1,2,3,...,26 elementos

19

•

w = Longitud de los individuos. Hemos de decidir cómo codificar el espacio de soluciones y por tanto cuál será la longitud de los cromosomas. De 26 espacios.

•

n = Tamaño de la población, con tamaños de población fijos; todas las poblaciones generadas tendrán ese tamaño.

•

m = Número de generaciones

•

Pr = Probabilidad de que las parejas seleccionadas se recombinen.

•

Pi = Probabilidad de mutación de un alelo

•

Fdecode = Función decodificación o decodificadora para evaluar el individuo

•

F(x) = Importancia de la máquina en la producción, de aptitud, o función Objetive

1.3.5 Codificación La codificación de los individuos es una parte muy importante en un algoritmo genético, existen diferentes tipos, entre ellos los siguientes: 1.3.5.1

Binaria

Es la más común por una serie de razones, histórica ya que Holland comenzó sus practicas con AGs empleando heurísticas sobre la asignación de los parámetros apropiados empleando la codificación binaria. Aunque la codificación binaria es poco natural y pesada en muchos problemas. 1.3.5.2

Codificación mediante valores reales y caracteres

Para muchas aplicaciones es más natural usar múltiples caracteres de un alfabeto o números reales para formar los individuos. En contra de la afirmación de Holland, que afirmaba que el comportamiento de la codificación con múltiples caracteres era peor que la de una codificación binaria, actualmente no hay un método que nos guíe sobre que codificación será la mejor. Para este caso en particular se recomienda la codificación mediante valores reales, para generar la cadena genética.

20

1.3.6 Método de selección Después de realizar la función decodificación y la función objetivo para encontrar la aptitud de cada individuo, el siguiente paso es como realizar la selección, que es como elegir los individuos de una población para crear los descendientes de la siguiente. 1.3.6.1

Ruleta

La selección es proporcional a la aptitud, en la cual el “valor esperado” se calcula dividiendo la aptitud del individuo entre el promedio de la aptitud de toda la población. A cada individuo se le asigna un sector de la rueda proporcional a su aptitud. Grafico 1. Diagrama de la ruleta

fuente: los autores. La rueda esta dividida en N partes, siendo N el número de individuos de la población. Sobre esta ruleta se implementa el método de elección de los padres de la siguiente generación. Se selecciona al azar dos regiones de la ruleta y esos será los individuos seleccionados. 1.3.6.2

Escalamiento Sigma

Forrest 1985, y fue llamado truncamiento sigma en Goldberg 1989, en esta estrategia el valor esperado de los individuos es función de su aptitud, la media de la población y de su desviación estándar. los individuos más saludables destacaran más, permitiendo que la evolución continúe.

21

1.3.6.3

Elitista

Introducido inicialmente por Kenneth De Jong(1975), es una adición a muchos Métodos de selección que fuerzan a los AG a mantener algún número de los mejores elementos de cada generación. Tales individuos pueden perderse si no son seleccionados para reproducir o si se destruyen por los operadores de mutación o cruzamiento. Muchas investigaciones han encontrado que el elitismo mejora significativamente el comportamiento de los AG. 1.3.6.4

Selección por rango

Es un método alternativo cuyo propósito es el de prevenir la convergencia demasiado rápida. Los individuos de la población son clasificados en función de su aptitud y el valor esperado de cada individuo depende de este rango más que del valor absoluto de su aptitud. El utilizar el valor relativo de la aptitud en lugar del valor absoluto puede tener ventajas: usar el valor absoluto puede tener problemas de convergencia. Desventajas: en algunos caso podría ser interesante conocer de un individuo cuanto más apto con respecto a su competidor más cercano. Este método trata de disminuir la presión de selección de los individuos cuando la variación en la aptitud en la población es elevada, y aumentar esa presión cuando la variación es baja. 1.3.6.5

Selección por torneo

Los métodos vistos anteriormente requieren dos fases, una es calcular la aptitud y el otro el valor esperado de cada individuo. Incluso en el de rango requiere una ordenación de la población entera por rango. La selección por torneo es similar a la selección por rango en términos referidos a la presión para seleccionar, pero computacionalmente es más eficiente y más fácil de paralelizar. Dos individuos son elegidos al azar de la población, un número aleatorio r es elegido entre 0 y 1. Si r es menor que k (fijado por el usuario) el más apto de los dos individuos es seleccionado para ser padre. En caso contrario es seleccionado el menos apto. Se puede elegir el mismo padre varias veces. El método que se plantea para la solución al problema de asignación de horarios de mantenimiento de la empresa Powel Continental LTDA. es el de Torneo, puesto que es el más recomendado porque la función objetive arroja que el mejor individuo es el de menor aptitud, sin dejar a un lado el elitismo para garantizar que el mejor de la población siga presente en la siguiente población.

22

1.3.7 Cruce Los diferentes tipos de cruce, especialmente los más utilizados son: 1.3.7.1

Cruce de punto simple

El cruzamiento de punto simple es la forma más sencilla: consiste en elegir un número Cr aleatorio entre uno y el tamaño de la cadena genética. A continuación se intercambia la parte de los dos padres posterior al punto de cruce para formar dos descendientes. La idea es recombinar diferentes bloque de construcción en diferentes cadenas. Un problema, es que este método no permite combinar todos los posibles esquemas. 1.3.7.2

Cruzamiento de dos puntos

En el cual dos posiciones son elegidas al azar y entre ambas se intercambian los valores de la cadena. Con el cruzamiento de dos puntos es más difícil que se rompan esquemas con definición de longitud larga y puede combinar más esquemas que el punto simple. Además el segmento que es intercambiado no tiene por que ser la parte final de la cadena, solucionando el problema del punto final. De nuevo hay esquemas que el cruzamiento de dos puntos no puede combinar. 1.3.7.3

Cruce de parametrización uniforme

Spears y De Jong (1991) creyeron fuertemente en la superioridad del “cruzamiento de parametrización uniforme” en la cual un intercambio ocurre en cada posición de la cadena con probabilidad Pcadena 1.3.8 Mutación Consiste en examinar cada alelo o espacio del individuo de cada cadena cuando se vaya a crear el nuevo descendiente a partir de sus padres simultáneamente al cruzamiento. Si un número generado aleatoriamente está por debajo de esa probabilidad, se cambiará el alelo (es decir, de 1 a w. Si no, se dejará como está. Según Holland, “el cruzamiento es el mejor instrumento para la innovación y la variación en los algoritmos genéticos, con la mutación aseguramos la población contra la fijación permanente en alguna posición particular y así jugar en más de un rol de fondo”.

23

1.4

IMPLEMENTACIÓN DE UN ALGORITMO GENÉTICO

Este problema está condicionado a las restricciones, y en donde se busca una secuencia apropiada para realizar el mantenimiento preventivo con el menor costo posible, que lo convierte en un problema de orden y distribución de horario. No existe actualmente un método para determinar si es bueno o no utilizar un algoritmo genético, pero no es recomendado cuando: •

El espacio de soluciones no es muy grande, se puede realizar una busqueda exhaustiva y esto nos garantiza que la mejor solución es encontrada, mientras que un AG puede converger en un máximo ó mínimo local y no obtener la solución óptima.

•

Si el espacio es continuo, se podría emplear un algoritmo de gradiente ascendente, de tal modo que accede a la solución de forma más eficiente que un AG.

El comportamiento de un AG dependerá mucho de detalles tales como el método de codificación de los candidatos solución, los operadores, los parámetros y el criterio de éxito. En el caso de Powel Continental LTDA. el número exacto de soluciones consiste en un modelo estadístico de combinación que desarrolle todas las posibles combinaciones de las máquinas, equipos o instalaciones y que luego sean evaluadas para encontrar la solución absoluta. Puesto que el espacio de búsqueda es tan grande, alrededor de 26! (Factorial del número de máquinas) no es conveniente computacionalmente ni por tiempo realizarlo de esta forma, por lo que un algoritmo genético reduciría el tiempo de computo y podría obtener una solución apropiada para el problema.

24

2. SITUACIÓN ACTUAL DE LA EMPRESA 2.1

HISTORIA

Powel Continental Ltda. fue fundada en el año 1973, viendo la necesidad de fabricar filtros sellados para los motores de combustión interna, debido a que las importaciones de este tipo de repuestos eran escasas y la demanda interna aumentaba constantemente. Originalmente se creó como una empresa productora de partes para filtros, específicamente las carcasas en lámina de acero tipo cold rolled las cuales eran vendidas a las diferentes empresas ensambladoras de filtros sellados, pero pronto se convirtió en fabricante de filtros sellados para aceite y combustible como también filtros para aire. En el año de 1980 dichas empresas iniciaron gestiones para la importación de prensas hidráulicas maquinaria utilizada en la fabricación de estas carcasas, esto obligó a la empresa a pensar en fabricar la totalidad del filtro para lo cual se cambio de razón social denominándose Powel Continental Ltda. y teniendo como objeto social la fabricación y distribución de filtros automotores, en esta etapa se adquirieron diversas máquinas importadas principalmente de Alemania y España como también se desarrollaron y construyeron otras que por ser de aplicaciones específicas no existían en el mercado. 2.2

PROCESO DE FABRICACIÓN Y DESCRIPCIÓN DEL PROCESO

Figura 1. Proceso de fabricación Embutición

Entrada de materia

Troquelado Piezas Externas Troquelado Piezas Internas Plisado

fuente: Powel Continental Ltda.

25

Soldado Y Roscado

Subensamble

Ensamble Alistamiento Y Despacho

El proceso se inicia con la recepción, revisión y aceptación de la materia prima la cual se divide en dos grandes grupos, el primero son las materias primas metálicas específicamente láminas de acero tipo cold rolled, y el segundo grupo esta compuesto por el papel filtrante. Una vez realizado este paso se procede a cortar las láminas de acero en tiras, para posteriormente enviarlas a las zonas de embutido y troquelado, en el proceso de embutido se toma una pieza de acero la cual es sometida a un proceso de estiramiento y deformación mediante el uso de prensas hidráulicas las cuales ejercen presión muy lentamente sobre el material y le permiten a este tomar forma de vaso, en el proceso de troquelado al igual que en el embutido se forma el acero de acuerdo a las distintas necesidades pero la diferencia radica en el uso de troqueladoras las cuales proporcionan al material un golpe más rápido el cual le permite además de cambiarle la forma al material abrirle, orificios que son necesarios para el correcto funcionamiento de dichas piezas. Estas piezas se pasan posteriormente a un proceso de roscado. Paralelamente se realiza el proceso de plisado del papel filtrante, el cual consiste en tomar los rollos de papel cortarlos para luego realizarles dobleces en forma de acordeón según las especificaciones técnicas de la referencia que se desee fabricar. Teniendo estos dos grupos se pasa al ensamble donde se une el papel filtrante a las piezas troqueladas, después de esto se toma este conjunto y se pasa a la parte de ensamble donde se da la forma final al filtro y se incorpora este conjunto con las carcasas. Luego se pinta el filtro, se le agregan los empaques de caucho se sellan con un termoplástico se empacan en cajas de cartón y se pasan al almacén de producto terminado. 2.3

PROCESO DE MANTENIMIENTO EN POWEL CONTINENTAL LTDA.

El mantenimiento se realiza principalmente en los meses de diciembre a enero que son los meses de mayor demanda y por lo tanto se hace casi imposible parar las máquinas para hacerles el mantenimiento respectivo. Esto trae problemas serios como la interrupción de los programas de producción y genera tiempos ociosos en los operarios de dichas máquinas. Por estas razones la empresa ha querido estudiar diversas posibilidades en la planeación de su mantenimiento preventivo para lo cual se plantea y se quiere evaluar como una posible distribución de horarios realizar el mantenimiento en un lapso de tiempo no mayor a 6 semanas. Durante estos días se realizará un mantenimiento preventivo a las máquinas que salgan seleccionadas mediante la aplicación del programa, pero se tendrá en cuenta que estos mantenimientos no produzcan demoras en la producción.

26

2.4

CARACTERÍSTICAS DE LAS MÁQUINAS

En la empresa se pueden clasificar las máquinas en doce grupos o tipos diferentes de acuerdo con las especificaciones y funciones de cada una de ellas, es por esto que se encuentran agrupadas las veintiséis máquinas (por cumplir con funciones similares, más no iguales) de la siguiente manera. Dentro del proceso de producción que se describe en 2.1.1 Proceso de fabricación y descripción del proceso se encuentran los siguientes tipos de máquinas y equipos: Grupo 1

Máquina # 1

Cizalla: esta máquina es utilizada para cortar las láminas de acero en tiras con el propósito de alimentar los otros procesos, es una máquina clave dentro del proceso ya que es la que da inicio a este. Tiene un tiempo de mantenimiento de 3 horas ¾ Cizallas

Foto 1 Grupo 2 Máquinas # 2 y 3 Prensas hidráulicas: la empresa cuenta en el momento con dos prensas, cuya función es hacer embutidos profundos para sacar las carcasas de los filtros, estas prensas son de características similares y tiene la ventaja de poderse suplir una a la otra con lo cual se minimiza la posibilidad de interrupciones en la producción. Tiempo de mantenimiento 4 y 2 horas respectivamente.

27

¾ Prensas hidráulicas para embutido profundo.

Foto 2 Grupo 3

Máquinas # 4, 5 y 6

Troqueladoras de volante: la empresa cuenta con tres máquinas de este tipo dos de las cuales son de características similares y la otra es de una capacidad (presión) mayor. Tiempo de mantenimiento 2, 4 y 4 horas respectivamente. ¾ Troqueladoras de volante y de puente

Foto 3

28

Grupo 4 Máquinas # 7, 8, 9 y 10 Troqueladoras de puente: se cuenta con dos parejas de troqueladoras para todo el proceso y cada una puede llegar a suplir las funciones de su pareja. Tiempo de mantenimiento 2 horas para las máquinas 7 y 8, 3 horas para las máquinas 9 y 10.

Grupo 5 Máquinas # 11 y 12 Plisadoras: se cuenta con dos plisadoras cuyas funciones son cortar el papel en las alturas requeridas y realizarle unos dobleces en forma de acordeón. Tiempo de mantenimiento 3 y 4 horas respectivamente. ¾ Plisadoras

Foto 4

29

Grupo 6

Máquinas # 13, 14, 15 y 16

Soldadores: se cuenta con dos tipos de soldadores, el primer tipo son soldadores de punto los cuales son utilizados para unir las piezas internas (tapa y disco) este grupo posee tres soldadores. Cada uno capas de suplir las funciones de los otros. Tiempo de mantenimiento 4 horas para las máquinas 13 y 14, 3 horas para la máquina 15 y 1 hora para la máquina 16. ¾ Soldadores

Foto 5 Grupo 7 Máquinas # 17 y 18 Roscadores: se cuenta con dos roscadores de características diferentes pero capaces de suplir cada uno las funciones del otro. Tiempo de mantenimiento 2 y 1 horas respectivamente. ¾ Rascadores

Foto 6

30

Grupo 8 Máquinas # 19 y 20 Serradoras: estas máquinas son las encargadas de sellar el filtro, unen la carcasa con la tapa inferior del filtro, su desempeño es de vital importancia puesto que no se pueden presentar fugas en el cierre debido a que estas fugas producen el daño de los motores. Tiempo de mantenimiento 1 y 3 horas respectivamente. ¾ Serradoras de carretes y probadores de cierre

Foto 7

Grupo 9 Máquina # 21 Probador: mediante el uso de esta máquina se determina la calidad del sellado, estas pruebas se realizan a todos los filtros antes de pasar a pintura es prioridad dentro del proceso ya que no hay otra máquina que la pueda reemplazar en caso de que llegue a fallar. Tiempo de mantenimiento 3 horas.

31

Grupo 10 Máquinas # 22 y 23 Hornos de curado de papel: el papel filtrante debe someterse a una cocción a altas temperaturas para que el papel logre sus condiciones físicas especificas, no hay una máquina que lo pueda suplir. Tiempo de mantenimiento 3 horas para cada una de ellas. ¾ Hornos para curado de papel

Foto 8 Grupo 11 Máquina # 24 Cámara de pintura: una vez ensamblado el filtro pasa a la etapa de pintura donde se pinta con lacas de diferentes colores según los requisitos de los clientes la pintura además de darle una excelente presentación al filtro impide que este se oxide, alargando así su vida optima. Tiempo de mantenimiento 3 horas.

32

Grupo 12 Máquinas # 25 y 26 Screen: luego de pintado el filtro y previo a la etapa de almacenamiento se debe marcar el filtro para poderlo reconocer en el almacén. Para esto se tienen una máquina que gracias a unas plantillas imprime las referencias en colores que hagan buen conjunto con el fondo que se aplico previamente al filtro, esta máquina es de vital importancia por no poseer otra que la pueda sustituir. Tiempo de mantenimiento 2 horas para cada una. ¾ Máquina de screen

Foto 9 2.5

DEFINICIÓN DEL PROBLEMA.

Las exigencias consideradas entonces para el mantenimiento preventivo en la empresa Powel Continental LTDA. Dependiendo del modelo y tipo de máquina son: •

Desgaste de piezas, valoración realizada por el equipo de mantenimiento, de acuerdo a la experiencia, ficha técnica del fabricante y al historial de la máquina

•

Tiempo sin mantenimiento, Tiempo transcurrido desde la realización del último mantenimiento.

33

•

Importancia en la producción, Tasa o porcentaje de acuerdo con la función que cumple la máquina en el proceso productivo de la compañía, dictado por el departamento de producción.

•

Cantidad de hombres / hora, Número de horas necesarias para realizar el mantenimiento de cada máquina con un número constante de personas del equipo de mantenimiento.

•

Distribución de la maquinaria, % de importancia de acuerdo con la ubicación de la máquina, equipo o instalación, dependiendo de donde se encuentre el equipo o personal de mantenimiento.

•

Número de máquinas, tipo, serie y modelo de maquinaria con su número exacto.

•

Usuario responsable, Seriedad del operario y manejo que este le da a la máquina para un buen funcionamiento y con el menor desgaste posible.

Estas variables son las mas relevantes, son las que implican los aspectos más importantes a la hora de realizar el mantenimiento preventivo a cualquier máquina, equipo o instalación. El problema consiste en optimizar la secuencia de mantenimiento preventivo mediante la distribución de tareas para el personal que realiza esta labor en la empresa Powel Continental LTDA. Se plantea entonces el mantenimiento preventivo para 26 máquinas1, divididas en 12 tipos de modelos diferentes, por las condiciones de la compañía se dispone de un máximo de un mes para realizar el mantenimiento preventivo ( una vez el programa arroje un horario de mantenimiento, esté no debe realizarse en un plazo mayor a 6 meses puesto que para el optimo funcionamiento del algoritmo genético propuesto, la solución que este arroje debe ser cumplido a cabalidad para que los problemas que actualmente se presentan en la empresa Powel Continental LTDA. no continúen.) de todas las máquinas. Se conoce el número de horas de uso de cada máquina desde que se realizó el último mantenimiento preventivo, se cuenta también con las recomendaciones del fabricante, fecha del último mantenimiento y el cambio de piezas desgastadas o deterioradas así como el tiempo necesario por cada máquina para realizar su mantenimiento preventivo (en horas exactas mínimo 1 máximo 4 dependiendo del modelo, serie y tipo de máquina), con una detallada ubicación espacial de cada 1

Se considera a las máquinas, equipos e instalaciones con las mismas variables relevantes y no se diferencian al utilizar el algoritmo genético, pueden ir mezcladas o separadas, a criterio del usuario..

34

máquina dentro de los departamentos de la empresa Powel Continental LTDA. y por último de la importancia de la máquina (% de importancia de la máquina de acuerdo a costos y producción). El mantenimiento en Powel Continental LTDA. es de suma importancia, puesto que en él se generan una gran cantidad de costos por disponer de mucho tiempo ocioso del equipo de mantenimiento y de un alto porcentaje de costos por fallas en los equipos y maquinarias por no tener un mantenimiento justo a tiempo. Actualmente el mantenimiento que se lleva a cabo consiste en realizar la reparación a las máquinas que presentan alguna falla, dado que el cronograma de tareas de mantenimiento mensual que cuentan es desordenado y solo en contadas ocasiones es cumplido a cabalidad. Cronograma actual mantenimiento preventivo Powel Continental LTDA. 1 Semestre del año periodo de Febrero – Marzo 2003

10 y 11

25

15, y 17

23 y 26

16 17 18 19 20

22

10 11 12 13 14 15

21

9

20 y 16

8

19

7

18

6

13 y 14

4

5

9 y 12

3

4

8

3

7

2

5y6

1

1y2

Máquinas

Tabla 1. Cronograma actual Días hábiles para el mantenimiento

Aptitud según función de evaluación 948524 Este cronograma utilizado para el mantenimiento de máquinas en Powel Continental LTDA. es ineficiente, puesto que solo se podía realizar una vez al año por los altos costos, siendo un requerimiento general de las máquinas por fabricante, que se realiza el mantenimiento y el cambio de piezas por lo menos dos veces en el año; en la tabla 1 no se tiene en cuenta la importancia de la máquina en el proceso, ni el tiempo optimo de reparación de la misma, generando contratiempos y problemas con el cumplimiento de la producción.

35

2.6

VARIABLES RELEVANTES

Para el mantenimiento de la empresa se han determinado las variables de mayor importancia de acuerdo a las especificaciones proporcionadas por los técnicos de la empresa2, y estas son: •

%TM = Porcentaje de trabajo diario de la máquina, según las recomendaciones del fabricante. (Horas de trabajo mensual) esta variable se hace importante debido a que todas las máquinas presentan un periodo en el cual es necesario realizar el mantenimiento para asegurar su correcto funcionamiento e impedir desgastes excesivos. horas de uso o funcionamiento durante el ultimo mes calculo:------------------------------------------------------------------ x 100% Horas recomendadas por el fabricante

•

%TUM = Porcentaje de tiempo transcurrido desde el ultimo mantenimiento. Las máquinas que presenten un periodo mayor sin realizarse su mantenimiento tendrán una mayor prioridad para la ejecución del mismo. horas trascurridas desde el ultimo mantenimiento calculo:-------------------------------------------------------- x 100% Horas recomendadas por el fabricante

•

•

%IM = Porcentaje de importancia de la máquina en el proceso productivo. Las máquinas que sean de mayor importancia en el proceso productivo tendrán prioridad en el mantenimiento para impedir que se presenten interrupciones no programadas en la línea de producción. calculo: definido por el depto de produccion x 100% %UR = Porcentaje de calificación del usuario en cuanto al manejo de la máquina. Se tendrá en cuenta el manejo que el operario le de a la máquina, debido a que si esta no es operada con el cuidado necesario se reducirá el tiempo útil de trabajo de la máquina. calculo: definido por el depto de producción x 100%

•

%DP = Porcentaje de desgaste de las piezas de la máquina. Las máquinas tienen piezas que deben ser reemplazadas cada cierto tiempo ó número de

2

la forma como se calculan estas variables es de reserva de la empresa Powel Continental, por lo cual no serán explicadas en detalle en este documento, se deja a criterio del lector su aplicabilidad

36

mantenimientos por lo cual se tiene en cuenta estos periodos para evitar rupturas de estas piezas. horas de uso de las piezas desde el ultimo cambio calculo:-------------------------------------------------------- x 100% Horas de uso recomendadas por el fabricante

37

3. SOLUCIÓN AL PROBLEMA 3.1 COMPARACIÓN CON EL SISTEMA DE EVALUACIÓN DE TODAS LAS POSIBLES SOLUCIONES En este tipo de problema de ordenamiento de horarios con múltiples restricciones, resulta fácil por medio de la estadística obtener el número exacto de posibles soluciones que puede tener el problema, en este caso para Powel Continental LTDA. el conjunto de todas las posibles soluciones es: No. Soluciones =

No. Máquinas!

Puesto que en el caso aquí planteado el número de máquinas actual es de 26 el conjunto de posibles soluciones es No. Soluciones = 26! = 4,03291E+26 Este conjunto de posibles soluciones es tan grande y complejo que tomaría demasiado tiempo evaluar todas las soluciones y computacionalmente imposible por el tiempo que tomaría realizar esta operación cada vez que fuera necesario. El Algoritmo genético aquí planteado resuelve este problema y se acerca a soluciones que son factibles y de hecho muy buenas, que no están muy lejos de la mejor solución posible. 3.2 MODELACIÓN DE UN ALGORITMO GENÉTICO PARA EL ÁREA DE MANTENIMIENTO EN LA EMPRESA POWEL CONTINETAL LTDA. El problema que se plantea de distribución de horarios de mantenimiento requiere de un número de restricciones que facilitan el planteamiento del problema y garantizan que pueda ser aplicado al mismo. Siendo estas: •

Sólo se puede realizar el mantenimiento preventivo en horas laborales no se permiten horas extras. Estas horas serán en días laborales, donde se dividen en dos bloques, el de la mañana de cuatro horas y el de la tarde de otras cuatro horas, si son días festivos se correrá el cronograma los días que sean necesarios a partir del día festivo para evitar el trabajo en estos días.

•

El mantenimiento preventivo de cada máquina debe ser continuo (no interrumpido por ningún motivo) dependiendo del número de horas que

38

necesite el equipo de mantenimiento para dicha máquina, por definición de las máquinas y recomendación de la empresa Powel Continental estas horas no pueden ser menor a una hora ni mayor a cuatro (por definición). •

El tiempo ocioso del personal de mantenimiento debe ser el mínimo posible, para reducir el tiempo improductivo del personal de mantenimiento.

•

Tiene mayor prioridad la máquina que lleva trabajando más del 100% del tiempo recomendado según el fabricante, esta consideración fue propuesta en el capítulo 2.

•

La segunda prioridad la tiene la máquina que lleva mayor tiempo sin que se le realice algún tipo de mantenimiento.

•

La importancia de la máquina depende de su posicionamiento espacial y de la labor que realice en el proceso productivo, esta importancia radica principalmente en su capacidad de producción.

3.3

CADENA GENÉTICA Y ALGORITMO GENÉTICO PROPUESTO

3.3.1 Codificación del problema para un algoritmo genético El punto principal es la codificación de las soluciones, en el capítulo 1 marco teórico se enuncian las principales estrategias de codificación, para este caso que nos compete, siendo el problema en encontrar el orden adecuado de 26 máquinas, la mejor manera de codificar la población de posibles soluciones es mediante valores enteros. 3.3.1.1

Codificación mediante valores reales, enteros o caracteres

Para esta aplicación es más natural usar múltiples caracteres de un alfabeto o números enteros para formar los individuos. Para este caso utilizaremos la codificación mediante valores enteros, para generar la cadena genética de individuos. 3.3.1.2

Ejemplo 1 (codificación)

Como ejemplo del problema utilizaremos parámetros menores, pero con las mismas características y restricciones para hacer más fácil la comprensión del algoritmo genético. En el capítulo de ANÁLISIS DE RESULTADOS estarán la cantidad de máquinas exactas y por medio de los casos de prueba, se obtendrá el rango del tamaño de la

39

población y el rango del número de generaciones en los que el algoritmo genético evolucione a soluciones optimas.

Los parámetros antes vistos son aplicados a este ejemplo •

a = Número de alelos; en nuestro caso la mayoría de veces representaremos los individuos como cadenas enteras x= 1,2,3,...,26 elementos

•

w = Longitud de los individuos. Hemos de decidir cómo codificar el espacio de soluciones y por tanto cuál será la longitud de los cromosomas. De 10 espacios.

•

n = Tamaño de la población, con tamaños de población fijos; todas las poblaciones generadas tendrán ese tamaño.

•

m = Número de generaciones. En este caso al criterio de parada y los casos de prueba generarán un rango de oscilación de los ciclos.

Entonces los individuos de la población serán codificados con caracteres de números de 1 hasta el número de máquinas, y el tamaño o longitud de los individuos es igual al número de máquinas, equipo o instalación. Siendo el número de máquinas para este ejemplo de 10, la codificación de los individuos es la siguiente:

Número de alelos (a): individuos con caracteres de 1 a 10 Longitud de los individuos (w): Longitud de los cromosomas 10 Tamaño de la población (n): Número de individuos 10 Teniendo los parámetros de codificación, se crea una población como la siguiente, cada individuo debe ser creado aleatoriamente y no se debe repetir la información contenida en cada alelo en un solo individuo, como se ve a continuación:

40

Individuo1 2 4 Individuo2 1 3 Individuo3 2 4 Individuo4 1 2 Individuo5 1 3 Individuo6 2 3 Individuo7 10 9 Individuo8 10 2 Individuo9 7 4 Individuo10 7 8

POBLACIÓN DE INDIVIDUOS 5

1

3

6

7

10

9

8

6

2

5

4

10

8

9

7

6

8

10

3

5

7

9

1

3

4

5

6

7

8

9

10

5

7

9

10

8

6

4

2

4

5

6

1

7

8

9

10

8

7

4

5

6

2

1

3

5

8

1

4

7

3

6

9

1

10

8

5

2

9

6

3

9

6

5

4

1

2

3

10

Obsérvese que para cada individuo no se repite la información de ningún campo 3.3.2 Funciones decodificación y objetivo Las funciones decodificación y función objetivo permiten en el algoritmo encontrar valores de aptitud para cada individuo de la población. 3.3.2.1

Función decodificación

En este problema de ordenamiento y selección de un horario de mantenimiento es necesario y útil que la función decodificación de este problema sea convertir cada cadena de individuos en un horario de mantenimiento preventivo, para lo cual se deben tener en cuenta las restricciones mencionadas en el capítulo 2, estas restricciones son básicamente para colocar la información del individuo en un espacio que se asemeja a un horario, en el cual se repite la información del alelo de acuerdo con las características mencionadas en el capítulo 2.

41

Lo primero es ubicar el individuo en una tabla que se llamará de decodificación, cumpliendo con las restricciones de posicionamiento: •

Solo se puede realizar el mantenimiento preventivo en horas laborales.

•

El mantenimiento preventivo de cada máquina debe ser continuo dependiendo del número de horas que necesite el equipo de mantenimiento para dicha máquina.

•

El tiempo ocioso del personal de mantenimiento debe ser el mínimo posible.

Nota: esta tabla de decodificación debe tener un tamaño fijo (escogido por el usuario), para que pueda existir una o más máquinas que no puedan ser insertadas en la tabla, logrando que para este individuo más adelante exista penalización por exceder el tamaño de la tabla de codificación. 3.3.2.2

Ejemplo 2 (Función decodificación)

Como ejemplo utilizaremos un individuo con las siguientes características: Número de alelos (a): individuos con caracteres enteros de 1 a 6 Longitud de los individuos (w): Longitud de los cromosomas 6 Tamaño de la población (n): Número de individuos 1 Tamaño de la tabla de decodificación: 9 x 5 = 45 Las características de la información contenida en cada alelo del individuo, representa el número de horas de mantenimiento, y estas se deben repetir en la tabla de decodificación. Tabla 2. Tabla de información 1 MÁQUINA HORAS DE MANTENIMIENTO 1 3 2 2 3 3 4 2 5 2 6 4 INDIVIDUO 2 6 3 1

4

5

42

Tabla 3. Tabla de decodificación 1 HORA 1 8:00 2 9:00 2 10:00 11:00 12:00 13:00 6 14:00 6 15:00 6 16:00 6

2 3 3 3

3 4 4 5 5

4

5

1 1 1

Como puede verse el alelo 1 del individuo contiene el carácter 2, por lo que según las horas que necesita para su mantenimiento son 2, entonces debe colocarse en la tabla decodificación dos veces seguidas. Es importante tener en cuenta la franja negra de la tabla decodificación que representa una hora de descanso, para el problema de la empresa Powel Continental LTDA., este espacio es el almuerzo. Al continuar con el ejemplo, el siguiente alelo contiene el carácter 6, cuyas horas de mantenimiento son 4, puesto que para cumplir con la restricción: •

El mantenimiento preventivo de cada máquina debe ser continuo dependiendo del número de horas que necesite el equipo de mantenimiento para dicha máquina.

Este no es posible ubicarlo en el primer bloque seguido del carácter 2, sino que es necesario ubicarlo en el segundo bloque, respetando así la restricción: • el mantenimiento debe ser continuo, por esto es necesario y solo se cumple para máquinas que tengan entre una y cuatro horas de mantenimiento preventivo. Es importante tratar de dejar el menor de espacios vacíos así que si una o más máquinas se acomodan en un bloque respetando la condición de que el mantenimiento debe ser continuo y quedar ubicado en el mismo bloque, es recomendado dejarlo así. Si llegado el caso el tamaño de la tabla decodificación es inferior y no se logra ubicar la totalidad de los alelos del individuo, no hay que preocuparse puesto que esta ubicación es penalizada más adelante, logrando que este individuo sea deficiente frente a los demás.

43

Los bloques mencionados son de 2 por cada día hábil y su tamaño es de cuatro espacios, que representan horas (puede considerarse también que los espacios representes diferentes tiempos 15min, ½ hora, etc). 3.3.2.3

Función objetivo

La función objetivo, es utilizada una vez aplicada la función decodificación, proporciona un número entero que diferencia a todos los individuos de la población entre sí, siendo el mejor de la población el que posea una aptitud menor, logrando que cada individuo sea fácilmente diferenciable dentro de la población. Para evaluar cada individuo, debemos primero aplicar la función decodificación, que logra ubicar al individuo en la tabla decodificación, es recomendado que el tamaño de esta tabla de decodificación sea igual al número de horas de trabajo de mantenimiento (el recomendado por la empresa). Una vez el individuo se encuentra en la tabla de decodificación, se crea entonces un vector de evaluación que permite insertar la tabla decodificación para poder ser evaluado el individuo. El tamaño del vector de evaluación es igual al tamaño de la tabla decodificación, que es el número de horas de trabajo diarias por el número de días hábiles para realizar el mantenimiento preventivo (recomendado). Esto es lo mismo a extender la tabla decodificación, dejándola en forma de vector. Luego se procede a encontrar la aptitud del individuo mediante una función, esta función será explicada a continuación en 3.2.2.4. Ejemplo 3. 3.3.2.4

Ejemplo 3 (Función Objetivo)

Como ejemplo utilizaremos un individuo con las siguientes características: Número de alelos (a): individuos con caracteres de 1 a 6 Longitud de los individuos (w): Longitud de los cromosomas 6 Tamaño de la población (n): Número de individuos 1 Tamaño de la tabla de decodificación: 9 x 5 = 45 Las características de la información contenida en cada alelo del individuo, representa el número de horas de mantenimiento, y estas se deben repetir en la tabla de decodificación. (El tamaño de la tabla de decodificación es a criterio del usuario)

44

INDIVIDUO 2 6 3 1

4

5

Tabla 4. Tabla de información 2 MÁQUINA HORAS DE MANTENIMIENTO 1 3 2 2 3 3 4 2 5 2 6 4 Tabla 5. Tabla de decodificación 2 HORA 1 8:00 2 9:00 2 10:00 11:00 12:00 13:00 6 14:00 6 15:00 6 16:00 6

2 3 3 3

3 4 4

1 1 1

5 5 5 5

4

5

En este caso 8 horas diarias por 5 días hábiles, que es igual a 40 horas. Exceptuamos la franja negra, puesto que representa la hora de almuerzo o de descanso. Figura 2. Vector evaluación VECTOR DE EVALUACIÓN Principio del vector evaluación

2 5

2 5

6 5

6

6

6

3

3

3

1

1

1

4

4

5 Final de la vector evaluación

45

Este vector evaluación posee 40 posiciones, comenzando en la primera posición con el carácter 2. Los caracteres vacíos representan tiempo ocioso. Dependiendo de la posición del carácter en el vector de evaluación, se tiene un factor de penalidad, de esta manera se castigan todos los caracteres de acuerdo a su posición dentro del vector de evaluación, esto busca que los mejores individuos son los que logran ubicar las máquinas, equipos o instalaciones más urgentes por realizarle mantenimiento en los primeros lugares del planteamiento. Una vez se tiene el vector de evaluación se procede a evaluar la aptitud al individuo, para esto utilizamos la siguiente función: Entonces la función Objetivo es: (esta función es creada a partir de la información del área de mantenimiento de la empresa Powel Continental) w

Evaluación = MIN [ ( Σ F(x) * PN1 ) * PN2 ] X=1

si

x dentro del vector entonces PN1 = posición dentro del vector evaluación x fuera del vector entonces PN1 = 2 veces Tamaño vector evaluación

donde PN1 = factor de penalidad por posición. PN2 = factor de penalidad por tiempo ocioso. F(x)= %TM + %TUM +%IM +%UR +%DP El porque de esta función de evaluación y no otra; puesto que esta función representa claramente las principales restricciones del problema, como son el ubicar en los primeros lugares de las maquinas, equipos o instalaciones más importantes, y el de minimizar el tiempo ocioso. El F(x) representa la importancia de la máquina, equipo o instalación dentro del planteamiento del problema. 3.3.2.5

Ejemplo 4 (función decodificación y función objetivo)

Continuando con lo ejemplos anteriores y utilizando un individuo generado aleatoriamente, aplicamos la función decodificación y función objetivo para un individuo de la población:

46

Individuo de la población n=10 w=10 es: 2

4

5

1

3

6

7

10

9

8

La tabla de características de las máquinas es: Tabla 6. Características de las máquinas MÁQUINA

%TM

%TUM

%IM

%UR

%DP

F(x)

Horas Mantenimiento

1 2 3 4 5 6 7 8 9 10

60 70 45 90 65 25 15 50 45 68

5 5 10 14 1 8 2 8 4 8

10 5 5 5 5 10 20 25 5 10

1 2 1 1 1 2 1 1 1 2

5 5 10 70 10 10 5 10 15 10

81 97 71 225 97 55 43 94 70 98

3 2 2 2 3 4 2 2 4 3

Tabla 7.Función decodificación HORA 1 8:00 2 9:00 2 10:00 4 11:00 4 12:00 13:00 5 14:00 5 15:00 5 16:00

2 1 1 1

3 6 6 6 6

4 10 10 10

3 3

7 7

9 9 9 9

47

5 8 8

Función objetivo Se crea un vector evaluación de tamaño 5 x 8 = 40 espacios, que corresponden al número máximo de posiciones dentro del vector (5= # de días, 8= # de horas del día) Figura 3. Función objetivo 2 2 4 4 5 5 5 7 7 10 10 10

1 9

1 9

1 9

9

3 8

3 8

6

6

6

6

Posición 9 Se utiliza la función de evaluación para obtener la aptitud del individuo, los datos obtenidos son los siguientes: X representa el carácter o la máquina, esta es una sumatoria de uno hasta el número de máquinas, en este caso igual al tamaño del individuo (10 alelos o campos) w

Evaluación = MIN [ ( Σ F(x) * PN1 ) * PN2 ] X=1

Lo primero que hace esta función es buscar uno a uno cada carácter dentro del vector de evaluación, por ejemplo el carácter 1 se encuentra en la posición 9, este debe buscar la primera posición donde se encuentra el carácter, sin importar que este se repite una o más veces. Al encontrarlo lo multiplica por PN1, que es la primera penalidad que castiga la posición. Esta penalidad se define así: si x dentro del vector entonces PN1 = posición dentro del vector evaluación x fuera del vector entonces PN1 = 2 veces Tamaño vector evaluador Entonces se multiplica la importancia del carácter buscado representado con su F(x) por la posición en la que se encuentra dentro del vector evaluación. Como se definió antes, puede existir que un carácter no sea ubicado en la tabla decodificación y por tanto tampoco en el vector evaluación, por tanto es penalizado severamente y consiste en que se multiplique la importancia del carácter buscado representado con su F(x) por dos veces el tamaño del vector evaluación (es poco posible que esto ocurra).

48

Continuando con el ejemplo, la función objetivo es la sumatoria, de la multiplicación de su importancia F(x) por la posición dentro del vector evaluación, una vez se tiene esta sumatoria, se procede a multiplicar por la segunda penalidad PN2. PN2 consiste en la cantidad de espacios vacíos que posee el vector evaluación, que representan el tiempo ocioso de mantenimiento para ese individuo. El resultado final se conocerá como la aptitud y representa cuantitativamente que tan bueno es el individuo, entre menor sea este número mejor es el individuo. Para el individuo: 2

4

5

1

3

6

7

10

9

8

Cuyas características son las siguientes: Tabla 8. Características de máquinas 2 MÁQUINA F(x)

Horas Mantenimiento 3 2 2 2 3 4 2 2 4 3

1 81 2 97 3 71 4 225 5 97 6 55 7 43 8 94 9 70 10 98 La tabla decodificación es la siguiente: Tabla 9. Tabla decodificación 3 HORA 1 8:00 2 9:00 2 10:00 4 11:00 4 12:00 13:00 5 14:00 5 15:00 5 16:00

2 1 1 1

3 6 6 6 6

4 10 10 10

3 3

7 7

9 9 9 9

49

5 8 8

Se genera un vector de evaluación con tamaño 40 2 7

2 7

4

4

5 5 5 10 10 10

1 9

1 9

1 9

9

3 8

3 8

6

6

6

6

Se le aplica la función objetivo dando como resultado una aptitud de 157352, PN2 o espacios vacíos dentro de vector evaluación son 13. Evaluación = (81*9 + 97*1 + 71*13 + 225*2 + 97*5 + 55*17 + 43*21+ 94*33+ 70* 29 + 98*25 ) * 13 Evaluación = (12104) x 13 Evaluación = 157352 3.3.3 Método de selección En el planteamiento del algoritmo genético se concluyó que es necesario en el transcurso de cada generación se seleccione el mejor individuo de la misma; dado que no se quiere perder la mejor información genética (aptitud) de una generación al crear la siguiente, este método lo conocemos como elitismo. La idea general es encontrar individuos más aptos en el transcurso de cada generación, mostrando una progresión en cada generación que trate de llegar a la menor aptitud, representando está cada vez una solución mejor al problema. Para crear una nueva generación es necesario un método para lograr que individuos de la población se crucen y formen nuevos individuos para una nueva población que se representa en la siguiente generación: este método se conocerá como el método del torneo. 3.3.3.1

Ejemplo 5 (Torneo y elitismo)

Suponiendo una población de 10 individuos, a los que se les aplicó la función decodificación y la función objetivo, para encontrar la aptitud a cada individuo que compone la población. Estos individuos fueron creados de la misma forma en que se plantea la codificación para cada individuo, cada individuo posee el mismo tamaño y cada alelo contiene un carácter numérico que representa una máquina.

50

Población de 10 individuos Tabla 10. Ejemplo aptitud Máquina

Aptitud

1 2 3 4 5 6 7 8 9 10

160277 154265 142584 165159 244848 111448 544448 124646 123554 154488

Población inicial Lo que primero se aplica es el método del elitismo, consiste en seleccionar el mejor individuo de la población y pasarlo directamente sin que sufra algún cambio en la siguiente población, puesto que cada vez que se aplica el método del torneo se generan dos individuos nuevos, si la población es par es necesario entonces realizar el elitismo dos veces, si por el contrario la población es impar el elitismo lo realizamos una sola vez. Para este ejemplo la población es par, por lo que se realiza el elitismo dos veces. Tabla 11. Ejemplo aptitud 2 Máquina

Aptitud

1 2 3 4 5 6 7 8 9 10

123554 123554

51

Entonces en la nueva generación tabla 11. los primeros dos individuos son idénticos, que es el mejor de la población inicial. En la tabla 11.r y en las siguientes aparece el individuo y su aptitud, es necesario tener claro que lo que en realidad debe conservarse es la cadena genética del individuo en la nueva población. A continuación se completa la población con nuevos individuos, para los que aplicamos el método del torneo. Al aplicar el método del torneo se generan dos individuos nuevos en la población, esto debe realizarse hasta completar el tamaño de la población, en este caso el método del torneo debe realizarse cuatro veces. Al aplicar el método del torneo sucede lo siguiente: Primero se seleccionan aleatoriamente dos individuos de la población inicial Tabla 12. Ejemplo aptitud 3 Máquina

Aptitud

1 5

160277 244848

Los individuos seleccionados fueron el 1 y 5, la tabla 12 muestra la aptitud de los individuos seleccionados. Una vez seleccionados dos individuos de la población inicial se escoge un número aleatorio r entre 0 y 1. se define de antemano K que es también un número aleatorio entre 0 y 1. Siguiendo con el ejemplo los números seleccionados aleatoriamente son los siguientes: K = 0.75, r = 0.42 Si r < K el individuo seleccionado es el más apto, en este caso el individuo 1. Este individuo seleccionado queda en espera mientras se selecciona otro con el cual se realizara el cruce y mutación para generar dos nuevos individuos que pertenecerán a la siguiente población. Nuevamente seleccionamos 2 individuos para encontrar el segundo individuo. Selección aleatoria de dos individuos en la población inicial

52

Tabla 13. Ejemplo aptitud 4 Máquina

Aptitud

4 10

165159 154488

Los individuos seleccionados fueron el 4 y 10, la tabla anterior muestra la aptitud de los individuos seleccionados. Una vez seleccionados dos individuos de la población inicial se escoge un número aleatorio r entre 0 y 1. Como el número K ya fue encontrado no es necesario volver a encontrarlo, se continua con el mismo. Siguiendo con el ejemplo los números seleccionados aleatoriamente son los siguientes: K = 0.75, r = 0.8 Como r > K seleccionamos el individuo de menor aptitud, en este caso el individuo 4. Los dos individuos seleccionados son el 1 y 4, de los cuales se crearán dos nuevos individuos. No olvidar que el mejor individuo de la población pasa directamente a la nueva generación en este caso el individuo 1 paso directamente a la siguiente generación. Estos dos individuos son los encargados de generar dos nuevos individuos mediante operadores genéticos, que formaran parte de una nueva población. Es necesario construir la siguiente generación por medio del método del torneo o mientras no se complete una población final del mismo tamaño a la población inicial. A continuación se muestra el funcionamiento del los operadores genéticos. 3.3.4 Operadores genéticos Una vez se cuenta con dos individuos seleccionados de la población inicial, la siguiente decisión para realizar la implementación de un AG es elegir que operadores genéticos utilizar. Esta decisión depende en gran parte de la estrategia de codificación. Los operadores genéticos utilizados serán el cruzamiento y la mutación, los cuales se explicaron anteriormente en el punto 1.4.7 y 1.4.8.

53

3.3.4.1

Ejemplo 6 (Cruce)

Según el punto 3.4.3.3 Ejemplo Método torneo y elitismo los individuos seleccionados fueron los individuos 1 y 4. Al seleccionar los individuos para el cruce, lo que se almacena es el código genético, para esto los individuos seleccionados están compuestos así: Individuo 1 2 4 5 1 3 6 7 10 9 8 Individuo 4 7 2

3

8

5

6

1

4

9

10

Una vez se conocen los individuos y como están formados se realiza una pregunta de si estos dos individuos deben cruzarse o no, para responder esto se explicara más adelante en la secuencia del algoritmo genético de Powel Continental LTDA. Estos dos individuos deben cruzarse primero se selecciona un número aleatorio Cr entre 1 y el tamaño del individuo, este número aleatorio indicara el punto por donde se realizara el cruce. Siguiendo con el ejemplo el número aleatorio es: Cr= 8 Entonces el punto de cruce es el espacio 8 Individuo 1 2 4

5

1

3

6

7

10

9

8

Individuo 4 7 2

3

8

5

6

1

4

9

10

Como muestra el grafico anterior los dos individuos se cruzaran por el alelo 8, el cruce consiste en intercambiar las colas de los dos individuos. Entonces siguiendo la gráfica el alelo 8 del individuo 1 debe ser cambiado por el alelo 8 del individuo 4.

54

Cola individuo 4 4 9 10 Se crea un nuevo individuo con la cadena del individuo 1 y la cola del individuo 4. Nuevo Individuo 1 2 4 5

1

3

6

7

10

9

8

Lo primero es buscar donde se encuentra el carácter numérico 4 dentro del individuo 1, este se encuentra en la posición 2, luego se procede a remplazar la posición 2 por el carácter de la posición 8 así: Nuevo Individuo 1 2 10 5

1

3

6

7

10

9

8

Por ultimo remplazamos la posición 8 del individuo 1 por el carácter numérico 4 así: Nuevo Individuo 1 2 10 5

1

3

6

7

4

9

8

Luego se busca donde se encuentra el carácter numérico 9 dentro del individuo 1, este se encuentra en la posición 9, como se encuentra en la misma posición, no se realiza nada, se deja igual y se procede con el carácter numérico 10 así: Se busca donde se encuentra el carácter numérico 10 dentro del individuo 1, este se encuentra en la posición 2, luego se procede a remplazar la posición 2 por el carácter de la posición 10 así: Nuevo Individuo 1 2 8 5

1

3

6

7

4

9

8

Por ultimo remplazamos la posición 10 del individuo 1 por el carácter numérico 10 así: Nuevo Individuo 1 2 8 5

1

3

6

55

7

4

9

10

Seguido del cruce el nuevo individuo 1 queda así. 2 8 5 1 3 6 7 De la misma forma el nuevo individuo 2 queda así:

4

9

10

7

10

9

8

2

3

4

5

6

1

De esta forma quedan los dos individuos nuevos 3.3.4.2

Mutación

Para que exista mutación se genera aleatoriamente un número que representa una probabilidad entre 0 y 1. Si el número generado aleatoriamente está por debajo de la probabilidad predeterminada para que exista mutación, se cambiará el alelo (es decir, este mutará). Si no, se dejará como está. Si el alelo muta, la información por la que es remplazada consistirá en un número aleatorio que representará una máquina, de la misma forma en que el individuo fue codificado. En este caso el número será un aleatorio entre 1 y 26 que representa la forma en la que se está codificando las soluciones al problema planteado. Para el problema que se plantea en este documento, el cruce se realiza por el método de cruzamiento de punto simple y la mutación se realiza en cada alelo dependiendo de la probabilidad y con enteros entre 1 y 26 que es el número de espacios de cada individuo. 3.3.4.3

Ejemplo 6 (Mutación)

Seguido del cruce y continuando con ejemplos anteriores se creo un nuevo individuo que se representa a continuación así: Nuevo individuo 1 2 8 5

1

3

6

7

4

9

10

Inmediatamente después de ser realizado el cruce y la generación de un nuevo individuo se aplica el operador de la mutación mediante un ciclo que recorre todo el nuevo individuo. La probabilidad de que se realice mutación es predeterminada y se conocerá como Pmuta, la Pmuta es un número entre 0 y 1, y será en este ejemplo así:

56

Pmuta = 0.1 Teniendo la probabilidad predeterminada Pmuta, la única forma para que un alelo del individuo nuevo mute será que un número aleatorio entre 0 y 1 sea menor a Pmuta. Entonces para cada alelo se genera un número Pi entre 0 y 1, La probabilidad de mutación Pi es aleatoria, para que exista mutación Pi debe ser menor o igual a Pmuta . La tabla 14 a continuación muestra los número aleatorios generados para cada alelo del nuevo individuo 1. Tabla 14. Ejemplo Pmuta ALELO 1 2 3 4 5 6 7 8 9 10

Pi 0.9 0.08 0.85 0.70 0.5 0.4 0.2 0.24 0.51 0.8

Como muestra la tabla anterior el único aleo que obtuvo una Pi < Pmuta fue el alelo 2, en donde se genero la mutación del individuo. La mutación del individuo consta de generar un cambio en la información del alelo, este cambio debe ser acorde a como se encuentra el individuo codificado y respetando dicha codificación; en este caso la codificación se representa en caracteres de números enteros entre 1 y el tamaño del individuo, puesto que el tamaño del individuo es 26 se debe generar un número aleatorio Mut entre 1 y 26. Parámetros de la mutación son: Alelo 2 Pi = 0.08 Pmuta = 0.1

Mut = 4

El individuo sin mutar es: Nuevo individuo 1 2 8 5

Mut 7

3

6

Alelo que mutará

57

1

4

9

10

Lo primero consiste en ubicar el carácter numérico Mut en el individuo, este se encuentra en el alelo 8, una vez ubicado el carácter numérico Mut, se intercambia la información de los dos alelos así: Nuevo individuo 1 mutado 2 4 5 7

3

6

1

8

9

10

Así se realiza la mutación hasta terminar el recorrido de la cadena, es importante que ningún número dentro de la cadena se repita, si esto sucede es que se esta realizando un procedimiento equivocado en la mutación o en el cruce. Después de aplicar la mutación a los campos que seleccionados por tener Pi= 50 GENERACIONES >= 150 PROBABILIDAD CRUCE 95% - 98% PROBABILIDAD MUTACION 0.5% - 1% Ejecución del programa con los parámetros anteriores de la tabla 15. , y con las características de máquinas, equipos o instalaciones (igual que en la figura 5): Figura 6. Ingresos datos en Programa

Con estos parámetros el algoritmo genético llegó a una solución satisfactoria, colocando las máquinas de mayor urgencia en los primeros lugares y dejando el menor tiempo ocioso para el grupo de mantenimiento de la empresa Powel Continental LTDA. el horario arrojado por el programa fue:

68

Figura 7. Horario

Aunque este horario no sea el mejor, si es, una solución muy aproximada. 4.6 UTILIZACIÓN DEL PROGRAMA CON LAS CARACTERÍSTICAS DE LA EMPRESA POWEL CONTINENTAL LTDA. Una vez identificados los parámetros, y comprobado el buen funcionamiento del programa y del AGs, se procede a utilizar el algoritmo genético mediante el programa diseñado, se aplican las características propias de las máquinas, equipos e instalaciones. (estas características de las maquinas, equipos e instalaciones en la empresa Powel Continental Ltda.. se encuentran en el Anexo C). Los resultados encontrados al ejecutar el programa 5 veces, con los datos siguientes se representan la tabla 13, los parámetros utilizados fueron: Máquinas : 26 Población : 50 Generaciones : 150 Probabilidad de cruce: 97% Probabilidad de mutación: 1%

69

Tabla 16. Resultados EJECUCIÓN 1 2 3 4 5 MENOR MAYOR PROMEDIO

APTITUD 541404 542563 553555 541585 545012 541404 553555 544824

Siendo el horario de mejor aptitud el siguiente: Figura 8. Horario mantenimiento Powel Continental Ltda..

Este horario genera el menor número de horas ociosas, ubicando las máquinas más urgentes en los primeros lugares, estas máquinas son la número 1, 21, 24 respectivamente, además de esto genera una muy buena solución , que comparada con el ultimo horario de mantenimiento de Powel Contiental (Tabla1.

70

cronograma actual) es una aptitud de casi un 50% menor, y sin duda con menor tiempo ocioso.

71

5. CONCLUSIONES Y RECOMENDACIONES En este trabajo de grado se propone el diseño de un algoritmo genético al problema de asignación de horarios de mantenimiento en la empresa Powel Continental LTDA. Los resultados experimentales obtenidos reafirman que los algoritmos genéticos son una poderosa herramienta para la resolución de problemas de distribución de horarios en los cuales el espacio de búsqueda es muy amplio y la función de optimización puede llegar a ser en extremo compleja. Como han afirmado varios autores, “los algoritmos genéticos no son un método de solución universal de problemas, sino un paradigma que debe adaptarse correctamente al problema a resolver”. El algoritmo propuesto logra resultados efectivos porque en el diseño del mismo se han adaptado los conceptos que aplican los algoritmos genéticos para el problema a resolver. Se logra así explorar el espacio de búsqueda en forma más eficiente. Los resultados presentados en el capítulo 4 muestran que el algoritmo genético propuesto encuentra soluciones de buena calidad, requiriendo una menor cantidad de operaciones para lograrlo, aun utilizando los mínimos valores de los parámetros recomendados. PARÁMETROS RECOMENDADOS INDIVIDUOS >= 50 GENERACIONES >= 150 PROBABILIDAD CRUCE 95% - 98% PROBABILIDAD MUTACION 0.5% - 1% Se encontraron soluciones de mejor calidad a las que se vienen utilizando por parte de la empresa Powel Continental LTDA. Las soluciones halladas por el algoritmo genético propuesto son de mayor calidad casi un 50% mejores (de acuerdo a las medidas definidas), según lo muestran los resultados expuestos en el capítulo 4, puesto que genera horarios con el menor tiempo ocioso de mantenimiento posible, y además de ubicar a las máquinas, equipo o instalación de mayor importancia o urgencia que necesitan mantenimiento preventivo en los primeros lugares del horario. Por otra parte, el programa es capaz de generar soluciones de menor calidad como parte del proceso, y extraer características positivas de ellas. De esta manera, el algoritmo genético nunca se encuentra restringido a una región del espacio de búsqueda. Los elementos de azar que intervienen en la selección, cruce y la

72

mutación pueden llegar a generar individuos en cualquier punto del espacio de búsqueda. El tiempo de búsqueda de soluciones se reduce considerablemente al compararlo con el sistema de evaluar todas las soluciones posibles para este problema que es del alrededor de 26!, mientras que con el programa AG MANTENIMIENTO se minimiza el tiempo de computo y obtiene las soluciones factibles. Características encontradas para este tipo de problemas: •

Es factible implementar un algoritmo genético para problemas de asignación de horarios.

•

Solución de horario es real y reduce considerablemente el tiempo de elaboración de horarios

•

La selección de parámetros en el AG es muy importante; Sin embargo no existe una metodología que indique los valores exactos que deben asignarse ya que varían de acuerdo a la naturaleza del problema.

•

El problema de asignación de horarios de mantenimiento es sumamente complejo debido a las restricciones particulares que varían de acuerdo a las características de las máquinas, equipos o instalaciones y a las políticas de seguridad industrial en la empresa Powel Continental LTDA., así como del criterio con el cual se apliquen dichas restricciones.

•

El algoritmo genético permite a los tomadores de decisiones de la empresa probar sus hipótesis en un ambiente libre de riesgo.

Al concluir el trabajo se ve que en la fase final del algoritmo genético, se puede hacer un aumento en la probabilidad de mutación cuando la evolución es más lenta, para tratar de mejorar un poco más la calidad de las soluciones utilizando este operador.

73

6. BIBLIOGRAFIA LAZO LAZO, Juan Guillermo; Pacheco, Marco Aurelio; Planeamiento para Mantenimiento de Máquinas de Impresión por Algoritmos Genéticos, Departamento de Engenharia Elétrica, PUC-Rio LÓPEZ TAKEYAS Bruno Jaime, JOHNSTON BARRIENTOS David, Modelo de asignación de carga académica usando algoritmos genéticos, Instituto Tecnológico de Nuevo Laredo, http://www.itnuevolaredo.edu.mx/takeyas LANDA BECERRA, Ricardo, tesis Algoritmos Culturales Aplicados a Optimización con Restricciones y Optimización Multiobjetivo. Centro de investigación y de estudios avanzados del instituto politécnico nacional E. LÓPEZ, C. Mendaña y M.A. Rodríguez; La gestión de inventarios con algoritmos genéticos, Departamento de Dirección y Economía de la Empresa Universidad de León Esp. NINOSKA MANEIRO, Malavé, algoritmos genéticos aplicados al problema cuadrático de asignación de facilidades (QAP), Departamento de Investigación

Operativa, Escuela de Ingeniería Industrial, Universidad de Carabobo, Valencia, Venezuela. Cómo funciona el algoritmo genético?, 2000. http://www.geocities.com/aguilar_2000/ALGORITMOS_GENETICOS/algoritmo_gen etico.html. Septiembre 10 de 2003 VALLES ARROYO, José María; NISTAL CALVO, Alberto, E.T.S. Ingeniería Informática - Universidad de Valladolid 2003 COSTA, Carlos, Algoritmos Agosto 25 de 2003

Genéticos,

1997.ccp.servidores.net/genetico.html.

ENCICLOPEDIA LIBRE UNIVERSAL, 1997. http://enciclopedia.us.es/wiki.phtml?title= Algoritmos+gen% E9ticos. Septiembre 2 de 2003 MARTINEZ José J. Introducción a la Informática Evolutiva. Editorial Universal. España: 1999, 10-50p. MERELO, Juan J. Algoritmos Genéticos, 1994.http://geneura.ugr.es/~jmerelo. Agosto 22 de 2003

74

PÉREZ Freddy. Inteligencia Artificial. Universidad de Puerto Rico. 1998 SCHULTZ, Alan C, Algoritmos Genéticos, 2001, http://www.aic.nrl.navy.mil/galist. Septiembre 10 de 2003

75

Anexo A La siguiente tabla representa el promedio de las corridas realizadas mediante el programa AG MANTENIMIENTO, aunque fueron alrededor de 11000 corridas, solo se muestran las 480 en las que se enfoco específicamente el capítulo 4 ANALISIS DE RESULTADOS. INDIVIDUIOS

GENERACIONES

PROBCRUCE

PROBMUTA

APTITUD

40

50

95

0

741213

40

50

95

1

648180

40

50

95

2

634275

40

50

95

3

1057043

40

50

96

0

683046

40

50

96

1

655839

40

50

96

2

653301

40

50

96

3

977197

40

50

97

0

767439

40

50

97

1

615033

40

50

97

2

630072

40

50

97

3

1047371

40

50

98

0

752301

40

50

98

1

635985

40

50

98

2

1016665

40

50

98

3

972322

40

50

99

0

764406

40

50

99

1

641547

40

50

99

2

617175

40

50

99

3

621630

40

50

100

0

817884

40

50

100

1

940524

40

50

100

2

666774

40

50

100

3

1018745

40

100

95

0

727767

40

100

95

1

626868

40

100

95

2

597681

40

100

95

3

1037075

40

100

96

0

677160

40

100

96

1

612954

40

100

96

2

968734

40

100

96

3

1016847

40

100

97

0

779103

40

100

97

1

603108

40

100

97

2

1333922

40

100

97

3

1502035

40

100

98

0

806409

76

40

100

98

1

624546

40

100

98

2

603927

40

100

98

3

947583

40

100

99

0

748413

40

100

99

1

605340

40

100

99

2

962325

40

100

99

3

608193

40

100

100

0

713187

40

100

100

1

605673

40

100

100

2

993980

40

100

100

3

748305

40

150

95

0

752796

40

150

95

1

600165

40

150

95

2

606303

40

150

95

3

691623

40

150

96

0

779625

40

150

96

1

917592

40

150

96

2

649224

40

150

96

3

610353

40

150

97

0

744435

40

150

97

1

600543

40

150

97

2

599877

40

150

97

3

660123

40

150

98

0

825795

40

150

98

1

601056

40

150

98

2

1065051

40

150

98

3

687447

40

150

99

0

836622

40

150

99

1

599049

40

150

99

2

649611

40

150

99

3

1117246

40

150

100

0

743724

40

150

100

1

611334

40

150

100

2

1005550

40

150

100

3

1022736

40

200

95

0

871704

40

200

95

1

600786

40

200

95

2

923416

40

200

95

3

602694

40

200

96

0

786339

40

200

96

1

601209

40

200

96

2

984217

40

200

96

3

991835

40

200

97

0

817362

40

200

97

1

603297

40

200

97

2

601983

77

40

200

97

3

618228

40

200

98

0

747099

40

200

98

1

599472

40

200

98

2

597177

40

200

98

3

612117

40

200

99

0

768960

40

200

99

1

599697

40

200

99

2

1038206

40

200

99

3

597969

40

200

100

0

746658

40

200

100

1

646200

40

200

100

2

595521

40

200

100

3

624546

40

250

95

0

757125

40

250

95

1

600156

40

250

95

2

615159

40

250

95

3

602334

40

250

96

0

753471

40

250

96

1

604845

40

250

96

2

597789

40

250

96

3

910949

40

250

97

0

839439

40

250

97

1

608373

40

250

97

2

596349

40

250

97

3

985595

40

250

98

0

703800

40

250

98

1

988156

40

250

98

2

880477

40

250

98

3

601641

40

250

99

0

727407

40

250

99

1

600786

40

250

99

2

599337

40

250

99

3

636759

40

250

100

0

686286

40

250

100

1

601965

40

250

100

2

953173

40

250

100

3

982813

50

50

95

0

736893

50

50

95

1

612081

50

50

95

2

905398

50

50

95

3

631665

50

50

96

0

821907

50

50

96

1

644508

50

50

96

2

626031

50

50

96

3

630369

50

50

97

0

653886

78

50

50

97

1

50

50

97

2

666585

50

50

97

3

1049841

50

50

98

0

690984

50

50

98

1

618192

50

50

98

2

956995

50

50

98

3

997867

50

50

99

0

721440

50

50

99

1

652446

50

50

99

2

645876

50

50

99

3

646983

50

50

100

0

780102

50

50

100

1

618417

50

50

100

2

1189591

50

50

100

3

652437

50

100

95

0

718038

50

100

95

1

602478

50

100

95

2

605376

50

100

95

3

662049

50

100

96

0

778410

50

100

96

1

599229

50

100

96

2

612126

50

100

96

3

710109

50

100

97

0

739413

50

100

97

1

620451

50

100

97

2

602316

50

100

97

3

1818327

50

100

98

0

693585

50

100

98

1

602100

50

100

98

2

631251

50

100

98

3

1047163

50

100

99

0

676062

50

100

99

1

604377

50

100

99

2

599130

50

100

99

3

1008332

50

100

100

0

751059

50

100

100

1

601920

50

100

100

2

606582

50

100

100

3

960713

50

150

95

0

766935

50

150

95

1

600453

50

150

95

2

647631

50

150

95

3

665730

50

150

96

0

796545

50

150

96

1

617391

50

150

96

2

604818

79

671724

50

150

96

3

637731

50

150

97

0

684387

50

150

97

1

603873

50

150

97

2

603225

50

150

97

3

608850

50

150

98

0

742608

50

150

98

1

598545

50

150

98

2

966966

50

150

98

3

1054950

50

150

99

0

712908

50

150

99

1

604989

50

150

99

2

598464

50

150

99

3

982904

50

150

100

0

683658

50

150

100

1

618408

50

150

100

2

939237

50

150

100

3

677133

50

200

95

0

743373

50

200

95

1

601632

50

200

95

2

598365

50

200

95

3

969371

50

200

96

0

637074

50

200

96

1

605538

50

200

96

2

597312

50

200

96

3

612792

50

200

97

0

728145

50

200

97

1

597528

50

200

97

2

600345

50

200

97

3

1019798

50

200

98

0

736569

50

200

98

1

601947

50

200

98

2

596142

50

200

98

3

1160627

50

200

99

0

737559

50

200

99

1

982475

50

200

99

2

642429

50

200

99

3

651195

50

200

100

0

748125

50

200

100

1

599373

50

200

100

2

603297

50

200

100

3

680976

50

250

95

0

749574

50

250

95

1

601461

50

250

95

2

955292

50

250

95

3

983879

50

250

96

0

756099

80

50

250

96

1

595305

50

250

96

2

599553

50

250

96

3

627219

50

250

97

0

748656

50

250

97

1

599193

50

250

97

2

601101

50

250

97

3

615078

50

250

98

0

696303

50

250

98

1

607257

50

250

98

2

598545

50

250

98

3

645678

50

250

99

0

862893

50

250

99

1

674739

50

250

99

2

603153

50

250

99

3

929734

50

250

100

0

709821

50

250

100

1

601461

50

250

100

2

693549

50

250

100

3

1004510

60

50

95

0

770940

60

50

95

1

705537

60

50

95

2

797121

60

50

95

3

1323875

60

50

96

0

738270

60

50

96

1

618210

60

50

96

2

1234272

60

50

96

3

1103921

60

50

97

0

776718

60

50

97

1

614358

60

50

97

2

1068210

60

50

97

3

956891

60

50

98

0

726192

60

50

98

1

683082

60

50

98

2

677574

60

50

98

3

1570936

60

50

99

0

667422

60

50

99

1

653589

60

50

99

2

613404

60

50

99

3

614214

60

50

100

0

662616

60

50

100

1

610452

60

50

100

2

634716

60

50

100

3

1245777

60

100

95

0

766773

60

100

95

1

599121

60

100

95

2

618480

81

60

100

95

3

706536

60

100

96

0

746199

60

100

96

1

601578

60

100

96

2

654903

60

100

96

3

982059

60

100

97

0

768933

60

100

97

1

606762

60

100

97

2

607050

60

100

97

3

714141

60

100

98

0

695277

60

100

98

1

607860

60

100

98

2

605259

60

100

98

3

989287

60

100

99

0

698355

60

100

99

1

600399

60

100

99

2

607095

60

100

99

3

654750

60

100

100

0

718191

60

100

100

1

603333

60

100

100

2

604620

60

100

100

3

991211

60

150

95

0

697383

60

150

95

1

744381

60

150

95

2

600228

60

150

95

3

616977

60

150

96

0

681912

60

150

96

1

922961

60

150

96

2

602928

60

150

96

3

631584

60

150

97

0

723744

60

150

97

1

600228

60

150

97

2

702846

60

150

97

3

665055

60

150

98

0

751230

60

150

98

1

903019

60

150

98

2

919464

60

150

98

3

1347063

60

150

99

0

696978

60

150

99

1

599463

60

150

99

2

643311

60

150

99

3

931866

60

150

100

0

771057

60

150

100

1

600039

60

150

100

2

603981

60

150

100

3

626292

60

200

95

0

708507

82

60

200

95

1

60

200

95

2

598581

60

200

95

3

1212510

60

200

96

0

751707

60

200

96

1

602019

60

200

96

2

904813

60

200

96

3

885612

60

200

97

0

767268

60

200

97

1

601200

60

200

97

2

625599

60

200

97

3

1095731

60

200

98

0

729918

60

200

98

1

598752

60

200

98

2

905749

60

200

98

3

604161

60

200

99

0

789381

60

200

99

1

602649

60

200

99

2

600957

60

200

99

3

1128413

60

200

100

0

699408

60

200

100

1

596691

60

200

100

2

616581

60

200

100

3

944918

60

250

95

0

675612

60

250

95

1

610461

60

250

95

2

601713

60

250

95

3

976378

60

250

96

0

719280

60

250

96

1

601209

60

250

96

2

915005

60

250

96

3

622791

60

250

97

0

730854

60

250

97

1

595467

60

250

97

2

596133

60

250

97

3

620811

60

250

98

0

714681

60

250

98

1

602145

60

250

98

2

1101022

60

250

98

3

613629

60

250

99

0

706356

60

250

99

1

600525

60

250

99

2

940628

60

250

99

3

620532

60

250

100

0

674073

60

250

100

1

595827

60

250

100

2

601785

83

601101

60

250

100

3

601965

70

50

95

0

714510

70

50

95

1

626076

70

50

95

2

620730

70

50

95

3

1478490

70

50

96

0

740637

70

50

96

1

626274

70

50

96

2

798030

70

50

96

3

666603

70

50

97

0

666738

70

50

97

1

621963

70

50

97

2

626769

70

50

97

3

1189058

70

50

98

0

699930

70

50

98

1

623475

70

50

98

2

980044

70

50

98

3

1011530

70

50

99

0

659412

70

50

99

1

613899

70

50

99

2

662598

70

50

99

3

1024335

70

50

100

0

762921

70

50

100

1

612036

70

50

100

2

633636

70

50

100

3

964106

70

100

95

0

702972

70

100

95

1

605880

70

100

95

2

631152

70

100

95

3

992472

70

100

96

0

711144

70

100

96

1

604260

70

100

96

2

601029

70

100

96

3

743409

70

100

97

0

731871

70

100

97

1

605925

70

100

97

2

922389

70

100

97

3

1177696

70

100

98

0

728973

70

100

98

1

608778

70

100

98

2

1047813

70

100

98

3

1761914

70

100

99

0

756927

70

100

99

1

596043

70

100

99

2

597933

70

100

99

3

819468

70

100

100

0

716616

84

70

100

100

1

605016

70

100

100

2

1109160

70

100

100

3

628173

70

150

95

0

692280

70

150

95

1

599877

70

150

95

2

634203

70

150

95

3

1633734

70

150

96

0

688437

70

150

96

1

703809

70

150

96

2

623394

70

150

96

3

605502

70

150

97

0

731034

70

150

97

1

606024

70

150

97

2

752517

70

150

97

3

613395

70

150

98

0

689391

70

150

98

1

598851

70

150

98

2

598869

70

150

98

3

1526906

70

150

99

0

684081

70

150

99

1

611181

70

150

99

2

602307

70

150

99

3

1277107

70

150

100

0

718992

70

150

100

1

927771

70

150

100

2

687807

70

150

100

3

981227

70

200

95

0

743067

70

200

95

1

602613

70

200

95

2

987103

70

200

95

3

617895

70

200

96

0

695790

70

200

96

1

619605

70

200

96

2

992745

70

200

96

3

623511

70

200

97

0

688806

70

200

97

1

598581

70

200

97

2

599481

70

200

97

3

684585

70

200

98

0

758439

70

200

98

1

599049

70

200

98

2

599553

70

200

98

3

1638868

70

200

99

0

769518

70

200

99

1

598293

70

200

99

2

609741

85

70

200

99

3

70

200

100

0

672921

70

200

100

1

1020682

70

200

100

2

601317

70

200

100

3

1043081

70

250

95

0

681309

70

250

95

1

654876

70

250

95

2

595305

70

250

95

3

1437282

70

250

96

0

719595

70

250

96

1

595593

70

250

96

2

932607

70

250

96

3

973310

70

250

97

0

682956

70

250

97

1

600156

70

250

97

2

697536

70

250

97

3

940745

70

250

98

0

747468

70

250

98

1

596331

70

250

98

2

1012700

70

250

98

3

971087

70

250

99

0

723519

70

250

99

1

599517

70

250

99

2

598401

70

250

99

3

602055

70

250

100

0

728433

70

250

100

1

601209

70

250

100

2

1284469

70

250

100

3

1310582

86

1081132

Anexo B MANUAL DE INSTALACIÓN MANTENIMIENTO

Y

UTILIZACIÓN

PROGRAMA

AG

1. INSTALACIÓN El programa AG MANTENIMIENTO se encuentra en un CD con la tesis. El primer paso es copiar en un disquete la carpeta AG MANTENIMIENTO, esta carpeta contiene todo el programa en Microsoft Visual Basic 6.0. Si no se posee el Microsoft Visual Basic 6.0, no importa, en la carpeta también se encuentra un archivo ejecutable llamado Powel Continental. Una vez esta la carpeta en el disquete, ejecute el archivo Powel Continental. 2. REQUERIMIENTOS MINIMOS Procesador : 550 MHz RAM : 198 Megas Unidad de CD Drive 3 ¼ 3. UTILIZACIÓN PROGRAMA

Abrir la unidad de disquete y ejecutar el archivo Powel Continental,

87

Al ejecutar el archivo debe aparecer:

Aparece una ventana pequeña en la que hay que introducir los parámetros de funcionamiento del algoritmo genético. De antemano existe un archivo de texto llamado características, ubicado en la carpeta AG MANTENIMIENTO, este archivo contiene las características de las máquinas, si desea modificar este archivo puede hacerlo directamente mediante WorPad o simplemente oprima el botón CARACTERÍSTICAS MÁQUINAS, al hacerlo aparece en la siguiente pagina: para modificar las características de las máquinas escoja la fila y columna que desea cambiar, seguido en el campo vacío escriba el valor de reemplazo y oprima el botón modificar características.

88

Una vez realizados todos lo cambios debe guardar los cambios en el archivo de texto, para esto oprima el botón GUARDAR CAMBIOS.

Nuevamente aparece la pantalla del principio, luego ingrese los parámetros y ejecute el botón AGs.

89

Lo que aparece es una ventana en donde se muestran las poblaciones iniciales y como cambian de generación en generación. Una vez termina el procesador de simular las generaciones, automáticamente abre una ventana en la que se muestra la ultima generación, con las aptitudes de sus individuos; además abre una ventana pequeña que indica la mejor aptitud en cada generación.

La franja roja indica el mejor individuo encontrado en la generación, para ver el horario, es necesario ingresar en número del individuo y oprimir el botón horario.

90

Cada vez que se ejecuta el programa, los resultados se almacenan en un archivo de texto llamado Resultados.Txt, este archivo es fácilmente exportado en programas estadísticos, base de datos y compiladores.

91

Anexo C Las características de las máquinas de Powel Continental son las siguientes: MÁQUINA

%TM

%TUM

%IM

%UR

%DP

F(x)

Horas Mantenimiento

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

80

10

10

1

5

106

3

70

5

5

2

5

87

4

45

10

5

1

15

76

2

51

14

5

1

10

81

2

65

1

5

1

15

87

4

25

8

5

1

15

54

4

15

2

5

1

15

38

2

50

8

10

2

5

75

2

45

4

15

2

5

71

3

68

8

5

2

5

88

3

60

2

5

2

20

89

3

60

5

10

1

5

81

4

70

5

5

2

5

87

4

45

10

5

1

15

76

4

20

14

5

1

10

50

3

65

1

5

1

15

87

1

25

8

5

1

15

54

2

15

2

5

1

15

38

1

50

8

10

2

5

75

1

45

4

15

2

5

71

3

94

8

5

2

5

114

3

60

2

5

2

20

89

3

70

6

5

1

10

92

3

98

1

5

1

15

120

3

25

8

5

1

15

54

2

15

2

5

1

15

38

2

92