Minimización de los costos de desperdicios a través de un Algoritmo Genético para la distribución de piezas en formatos. Caso de estudio empresa FERROCARPINTERIA FORMAR. Sergio de Jesús Leottau Sanmiguel Juan Carlos Rodríguez Noriega Universidad Tecnológica de Bolívar Programa de ingeniería industrial Cartagena Junio de 2012 Minimización de los costos de desperdicios a través de un Algoritmo Genético para la distribución de piezas en formatos. Caso de estudio empresa FERROCARPINTERIA FORMAR. Sergio de Jesús Leottau Sanmiguel Juan Carlos Rodríguez Noriega DIRECTOR Jairo Rafael Coronado Hernández Ingeniero Industrial Universidad Tecnológica de Bolívar Programa de ingeniería industrial Cartagena Junio de 2012 Cartagena de Indias D. T y C. 13 de Junio de 2012 Señores: COMITÉ CURRICULAR Programa de Ingeniería Industrial La ciudad Respetados Señores: Por medio de la presente me permito someter a su consideración la propuesta de Trabajo de grado titulado “Minimización de los costos de desperdicios a través de un Algoritmo Genético para la distribución de piezas en formatos. Caso de estudio empresa FERROCARPINTERIA FORMAR”, desarrollada por los estudiantes Sergio de Jesús Leottau Sanmiguel y Juan Carlos Rodríguez Noriega, como requisito para optar al título de Ingenieros Industriales, en la que me desempeñare cumpliendo la función de director. Atentamente, _______________________________ Jairo Rafael Coronado Hernández Director del Trabajo de grado Cartagena de Indias D. T y C. 13 de Junio de 2012 Señores: COMITÉ CURRICULAR Programa de Ingeniería Industrial La ciudad Respetados Señores: Por medio de la presente me permito someter a su consideración la propuesta de Trabajo de grado titulado “Minimización de los costos de desperdicios a través de un Algoritmo Genético para la distribución de piezas en formatos. Caso de estudio empresa FERROCARPINTERIA FORMAR”, desarrollada por los estudiantes Sergio de Jesús Leottau Sanmiguel y Juan Carlos Rodríguez Noriega, como requisito para optar al título de Ingenieros Industriales. Atentamente, ______________________________ ________________________ Sergio de Jesús Leottau Sanmiguel Juan Carlos Rodríguez Noriega Cartagena de Indias D. T y C. 13 de Junio de 2012 Señores: COMITÉ CURRICULAR Programa de Ingeniería Industrial La ciudad Respetados Señores: Por medio de la presente manifestamos el interés y apoyo incondicional en el suministro de la información necesaria para el desarrollo del Trabajo de grado titulado “Minimización de los costos de desperdicios a través de un Algoritmo Genético para la distribución de piezas en formatos. Caso de estudio empresa FERROCARPINTERIA FORMAR”, desarrollada por los estudiantes Sergio de Jesús Leottau Sanmiguel y Juan Carlos Rodríguez Noriega, como requisito para optar al título de Ingenieros Industriales. Atentamente, __________________________________ Justo Padilla Barros Gerente general Nota de aceptación: _________________________ _________________________ _________________________ ____________________________ Firma del presidente del jurado ____________________________ Firma jurado ____________________________ Firma jurado Cartagena, 13 de Junio de 2012 DEDICATORIA A mi familia por su apoyo incondicional, por su Confianza, y su creencia en mis habilidades. A mi novia Carolina por brindarme Amor, cariño en todo Momento. Sergio Leottau Sanmiguel DEDICATORIA Dedico este trabajo a mis familiares, en especial Mi padre y mi madre, quienes han sido El motor de mi vida. Juan Carlos Rodríguez Noriega. AGRADECIMIENTOS Los autores expresan sus agradecimientos a: Jairo Rafael Coronado Hernández, Ingeniero de industrial, por su incondicional apoyo en el desarrollo del presente trabajo de grado, por el tiempo dedicado y bien intencionadas recomendaciones. Al cuerpo de docentes del programa de Ingeniería Industrial de la Universidad Tecnológica de Bolívar, por fortalecer nuestras bases como ingenieros y brindarnos formación profesional. Contenido 1. CONSIDERACIONES GENERALES ..................................................... 20 1.1. OBJETIVOS ..................................................................................... 20 1.2. PROBLEMA DE INVESTIGACIÓN. ................................................. 21 1.2.1. Descripción del problema. ............................................................... 21 1.2.2. Formulación del problema ............................................................... 22 1.3. JUSTIFICACIÓN .............................................................................. 23 1.4. ASPECTOS METODOLOGICOS .................................................... 24 1.4.1. Tipo de investigación ....................................................................... 24 1.4.2. Metodología de trabajo .................................................................... 25 2. MARCO REFERENCIAL. ................................................................ 27 2.1. MARCO CONCEPTUAL .................................................................. 27 2.2. MARCO TEÓRICO. ......................................................................... 28 2.2.1. Metaheurísticas ............................................................................... 28 2.2.2. Algoritmo genético (AG). .................................................................. 29 2.2.3. Problemas de empaquetamiento. .................................................... 31 2.2.4. Problemas de empaquetamiento más comunes .............................. 32 2.2.5. Modelo matemático del bin packing problem. .................................. 32 2.2.6. Complejidad computacional ............................................................. 35 2.2.7. Clasificación. .................................................................................... 35 2.3. ANTECEDENTES. ........................................................................... 38 3. DIAGNOSTICO ................................................................................ 43 3.1. GENERALIDADES DE LA EMPRESA............................................. 43 3.1.1. Misión .............................................................................................. 43 3.1.2. Visión ............................................................................................... 43 3.1.3. Reseña histórica .............................................................................. 43 3.1.4. Organigrama .................................................................................... 44 3.2. DESCRIPCIÓN DE LOS RECURSOS ............................................. 45 3.2.1. Recursos Humanos. ........................................................................ 45 3.2.2. Recursos Físicos ............................................................................. 46 3.3 PRODUCTOS Y PROCESOS DE FERROCARPINTERIA FORMAR . 49 3.3.1 Productos ......................................................................................... 49 3.3.2 Procesos .......................................................................................... 50 3.4 PLANIFICACIÓN Y CORTE DE PIEZAS. ........................................ 53 3.5 INSTANCIA OBJETO DE ESTUDIO................................................ 54 3.5.1 Elección del producto....................................................................... 54 3.5.2 Descripción del producto: ................................................................ 56 3.5.3 Caracterización de las piezas que conforman el producto............... 57 3.5.4 Formulación del indicador de desperdicio........................................ 64 3.5.5 Promedio histórico de desperdicio. ................................................. 65 3.5.6 Análisis del costo de los desperdicio. .............................................. 66 3.5.7 Tiempo utilizado en la distribución de las piezas de forma manual. 67 4 HERRAMIENTA COMPUTACIONAL .................................................... 69 4.1 DISEÑO DEL ALGORITMO GENÉTICO. ........................................ 69 4.1.1 Codificación ..................................................................................... 70 4.1.2 Operados genéticos ......................................................................... 75 4.1.3 Heurística para el bin packing problem ............................................ 86 4.1.4 Calculo de la función fitness ............................................................ 90 4.1.5 Convenciones geométricas .............................................................. 91 4.1.6 Calculo de área de piezas ............................................................... 92 4.2 CONSTRUCCIÓN DE LA HERRAMIENTA COMPUTACIONAL PROTOTIPO. ............................................................................................ 94 4.2.1 Requerimientos. ............................................................................... 94 4.2.2 Arquitectura de software .................................................................. 96 4.2.3 Casos de uso ................................................................................... 98 4.2.4 Vistas estáticas ................................................................................ 98 4.2.5 Funcionalidades a implementar. .................................................... 102 4.2.6 Lenguaje de programación. ........................................................... 103 4.2.7 Comunicación con software de CAD. ............................................ 104 4.2.8 Validación herramienta prototipo. .................................................. 105 5 APLICACIÓN DE LA HERRAMIENTA ................................................. 107 5.1 PARÁMETROS DEL ALGORITMO GENÉTICO ............................ 108 5.2 CÁLCULO DEL TAMAÑO DE MUESTRA ..................................... 109 5.3 INDICADOR PROMEDIO DE DESPERDICIO ARROJADO POR LA HERRAMIENTA ...................................................................................... 110 5.4 ANÁLISIS DE COSTO PARA LA DISTRIBUCIÓN ARROJADA POR LA HERRAMIENTA ................................................................................. 111 5.4.1 Análisis Comparativo ..................................................................... 111 5.5 TIEMPOS COMPUTACIONALES .................................................. 113 6 CONCLUSIONES ................................................................................ 114 ANEXOS ..................................................................................................... 120 LISTA DE TABLAS Tabla 1. Recursos humanos administrativos ................................................ 45 Tabla 2. Recursos humanos operativos. ....................................................... 45 Tabla 3. Descripción de piezas de una cocina integral. ................................ 57 Tabla 4. Datos históricos de indicador promedio de desperdicio .................. 65 Tabla 5. Análisis de costo para la distribución manual ................................. 67 Tabla 6. Población inicial .............................................................................. 76 Tabla 7. Resultado del experimento para la selección de los parámetros .. 108 Tabla 8. Datos de la muestra piloto ............................................................ 110 Tabla 9. Análisis de costo para la herramienta computacional ................... 112 Tabla 10. Cuadro comparativo de resultados ............................................. 112 Tabla 11. Características del pc. ................................................................. 113 LISTA DE FIGURAS Figura 1. Operador de cruce básico. ............................................................. 30 Figura 2. Operador de mutación básico. ....................................................... 31 Figura 3. Herramienta para la distribución de piezas con formas regulares o irregulares en una lamina ............................................................................. 42 Figura 4. Organigrama de la empresa FERROCARPINTERIA FORMAR ... 44 Figura 5. Mapa de procesos de la empresa ................................................. 50 Figura 6. Diagrama BPM para la descripción de corte de piezas de triplex .. 54 Figura 7. Diagrama de Pareto de utilidades por producto. ............................ 55 Figura 8. Modelo del producto realizado en la empresa ............................... 57 Figura 9. Ubicación de las piezas en el módulo superior .............................. 62 Figura 10. Pieza de las puertas .................................................................... 62 Figura 11. Ubicación de las piezas en el módulo inferior .............................. 63 Figura 12. Gaveta del módulo inferior ........................................................... 63 Figura13.Gaveta con pieza de polígono de ángulo recto .............................. 64 Figura 14. Diagrama de flujo para el algoritmo genético ............................... 70 Figura 15. Representación basada en láminas ............................................. 71 Figura 16. Representación de la redundancia en las soluciones .................. 71 Figura 17. Representación basada en objetos. ............................................ 73 Figura 18. Redundancia en la representación basada en objetos ............... 73 Figura 19. Representación base del cromosoma.......................................... 74 Figura 20. Representación basada en grupos .............................................. 74 Figura 21. Asignación de probabilidad a individuos ..................................... 77 Figura 22. Mecanismo de selección mediante el SUS .................................. 78 Figura 23 . Representación del punto de corte del cromosoma .................... 79 Figura 24. Cruce por un punto ...................................................................... 79 Figura 25. Cruce por dos puntos................................................................... 80 Figura 26. Operador de cruce uniforme ........................................................ 82 Figura 27. Operador de cruce PMX .............................................................. 83 Figura 28. Operador de mutación 2-opt ........................................................ 85 Figura 29. Secuencia de empaquetamiento ................................................. 86 Figura 30. Reconstrucción de los límites ...................................................... 87 Figura 31. Representación válida para dos individuos .................................. 88 Figura 32. Solución inalcanzable .................................................................. 89 Figura 33. Altura máxima de lámina. ............................................................ 91 Figura 34. Ejes coordenados y recorrido de la pieza .................................... 92 Figura 35. Calculo de área de las piezas ...................................................... 93 Figura 36: Estructura de la herramienta computacional ................................ 94 Figura 37. Arquitectura de software por capas. ............................................ 97 Figura 38. Diagrama de casos de uso .......................................................... 99 LISTA DE ECUACIONES Ecuación 1. Indicador de desperdicio ........................................................... 64 Ecuación 2. Fórmula de cálculo de probabilidad........................................... 76 Ecuación 3. Función fitness .......................................................................... 90 Ecuación 4.Fórmula de tamaño optimo de muestra .................................... 110 ANEXOS Anexo 1. Maquinaria industrial. ................................................................... 120 Anexo 2. Herramientas manuales. ............................................................. 121 Anexo 3. Resultado de la ejecución de la herramienta. .............................. 122 Anexo 4. Área utilizada distribuciones obtenidas con la herramienta. ....... 122 Anexo 5. Distribución manual de las piezas. .............................................. 123 Anexo 6. Distribución promedio en la herramienta. .................................... 125 Anexo 7.Diagrama de clases ...................................................................... 127 Anexo 8.Diagrama de paquetes.................................................................. 128 Anexo 9. Formato validación de la herramienta prototipo. .......................... 129 Anexo 10.Resultados de la encuesta de validación .................................... 130 Anexo 11Tiempos empleados en la distribución manual. ........................... 131 Anexo 12. Tiempos empleados en la distribución por la herramienta computacional ............................................................................................. 131 Anexo 13. Utilidades por producto. ............................................................. 133 Anexo 14. Manual de usuario. .................................................................... 134 INTRODUCCIÓN Uno de los principales problemas en las empresas que tiene dentro de sus procesos, el corte de piezas en formatos, es la distribución de estas, tal que el desperdicio generado durante este proceso, sea mínimo. Para este tipo de problemáticas existe una gran variedad de alternativas que permiten encontrar distribuciones, siendo las más utilizadas las técnicas metaheurísticas, debido a los buenos resultados obtenidos en tiempos relativamente cortos. En este trabajo se presenta una aplicación del bin packing problem al proceso de corte de piezas en formato (láminas de triplex) para las cocinas integrales en la empresa FERROCARPINTERÍA FORMAR, para la solución del mismo, se recurre al uso de técnicas metaheurística, en este caso se escoge al algoritmo genético, debido a su flexibilidad en cuanto a su fácil adaptación a una gran variedad de problemas. En la primera sección se realiza una descripción detallada de los diferentes procesos en la empresa, haciendo mayor énfasis en el de corte, en la segunda se discuten los mecanismos utilizados en la solución del problema de empaquetamiento, para esto se muestra la estructura del algoritmo genético utilizada, y se entra a debatir los diferentes sistemas de codificación existente para el caso del bin packing problem, de igual forma se hace con los operadores genéticos; a partir de esta discusión y con base en las revisiones bibliográficas, se eligió el sistema de codificación y los operadores genéticos a utilizar en la construcción del algoritmo. En la tercera sección se muestran los requerimientos funcionales de la herramienta computacional que tiene como base el algoritmo genético previamente diseñado. En este mismo capítulo se establecen los alcances del prototipo que se implementara para la herramienta. Finalmente en la última sección se establecen los resultados obtenidos por la herramienta computacional, para esto se ejecuta un caso de estudio identificado durante la etapa del diagnóstico y descripción de los procesos, luego se compara mediante un análisis de costo los resultados de la herramienta con los obtenidos por los trabajadores de la empresa FERROCARPINTERIA FORMAR. 1. CONSIDERACIONES GENERALES 1.1. OBJETIVOS OBJETIVO GENERAL Diseño y aplicación de una herramienta computacional para minimizar los costos asociados a la distribución de piezas en láminas en la empresa FERROCARPINTERIA FORMAR en la ciudad de Cartagena. OBJETIVOS ESPECIFICOS  Realizar un diagnóstico de la situación actual del proceso de distribución de piezas en láminas, mediante la utilización de herramientas de ingeniería que permitan la construcción de un indicador del porcentaje de desperdicio, con objeto de contrastarlo con los resultados obtenidos en la herramienta.  Diseñar el algoritmo genético basados en implementaciones existentes en la literatura, para problemáticas similares, con el fin de seleccionar los mejores operadores.  Construir una herramienta computacional prototipo basada en el algoritmo genético diseñado, empleando el lenguaje de programación Java, permitiendo así la búsqueda de soluciones para la instancia objeto de estudio.  Aplicación de la herramienta prototipo al proceso de distribución de piezas en la empresa FERROCARPINTERIA FORMAR, determinando el grado de eficiencia de las soluciones encontradas, en comparación con el nivel de desperdicio calculado durante el diagnostico. 20 1.2. PROBLEMA DE INVESTIGACIÓN. 1.2.1. Descripción del problema. En la mayoría de las organizaciones no solo es suficiente con lograr los objetivos propuestos, también es relevante la forma como éstos son alcanzados, es por esto que las organizaciones se encuentran en una constante búsqueda de mecanismos que les permitan hacer mejor uso de los recursos utilizados en la consecución de los objetivos. La industria maderera no es la excepción, ésta al igual que todas las demás, busca que en sus procesos los recursos se utilicen de forma eficiente. FERROCARPINTERIA FORMAR es una empresa dedicada a la fabricación de productos en madera, que se preocupa para que cumplan con los más altos estándares de calidad, buscando el mayor nivel de satisfacción de sus clientes. En el proceso de construcción de los productos en madera, se encuentra una etapa destinada a realizar el diseño de los mismos, en la cual se especifican mediante planos las estructuras o piezas, que conformarán el producto final. Algunas de las piezas utilizadas en la fabricación de los productos, son obtenidas a partir de láminas de madera de diferentes calibres, que previamente tiene que ser cortados en formatos de dimensiones prestablecidas. Antes que las piezas sean cortadas, éstas deben ser organizadas dentro del formato, buscando distribuciones que permitan obtener el menor desperdicio de material posible, siendo consecuentes con el principio expuesto, que consiste en hacer un mejor aprovechamiento de los recursos, en este caso de los insumos de madera. La distribución de las piezas en los formatos, es un problema conocido dentro de la literatura como el empaquetamiento optimo en placas (2D-BPP) del inglés two-dimensional bin packing problem, que consiste en “un conjunto de figuras que deben ser ubicados en áreas rectangulares llamadas placas con anchos y largos definidos e idénticos, el objetivo es encontrar el 21 número mínimo de placas necesarias de forma tal que la totalidad de las piezas sean ubicadas, sin sobreponer las piezas y sin sobrepasar los límites de las placas”1. En la empresa FERROCARPINTERIA FORMAR, en la actualidad las piezas son distribuidas manualmente dentro de los formatos en la etapa de planificación, es decir, antes de realizar el corte de las piezas en las láminas, sin embargo, esta distribución manual no garantiza que se esté haciendo un buen uso del recurso; adicionalmente este mecanismo puede resultar agotador para el trabajador, así como demandar grandes cantidades de tiempo para obtener distribuciones que disminuyan el porcentaje de desperdicio de las láminas de madera. Por todo lo expuesto anteriormente, se propone construir una herramienta que permita realizar la distribución de las piezas en los formatos de forma automatizada, con el fin de disminuir la cantidad de material necesario para realizar el corte de cierta cantidad de piezas, y por ende, disminuir el porcentaje de desperdicio del material, en comparación con la realización de esta distribución de forma manual. Adicionalmente se busca que esta herramienta pueda encontrar soluciones en tiempos cortos, en los que el trabajador podrá estar realizando cualquier otra actividad que agregue valor a los productos. 1.2.2. Formulación del problema Conforme a las necesidades presentadas en la empresa FERROCARPINTERIA FORMAR, se pretende dar solución al siguiente problema de investigación: ¿Cómo minimizar los costes asociados a los desperdicios distribuyendo correctamente las piezas en láminas? 1 ÁLVAREZ MARTÍNEZ, David. Solución del problema de empaquetamiento óptimo 22 1.3. JUSTIFICACIÓN Los problemas de empaquetamiento, corte óptimo de piezas, despacho y almacenamiento de materiales juegan un papel importante en la industria. Ya que estos representan una oportunidad de mejora, especialmente en aquellos procesos que involucran el corte como una fase necesaria para la transformación de materia prima. Es así como en FERROCARPINTERIA FORMAR, empresa dedicada a la elaboración de productos en madera, en la cual en su etapa de planificación (distribución de las piezas en láminas) se realiza en forma manual, lo cual hace que en la actualidad este proceso no se realice en forma metódica y por consiguiente no garantice que las distribuciones de las piezas sean las más adecuadas Por tal motivo el estudio y posterior aplicación de un problema tipo bin packing al proceso de corte en la empresa FERROCARPINTERIA FORMAR, permitiría generar distribuciones de piezas en láminas de tamaño predeterminado, a través de técnicas metaheurísticas (algoritmo genético), las cuales tendrían un impacto significativo en la reducción de los desperdicios generados, lo que se traduce en menores costos para la organización, como también en un uso eficiente de los materiales. La utilización de los algoritmos genéticos resulta ser muy ventajoso a la hora de resolver problemas de categoría NP-Hard en comparación con los métodos exactos, esto se debe a que los métodos exactos hacen exploraciones exhaustivas del espacio de solución, incrementando la necesidad de recurso computacional, a la vez que el tiempo empleado para encontrar dicha solución sea excesivamente largo; por el contrario el uso de técnicas metaheurísticas como lo es el algoritmos genético, hace que la demanda de recursos computacionales sea menor, como también los tiempos asociados a la búsqueda de soluciones sea corto, de esta forma el desarrollo de esta herramienta prototipo ayudaría a la disminución de los tiempos relacionados con la fase de planificación del corte lo cual significa 23 que el tiempo empleado en generar una solución (distribución de pieza) es corto, en comparación con el tiempo empleado para realizar una distribución de la piezas en forma manual. 1.4. ASPECTOS METODOLOGICOS 1.4.1. Tipo de investigación Para la ejecución de la investigación, se utilizará un tipo de estudio de carácter descriptivo-correlacional, “la investigación descriptiva busca especificar, propiedades características y rasgos importantes de cualquier fenómeno que se analice mientras que los estudios correlaciónales tiene como propósito conocer la relación que exista entre dos o más conceptos, categorías o variables en un contexto en particular”23. En una etapa inicial el estudio es descriptivo porque pretende ver en forma detallada las características del problema, que variables hay que tener en cuenta en la distribución de las piezas en las láminas de madera, caracterizar los parámetros del algoritmo genético y los mecanismos implementados en éste; Posteriormente se implementará un tipo de estudio correlacional, porque con éste se pretende establecer relaciones entre los diferentes mecanismos y parámetros implementados en el algoritmo genético en contraste con las soluciones obtenidas. El diseño metodológico para esta investigación es experimental, los diseños experimentales “se refieren a un estudio en el que se manipulan intencionalmente una o más variables independientes”4, con este diseño metodológico, se podrá establecer los parámetros que mejores resultados arrojan en el Algoritmo Genético. 2 HERNANDEZ, Sampier y FERNANDEZ, Carlos. Metodología de la investigación. Cuarta Edición. Mexico D.F.: Mc Graw Hill, 2006.p 103. ISBN 978-970-10-5753-7. 3 Ibid., p. 104. 4 Ibid., p. 160. 24 Finalmente se tiene que los medios de recolección de información a utilizar durante el desarrollo de la investigación son; la bitácora o diario de campo, la cual permitirá llevar un registro detallado de todas las observaciones que se hagan en cada visita a la planta de producción, así mismo se implementará a la entrevista como otro mecanismo a tener en cuenta, ya que nos permitirá comprender el funcionamiento del sistema bajo estudio. Dentro de las fuentes de recolección de información primaria se cuenta con el asesor de la tesis, los operarios de la planta encargados del proceso de corte. Como fuente segundaria se encuentra a los artículos científicos relacionados con el problema de empaquetamiento, libros, materiales de internet, etc. 1.4.2. Metodología de trabajo Para el cumplimiento de los objetivos se establecieron un conjunto de actividades, las cuales sumadas podrán dar con el cumplimiento de los objetivos propuestos. En este caso la primera a realizar consiste en el reconocimiento pleno del proceso a mejorar, para este caso se realizarán visitas periódicas a la empresa, con el fin de recolectar información relacionada con los mecanismos utilizados por la empresa en el proceso de corte, en especial en la planificación (distribución de la piezas en las placas). Una vez culminada esta etapa, se procederá a realizar una revisión bibliográfica que permita identificar implementaciones similares de algoritmos genéticos en la literatura especializada. A partir de éstos se procederá a realizar el diseño del algoritmo genético, por lo cual se tendrá en cuenta los diferentes operados como lo son: cruce, selección, mutación, etc. Finalizada esta etapa, el siguiente paso consiste en la construcción de la herramienta computacional, para lo cual se tendrá en cuenta el algoritmo genético previamente diseñado como también la utilización de lenguaje de programación Java. 25 Una vez terminada la herramienta prototipo, se procede a resolver un caso de estudio asociado al proceso de distribución de piezas en la empresa, esto con el fin de seleccionar los parámetros, tales como el porcentaje de mutación, cruce y número de generaciones con el cual el algoritmo genético tiene mejor desempeño. De igual forma este caso de estudio se utilizará en el cálculo del número de réplicas, para el cual la herramienta prototipo se debe ejecutar con el objetivo de saber el indicador promedio de desperdicio arrojado por ésta en un caso particular. Concluida con la fase de determinación de los parámetros y el número de réplicas, el paso a seguir es ejecutar en la herramienta prototipo un caso de estudio identificado durante el diagnóstico, con el fin de comparar el porcentaje de desperdicio obtenido en el proceso de corte cuando la distribución se realiza en forma manual, versus el porcentaje de desperdicio arrojado por la distribución de las piezas hecha por la herramienta prototipo. 26 2. MARCO REFERENCIAL. 2.1. MARCO CONCEPTUAL A continuación se presentan un conjunto de conceptos que servirán como base en el desarrollo de la presente investigación:  Desperdicio de material: Residuo de lo que no se puede o no es fácil aprovechar o se deja de utilizar por descuido5.  Pieza: Cada una de las partes que suelen componer un artefacto6.  Herramienta computacional: aplicación de tipo informático diseñado para permitir a un usuario realizar uno o diversos tipos de trabajo. Las herramientas computacionales pretenden automatizar una tarea que suele ser complicada de realizar de forma manual.  Optimización: Un problema de optimización trata de tomar una decisión óptima para maximizar (ganancias, velocidad, eficiencia, etc.) o minimizar un criterio determinado (costos, tiempo, riesgo, error, etc.).  Casos de estudio: Se refiere al el conjunto de piezas que se pretende sean distribuidas en las láminas, este especifica la forma de las piezas al igual que su cantidad.  Industria maderera: Es la actividad económica que se concentra en el procesamiento de la madera desde su plantación hasta su posterior transformación en productos. 5 Real academia de la lengua española [En línea]. [citado el 20 de diciembre, 2011] Disponible en: 6 Real academia de la lengua española [En línea]. [citado el 20 de diciembre, 2011] Disponible en: 27 2.2. MARCO TEÓRICO. 2.2.1. Metaheurísticas El termino metaheurística fue introducido por primera vez por Glover7 en el año de 1996, al definir una clase de algoritmos de aproximación que combinan heurísticos tradicionales con estrategias eficientes de exploración del espacio de búsqueda8. El termino metaheurística se deriva etimológicamente del griego meta que significa “más allá” o “nivel superior”, mientras que el término heurística significa “búsqueda”, por lo que juntas estas dos palabras significarían “un nivel superior de búsqueda”9. En la actualidad no existe una definición comúnmente aceptada para el termino metaheurística, sin embargo, muchos investigadores en los últimos años han propuesto definiciones, Osman y Laporte la definen como “Un proceso iterativo de generación que guía una heurística subordinada, combinando de forma inteligente distintos conceptos para explorar y explotar el espacio de búsqueda, estrategias de aprendizaje que se utilizan para estructurar la información con el fin de encontrar de manera eficiente soluciones casi óptimas”10. La mayor ventaja de las metaheurísticas frente a otros métodos está en su gran flexibilidad, lo que permite usarlos para abordar una amplia gama de problemas. Las metaheurísticas no existen para problemas específicos, éstas se pueden adaptar de forma relativamente sencilla, realizando pequeñas modificaciones sobre la metaheurística base. 7 GLOVER, F. Future paths for integer programming and links to artificial intelligence. En: Computers and Operations Research. 1986. Vol. 13, No. 5. p. 533-549. 8 VELEZ, Mario y MONTOYA, JOSÉ. Metaheurísticos: una alternativa para la solución de problemas combinatorios en administración de operaciones. En: EIA. Diciembre, 2007. No. 8. p. 99-115. ISSN 1794-1237. 9 BLUM, Christian y ROLI, Andrea. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. En: ACM Computing Surveys. Septiembre, 2003.Vol. 35, No. 3. p. 268-308. 10 OSMAN, I.H. y LAPORTE,G. Metaheuristics: A bibliography. En: Ann. Oper. 1996. No. 63. p. 268-308. 28 Existen una gran variedad de metaheurísticas, en su mayoría basadas en analogías de la naturaleza, entre las cuales se encuentra el Recocido Simulado, la Búsqueda Tabú, Algoritmo Genético, Sistemas Inmune Artificiales, optimización por Colonia de Hormigas, optimización por Enjambre de Partículas, Evolución Diferencial, entre otras. 2.2.2. Algoritmo genético (AG). Los algoritmos genéticos son métodos adaptativos, usados por lo general en problemas de búsqueda y optimización, estos se basan en la reproducción sexual y en el principio de supervivencia del más apto11. El desarrollo de los algoritmo genéticos se debe en gran medida a las investigaciones realizas por John Holland, investigador de la Universidad de Michigan. Éste desarrollo en la década de 1960 una técnica que imitaba en su funcionamiento a la selección natural de las especies. Inicialmente esta técnica tomo el nombre de planes reproductivos, sin embargo, con la aparición del libro “Adaptation In Natural And Artificial Systems” escrito por el mismo Holland12, se popularizó el nombre de algoritmo genético. Una de las definiciones más aceptadas es la dada por Goldberg, “Algoritmos de búsqueda basados en los mecanismos de selección natural y genética natural. Combinan la supervivencia de los más compatibles entre las estructuras de cadenas, con una estructura de información ya aleatorizada, intercambiada para construir un algoritmo de búsqueda con algunas de las capacidades de innovación de la búsqueda humana”13. 11 GESTAL POSE, Marcos. Introducción a los algoritmos genéticos. España: Universidad de la Coruña. Dpto. tecnologías de la información y comunicación. p. 2. 12 Holland, J. H. Adaptation in Natural and Artificial Systems. Michigan: Universidad de Michigan. 1992. 13 GOLDBERG, D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley. 1989. 29 Los algoritmos genéticos operan sobre una población o conjunto de soluciones de la problemática planteada, estas soluciones son representadas mediante cadenas por lo regular de tipo binario, aunque también pueden ser secuencias de tipo real. En la ejecución, el algoritmo realiza operaciones sobre los individuos (soluciones) de la población, y preserva aquellos de mayor aptitud para las siguientes generaciones, mientras que los de menor aptitud van desapareciendo al transcurrir la ejecución. Entre las operaciones más comunes que se realizan los individuos de la población se encuentran la selección, cruce, mutación:  Selección: Esta fase se encarga de seleccionar los individuos o soluciones que tendrán la oportunidad de reproducirse.  Cruce: Operación por medio de la cual se producen nuevos descendientes a partir de dos cromosomas padre seleccionados al azar.  Mutación: En esta operación se seleccionan al azar y se cambian uno o más genes en el cromosoma, esta operación ocurre con probabilidades muy bajas. Figura 1. Operador de cruce básico. Fuente: VELEZ, Mario y MONTOYA, JOSÉ. 30 Se debe tener en cuenta que para cada operador (selección, cruce, mutación) existen diferentes mecanismos de implementación, por lo cual se deberá determinar en el transcurso de la investigación cuál de las opciones expuestas en la literatura se implementará en la construcción del algoritmo genético. Figura 2. Operador de mutación básico. Fuente: VELEZ, Mario y MONTOYA, JOSÉ. 2.2.3. Problemas de empaquetamiento. Los problemas de empaquetamiento son en su forma más básica, la búsqueda de mecanismos por los cuales se pueden distribuir de forma adecuada unos elementos (piezas) dentro de otro de mayor tamaño (lamina), con el fin de poder ingresar el mayor número de elementos dentro del objeto de mayor tamaño. Los problemas de empaquetamiento han sido ampliamente estudiados a lo largo del tiempo, debido a su gran aplicabilidad en las diferentes industrias, en especial en aquellas que requiera del proceso de corte para la transformación de sus materias primas. Estas industrias necesitan herramientas que le den solución a dicho problema y puedan ser 31 aplicadas en el corte de materiales como el metal, madera, vidrio, plástico, papel, pieles, entre otras14. 2.2.4. Problemas de empaquetamiento más comunes En la literatura existe una gran variedad de problemas de empaquetamiento, entre los que se distinguen tres de estos, el empaquetamiento óptimo en placas (2D-BPP) del inglés two-dimensional bin packing problem, el de corte óptimo en una sola placa (2D-CSP) del inglés two dimensional cutting stock problem y el empaquetamiento óptimo en rollos (2D-SPP) del inglés two- dimensional strip packing problem. El primero (2D-BPP) de estos 3 problemas, consiste en un conjunto de piezas que deben ser ubicados en áreas rectangulares llamadas placas con anchos y largos definidos, el objetivo es encontrar el número mínimo de placas necesarias de forma tal que la totalidad de las piezas sean ubicadas, sin sobreponer las piezas y sin sobrepasar los límites de las placas. El segundo (2D-CSP) de los problemas consiste, en un conjunto de piezas que deben ser cortados en un área rectangular llamada placa con un ancho y largo definido, el objetivo es encontrar la ubicación de las piezas en la placa para ser cortadas, minimizando el espacio desperdiciado de la placa, sin sobreponer las piezas y sin sobrepasar los límites de la placa. Por último, el tercero (2D-SPP) de estos 3 problemas, consiste en un conjunto de rectángulos que deben ser ubicados en un área rectangular llamada rollo con un ancho definido y un largo que se supone infinito, el objetivo es encontrar el largo mínimo del rollo de forma tal que la totalidad de las piezas sean ubicadas en el rollo, sin sobreponer las piezas y sin sobrepasar los límites del rollo. 2.2.5. Modelo matemático del bin packing problem. A continuación es presentado un modelo matemático general, inicialmente propuesto por Chen15, el cual es aceptado por la comunidad académica que investiga en el tema, es presentado como un modelo de programación lineal 14 ALVAREZ. Op. cit., p. 13. 15 Chen C. Lee S. y Shen Q., An analyticalmodel for the container loading problem. En: European Journal of Operational Research, vol. 80, 1995, pp. 68-76. 32 entera mixta. Este modelo ha sido adaptado por Álvarez16 a fin de describir el bin packing problem. A continuación se describe algunas de las notaciones necesarias para comprender el modelo matemático: Número disponible de rectángulo para posicionar en la hoja de material. Largo de la lámina. Ancho de la lámina Largo del rectángulo i. Ancho del rectángulo i. Variable que indica la posición del rectángulo i, teniendo como punto de referencia el vértice inferior izquierdo de la lámina. Variable binaria que indica si el rectángulo i fue ubicado en la lámina. Variable binaria que indica el eje de la hoja del material. El lado del rectángulo i está en paralelo. Variable binaria que indica el eje de la hoja del material. El lado del rectángulo i está en paralelo. En caso de que sea 1, indica que el rectángulo está al lado izquierdo del rectángulo k. En caso de que sea 1, indica que el rectángulo está al lado derecho del rectángulo k. En caso de que sea 1, indica que el rectángulo i está a tras del rectángulo k. En caso de que sea 1, indica que el rectángulo i está al frente del rectángulo k. Número entero muy grande. La función objetivo consiste en minimizar la cantidad de material desperdiciado, tal como se muestra en la ecuación 1. 16 ÁLVAREZ, D. Y TORO, E. Algoritmo de optimización de partículas aplicado en la solución del problema óptimo bidimensional con y sin rotación. En: Scientia et Technica No 43, Diciembre de 2009, Universidad Tecnológica de Pereira. p. 6-7. 33 ∑ (1) Sujeto a: (2) (3) (4) (5) Las ecuaciones 2 hasta 5 evitan superposiciones entre los rectángulos ubicado en la lámina. (6) La ecuación 6 garantiza que el par de rectángulos evaluados con las ecuaciones anterior estén dentro de las dimensiones de la lámina. (7) (8) Las ecuaciones 7 y 8 garantizan que el posicionamiento de las piezas obedezca al dado por las dimensiones de la lámina. Los modelos del problema de empaquetamiento sin rotación de piezas se obtienen al remplazar las ecuaciones 2, 3, 4, 5, 7, 8 por las ecuaciones 9 hasta la 13, respectivamente. (9) (10) 34 (11) (12) (13) (14) Al analizar el modelo, encontramos que el número de variables y de ecuaciones crece en forma exponencial con el número de piezas a empacar. 2.2.6. Complejidad computacional Los problemas de empaquetamiento, inclusive los 3 mencionados anteriormente, tienen la característica de poseer un gran espacio de solución factible, lo que dificulta la búsqueda de una solución óptima, por lo cual, los problemas de empaquetamiento son considerados NP-Hard1718, demostrado en el caso especial en el que los elementos (piezas) tiene la misma longitud y diferente altura, y cuyo objetivo es distribuirlos en el material de mayor tamaño en una sola dimensión, este problema también es conocido como (1D-BPP) one dimensional bin packing. 2.2.7. Clasificación. Como se mencionó anteriormente existe una gran variedad de problemas de empaquetamiento en la literatura, estos se han estudiado desde hace mucho tiempo. Se pueden presentar obstáculos para el estudio de un tipo de problema en particular, sino no se tiene plenamente identificado a que tipo corresponde, Dyckhoff19 presenta una propuesta de clasificación de los problemas de empaquetamiento basado en sus características comunes, permitiendo segregar el problema de investigación de los demás problemas 17 GAREY, M. y JOHNSON, D. Computers and Intractability: A Guide to the Theory of NP- Completeness. PrimeraEdición. San francisco: W. H. Freeman, 1979. 340 paginas.978- 0716710455. 18 MARTELLO, S. y VIGO, D.An exact approach to the strip-packingproblem.En: INFORMS Journal on Computing. Septiembre, 2003.Vol. 15, No. 3. p. 310-319. 19 DYCKHOFF H. A typology of cutting and packing problems.En: European Journal of Operational Research. 1990. Vol. 44. p. 145-160. 35 de empaquetamiento. Para la clasificación propuesta por Dyckhoff, este explica de forma detallada en qué consisten los problemas de corte y empaquetamiento, en donde existen dos elementos principales, los ítems (que serán llamados piezas o elementos a lo largo de este documento) y los objetos de mayor tamaño (que se denominaran láminas), en donde el objetivo principal del problema, es distribuir los ítems dentro de los objetos de mayor tamaño de forma eficiente. A continuación se presenta la clasificación propuesta por Dyckhoff (las 4 primeras clasificaciones), complementada con las clasificaciones hechas por Lodi20 permitiendo particularizar mejor la problemática de investigación: a) Dimensionalidad: la característica más importante, define el número mínimo de dimensiones necesarias para describir la geometría de la disposición de los ítems en los objetos.  Unidimensional  Bidimensional  Tridimensional  Multidimensional con N>3 b) Clase de asignación: disponibilidad tanto de los ítems como de los objetos.  Todos los objetos y una selección de ítems  Una selección de objetos y todos los ítems c) Surtido de los objetos: número de diferentes formas de los objetos.  Un objeto  Figuras idénticas  Diferentes figuras d) Surtido de los ítems: número de diferentes formas de los objetos. 20 LODI A, MARTELLO S, y VIGO D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. En: INFORMS J. Computer. 1999. Vol. 11. p. 345- 357. 36  Pocos ítems (de diferentes figuras)  Muchos ítems de muchas diferentes figuras  Muchos ítems de relativamente pocas diferentes figuras (no- congruentes)  Figuras congruentes e) Restricciones inherentes al patrón de corte: tipos de corte, separación entre los cortes.  Exclusivamente cortes tipo guillotina  No requiere cortes tipo no guillotina f) Restricciones inherentes a la orientación de las piezas: posibilidad de que las piezas puedan rotar 90° o no.  Las piezas pueden rotar 90°  Las piezas no pueden rotar 90° g) Valores de las piezas: beneficio que ofrece empacar una determinada pieza.  Ítems con valores de beneficio diferente a su área (weighted)  Ítems con valores de beneficio igual a su área (un-weighted) h) Demanda de las piezas  Piezas con límite máximo de corte  Piezas sin límite de corte (infinito) i) Forma de las piezas  Ítems con forma regular (rectángulos, círculos, cubos, esferas, cilindros, etc.)  Ítems con forma irregular 37 2.3. ANTECEDENTES. Para la dar solución a los problemas de empaquetamiento se encuentran una gran variedad de técnicas, pertenecientes ya sea al grupo que arrojan resultados exactos, o al grupo de técnicas que se fundamentan en las probabilidades (técnicas Heurísticas y Metaheurísticas), arrojando buenas soluciones (no necesariamente las soluciones optimas), pero en tiempos computacionalmente razonables. En la presente sección se realizará una revisión de las investigaciones previamente realizadas en este campo de investigación, buscando establecer bases teóricas para el presente proyecto de investigación. En 1966 Gilmore y Gomory21 proponen un algoritmo exacto para la solución de problemas de empaquetamiento, más específicamente para la solución del problema del corte óptimo en una sola placa (CSP) del inglés two dimensional cutting stock problem, mientras en 1977 Christofides y Withlock22 proponen por su parte un algoritmo de búsqueda en árbol fundamentado en el algoritmo de Gilmore y Gomory. En 1983 Wang23 presenta un algoritmo de desarrollo incremental también para el problema del empaquetamiento óptimo en una sola placa (CSP), algoritmo que fue mejorado por Vasko24 en 1989, al igual que por Oliveira y Ferreira25 en 1990. 21 GILMORE, P. y GOMORY, R. Thetheory and computation of knapsackfunctions [La teoría y el cálculo de las funciones del problema de la mochila]. En: OperationsResearch. Marzo, 1966.Vol. 17. p. 1045-1074. 22 CHRISTOFIDES, N. y WHITLOCK, A..Analgorithmfortwo dimensional cuttingproblems [Un algoritmo para problemas de corte de 2 dimensiones]. En: OperationalResearch. Enero, 1977. Vol. 25, No. 3. p. 30-44. 23 WANG, P. Twoalgorithmsforconstrainedtwodimensionalcutting stock problems [Dos algoritmo para limitados problemas de corte en dos dimensiones]. En: OperationalResearch. Enero, 1983. Vol. 31, p. 573-586. 24 VASKO, F. ComputationalimprovementtoWang'stwo-dimensional cutting stock algorithm [Mejoras computacionales al algoritmo de corte en dos dimensiones de Wang´s]. En: Computers and Industrial Engineering. Enero, 1989. Vol. 16, p. 109-115. 25 OLIVEIRA, Jose y FERREIRA, Jose. Animprovedversion of Wang'salgorithmfortwo - dimensional CuttingProblems[Una versión mejorada del algoritmo de Wang´s para problemas de corte en dos dimensiones]. En: EuropeanJournalOperationsResearch. Febrero, 1990. Vol. 44, p. 256-266. 38 En 1998 Martello y Vigo26 también proponen un algoritmo exacto en este caso para la solución del problema del empaquetamiento óptimo en placas (2D-BPP) del inglés two-dimensional bin packing problem, cuyos resultados comparan con los resultados óptimos arrojados por el algoritmo branch-and- bound. En 2000 Martello y Vigo27 extienden el trabajo realizado en 1998 para problemas de empaquetamiento óptimo en placas (2D-BPP) a problemas de empaquetamiento óptimo en contenedores (3D-BPP), realizando una definición preliminar del problema con programación lineal entera. Hasta el momento se han mencionados diferentes investigaciones realizadas a través del tiempo de problemas de empaquetamiento, todos estos resueltos mediante la utilización de algoritmo exactos. La utilización de técnicas aproximadas para la solución de problemas de empaquetamiento es mas común que la utilización de algoritmo exactos, esto debido a la complejidad computacional (ver sección 2.2.6) que poseen este tipo de problemas. A continuación se revisaran las investigaciones realizadas utilizando métodos aproximados para solucionar los problemas de empaquetamiento. Primero se presentara la utilización del Recocido simulado para la solución del problemas de empaquetamiento, en 1993 Dowsland28 presenta una variedad de experimentos en donde demuestra la efectividad de la utilización del Recocido Simulado para la solución de problemas de empaquetamiento, esta utiliza una búsqueda local con una estructura de vecindario en donde 26 MARTELLO, Silvano y VIGO, Daniele .ExactSolution of theTwo-Dimensional FiniteBinPackingProblem[Solución exacto del problema de empaquetamiento optimo en placas en dos dimensiones]. En: Management Science. Marzo, 1998. Vol. 44, No. 3. p. 388- 399. 27 MARTELLO, Silvano y VIGO, Daniele. TheThree Dimensional BinPackingProblem [El problema de empaquetamiento en contenedores]. En: OperationsResearch. Marzo, 2000. Vol. 48, No. 2. p. 256-267. 28 DOWSLAND, Kathryn. Someexperimentswithsimulatedannealingtechniquesforpackingproblems[Algunas experiencias con técnicas de Recocido Simulado para problemas de empaquetamiento]. En: European Journal of Operational Research. Junio, 1993.Vol. 68, No. 3. p. 389-399. 39 ubica las piezas de forma aleatoria para luego realizar intercambios. En 1998 Parada29 al igual que Dowsland propone una solución al problema de empaquetamiento con un algoritmo de Recocido Simulado, este utiliza una codificación de árbol binario, facilitando la solución aleatoria de soluciones dentro del espacio de soluciones. En 2009 Álvarez30 presenta un algoritmo hibrido (una combinación de un algoritmo de Recocido Simulado con un algoritmo de Búsqueda en Vecindario Variable) para la solución de un problema de empaquetamiento en placas, que es el resultado de realizar cortes al problema de empaquetamiento en rollos, finalmente realiza una verificación de las bondades del método construido, evaluándolo con 34 casos de estudios, logrando mejoras en la mayoría de estos. Por otro lado se revisaran las investigaciones en las cuales se utilizaron como método de solución un Algoritmo Genético (AG). En 2001 Leung31 utiliza un algoritmo evolutivo para preservar las mejores soluciones encontradas por un algoritmo de Recocido Simulado propuesto por Lai y Chan32 anteriormente. En 2003 Beasley presenta una solución con la utilización de Algoritmo Genéticos, basado en una nueva formulación no- lineal del problema. En 2003 Pasha33 también utiliza AG para la solución de problema, con el valor agregado que en este caso se trata de la distribución 29 PARADA, Victor. Solution for the Constrained Guillotine Cutting Problem by Simulated Annealing [Solución del problema de corte con la restricción de guillotinamedianteRecocidoSimulado].En: Journal on Computers and Operations Research. Enero, 1998.Vol. 25, No. 1. p. 37-47. 30 ÁLVAREZ, David y TORO, Eliana. A hybridalgorithmforthetwo-dimensional strippackingproblem[solución al problema de empaquetamiento óptimo bidimensional en rollos infinitos usando un algoritmo híbrido]. En: Scientia et Technica. Junio, 2009. Vol. 15, No. 42. p. 205-210. 31 LEUNG T. Y YUNG C. Applications of geneticsearch and simulatedannealingtothetwo- dimensional non-guillotine cutting stock problem [Aplicaciones de Algoritmo Genéticos y Recocido Simulado para el problema de empaquetamiento optimo en una placa en dos dimensiones]. En: Computers and Industrial Engineering. Julio, 2001. Vol. 40. p. 201-214. 32 LAI, K y CHAN, J. A evolutionaryalgorithmforthe rectangular cutting stock problem [Un algoritmo evolutivo para el problema de empaquetamiento óptimo de rectángulos en una placa]. En: International Journal of Industrial Engineering. Julio, 1997.Vol. 4. p. 130-139. 33 PASHA, Arfath.Geometricbinpackingalgorithmforarbitraryshapes [Problemas de empaquetamiento optimo en placas para formas irregulares]. Trabajo de grado magíster en ciencias. Gainesville: Universidad Florida. 2003. 99 P. 40 de figuras irregulares en placas. En 2006 Binkley y Hagiwara34 describen para el problema la heurística de las 4 esquinas en conjunto con un algoritmo genético auto-adaptativo, que por definición busca por sí mismo los parámetros adecuados para encontrar las mejores soluciones al problema. En 2008 Lee LaiSoon35 al igual que los anteriores utiliza un AG para la solución del problema, cuya mayor innovación radica en la utilización de un operador de cruzamiento que permite generar varios hijos a partir de una pareja de padres, pasando el algoritmo a tomar el nombre de Algoritmo genético con cruzamiento múltiple del inglés Multi Crossover Genetic Algorithm. Es importante destacar que en su mayoría las investigaciones que se han presentado hasta el momento se refieren solo a la distribución de piezas de forma rectangular en láminas también de forma rectangular, sin embargo, en la mayoría de las industrias las piezas no tiene forma rectangular, ni siquiera forma regular, a continuación se presentan las investigaciones que se han realizado del problema de empaquetamiento con la utilización de figuras irregulares. En 1980 Albano36 realiza una de las primeras investigaciones relacionadas con el problema, en donde se aceptan piezas con forma regular o irregular, este utiliza una heurística como método de búsqueda. En 1996 Cagan y en 1997 Mcgee buscan solucionar el problema de empaquetamiento optimo en contenedores permitiendo la utilización de piezas con formas irregulares. Finalmente en 2003 Pasha presentan de los trabajos más destacados, utilizando un Algoritmo Genético y un algoritmo de Recocido 34 BINKLEY, Kevin y HAGIWARA, Masafumi. Applyingself-adaptive evolutionary algorithms to two-dimensional packing problems using a fourcorners[Aplicación de algoritmos evolutivos auto-adaptativos en problemas de empaquetamiento en placas usando las 4 esquinas]. En: European Journal of Operational Research. Diciembre, 2006.Vol. 183. p. 1230-1248. 35 LAI, Lee. A Genetic Algorithm for Two-Dimensional Bin Packing Problem[Un Algoritmo Genético para el problema de empaquetamiento en placas]. En: Research Bulletin of Institute for Mathematical Research. p.34 -39. 36 ALBANO, Antonio y SAPUPPO, Giuseppe. Optimal Allocation of Two Dimensional Irregular Shapes Using Heuristic Search Methods [Asignación óptima de piezas irregulares en dos dimensiones utilizando Heurísticas de búsquedas]. En: Systems, Man and Cybernetics, IEEE Transactions on. Mayo, 1980.Vol. 10, No. 5. p. 242-248. 41 simulado para la solución del problema, este también presenta una herramienta (ver Figura 3) en donde se pueden probar los métodos de búsqueda construidos. Figura 3. Herramienta para la distribución de piezas con formas regulares o irregulares en una lamina Fuente: Arfath Pasha37. 37 PASHA.Op. cit., p. 83. 42 3. DIAGNÓSTICO 3.1. GENERALIDADES DE LA EMPRESA 3.1.1. Misión “Somos una empresa dedicada a la fabricación de productos en madera, que se preocupa para que cumplan con los más altos estándares de calidad, buscando el mayor nivel de satisfacción de sus clientes, apoyándonos en los principios de honestidad, responsabilidad y cumplimiento para elaborar con precisión, exactitud y puntualidad nuestros pedidos con base en las exigencias de nuestros clientes”38. 3.1.2. Visión “La empresa FERROCARPINTERIA FORMAR se proyecta a ser la mejor opción a través del diseño y elaboración de productos modernos y funcionales que buscan dar respuesta a las necesidades y gustos de los clientes más exigente, y ser reconocida en el mercado por ofrecer buenos productos y a los mejores precios”39. 3.1.3. Reseña histórica FERROCARPINTERIA FORMAR es una empresa que con el pasar del tiempo ha sufrido varios cambios de propietarios, pese a esto siempre ha mantenido la misma razón social. En el año 1996 fue fundada como una empresa dedicada a la fabricación de productos en madera, con un nombre diferente al que tiene en la actualidad, cuyos fundadores fueron una sociedad entre familiares. Esta empresa fue constituida con el objetivo de generar empleo a la familia y satisfacer las necesidades de los consumidores de este mercado, fabricando principalmente muebles, puertas y cocinas integrales. La empresa fue registrada en la cámara de comercio como “FORMAR”. Esta sociedad tenía como socio capitalista a Justo Padilla Barros y como socio 38 PADILLA, Justo. FERROCARPINTERIA FORMAR. Cartagena, Colombia. Observación. 2012. 39 PADILLA, Justo. FERROCARPINTERIA FORMAR. Cartagena, Colombia. Observación. 2012. 43 operativo Walfran Villarreal (primo). La sociedad fue disuelta por problemas personales y diferencias de intereses entre socios, pero la empresa se mantuvo al conseguirse un nuevo socio operativo: Campo Elías Mieles y se cambió el nombre de la empresa a “FORMAS Y DISEÑOS”, manteniendo la misma línea de producción. Tiempo más tarde la sociedad con el socio operativo se disolvió quedando dos empresas por separado, en el año 2004: “SERVICARPINTERIA” y “FERROCARPINTERIA FORMAR”. Actualmente “FERROCARPINTERIA FORMAR”, tiene su local propio con un espacio de 500 mts cuadrados y se encuentra ubicada en la carretera a Mamonal diagonal 29 D # 56-63 manzana B lote 11B. 3.1.4. Organigrama El organigrama de la empresa FERROCARPINTERIA FORMAR se muestra a continuación: Figura 4. Organigrama de la empresa FERROCARPINTERIA FORMAR Gerente Jefe de Jefe de recursos Jefe de almacen operaciones humanos Fuente: Elaboración propia. La empresa FERROCARPINTERIA FORMAR, maneja cuatro procesos fundamentales, los cuales son: el proceso administrativo, procesos de 44 recepción de materiales y manejo de inventario, el proceso de fabricación, y el proceso de manejo de personal. 3.2. DESCRIPCIÓN DE LOS RECURSOS 3.2.1. Recursos Humanos. La empresa FERROCARPINTERIA FORMAR se encuentra conformada por un total de 22 trabajadores. 18 trabajadores operativos y 4 administrativos. Observe la distribución de cada uno en las siguientes tablas, en la Tabla 1personal administrativo, y en la Tabla 2personal operativo. Tabla 1. Recursos humanos administrativos Cargo Hombre Mujer Total Gerente general y jefe de recursos humanos 1 0 1 Jefe De Producción 1 0 1 Total administrativos 2 0 2 Fuente: Elaboración propia. Tabla 2. Recursos humanos operativos. Cargos Hombre Mujer Total Pintores 6 0 6 Carpinteros 5 0 5 Ayudantes 4 0 4 Tapiceros 1 0 1 Almacenista 1 0 1 Total operativos 17 0 17 Fuente: Elaboración propia. 45 3.2.2. Recursos Físicos 3.2.2.1. Maquinaria industrial. FERROCARPINTERIA FORMAR cuenta con nueve (9) máquinas industriales con las que realiza los procesos de alistamiento, preparado y moldeado de la madera, estas son descritas a continuación (ver imágenes en el Anexo 1):  Canteadora: Esta máquina es utilizada para obtener superficies planas en los cantos y caras a trabajar y de esta forma lograr un ángulo recto en dos caras adyacentes.  Sierra circular: Esta máquina está compuesta por una hoja de disco montada encima del tablero de la mesa, esta máquina es utilizada para cortar piezas grandes de madera en partes más pequeñas. La empresa posee dos cierras circulares una para realizar cortes a materia prima pesada, como es la madera, y la sierra circular liviana para realizar corte a materiales.  Sierra sin fin: Máquina que al igual que las otras sierras sirve para realizar cortes, pero con la diferencia que es utilizada para hacer cortes sinuosos o de rodeado y aserrados diversos, rectos, cilíndricos o transversales.  Cepillo: La principal funcionalidad de esta máquina es realizar cepillado a la pieza de madera para conseguir un espesor uniforme y adecuado para el trabajo a realizar. Para este efecto la pieza debe estar lisa y previamente plana en cada una de sus caras.  Trompo: Es una máquina utilizada en una gran variedad de trabajados como traslapos, cavas, machihembrados, y molduras; gracias a la sencillez de su montaje y a la fácil regulación de las de las herramientas que pueden fijarse a ella. 46  Taladro de columna: Es un taladro estacionario con movimiento vertical y mesa para sujetar el objeto a taladrar. La principal ventaja de este taladro es la absoluta precisión del orificio y el ajuste de la profundidad. La empresa cuenta con un (1) taladro de este tipo. 3.2.2.2 Maquinaria manual. Las maquinas manuales son utilizadas para facilitar el acabado de las piezas del producto que se va a ensamblar. La empresa posee 21 máquinas manuales, entre las cuales se encuentran (ver Anexo 2):  Compresor: Un compresor es una máquina de fluido que está construida para aumentar la presión y desplazar cierto tipo de fluidos llamados compresibles, tal como lo son los gases y los vapores. Esto se realiza a través de un intercambio de energía entre la máquina y el fluido en el cual el trabajo ejercido por el compresor es transferido a la sustancia que pasa por él convirtiéndose en energía de flujo, aumentando su presión y energía cinética impulsándola a fluir. Esta máquina es utilizada para el proceso de pintura.  Taladro: El taladro es una maquina manual que permite hacer agujeros en superficies, la empresa actualmente cuenta con seis (6) taladros eléctricos.  Sierra caladora: La máquina sierra caladora es una maquina eléctrica manual, que permite realizar cortes y moldes internos en la madera. El tipo de corte de la sierra caladora está dado por el tipo de hoja que se emplee. Las de dientes grandes dan un corte alternado, sirven para maderas y derivados, en tablas de hasta 60mm. 47  Ruteadora: Sirve para copiar piezas, con una calidad de corte excelente siempre que se cuente con una buena Ruteadora y una fresa bien afilada. La empresa cuenta con dos (2) Ruteadora manuales.  Sierra circular manual: Máquina compuesta de una hoja circular de bordes cortantes. Cortar tableros, maderas, plásticos. Permite variar la profundidad e inclinación del corte. La empresa cuenta con tres (3) herramientas manuales de este tipo.  Lijadora manual: Herramienta con una cuchilla giratoria de profundidad de corte regulable. Acabados de buena calidad, levanta finas capas de madera, dejando superficies lisas y brillantes. En la empresa existe una (1) lijadora manual.  Pulidora: Las pulidoras eléctricas son máquinas para pulir madera, que ayuda a conseguir superficies planas y lisas antes de realizar el proceso de pintados.  Engrapadora industrial: Esta herramienta es utilizada para unir dos láminas de madera, papel, tela, entre otros, colocando una grapa a través de los elementos que se unen.  Esmeril: Se utiliza para afilar las herramientas de taller y también para desbarbar piezas pequeñas. Generalmente lleva fijadas en cada extremidad del eje motor dos muelas o dos herramientas abrasivas. 48 3.2.2.3 Herramientas manuales. Las herramientas manuales son utilizadas para darle el acabado inicial a los productos fabricados; esto se utiliza en actividades donde las máquinas no pueden desempeñarse bien, ya que al utilizarla pueden dañar el acabado del producto, en la empresa se cuenta con herramientas tales como: martillo, destornillador, compas, formón, cepillo de madera manual (ver Anexo 2). 3.2.2.4 Materiales.  Materia prima: La materia prima utilizada por la empresa para la fabricación de los diferentes productos es la madera, siendo las más comunes el roble, cedro, pino, ceiba, teka y abarco. Como otra materia prima encontramos a las maderas prensadas, como lo son el Triplex, MDF, Table.  Insumos: Para la elaboración de los diferentes productos que ofrece la empresa, es necesario la adquisición de los siguientes insumos: Cerraduras, Tornillos, Puntillas, Chazos, Bisagras, Rieles, Pegamento, Tiradores. La empresa FERROCARPINTERIA FORMAR, cuenta con distintos materiales químicos que son utilizados en el proceso de fabricación, entre los cuales se encuentran: los tintes, la gasolina, el Thiner, el sellador catalizado y corriente, la laca de acabado, el ACPM, bar sol, y la brea. 3.3 PRODUCTOS Y PROCESOS DE FERROCARPINTERIA FORMAR 3.3.1 Productos La empresa FERROCARPINTERIA FORMAR ofrece a sus clientes una gran variedad de productos en maderas, acorde con las necesidades de cada uno de éstos, adicional a esto ofrece productos tales como: mesas, puertas ventanas, closet, cocinas integrales. 49 3.3.2 Procesos La empresa FERROCARPINTERIA FORMAR, maneja cuatro procesos fundamentales, los cuales son: el proceso administrativo, procesos de recepción de materiales y manejo de inventario, el proceso de fabricación, y el proceso de manejo de personal, esto se ven reflejado claramente en el siguiente mapa de procesos: Figura 5. Mapa de procesos de la empresa Fuente: Elaboración propia. 3.3.2.1 Procesos estratégicos.  Inteligencia de mercado: El responsable de este proceso es el gerente, quien hace actividades relacionadas con el contacto de clientes, promoción de los productos y seguimiento de los niveles de satisfacción de los clientes.  Comunicación con los proveedores: Al igual que el proceso descrito anteriormente este está bajo la responsabilidad del gerente, el 50 cual realiza actividades relacionada con la ubicación de proveedores estratégicos para la empresa. 3.3.2.2 Procesos de apoyo.  Gestión del talento humano: Este es manejado directamente por el gerente de la empresa, el proceso abarca el manejo de todos los trámites relacionados con los salarios y compensación de los trabajadores.  Gestión Financiera: El proceso de gestión financiera está a cargo del gerente, quien es el que coordina los pagos y de las diferentes obligaciones adquiridas por la empresa. 3.3.2.3 Proceso operativos. La totalidad de los productos que ofrece la empresa FERROCARPINTERIA FORMAR, tiene que pasar por los procesos de mecanizado, ensamblado, pre acabado y acabado superficial; tal como se mostró en el diagrama de procesos. A continuación se describen en detalle cada uno de estos procesos:  Recepción de materiales: Este proceso consiste en la coordinación de los pedidos a los proveedores y la posterior revisión, como también del control de las existencias de materiales y equipos existentes en bodega. De este proceso se encarga el almacenista.  Mecanizado: Este proceso consiste en la trasformación de la materia prima (trozos de madera grandes, láminas de triplex)en partes más pequeñas, para luego darles las dimensiones exactas de espesor, ancho y largo, de acuerdo a las especificaciones de los planos y listado de partes y piezas. Este proceso se encuentra dividido por tres sub procesos los cuales son: planificación del corte, corte y pulido de las pizas. 51  Ensamble: El proceso de ensamble es el proceso que se lleva a cabo para realizar el armado del mueble o producto en madera. En este se unen o acoplan las partes mecanizadas para lo que será el diseño del producto. Dicho proceso consta de tres actividades principales: el pre- armado, lijado y armado final.  Pre-acabado: El proceso de pre-acabado consiste en preparar el producto de madera para el proceso de pintura. El primer paso es aplicar masilla a las partes del mueble que lo requieran, con la finalidad descubrir las imperfecciones. Una vez se seca la masilla se procede a realizar el lijado final, este se realiza con lijas de papel para dar un acabado fino y suave a las piezas, seguido de esto se procede a aplicar sellador para obtener un acabado terso y uniforme, este es un producto de aerosol que tiene como propiedad sellar los poros de la madera aumentando el rendimiento de la pintura de acabado.  Acabado superficial: Para comenzar con este proceso, se verifica que producto casi terminado cuente con superficies lisas y libres de imperfecciones. El proceso de acabado tiene tres pasos, el primero consiste en aplicar el tinte del color que se desee, este es aplicado con un compresor de aire el cual es recargado con el tinte y se aplica de manera horizontal de derecha a izquierda. El segundo paso es aplicar un acabado, este es una laca brillante que impide que el tinte aplicado se ralle y que tenga mayor durabilidad. El tercer y último paso es el secado, paso necesario que se haga antes de entregar el producto, ya que permite que la pintura se adhiera de forma correcta al mueble en madera e impide que en el momento de transporte se raye. 52 3.4 PLANIFICACIÓN Y CORTE DE PIEZAS. La planificación y corte de piezas hacen parte del proceso de mecanizado, antes del corte es necesario realizar el proceso de planificación, el cual consiste en listar y posteriormente realizar un trazado de todos los componentes que conforman el producto en las láminas de triplex. El proceso comienza cuando se dan las especificaciones y dimensiones del producto, posteriormente se procede a realizar gráficamente los diferentes componentes de éste, los cuales llevan a su vez las medidas como lo son la anchura, altura y profundidad de cada pieza, los bocetos de cada parte del producto pasan a la sección de corte, donde se procede a realizar un trazado de cada uno de estos en las láminas de triplex, este proceso es realizado en forma manual y en la actualidad no existe un mecanismo predeterminado utilizado por el operario al momento de realizar la distribución de los componentes del producto en las láminas. Cuando se culmina con el trazado de las piezas en las láminas, se procede al corte, para esto se tiene en cuenta que cuando las piezas son con dimensiones rectangulares, el corte se realiza en la cierra circular, mientras que para piezas que tienen formas de polígonos de ángulos rectos el corte se realiza en la cierra sin fin. A continuación se muestra en forma más detallada, la caracterización del proceso de mecanizado del triplex en la fabricación de una cocina integral: 53 Figura 6. Diagrama BPM para la descripción de corte de piezas de triplex Fuente: Realizado por el equipo de trabajo. 3.5 INSTANCIA OBJETO DE ESTUDIO Como se ha explicado anteriormente, en la presente investigación se busca optimizar el proceso de distribución y corte de piezas en láminas de triplex en la empresa FERROCARPINTERÍA FORMAR, dado que la empresa ofrece gran variedad de productos a sus clientes, es de vital importancia definir uno, al cual se le optimizará el proceso de distribución y corte de los diferentes componentes, para esto es necesario saber las diferentes piezas que conforman al producto (solo aquellos componentes de triplex), a este conjunto de componentes se les llamará como caso de estudio. 3.5.1 Elección del producto En la actualidad la empresa cuenta con pocos productos estándares, esto se debe a que el sistema de producción es por pedidos y adicional a esto, muchos de los productos son hecho acordes con especificaciones particulares de cada cliente. Esto hace que de antemano sea complicado establecer un número estándar de piezas que serán distribuidas en las 54 láminas, y posteriormente cortadas ya que esto depende del tipo de producto que esté en lista de espera para la fabricación. Por tal motivo se procedió a realizar un análisis detallado de los productos ofrecidos por la empresa y se encontró que anualmente los de mayor venta son: puertas, closet y cocinas integrales; de las cuales este último es de mayor rotación y además es el que tiende a mantener una forma estándar, es decir, los requerimientos de los clientes para este producto como las dimensiones y los acabados son muy similares. Adicionalmente, éste es el que genera mayor margen de ganancia y consumo de triplex en comparación con los demás productos, lo cual lo hace el más adecuado para optimizar el proceso de corte. En el siguiente diagrama de Pareto se muestra la contribución a las utilidades de la empresa por cada producto, y en el anexo 13 se presentan un conglomerado de las utilidades por producto anualmente. Figura 7. Diagrama de Pareto de utilidades por producto. Fuente: Elaboración propia. Como se puede observar el 80% de los ingresos de la empresa está dado por la fabricación y venta de las cocinas y otros productos, donde en la categoría de otros productos encontramos los que son hechos acorde con 55 las especificaciones de los clientes, como lo son muebles, mesas, comedores, sillas, etc. 3.5.2 Descripción del producto: Para este estudio se seleccionó a las cocinas integrales como el producto adecuado para realizar la mejora del proceso de distribución y corte de las piezas. Éste cuenta con dos partes denominadas módulo superior y módulo inferior, a continuación se muestra las dimensiones de cada una de estas: Módulo superior:  Ancho: 180 cm  Alto: 50 cm  Profundidad: 30cm Cuenta con 4 puertas de dimensiones de 30 cm de ancho, 50 cm de alto por 2 cm de profundidad, y dos puertas pequeñas con dimensiones de 30 cm de ancho, 25 cm de alto y 2 cm de profundidad. Módulo inferior:  Ancho: 180 cm  Alto: 73 cm  Profundidad: 50cm Cuenta con 4 puertas de dimensiones de 30 cm de ancho, 50 cm de alto por 2 cm de profundidad, cinco gavetas, dos con la forma similares, mientras que las restantes tienen otra apariencia. Para la fabricación del producto, se utiliza láminas de triplex de 12 mm de espesor. En la siguiente figura se muestra un diseño de las cocinas realizadas en la empresa. 56 Figura 8. Modelo del producto realizado en la empresa Fuente: realizado por el equipo de trabajo. 3.5.3 Caracterización de las piezas que conforman el producto. A continuación se encuentra listada cada una de las piezas (que se obtendrán a partir de láminas de triplex) y las cantidades necesarias para fabricar una cocina integral: Tabla 3. Descripción de piezas de una cocina integral. Hoja 1 de 5 IMAGEN ID DESCRIPCIÓN CANTIDAD Esta pieza 1 corresponde a la cara 1 posterior de la cocina. Esta pieza hace parte de las puertas del 2 módulo superior de la 8 cocina y del módulo inferior de la cocina. 57 Hoja 2 de 5 IMAGEN ID DESCRIPCIÓN CANTIDAD Esta pieza forma parte de la puerta pequeña 3 que se encuentra en el 2 módulo superior de la cocina. Esta forma la cara 4 frontal de las gaveta 2 derechas del modulo inferior de la cocina. Divide el 5 compartimiento interno 2 del modulo inferior Esta pieza forma parte 6 de la cara lateral 1 derecha del modulo superior de la cocina Esta pieza divide en 7 compartimiento el 1 interior del modulo superior. 58 Hoja 3 de 5 IMAGEN ID DESCRIPCIÓN CANTIDAD Esta pieza conforma la 8 cara inferior del 1 módulo superior de la cocina. Esta pieza conforma la 9 cara inferior del 1 módulo superior de la cocina. Eta pieza se encuentra 10 ubicada en el modulo 2 superior de la cocina. Esta pieza divide en 11 compartimiento el 1 interior del modulo superior. 12 Esta pieza hace pate del módulo inferior de 2 la cocina. 59 Hoja 4 de 5 IMAGEN ID DESCRIPCIÓN CANTIDAD Esta piza corresponde 13 a la cara superior e 2 inferior del módulo inferior de la cocina. Esta pieza forma el 1 14 respaldo de el modulo inferior de la cocina Esta pieza se encuentra ubicada en 15 el modulo inferior de la 4 cocina, este divide en compartimiento de las gavetas. Esta pieza hace parte 16 de las gavetas del 3 módulo inferior de la cocina. Esta pieza hace parte 17 de las caras laterales 10 de la gaveta 60 Hoja 5 de 5 IMAGEN ID DESCRIPCIÓN CANTIDAD 18 Esta forma el fondo de 5 la gaveta. Esta pieza forma la 19 parte trasera de la 5 gaveta Esta pieza 20 corresponde a la cara 1 superior de la cocina Fuente: Elaboración propia. A continuación se muestra la ubicación de cada una de las piezas en la cocina integral.  Ubicación en el módulo superior: Como se puede observar, la mayoría de las piezas utilizadas en la construcción de la cocina son rectángulos, tal como se mostraron anteriormente; a excepción de algunas que forman las puertas del producto como se puede ver en la Figura 9. 61 Figura 9. Ubicación de las piezas en el módulo superior Fuente: Elaboración propia. A este tipo de piezas se denota como polígono de ángulo recto, dado que poseen varios lados y además el ángulo formado entre lados consecutivos es de 90°. En la Figura 10 se observa que solamente está enumerada la pieza del centro, esto se debe a que los marcos son de madera, razón por la cual no se tiene en cuenta ya que en este trabajo se busca optimizar el consumo de material triplex. Figura 10. Pieza de las puertas Fuente: Elaboración propia. 62  Ubicación de las piezas en el módulo inferior. Figura 11. Ubicación de las piezas en el módulo inferior Fuente: Elaboración propia. Al igual como sucedía con las puertas que fueron presentadas con anterioridad, en la parte frontal de las gavetas también se cuenta con un marco de madera que no se enumerarán como piezas, tal como se muestra en la siguiente figura. Figura 12. Gaveta del módulo inferior Fuente: Elaboración propia. 63 De igual forma existen gavetas que en la parte frontal cuenta con figuras que no son rectángulos (polígono de ángulo recto). Tal como se muestra en la figura 13. Figura13.Gaveta con pieza de polígono de ángulo recto Fuente: Elaboración propia. 3.5.4 Formulación del indicador de desperdicio. En la actualidad en la empresa FERROCARPINTERÍA FORMAR no existe un mecanismo que permita llevar el control del consumo de triplex, razón por la cual se procedió a formular la siguiente expresión que relaciona el área no utilizada en la distribución de las piezas del producto en comparación con el área total de la lámina. Ecuación 1. Indicador de desperdicio Fuente: Elaboración propia. 64 Donde: =Indicador promedio de desperdicio =Área total de las láminas =Suma de las áreas de las piezas ubicadas en las láminas. 3.5.5 Promedio histórico de desperdicio. Teniendo en cuenta que las distribuciones de las piezas varían en la fabricación de las cocinas, es decir, no existe una distribución estandarizada para el corte de las piezas, se deberá calcular un promedio histórico de desperdicio que permita establecer el porcentaje de material desechado en el proceso de corte en la empresa. Debido a que en la actualidad FERROCARPINTERÍA FORMAR no cuenta con registros detallados de los desperdicios generados en el corte de las láminas de triplex, fue necesario recolectar información relacionada con las distribuciones de las piezas por producto durante un periodo de tres meses (periodo de duración de la investigación), durante el cual se fabricaron 10 cocinas integrales con las características del producto escogido como instancia objeto de estudio, y a cada distribución del producto se le calculó el índice de desperdicio con la ayuda de la ecuación 1. Se realizaron en total 10 mediciones, es decir, se calculo el porcentaje de desperdicio a diez (10) distribuciones, cada una correspondiente a una cocina integral. Tabla 4. Datos históricos de indicador promedio de desperdicio MUESTRA 1 2 3 4 5 6 7 8 9 10 Desperdicio 28,50% 35,10% 34,70% 28,40% 31,10% 33,00% 29,80% 32,50% 31,20% 34,10% promedio. Fuente: Elaboración propia. De los datos presentados se puede determinar que el porcentaje promedio de desperdicio generado en el proceso de corte es del 31.84% para la 65 distribución. Esta servirá como medio de comparación con las distribuciones arrojadas por la herramienta. En el Anexo 5 se presenta una distribución representativa de la distribución manual de las piezas realizada en la empresa. 3.5.6 Análisis del costo de los desperdicio. La empresa para su proceso de fabricación utiliza lámina de triplex de 240 cm x 120 cm con 12 mm de grosor, en el mercado actual estas se cotizan en $66.000 pesos. Dado que el porcentaje de desperdicio promedio está alrededor de 31.84%, se puede establecer cuál es la perdida mensual de dinero, para esto, en primera instancia se determina el área no utilizada en el proceso de corte, la cual resulta del producto entre el porcentaje promedio de desperdicio y el área utilizada en la distribución de la piezas. Para la distribución de un producto el cálculo del área utilizada está dado por la suma de las áreas de las láminas en las que se distribuyeron piezas, teniendo en cuenta que en la última lámina el área se determina con la altura máxima. Se debe tener en cuenta que para el corte de las piezas de una cocina, basados en la distribución manual, en la actualidad se utilizan en promedio 7 laminas por producto. De esta forma el área promedio utilizada es la media de los valores obtenidos de las distribuciones manuales realizadas durante el tiempo que se registraron las mediciones, cuyo resultado es 18,46 m2. En la siguiente tabla se mostraron los cálculos de los desperdicios en términos monetarios para el proceso de corte en la empresa, teniendo en cuenta que para el cálculo de los costos mensuales se fundamento el cálculo en un promedio de fabricación de cinco cocinas en dicho periodo (información suministrada por la empresa). 66 Tabla 5. Análisis de costo para la distribución manual RESULTADO DESCRIPCIÓN FÓRMULA ( ) Área 5,88 m2 desperdiciada ( ) Costo desperdicio $134.842,40 por producto ( ) ( ) ( ) Costo desperdicio $674.212,00 mensual. ( ) Costo desperdicio $ 8.090.544,00 anual. Fuente: Elaboración propia. 3.5.7 Tiempo utilizado en la distribución de las piezas de forma manual. En el cálculo del tiempo empleado por la distribución manual se utilizó el cronómetro como instrumento de medición, en el caso de la muestra utilizada para el cálculo del promedio histórico de desperdicio se tomó el tiempo que empleaba el operario en distribuir las piezas en cada lámina, cabe resaltar que el tiempo de distribución no incluye el de trazado, por lo cual se realizaba pausas en el cronómetro cuando el operario comenzaba a realizar el trazado, de esta forma el tiempo de distribución es aquel comprendido entre la terminación del trazado de una pieza y el comienzo del trazado de otra (cuando se piensa la ubicación de una pieza en la lámina). En el anexo 11 se muestra una tabla que refleja los tiempos empleados para diez distribución manuales, teniendo en cuenta el tiempo empleado en ubicar las piezas en cada lámina, a partir de esta información se establece el 67 tiempo empleado para realizar la distribución de cada producto, primero sumando los tiempos empleado en hacer la distribución de las piezas en las láminas y luego promediando para los diez datos obtenidos. De esta forma se tiene que el tiempo promedio empleado en realizar la distribución de forma manual es de 32,5 minutos. 68 4 HERRAMIENTA COMPUTACIONAL 4.1 DISEÑO DEL ALGORITMO GENÉTICO. El algoritmo genético sigue los pasos descrito en la figura 14, como en la mayoría de los casos, se tiene una población inicial la cual es generada de forma aleatoria, para esto es necesario de la ayuda de una heurística, la cual se le denomina como “heurística para polígonos de ángulo recto”, esta servirá para establecer el orden en que se van empaquetando las piezas y así determinar la adaptación para cada individuo con la ayuda de la función fitness, seguido se procede a realizar el proceso de selección, en el cual se determina cuales individuos pasa al proceso reproductivo acorde con los resultados arrojados por la función fitness. Una vez seleccionado los más aptos, se realiza una combinación de sus códigos genéticos y de esta forma se producen nuevos cromosomas hijos, los cuales contiene información genética de sus padres, luego esta nueva generación muta, proceso en el cual el código genético de los cromosomas es alterado, posteriormente a estos nuevos individuos son evaluados con la función fitness, la cual servirá de base para determinar que individuos serán remplazados de la población actual, teniendo como criterio que aquellos menor adaptados son remplazados por los mejor adaptados. 69 Figura 14. Diagrama de flujo para el algoritmo genético Fuente: Elaboración propia. 4.1.1 Codificación Un aspecto importante a la hora de construir el algoritmo genético, es la forma como se representan las soluciones del problema a tratar, para el caso del bin packing problema en dos dimensiones, existen tres formas usuales de codificar las soluciones, según Mitsuo Gen40, estas son: representación basada en láminas (bin-based representation), representación basada en objetos o piezas (object-based representation) y representación basada en grupos (group-based representation). Como se verá más adelante, la utilización de una determinada codificación no representa una solución completa para el problema tratado, ya que esta solo hace el ejercicio de asignar las piezas a las láminas, por tal motivo es necesario recurrir a una heurística que permita establecer la ubicación exacta en la que se posicionan las piezas en las láminas. 40 Mitsuo gen, Runweicheng, Genetic Algorithms and Engineering optimization. John Wiley & Sons, Inc.new York 2000.Página 65. 70 4.1.1.1 Representación basada en láminas (Bin-Based Representation) Esta codificación se caracteriza porque la posición del gen representa la pieza, mientras que su valor respectivo representa la lámina donde se va a empacar esa pieza, tal como se muestra en la figura 15; para este ejemplo la secuencia 4 6 5 3 2 1, representaría una solución en la cual la pieza 1 se empaca en la lámina 4, la 2 en la 6, la tres en la 5, la 4 en la 3, la 5 en la 2 y la 6 en la 1. Figura 15. Representación basada en láminas Fuente: Elaboración propia. Esta denotación tiene sus ventajas y desventajas, dentro de las desventajas se encuentra que de antemano se debe conocer el número de láminas necesarias para empacar todos los objetos, otra desventaja se refleja en la alta probabilidad de presentarse redundancia, está se muestra cuando existen dos cromosomas con secuencias diferentes que representan la misma solución del problema, por ejemplo dado el par de cromosomas: representación 1: 4 1 5 5 3 2 2y representación 2: 1 5 2 2 4 3 3, se observa en la figura 2, que es la misma solución, esto se debe a que el fitness de una solución particular depende solamente de las piezas que estén empacadas juntas en una lámina en particular. Figura 16. Representación de la redundancia en las soluciones 2 6 7 5 1 3 4 1 3 4 6 7 5 2 Cromosoma 1 Cromosoma 2 Fuente: Elaboración propia. 71 Este problema es aún más recurrente cuando el número de láminas es mayor, por tal motivo se dice que “el grado de redundancia crece exponencialmente con el número de láminas utilizadas”41, lo cual hace que el espacio de búsqueda del problema se torne más grande, haciendo que disminuya la capacidad del algoritmo genético para dar con buenas soluciones en tiempos razonables. De igual forma, para este tipo de codificación, es frecuente que se presente soluciones infectables, debido a que en una representación del cromosoma puede haber muchas piezas en una determinada lámina, lo cual entra en conflicto con la restricción de capacidad de área de las láminas. Una de las ventajas de este sistema de codificación, es que el tamaño de los cromosomas es constante, lo cual permite la aplicación de los operadores genéticos estándares. 4.1.1.2 Representación basada en objetos (object-based representation) La codificación basada en objeto consiste en una permutación de piezas dadas, en ésta, a diferencia de la representación basada en láminas, los valores de cada gen representa a las piezas, mientras que el sub índice solo sirve para indicar el orden en el cual se empaca en la láminas, por ejemplo; dado el siguiente cromosoma 3 2 4 5 6 1, en la representación basada en objetos quedaría como se muestra en la Figura 17. En este ejemplo, las láminas están representadas por los intervalos comprendidos entre los segmentos de recta rojos, como se muestra en la figura 17, para este caso se puede ver que en la lámina 1 se empacan las piezas 3,2, en la lámina 2 se empacan las piezas 4,5 y en la lámina 3 se empacan la piezas 6,1. 41 Mitsuo gen, Runweicheng, Genetic Algorithms and Engineering optimization. John Wiley & Sons, Inc.new York 2000.Página 65. 72 Figura 17. Representación basada en objetos. Fuente: Elaboración propia. La representación basada en objetos, al igual que la basa en láminas, presenta alto grado de redundancia entre soluciones, como por ejemplo el par de cromosomas siguientes: Figura 18. Redundancia en la representación basada en objetos Fuente: Elaboración propia. En esta representación, a diferencia de la discutida anteriormente, no es necesario conocer de antemano el número de láminas necesarias para empacar a las piezas, además el número de piezas a empacar no necesariamente deben ser las mismas en cada lámina, como se mostró en los ejemplos anteriores; esto depende básicamente del tamaño de las piezas, por lo cual puede haber láminas que tengan tres piezas como otras que tengan dos. 4.1.1.3 Representación basada en grupos (Group-Based Representation) Esta representación del cromosoma integra los conceptos visto en la representación basada en objetos y láminas, la representación Group-Based 73 Representation cuenta con dos partes, la primera informa que pieza pertenece a que lámina y la segunda nos da información acerca de que lámina es utilizada. Para ilustrar como se codifica con este esquema, supóngase que hay varias piezas enumeradas de 1 a 6 y un cromosoma dado por la secuencia (2 3 4 1 2 5), lo cual representa que la pieza 1 se empaca en la lámina 2, la dos en la tres y así sucesivamente; a cada gen del cromosoma lo remplazamos por una letra, en este caso podemos decir que C=2, J=3, U=4, T=1, W=5; por tal motivo el cromosoma bajo el esquema de la representación de grupos quedaría tal como se ilustra en la figura 19. Figura 19. Representación base del cromosoma Fuente: Elaboración propia. Para que la anterior representación agrupe a las piezas por láminas, se debe agrupar las letras que se repiten a lo largo del cromosoma, de esta forma como la lámina C=2 se repite dos veces, la codificación según el group based representation queda de la siguiente forma: Figura 20. Representación basada en grupos Fuente: Elaboración propia. 74 Entre las desventajas de la representación mediante grupo se encuentra que el tamaño de los cromosomas es variable, esto hace que la implementación de los diferentes operadores sea más compleja. Para la implementación del algoritmo genético se utiliza la representación basada en objetos, porque en la literatura se ha encontrado varios trabajos en los cuales la codificación de las soluciones se ha realizado mediante el object-based representation, como es el caso de Arfath pasha42, LeeLaiSoon43, entre otros. Además a nivel de los operadores genéticos la implementación es muy manejable con esta codificación. 4.1.2 Operados genéticos 4.1.2.1Operador de selección Los algoritmos genéticos emulan el proceso evolutivo de los seres vivos, en el cual los individuos más fuertes de una especie pasan a hacer parte de la siguiente generación, de esta forma, en el contexto del algoritmo genético, es necesario definir un mecanismo el cual permita seleccionar a individuos (cromosomas) de una población inicial, y que posteriormente pasen a reproducirse. El criterio utilizado para la selección se basa en la evaluación de los individuos mediante una función fitness, la cual dará una medida de cuan adaptado se encuentra los integrantes de la población y combase en esto, asignar una mayor posibilidad de ser seleccionado a los individuos más aptos. En la literatura existen diferentes tipos de operadores de selección, entre los cuales encontramos, torneo, ranking, truncamiento y el método de selección por proporciones propuesto por J. holland, los cuales se dividen en rueda de ruletas (RWS - Rulette Wheel selection) y selección por muestreo aleatorio universal (SUS-stochastic universal sampling)44 .Estos últimos son 42 Arfathpasha.Op. cit., p. 28. 43 Lee Lai Soon.Op. cit., p. 1. 44 J. Dreo A. Petrowski, Metaheuristics for hard optimization, Springer-Verlag Berlin Heidelberg 2006; Página 83. 75 los más utilizados por los buenos resultados obtenidos, razón por la cual en este trabajo se abordarán con más detalle.  Método de selección de rueda de ruletas (RWS) Éste método se basa en la asignación de una probabilidad de selección, en proporción al fitness de cada uno de los individuos de una población, esto se hace con el fin de que los cromosomas de los individuos más aptos tengan mayor probabilidad de pasar a la siguiente generación. El proceso de selección comienza cuando se genera una población inicial de cromosomas, a los cuales se les calcula su respectivos fitness, luego se procede a asignar una probabilidad de selección a cada cromosoma de la población, acorde con la siguiente fórmula: Ecuación 2. Fórmula de cálculo de probabilidad ∑ Donde cada y representa la probabilidad que sea seleccionado y el fitness de cada individuo respectivamente. La letra representa el total de la población generada, para ilustrar en forma más clara esta situación, suponga que se cuenta con una población inicial y su respectivo fitness como se muestra en la figura 21. Tabla 6. Población inicial 1 2 3 4 5 200 500 800 100 250 0,108 0,270 0,432 0,054 0,155 Fuente: Elaboración propia. 76 Los para cada individuo, fueron calculada con la fórmula mostrada en la ecuación 2, el anterior ejemplo podemos representarlo como si fuera una lámina la cual es dividida en porciones de tamaños diferentes, acorde con la probabilidad de selección determinada, como se muestra en la figura 21. Figura 21. Asignación de probabilidad a individuos Fuente: Elaboración propia. El siguiente paso en el proceso de selección consiste en obtener un número aleatorio y mirar a qué intervalo de la Figura 21 pertenece, luego se procede a seleccionar el individuo asociado con dicho intervalo.  Selección universal aleatoria (SUS) Este mecanismo de selección es una mejora al anteriormente expuesto, la forma como en este método se asignan las probabilidades a cada uno de los individuos de la población es igual al realizado en el (RWS), la diferencia se encuentra en que éste considera una recta dividida en segmentos iguales, en el cual el número de divisiones es igual al tamaño de la población. Una vez determinado el número de divisiones de las rectas y la magnitud de estas, al igual que el método de la ruleta, se procede a generar un número aleatorio luego hace coincidir un extremo de la recta con el número aleatorio, esta situación se ilustra claramente en la Figura 22. En el anterior ejemplo las flechas que apunta a cada una de los individuos son los que van a ser elegidos para la reproducción, en este caso fueron escogidas las soluciones 3, 2, 2, 1 mientras que los individuos representados por 5 y 4 no lo fueron. 77 Figura 22. Mecanismo de selección mediante el SUS Fuente: Elaboración propia. En el operador de cruce SUS solo se necesita un número aleatorio y con este se obtiene a todos los individuos que harán parte del proceso de reproducción, por el contrario el ruda de ruletas generan tantos números aleatorios como individuo se desean seleccionar, lo cual hace de éste un mecanismo ineficiente al momento de realizar la implementación, ya que a nivel computacional se tiene que realizar más instrucciones en comparación con el SUS, por tal motivo en la construcción de la herramienta se utilizará el operador SUS. 4.1.2.2 Operador de cruce Entre los operadores de cruce más utilizados, encontramos cruce por un punto (one-point crossover), cruce por dos puntos, uniforme, PMX, OX.  Cruce por un punto Es uno de los operadores de cruce más simple y comúnmente usado, este operador corta el código del cromosoma, en una posición indicada al azar y luego procede a intercambiar la información genética entre los cromosomas. Para ilustrar como funciona, suponga que se tiene el par de cromosomas: 2 3 4 5 1 y 1 3 2 5 5. En ambos cromosomas se ubica la posición correspondiente indicada por un número aleatorio, imagine que el número aleatorio indica la posición comprendida entre 1 y 2 de los cromosomas, tal como lo indica la Figura 24. 78 Figura 23 . Representación del punto de corte del cromosoma Fuente: Elaboración propia. Ésta indica el punto de corte, en el cual los cromosoman se dividirán en dos partes, combinándose el primer segmento de código del primer cromosoma, con el segundo del cromosoma 2, y el primer segmento del cromosoma 2 con el segundo segmento del cromosoma 1, como se ilustra en la Figura 24. Figura 24. Cruce por un punto Fuente: Elaboración propia. Como resultado obtenemos dos cromosomas hijos, donde cada uno de ellos tiene información genética de cada uno de los padres. 79  Cruce por dos puntos El cruce por dos puntos se trata de una generalización del cruce por un punto45, en este en ves realizar un solo corte, realiza dos, para lo cual es necesario tener un par de números aleatorios que indicarán en qué posición de los cromosomas se dará los puntos de corte, en esta parte tiene que validarse que dichos números no indique la posición extrema de los cromosomas, esto con el fin de garantizar que se formen tres segmentos y así proceder con el intercambio de los códigos genéticos entre los individuos, este proceso ser ilustrado en la siguiente figura. Figura 25. Cruce por dos puntos Fuente: Elaboración propia. En el ejemplo anterior se procedió a insertar el segmento central de cada cromosoma en cada uno de los hijos, y posteriormente a rellenar las casillas restantes de cada uno de los cromosomas con información genética del padre contrario al que había heredado el segmento de código central. Es evidente que se puede añadir más punto de cruce pero se ha demostrado que no es conveniente46, entre una de las desventajas de tener varios puntos 45 Gestas Marcos, Introducción a Los Algoritmos Genéticos; Departamento de la Información y las Comunicaciones, universidad de Coruña. Página 10. 46 Gestas Marcos, Introducción a Los Algoritmos Genéticos; Departamento de la Información y las Comunicaciones, universidad de Coruña. Página 11. 80 de corte está el hecho de reducir el rendimiento del algoritmo, y entre las ventajas se encuentra el brindar al algoritmo la capacidad de explorar el espacio de búsqueda más afondo.  Operador de cruce uniforme En éste operador, cada gen de los padres tienen la misma oportunidad de pertenecer a los hijos, este mecanismo de selección tiene varias formas de implementarlo, uno de esto consiste en generar un número aleatorio, si este supera un cierto umbral se elige un gen de un padre determinado, de lo contrario se elige del otro. La técnica más usual de implementar este operador, es creando una máscara de cruce. Una máscara de cruce consiste en un arreglo binario que tiene la misma longitud de los cromosomas de los padres. Este es creado de forma aleatoria, si una posición del arreglo es 1, entonces el cromosoma descendiente adquiere el gen de esa posición que está en el cromosoma padre uno, de los contrario adquiere del cromosoma padre dos. Este proceso de cruce se ilustra claramente en la Figura 26. Para este mecanismo de reproducción, se puede definir un operador de cruce basado en la función fitness, en el cual al momento de crear el arreglo binario, se asigne más probabilidad de ser seleccionado al individuo con mayor adaptación, por ejemplo si en la Figura 26, el cromosoma 2 tiene mejor función adaptación que el cromosoma 1, al momento de construir la máscara de crúcele daríamos la opción de asignar mayor probabilidad de tener más ceros que uno. 81 Figura 26. Operador de cruce uniforme Fuente: Elaboración propia.  Operador de cruce por segmento parcial (PMX) Este operador consiste en la copia de un segmento de cadenas del cromosoma de unos de los padres, para insértalo en el cromosoma hijo y posterior mente llenar los espacios en blanco con la información del otro padre, tal que los genes no se repita a lo largo del código genético. Para ilustrar este mecanismo de cruce, suponga que se tiene las cadenas de códigos que se muestran a continuación. 2 3 4 5 1 y 1 3 2 4 5, el primer paso consiste en copiar un segmento de uno de los padres para este ejemplo se elige 3 4 del cromosoma uno y se inserta en la misma posición del cromosoma dos. Tal como se muestra en la Figura 27. Posteriormente, se busca en el cromosoma hijo los genes que se repite, como se ve en la ilustración el gen que se repite se encuentra en la posición 4, razón por la cual es remplazado por uno que no esté presente en la codificación resultante. 82 Figura 27. Operador de cruce PMX Fuente: Elaboración propia.  Order crossover (OX) En este mecanismo de cruce se selecciona un segmento de código genético de cada cromosoma padre, los cuales son copiados en forma directa a sus hijos, luego los espacios que resultan en cada cromosoma hijo (casilla de genes vacíos) son llenados en forma ordenada con los genes del padre restante. Para ilustrar este mecanismo, del ejemplo anterior se coge los dos padres representados por el códigos 2 3 4 5 1 y 1 3 2 4 5. Seguido se selecciona los segmentos 3 4 y 3 2 de los cromosomas 1 y 2 respectivamente, que serán insertados en los hijos 1 y 2. Lo cual da como resultado (*, 3, 4, *, *) para el cromosoma hijo 1 y (*, 3, 2, *, *) para el cromosoma hijo 2. Luego los espacios en blanco de cada cromosoma hijo son llenados en forma ordenada cogiendo la información genética del padre del que aún no ha recibido información genética, en este caso los espacios en blanco del cromosoma hijo 1 son completados con los genes del cromosoma padre 2, por el contrario el cromosoma hijo 2 es completado con la información genética del cromosoma 1. Para el llenado se parte de un punto de corte y se copia la información genética respetando el orden en el que se encuentran dispuesta en cada cromosoma padre, de esta forma 83 para el ejemplo tratado se tiene que los cromosomas hijos quedarían de la siguiente forma: (2, 3, 4, 5, 1) y (4, 3, 2, 5 ,1). 4.1.2.3 Operador de mutación Después del cruce se da la mutación, esta permite que el algoritmo genético tenga un campo más amplio en la exploración del espacio de búsqueda. La mutación consiste en la modificación de ciertos genes de forma aleatoria, por tal motivo el tipo de codificación utilizada es de suma importancia, para el caso del bin packing problem tenemos que la representación de las soluciones necesariamente tienen que ser por objetos, debido a que es poco conveniente realizar cambios aleatorios en el orden de llenado de las láminas cuando se utiliza una codificación basadas por láminas. Para el caso de la representación basada en objetos o pieza, existe una gran variedad de operadores, entre estos están el operador de mutación basado en el desplazamiento el cual consiste en la selección aleatoria de un grupo de objetos de un cromosoma y su posterior ubicación en un lugar distinto seleccionado aleatoriamente dentro del cromosoma, el operador de mutación basado en inserción; este consiste en la selección aleatoria de un objeto (gen) del cromosoma, sacarlo e insértalo en un lugar distinto seleccionado aleatoriamente, operador de mutación basado en la inversión simple el cual consiste en la selección de dos puntos de corte seleccionados aleatoriamente, luego los genes comprendidos entre estos puntos de cortes les es invertidos el orden en el que se encuentran. Y finalmente encontramos al operador de mutación basado en el doble intercambio (2-opt), este consiste en seleccionar dos objetos aleatoriamente y se procede a intercambiar tal que uno ocupe la posición del otro, de antemano se tiene en cuenta que los números aleatorios utilizados para la selección de los objetos (piezas) no sean los mismos. Esta situación se puede observar claramente en la siguiente figura. 84 Figura 28. Operador de mutación 2-opt Fuente: Elaboración propia. Como se había mencionado anterior mente, la mutación es de vital importancia porque le da capacidad al algoritmo de ampliar su espacio de búsqueda sin dejar que caiga rápidamente en mínimos locales. Por otro lado se tiene que si se abusa de la mutación se incurre en el error de que el algoritmo genético solo efectúe búsquedas aleatorias, razón por la cual es conveniente trabajar con porcentaje de mutación bajo. 4.1.2.4 Operador de remplazo Este operador consiste en la sustitución de algunos integrantes de la población por nuevos individuos generados, entre los operadores de remplazo más conocido está el elitismo, el cual se basa en la función adaptación (función fitness), para saber cuál individuo o representación de una solución es la más adecuada y de esta forma dar prioridad a estos individuos de permanecer en las generaciones futuras, de esta forma y al igual que en el proceso de evolución natural, los soluciones menos factibles son remplazadas por las que tienen mejor fitness. Adicional a este existe otro operador denominado generacional, el cual consiste en la sustitución de la población inicial por una nueva. Para la implementación se utiliza una mescla de los dos operadores descrito con anterioridad, inicial mente se evalúa a los individuos más aptos y estos pasan a remplazar a los individuos de la población. 85 4.1.3 Heurística para el bin packing problem Como se pudo observar en la codificación de las soluciones para el bin packing problem, éstas nos brindan información relacionadas con la asignación de piezas a cada lámina, pero la posición de cada pieza en ésta no se puede saber con este tipo de representación, razón por la cual es necesario hacer uso de una heurística que permita distribuir la pieza para así saber cuál es la ubicación de cada una dentro de la lámina. Para este caso Jakobs propone el algoritmo llamado Bottomleft47, el cual consiste en colocar la pieza lo más abajo y a la izquierda posible. El algoritmo empieza cuando introduce una pieza y la lleva al fondo de la placa hasta encontrar un límite que está determinado por la forma de la lámina o de las piezas puestas con anterioridad. Luego ésta es rodada hasta el extremo izquierdo, tal como se muestra en la Figura 29. Figura 29. Secuencia de empaquetamiento Fuente: Elaboración propia. 47Amarras de la peña Jorge, Parra Truyol Antonio, resolución del problema deStrip-packing mediante la Metaheurística algoritmos genéticos.Universidad Carlos III, página 2. 86 Si bien, previo al inicio del empaquetado se establece como límites los bordes de la lámina, en la medida que se va llenando estos se van remplazando por los bordes de las piezas que se van empacando. Tal como se muestra en la siguiente figura, donde el borde rojo representa el nuevo límite. Figura 30. Reconstrucción de los límites Fuente: Elaboración propia. En resumen lo que hace la heurística es arrastrar la pieza hacia abajo, si encuentra algún límite rueda la pieza a la izquierda. Esta heurística presenta dos inconvenientes, el primero está relacionado con la posibilidad de que dos cromosomas diferentes pueden representar la misma distribución dentro de la lámina y por ende el mismo fitness48, esta situación se ilustra en la Figura 31. En este caso vemos que la figura puede estar representada por la secuencia (1, 2, 3) y (1, 3, 2). Si se mira con mayor detalle la secuencia uno, podemos ver que la heurística comienza insertando la pieza 1, la baja al fondo y posteriormente la rueda a la izquierda, así mismo hace con la pieza dos y la ubica justo al lado de la pieza 1, finalmente la pieza 3 es arrastrada hacia 48 Amarras de la peña Jorge, Parra Truyol Antonio, resolución del problema deStrip-packing mediante la Metaheurística al goritmos genéticos. Universidad Carlos III, página 2. 87 abajo, como la pieza dos impide que llegue al fondo ya que como se explicó anteriormente los límites reconstruidos impiden la sobre posición de las pieza, entonces es arrestada a la izquierda. Ahora en la secuencia dos se presenta que primero es colocada la pieza 1, luego la pieza 3 pero como no cabe en el espacio comprendidos entre la pieza uno y el límite extremos derecho, entonces es arrastrada hacia la izquierda, finalmente se introduce la pieza 2. Figura 31. Representación válida para dos individuos Fuente: Amarras de la Peña Jorge, Parra Truyol Antonio. El otro problema consiste en que hay soluciones que no se puede alcanzar con esta heurística, como ejemplo tenemos a la distribución mostrada en la Figura 32. Esto sucede porque la pieza 4 nunca alcanza la posición óptima, si miramos la secuencia de la heurística podemos ver que la primera en ser empacada es la pieza 1, seguida de la pieza 2, posteriormente la pieza 3 luego cuando la pieza 4 es dirigida hacia abajo por el lado derecho de la lámina, se encuentra que la pieza 3 está debajo de ella, razón por la cual la heurística hace que ésta sea dirigida hacia la izquierda y quede encima de la pieza 1, haciendo imposible alcanzar la distribución mostrada en laFigura 32. 88 Figura 32. Solución inalcanzable Fuente: Amarras de la peña Jorge, Parra Truyol Antonio. 4.1.3.1 Bottom left con caída libre La heurística en caída libre es una mejora al Bottom left expuesto con anterioridad, en esta, al igual que el bottom left, se busca ubicar lo más abajo y a la izquierda posible pero con la diferencia de que esta heurística no corre del todo la pieza a la izquierda, antes de esto verifica si hay espacio hacia abajo donde pueda caber la pieza sino sigue corriendo a la izquierda y explora nuevos espacios libres. 4.1.3.2 Bottom left con caída libre y con remplazo Es heurística realiza el mismo procedimiento como la que se hace en el algoritmo en caída libre, pero con la diferencia de que una vez puesta la pieza verifica si la pieza en espera para ser ubicada cabe en algún espacio libre entre las piezas puestas, de ser así procede a insertarla en ese lugar de lo contrario sigue los pasos expuesto en el algoritmo de caída libre. 4.1.3.3 Heurística para polígonos de ángulos rectos Se llama polígono de ángulo recto a la figura geométrica que cuenta con más de cuatro lados, y el ángulo entre lados consecutivos es de noventa grados. 89 Como en la caracterización de las piezas se encontró varias figuras que poseen la forma anteriormente descrita, es necesaria definir una heurística que permita la correcta distribución de las piezas en las láminas. La heurística de polígonos de ángulos rectos comienza recorriendo los límites horizontales, ubica la pieza en el extremo derecho del límite recorrido, luego busca las caras laterales izquierda de la pieza y traza líneas de cruce comprendida entre las caras laterales izquierda y los limites izquierdos encontrados, esto se hace con el fin de saber si existe huecos o espacios libres en los cuales encaje de forma exacta la pieza, seguido busca posicionar la cara de la pieza que se encuentra más a la derecha con el limite izquierdo que se encuentra más a la derecha, para esto se guía con la línea de cruce es más corta. 4.1.4 Calculo de la función fitness El objetivo fundamental de la investigación es la disminución de los desperdicios generados en el proceso de corte en la empresa FERROCARPINTERÍA FORMAR, por tal motivo la función fitness que evalúa la calidad de las soluciones tiene que estar asociada con dicho objetivo, tal como se muestra en la siguiente expresión. Ecuación 3. Función fitness ∑∑ En la ecuación 2, representa el área de la lámina , y representa el área de una pieza empacada en la lámina . En la expresión anteriormente mostrada, se busca determinar el área total no utilizada en la distribución de las piezas del producto, y con esto poder establecer el indicador promedio de desperdicio arrojado por la herramienta. 90 Hay que resaltar que para la última lámina utilizada en el proceso de distribución de las piezas, no se toma el área total, en lugar de esto se trabaja con el área determinada por la altura máxima, siendo la altura máxima aquella comprendida entre la base de la lámina y el borde de la pieza que sobresale entre todas las empacadas en la lámina, tal como se muestra en la siguiente figura. Figura 33. Altura máxima de lámina. Fuente: Elaboración propia. Este mecanismo de evaluación permite que no se generen soluciones con igual fitness, debido a que si no se tiene en cuenta la altura máxima, el algoritmo siempre calculará el área total de las láminas menos el área de las piezas empacadas, y como se sabe que la cantidad de láminas para diferentes distribuciones puede ser la misma y el número de piezas siempre es constante, tendremos como resultado una función fitness constante con diferentes distribuciones. Por el contrario si tenemos en cuenta la altura máxima, diferentes distribuciones generan deferentes alturas máxima por lo cual de esta forma si se puede determinar qué solución es mejor que otras. 4.1.5 Convenciones geométricas Para efectos de implementación los ejes coordenados se encuentran en una posición diferente a la convencional, donde el origen está ubicado en la esquina superior izquierda de la lámina, es así como los valores positivos del 91 eje X van de izquierda a derecha y del eje Y de arriba hacia abajo, tal como se indica en la Figura 34-a. El motivo por el cual se utiliza el sistema coordenado de la forma presentada, se fundamenta principalmente en que el lenguaje de programación en el que será implementada la herramienta (Java) lo presenta de dicha forma. Por lo cual se facilitarían la representación de las piezas y su representación grafica en la herramienta. Por otro lado, se defino un mecanismo para el recorrido de una pieza, este está dado en el sentido contrario a las manecillas del reloj y para el trazado de la pieza, el punto de partida es la esquina izquierda de la línea horizontal superior, tal como se muestra en la Figura 34-b. Figura 34. Ejes coordenados y recorrido de la pieza a) b) Fuente: Elaboración propia. 4.1.6 Calculo de área de piezas Para calcular el área de una pieza (zona de color amarilla), se procede a realizar la diferencia entre el área determinada por los bordes inferiores (líneas rojas) de la pieza menos el área determinada por los bordes superiores de la pieza (líneas azules), tal como se muestra en la Figura 35-a. 92 Figura 35. Calculo de área de las piezas a) b) c) Fuente: Elaboración propia. El primer paso como se menciono anteriormente para el cálculo del área de una pieza, es calcular el área comprendida entre los bordes inferiores de la pieza y la abscisa (eje x), es decir, el área representada por el color azul en la Figura 35-b, este cálculo se realiza mediante la sumatoria del área de los rectángulos formados por los bordes inferiores horizontales y el eje coordenado x. De manera similar se deberá calcular el área comprendida entre los bordes superiores y también el eje coordenado x (área de azul en la Figura 35-c). Finalmente se deberá realizar la resta entre las dos áreas, quedando como resultado de esta resta el área de la pieza. 93 4.2 CONSTRUCCIÓN DE LA HERRAMIENTA COMPUTACIONAL PROTOTIPO. La herramienta está fundamentada en el diseño asistido por computador (CAD), en el cual se le suministra información relacionada con el diseño de las piezas del producto, luego estas son procesadas por la herramienta y posteriormente genera como resultado la distribución de las piezas en los formatos de las láminas. El formato de entrada para las piezas es de tipo DXF, de igual forma se puede obtenerlas distribución si el usuario lo desea, ya que este tiene la opción de visualizarlo directamente desde la herramienta o exportarlo en formato DXF. En la siguiente imagen se muestra la secuencia del proceso de información para la herramienta computacional. Figura 36: Estructura de la herramienta computacional SALIDA Fuente: Elaboración propia. Como se puede observar la herramienta computacional, podría integrarse como una herramienta de manufactura asistida por computadora (CAM) en aquellos procesos en los cuales se requiera. 4.2.1 Requerimientos. La documentación de los requerimientos funcionales y no funcionales tuvo como fuente principal de información entrevistas verbales que se le practicaron al gerente general de la empresa FERROCARPINTERIA 94 FORMAR, el sr. Justo Padilla Barros, quien expresó las necesidades existentes en dicha organización con respecto al subproceso de planificación de corte de piezas en láminas. Estas necesidades fueron complementadas con información existente en la literatura para el bin packing problem, lo que finalmente tuvo como resultado los requerimientos funcionales y no funcionales de la herramienta. 4.2.1.1 Requerimientos Funcionales Los requerimientos funcionales son declaraciones de los servicios que debe proporcionar el sistema, de la manera en que éste debe reaccionar a entradas particulares y de cómo se debe comportar en situaciones particulares49. A continuación se listan los requerimientos funcionales de la herramienta propuesta:  R- 001. Importar piezas creadas en programas de diseño asistido por computadora.  R- 002. Diseñar pieza.  R- 003. Validar piezas.  R- 004. Visualizar galería de piezas.  R- 005. Visualizar características de una pieza.  R- 006. Seleccionar demanda de una pieza.  R- 007. Seleccionar dimensiones de la lámina.  R- 008. Seleccionar los operadores del Algoritmo Genético.  R- 009. Seleccionar los parámetros del Algoritmo Genético.  R- 010. Ejecutar Algoritmo Genético.  R- 011. Visualizar una distribución de piezas en láminas.  R- 012. Reacomodar distribución de forma manual.  R- 013. Exportar distribución encontrada por el Algoritmo genético. 49 SOMMERVILLE. Op. cit., p. 110. 95 4.2.1.2 Requerimientos no funcionales Los requerimientos no funcionales son restricciones de los servicios o funciones ofrecidas por el sistema. A continuación se listan los requerimientos no funcionales del software propuesto:  RN- 001. El sistema debe facilitar la interpretación por parte del usuario de las distribuciones obtenidas del algoritmo genético.  RN- 002. El sistema debe ser extensible, permitiendo la creación de nuevos operadores de selección, cruce y mutación.  RN- 003. Se debe brindar la flexibilidad de ejecutar el algoritmo genético con diferentes combinaciones de operadores y parámetros.  RN- 004. El sistema debe permitir la comunicación con sistemas de diseño asistido por computadoras mediante un formato estándar (Ej: formato DXF). 4.2.2 Arquitectura de software Teniendo como base los requerimientos funcionales, no funcionales y las características particulares de la herramienta que se desea implementar, se decidió utilizar una arquitectura por capas, este tipo de arquitectura organiza el sistema como su nombre lo indica en capas, cada una de las cuales proporciona un conjunto de servicios. El modelo por capas soporta el desarrollo incremental de los sistemas, permitiendo implementar primero las capas más prioritarias para el funcionamiento del sistema. Esta arquitectura también soporta bien los cambios y permite la portabilidad de dichas capas. En la medida en que la interfaces de una capa permanezca sin cambios, esta puede ser remplazada por otra equivalente50. Una de las arquitecturas por capas más utilizadas es la de 3 niveles, en donde la primera capa se refiere a la capa de presentación, la segunda al modelo de negocios y la última a la capa de datos. De forma similar para la 50 SOMMERVILLE. Op. cit., p. 227. 96 herramienta que se desea implementar, se utilizará una arquitectura de capas con tres niveles, sin embargo, la arquitectura del sistema tiene algunos cambios con respecto a usualmente utilizada. Figura 37. Arquitectura de software por capas. Presentación Procesamiento Comunicación Fuente: Elaboración propia. A continuación se describen los tres niveles que conforman la arquitectura del sistema (ver Figura 37):  Presentación: Esta capa es la encargada de toda la interacción con el usuario, permitiéndole a este poder configurar el Algoritmo Genético, visualizar las distribuciones, entre otras funcionalidades.  Procesamiento: Esta capa es la encargada de procesar la información ingresada por el usuario. Esta contiene el algoritmo genético el cual obtendrá las distribuciones de las piezas en las láminas.  Comunicación: Esta capa es la encargada de permitir la comunicación del sistema con programas de diseño asistido por computadora, mediante la lectura y escritura de archivos. 97 4.2.3 Casos de uso Los casos de uso capturan el comportamiento de un sistema, de un subsistema, o de una clase, tal como se muestran a un usuario exterior. Estos reparten la funcionalidad del sistema en transacciones significativas para los actores-usuarios ideales de un sistema51. Un caso de uso describe una interacción con los actores como secuencia de mensajes entre el sistema y uno o más actores. En la presente sección se presentarán los casos de uso para el software propuesto, y finalmente se realizara una descripción de estos. 4.2.3.1 Diagrama de casos de uso. Un diagrama de casos es una representación gráfica, que presenta con claridad las interacciones entre diferentes elementos, estos son los actores, el sistema, los casos de uso, y las relaciones. A continuación se presenta el diagrama de casos de uso del software propuesto: 4.2.4 Vistas estáticas La vista estática modela los conceptos del dominio de la aplicación, así como los conceptos internos inventados como parte de la implementación de la aplicación52. Esta clase de vistas son estáticas porque no describen el comportamiento del sistema dependiente del tiempo. Los componentes principales de este tipo de vistas son las clases, las relaciones y los paquetes. En la fase de diseño del software propuesta se realizaran dos vistas estáticas, el diagrama de clases y el diagrama de paquetes. 51 RUMBAUGH, James y JACOBSON, Ivar. El lenguaje unificado de modelado. Manual de referencia. Primera edición. Madrid: Addison Wesley, 2000. 552 páginas. ISBN 84-7829-037- 0. 52 Ibid., p. 22. 98 Figura 38. Diagrama de casos de uso uc Diagrama de casos de uso Sistema Seleccionar ubicacion «include» Importar Piezas «include» Leer archiv o Generación de piezas Diseñar Piezas Ver propiedades Pieza «extend» «extend» Seleccionar Ver Galeria de piezas Validar Piezas «extend» Operadores Operario «include» «extend» Configurar Algoritmo Genetico Seleccionar Parametros «include» «include» Distribuir piezas «include» Seleccionar «include» dimensiones de la Ejecutar Algoritmo lamina Genetico «include» Exportar Distribucion «extend» Visualizar Distribucion. «extend» Reacomodar Distribución Fuente: Elaboración propia. 4.2.4.1 Diagrama de clases El diagrama de clases es una representación gráfica que muestra la estructura de un sistema presentando claramente las clases y sus relaciones. En el Anexo 7 se presenta el diagrama de clases de la aplicación, este tiene como eje central la clase “Algoritmo Genético”, la cual contiene información 99 relacionada con los parámetros (Numero de generaciones, tamaño de población y el porcentaje de mutación), de igual manera ésta clase esta conformada por los operadores (Selección, Mutación y Cruce) y la heurística, con los cuales tiene una relación de composición. Por otro lado la clase Algoritmo Genético tiene una única operación, llamada ejecutar, que se encarga de realizar la búsqueda de la distribución de las piezas en las laminas. En la búsqueda de distribuciones el algoritmo genético representa una solución mediante un cromosoma (como se presento en la sección 4.1.1), por lo cual la clase Algoritmo Genético mantiene una relación de uno a muchos con la clase Cromosoma. Como se mostró en el capítulo de estructuración del algoritmo genético, existen múltiples posibilidades de implementación de cada tipo de operador, por ejemplo, el operador de cruce presenta las siguientes posibles implementaciones: por un punto, por dos puntos, PMX, OX, entre otros. Teniendo en cuenta este hecho, el diseño estructural del software debe permitir cambiar de una implementación a otra para un operador en particular sin generar mayores traumatismos en las demás clases. Al igual que se debe permitir agregar posteriormente nuevas implementaciones a las construidas inicialmente para los diferentes tipos de operadores en la herramienta. Con la finalidad de cumplir con las dos características mencionadas, se decidió utilizar el patrón de diseño Factory, el cual consiste en utilizar una clase constructora abstracta que tiene la posibilidad de tener algunos métodos definidos y otro abstracto, este último es el encargado de la construcción de objetos de un subtipo determinado. Este patrón consta de dos clases principales, la fábrica y el producto, en donde la fábrica necesita crear instancias de diferentes productos. Se utilizo el patrón Factory para el operador de selección, el operador de cruce, el operador de mutación y la heurística, esta al igual que los operadores puede ser implementada de diversas formas. 100 Por otro lado, el diagrama de clase muestra que las piezas son representadas por la clase Polígono, la cual contiene la información relacionada con forma de la pieza. Esta clase se encuentra relacionada con la clase Heurística, debido a que esta última es la encargada de la distribución de una solución en particular en las láminas. Finalmente Algoritmo Genetico mantiene una relación de dependencia con la clase Archivo, esta última es la encargada de permitir la comunicación con programas de diseño asistido por computadora, mediante la lectura y escritura de archivos. 4.2.4.2 Diagrama de paquetes El diagrama de paquetes muestra como un sistema esta subdivido en agrupaciones lógicas, mostrando las dependencias entre esas agrupaciones. En el Anexo 8 se presenta el diagrama de paquetes de la aplicación propuesta, este se fundamenta principalmente en la arquitectura del sistema, es decir, representa cada una de las capas señaladas en la arquitectura como un paquete, sin embargo, en el diagrama presentado se muestran dos paquetes (el de comunicación y el de procesamiento), debido a que el diseño de la herramienta no contempla el diseño de la interfaz grafica de usuario (GUI), gracias a que esta puede tener muchas variaciones. El paquete de comunicación solo está compuesto por una interfaz que expone los servicios de comunicación, y una o varios clases concretas que implementan estos servicios. De los dos paquetes presentados en el diagrama, se logra ver claramente que el más robusto es el de procesamiento, este se encuentra subdividido a su vez en tres diferentes paquetes: algoritmo, heurística y operadores. El paquete algoritmo agrupa a la clase Algoritmo Genético y a la clase Cromosoma. Por otro lado el paquete heurística está conformado por las clase abstracta Heurística y por su fabrica también abstracta, al igual que por 101 sus implementaciones concretas, adicionalmente también contiene las clase Polígono y Línea necesarias para realizar las distribuciones en las laminas. Finalmente el paquete operadores esta también subdivido a su vez por tres paquetes, para cada uno de los tipos de operadores (selección, cruce, mutación), y en cada uno de estos se encuentra operador abstracto, su fábrica y las clases concretas que las implementan. 4.2.5 Funcionalidades a implementar. En el secciones anteriores se presentaron la lista de requerimientos funcionales y no funcionales de la aplicación diseñada, de dichos requerimientos funcionales se deberán escoger los que serán implementados en el prototipo de la herramienta, teniendo como criterio de escogencia aquellos requerimientos que permitan ejecutar la instancia objeto de estudio, obtenido de esta manera la eficiencia de las soluciones, que finalmente permitan realizar un análisis comparativo con los niveles de desperdicio presentados en la organización en la actualidad. A continuación se listan los requerimientos que se consideran cumplen con el criterio de escogencia anterior, es decir, la lista de requerimientos que serán implementados en el prototipo de la herramienta:  R- 001. Importar piezas creadas en programas de diseño asistido por computadora.  R- 003. Validar piezas.  R- 004. Visualizar galería de piezas.  R- 005. Visualizar características de una pieza.  R- 006. Seleccionar demanda de una pieza.  R- 007. Seleccionar dimensiones de la lámina.  R- 008. Seleccionar los operadores del Algoritmo Genético.  R- 009. Seleccionar los parámetros del Algoritmo Genético.  R- 010. Ejecutar Algoritmo Genético.  R- 011. Visualizar una distribución de piezas en láminas.  R- 012. Reacomodar distribución de forma manual. 102  R- 013. Exportar distribución encontrada por el Algoritmo genético. En total serán implementados en el prototipo de la herramienta 12 de un total de 13 requerimientos funcionales, lo que corresponde a 92% de funcionalidades implementadas en la herramienta prototipo. 4.2.6 Lenguaje de programación. El lenguaje de programación con que será implementado el prototipo de la herramienta es Java, este es un lenguaje de programación orientado a objetos, desarrollado por Sun Microsystems a principios de los años 9053. Este lenguaje fue escogido para la implementación de la herramienta debido a los siguientes factores:  Orientación a Objetos: Esta es una de las principales características del lenguaje, la cual permite entre otras cosas la reutilización de código, al igual que la generación de diferentes niveles de abstracción (ver más información sobre programación orientada a objetos en la).  Independencia de la plataforma: La segunda característica, indica que programas escritos en el lenguaje Java pueden ejecutarse igualmente en cualquier tipo de hardware. Este es el significado de ser capaz de escribir un programa una vez y que pueda ejecutarse en cualquier dispositivo, tal como predica el axioma de Java, ‘’write once, run any where’’.  API grafica: Java posee una rica API grafica, lo cual facilita al momento de programar la creación de interfaces graficas de usuario (GUI), esenciales para la representación de las distribuciones encontradas por el Algoritmo Genético. 53 DEITEL. Op. cit., p. 9. 103  Amplia comunidad de desarrollo: Java a través de los años a ganado popularidad entre la comunidad de desarrolladores, lo cual genera la creación de muchas utilidades (API o librerías) de licencia publica, estas facilitarían la implementación de ciertas funcionalidades de la herramienta (como la comunicación con programas de diseño asistido por computadoras). 4.2.7 Comunicación con software de CAD. Con el fin de comunicarse con programas de diseño asistido por computadoras, se decidió, utilizar el formato DXF, este es un formato de archivo informático para dibujos de diseño asistido por computadora, creado fundamentalmente para posibilitar la interoperabilidad entre los archivos .DWG, usados por el programa AutoCAD, y el resto de programas del mercado. Este formato fue escogido debido a que es soportado por un gran número de programas de diseño asistido por computadores, incluyendo el más usado de este tipo de programas (AutoCAD). Una vez se decidió el tipo de formato que se desea utilizar para la comunicación, es necesario determinar el mecanismo de lectura y escritura de los archivos con el formato escogido. Una de las posibilidades es utilizar una API o librería que haya sido creada para tal fin, en el lenguaje de programación en el que será implementado el prototipo de la herramienta, es decir, en el lenguaje de programación Java. Se realizó una búsqueda de este tipo de librerías, y se encontraron las siguientes:  Kabeja.  YCAD  DXF Exporter.  Jdwglib. 104 De las cuales se decidió escoger la librería Kabeja, esta es una librería en Java, para el análisis, procesamiento y conversión de archivos en formato DXF. La cual se escogió gracias a que se puede utilizar desde la línea de comandos o embebido en una aplicación (directamente en la herramienta prototipo). Como resultado del análisis realizado al archivo en formato DXF, esta librería permite acceder a los datos mediante una estructura de árbol, lo que facilita el procesamiento de las entidades leídas del archivo, otra de las razones por las cuales fue escogida la librería. En contraste con las ventajas mencionadas, la librería escogida (Kabeja) presenta como desventaja que solo permite la lectura de archivos, es decir, no permite la escritura de archivos de este tipo, sin embargo, teniendo en cuenta que dentro de los requerimientos funcionales que se determino se van a implementar en el prototipo de la herramienta, no se encuentra el requerimiento relacionado con la escritura de archivos, se puede utilizar esta librería sin inconvenientes. 4.2.8 Validación herramienta prototipo. Finalizada la implementación de la herramienta prototipo es fundamental validarla, de tal forma que se pueda constatar que el producto construido satisface las necesidades del usuario, es este caso el gerente de la empresa FERROCARPINTERIA FORMA, el sr. Justo Padilla Barros. Con el fin de realizar dicha validación se construyó una encuesta (ver Anexos 9 y 10), que consta de tres secciones, información de la elaboración de la encuesta, los criterios de valoración, y una lista de las características de la herramienta. El listado de características que se encuentran en la encuesta se fundamenta en los requerimientos funcionales, los cuales a su vez se construyeron basados en la información suministrada por el gerente de la empresa FERROCARPINTERIA FORMAR, es decir, se permitirá que el usuario evalué la forma como se implementaron las características que este mismo propuso para la construcción de la herramienta. 105 La lista de características se evaluara de acuerdo en los siguientes criterios, los cuales se encuentran en el Anexo 9:  Supera las expectativas  Cumple las expectativas  Necesita mejorar  No cumple las expectativas  Sin implementar. De la encuesta realizada al gerente general de la empresa FERROCARPINTERIA FORMAR, se obtuvieron los siguientes resultados (ver evaluación completa en el Anexo 10):  6 de las 12 características (50%) superaron las expectativas del usuario, es decir, estas características tienen un mejor desempeño del que el usuario esperaba.  5 de las 12 características (42%) cumple con las expectativas del usuario, es decir, estas características realizan exactamente lo que el usuario esperaba.  8% de las características no se encontraban implementadas en la herramienta, es decir, 1 de las 12 características. Esta situación se debe a que esta funcionalidad según los criterios determinados en la sección anterior, no tenían la suficiente prioridad para ser incluidas dentro de la implementación de la herramienta prototipo. 106 5 APLICACIÓN DE LA HERRAMIENTA En la presente sección se ejecutará la herramienta, presentando las distribuciones encontradas por el Algoritmo Genético, con el fin de determinar el porcentaje promedio de desperdicio para dichas distribuciones, el cual será comparado posteriormente con el porcentaje promedio de desperdicio de las distribuciones realizadas de forma manual por parte de los trabajadores de la empresa FERROCARPINTERIA FORMAR. Finalmente se realizará un análisis de costo, tanto de las distribuciones encontradas por la herramienta como de las distribuciones realizadas de forma manual, determinando la diferencia entre estas dos distribuciones, en términos monetarios. Se debe tener en cuenta que los algoritmos genéticos realizan una serie de operaciones aleatorias que dan como resultado una solución que podría estar cercana al óptimo, esto depende en gran parte de la forma como se estructure el algoritmo, los operadores genéticos implementados y de los parámetros seleccionados. Debido a la importación en la escogencia de los parámetros, en la búsqueda de buenos resultados en el Algoritmo Genético, se deberá utilizar mecanismos que permitan la escogencia de estos, en la presente sección se mostrará el mecanismo utilizado para la escogencia de los parámetros. Una vez se hayan determinado los parámetros que se deberán utilizar durante la ejecución de la herramienta, se calcula el número de veces que se deberá ejecutar el Algoritmo Genético, para calcular el porcentaje de desperdicio promedio de las distribuciones. 107 5.1 PARÁMETROS DEL ALGORITMO GENÉTICO La selección de los parámetros tales como el porcentaje de mutación, número de generaciones y tamaño de población, son determinante a la hora de obtener buenos resultados en la ejecución del algoritmo genético, razón por la cual en la investigación se realiza un experimento en el cual se seleccionan unos parámetros determinados acorde con la literatura y los recursos computacionales disponibles. En el caso de la mutación, los porcentajes seleccionados son: 1%, 5% y 10%. En el número de generaciones se tiene: 100, 150, y 200, en la población inicial se experimentó con números de 20 hasta 50, con incrementos de 10 generaciones. En la Tabla 7se muestra los resultados obtenidos del experimento. Tabla 7. Resultado del experimento para la selección de los parámetros MUTACIÓN 1% 5% 10% NÚMERO DE 100 150 200 100 150 200 100 150 200 GENERACIONES 20 0,2476663 0,2955444 0,253333 0,2431681 0,2729517 0,19884150 0,2417517 0,2174335 0,2174335 30 0,1963166 0,2192436 0,2431681 0,2398804 0,2201455 0,22104535 0,2476663 0,2476663 0,2151894 40 0,2192436 0,1963166 0,2192436 0,2210453 0,2210453 0,22104535 0,2174335 0,2192436 0,2150069 50 0,2201455 0,1943985 0,1963166 0,2210453 0,2210453 0,18988716 0,1943985 0,2192436 0,2150069 Fuente: Elaboración propia. Cada valor de la casilla que se encuentra en el cuerpo de la tabla representa el promedio de haber ejecutado cinco veces la herramienta bajo las condiciones indicadas, por ejemplo, el valor que se encuentra en la primera casilla es el promedio de los resultados obtenidos por haber ejecutado la herramienta cinco veces y con porcentaje de mutación del 1%, tamaño de población de 10 y un número de generación de 100. 108 TAMAÑO DE POBLACIÓN Como se puede observa en laTabla 7, el menor porcentaje de desperdicio arrojado por la herramienta se obtuvo con una población inicial de 50, número de generación de 200 y un porcentaje de mutación del 5%. Por tal motivo para la solución del caso de estudio y los análisis de los resultados se trabaja con dichos parámetros. 5.2 CÁLCULO DEL TAMAÑO DE MUESTRA Como bien se sabe la naturaleza probabilística de los algoritmos genéticos hace que los resultados entre una ejecución y otra sean variables, esto causa que sea complicado realizar un análisis detallado de los desperdicios arrojados por la herramienta, por tal motivo es necesario tener un valor representativo con el cual poder comparar la calidad de las soluciones obtenidas por la herramienta con las obtenidas de forma manual. Este valor representativo es determinado mediante el promedio de los valores arrojados al ejecutarlo un número determinado de veces la herramienta. Ahora es de interés determinar el número adecuado de veces que se ejecuta la herramienta, para esto se recurre a la fórmula de tamaño óptimo de muestra, a continuación se muestran los pasos para determinar el número de ejecuciones adecuadas.  Unidad Poblacional: La unidad poblacional hace referencia a una solución particular o cromosoma obtenida al ejecutar la herramienta.  Tamaño de población: La población es el conjunto de soluciones factibles para el problema tratado, como el bin packing problem está dentro de la categoría de problemas NP-Hard, el espacio de soluciones es demasiado grande, razón por la cual el tamaño de la población se considera como infinita.  Calculo: Para el cálculo del tamaño óptimo de muestra se procede a tomar una muestra piloto, para esto se establece una muestra de tamaño 10, es decir, que este valor indica el número de veces que será ejecutada la herramienta en busca de distribuciones de piezas en los formatos; para cada una de estas distribuciones la herramienta calculará 109 un porcentaje de desperdicio, con el cual se determina la desviación estándar y así poder utilizar la fórmula de tamaño optimo de muestra, la cual se ilustra a continuación. Ecuación 4. Fórmula de tamaño optimo de muestra De la fórmula anterior hace referencia al error permitido, es la desviación estándar de los datos perteneciente a la muestra piloto. Alfa es el error muestral, el cual permitirá determinar el valor del estadístico Z que corresponde a la distribución normal estándar. Los resultados de la muestra piloto se muestran a continuación: Tabla 8. Datos de la muestra piloto Distribución 1 2 3 4 5 6 7 8 9 10 % de desperdicio 19,65% 20,21% 19,46% 15,64% 21,52% 21,52% 19,65% 21,77% 24,79% 21,52% Fuente: Elaboración propia. Para realizar los cálculos se escoge un alfa de 5%, error de 0,008 y con la ayuda de los datos de la Tabla 8 se determina la desviación de los datos, finalmente se remplazan estos valores en la Ecuación 4, dando como resultado para el tamaño óptimo de muestra un valor de 33 ejecuciones. 5.3 INDICADOR PROMEDIO DE DESPERDICIO ARROJADO POR LA HERRAMIENTA Una vez determinado el tamaño óptimo de ejecuciones, se procede a ejecutar el Algoritmo Genético tantas veces como lo indique dicho tamaño de muestra, con el fin de obtener una distribución representativa para el producto en cuestión, con la cual se pueda realizar un análisis comparativo 110 con respecto a las distribuciones realizadas de forma manual actualmente en la empresa FERROCARPINTERIA FORMAR. La herramienta fue ejecutada 33 veces con los operadores escogidos en la sección cuatro y los parámetros determinados anteriormente en esta misma sección. En el Anexo 3 se presentan los porcentajes de desperdicio para cada una de las 33 ejecuciones realizadas en la herramienta, cuyo promedio y desviación estándar son iguales a 21,25% y 1,53% respectivamente. En el Anexo 6 se encuentra una representación de las soluciones arrojadas por la herramienta. 5.4 ANÁLISIS DE COSTO PARA LA DISTRIBUCIÓN ARROJADA POR LA HERRAMIENTA Una vez determinado el indicador promedio de desperdicio, se procede a realizar el cálculo de los costos relacionados a dicho indicador. El procedimiento aplicado para hallar el desperdicio en términos monetario es el mismo que el utilizado en la distribución manual, pero con la diferencia que el porcentaje promedio de desperdicio utilizado es el arrojado por la herramienta al ser ejecutadas 33 veces, que es el tamaño óptimo de muestra, de igual forma sucede con el área promedio gastada en la distribución de las piezas, en este caso el área promedio es de 15,45 m2. En la Tabla 9 se muestra los cálculos pertinentes. 5.4.1 Análisis Comparativo Teniendo en cuenta los resultados del diagnóstico y los obtenidos con la herramienta computacional, se puede establecer un cuadro comparativo en el cual se muestran los resultados obtenidos por ambas formas de realizar la distribución, tal como se muestra a continuación: 111 Tabla 9. Análisis de costo para la herramienta computacional DESCRIPCIÓN FÓRMULA RESULTADO ( ) Área 3,28 m2 desperdiciada(m2) ( ) Costo desperdicio $ 75.314,84 por producto ( ) ( ) ( ) Costo desperdicio $ 376.574,19 mensual. ( Costo desperdicio ) $ 4.518.890,28 anual. Fuente: Elaboración propia. Tabla 10. Cuadro comparativo de resultados HERRAMIENTA DISTRIBUCION DESCRIPCIÓN AHORRO COMPUTACIONAL MANUAL Porcentaje de desperdicio 21,29% 31,84% 10,55% Área desperdiciada 3,286 5,88 2,594 Costo desperdicio por $ 75.314,84 $ 134.842,40 $ 59.527,56 producto Costo desperdicio mensual. $ 376.574,19 $ 674.212,00 $ 297.637,81 Costo desperdicio anual $ 4.518.890,28 $ 8.090.544,00 $ 3.571.653,72 Fuente: Elaboración propia. 112 Como se puede observar, con el uso de la herramienta en el proceso de la distribución de las piezas en láminas, la empresa se ahorra un 10,55% en el consumo de material triplex, lo cual se traduce en $ 297.637,81 mensual y si se lleva a anual tenemos que el ahorro es de $ 3.571.653,72. 5.5 TIEMPOS COMPUTACIONALES Se pudo determinar que los tiempos asociados con la distribución de piezas arrojado por la herramienta fueron muy bajos en comparación con los empleados en la distribución manual, como se puede observar en el Anexo 12, se muestra los tiempos computacionales en milisegundo para 33 distribuciones diferentes (las mismas distribuciones utilizadas para el cálculo promedio de desperdicio), la cual da un promedio de 8.8 minutos,al comparar este promedio, con el promedio obtenido de las distribuciones manuales (32,56 minutos) se evidencia una disminución sustancial de 23.67 minutos en promedio. Se debe tener en cuenta las características del equipo de cómputo en el que se ejecutó la herramienta computacional (ver Tabla 11. Características del pc.), dado que los tiempos obtenidos están muy relacionados con las capacidades del equipo de cómputo. Tabla 11. Características del pc. Característica Valor. Procesador AMD Turión 2.00GHz RAM 3 GB Disco duro. 500GB Sistema operativo. Windows 7 Profesional. Marca HP Modelo Pavilion dv600 Fuente: Elaboración propia. 113 6 CONCLUSIONES Con base en las experiencias obtenidas a lo largo de la presente investigación, se pudo establecer en la fase de diagnóstico el estado actual del proceso de corte de piezas en formatos en la empresa FERROCARPINTERIA FORMAR, determinando el nivel promedio de desperdicio, el cual fue de 31.84%, lo que refleja un alto porcentaje de ineficiencia del proceso, llevándolo a términos monetarios muestra un alto costo para la empresa ($ 134.842,00 por producto). Una vez terminada la fase de diagnóstico se procedió con el diseño del Algoritmo Genético, realizando una revisión del estado del arte de las estructura de codificación y operadores existentes para este problema, se seleccionó de acuerdo a las ventajas y desventajas el que mejor desempeño podría ofrecer. Para el problema tratado se escogió Object-based representation como estructura de codificación, mientras que los operadores de selección, cruce y mutación escogidos fueron Stochastic universal sampling (SUS), Order Crossover (OX) y Two-OPT respectivamente. A los cuales se les comprobó experimentalmente su eficiencia en comparación con los demás operadores implementados. De igual forma se realizó el diseño de una herramienta que permitirá distribuir las piezas de un producto en formatos de lámina. Éste realiza la distribución de las piezas características de los productos fabricados, en la empresa FERROCARPINTERIA FORMAR, es decir, polígonos con todos sus ángulos rectos, por lo cual se diseñó una heurística que permite distribuir este tipo de piezas. Basados en el diseño realizado de la herramienta se implementó un prototipo de la misma, permitiendo resolver la instancia objeto de estudio y realizar el análisis comparativo entre los resultados encontrados por la herramienta y las distribuciones manuales. 114 Se resolvió la instancia objeto de estudio utilizando la herramienta construida, obteniendo como resultado un promedio de desperdicio igual a 21.29%, significativamente menor al porcentaje promedio de desperdicio calculado para las distribuciones realizadas de forma manual (31.84%). El porcentaje de desperdicio hallado por la herramienta se traduce en términos monetarios en un costo de $75.314,84, lo cual significa un ahorro para la empresa de $59.527,56 por producto. Finalmente para la mismas ejecuciones de la instancia objeto de estudio se midió la duración en que la herramienta realiza las distribuciones de forma desatendida, esta duración toma el valor en promedio de 8,8 minutos, significativamente menor a la duración promedio en que él operario realiza la distribución de las piezas en las láminas de forma manual, es decir, la utilización de la herramienta le brindaría a la empresa dos grandes beneficios, el primero relacionado con la diminución en los porcentajes de desperdicio, y por ende con la disminución de los costos, y el segundo relacionado con la disminución en la duración de las distribuciones de las piezas, traducidos en mejoras en la productividad de la empresa. 115 BIBLIOGRAFÍA ALBANO, Antonio y SAPUPPO, Giuseppe. Optimal Allocation of Two Dimensional Irregular Shapes Using Heuristic Search Methods [Asignación óptima de piezas irregulares en dos dimensiones utilizando Heurísticas de búsquedas]. En: Systems, Man and Cybernetics, IEEE Transactions on. Mayo, 1980.Vol. 10, No. 5. p. 242-248. ÁLVAREZ, David. Solución del problema de empaquetamiento óptimo bidimensional en una sola placa, en placas y rollos infinitos con y sin rotación de piezas usando técnicas metaheurísticas de optimización. Trabajo de grado magíster en ingeniería eléctrica. Pereira: Universidad Tecnológica de Pereira. Facultad de Ingeniería, 2010. 77 P. ÁLVAREZ, David y TORO, Eliana. A hybrid algorithm for the two-dimensional strip packing problema [solución al problema de empaquetamiento óptimo bidimensional en rollos infinitos usando un algoritmo híbrido]. En: Scientiaet Technica. Junio, 2009.Vol. 15, No. 42. p. 205-210. Amarras de la peña Jorge, Parra Truyol Antonio, resolución del problema deStrip-packingmediantelaMetaheurísticaalgoritmosgenéticos.Universidad Carlos III, página 2. BINKLEY, Kevin y HAGIWARA, Masafumi. Applying self-adaptive evolutionary algorithms to two-dimensional packing problema asusing a fourcorners [Aplicación de algoritmos evolutivos auto-adaptativos en problemas de empaquetamiento en placas usando las 4 esquinas]. En: European Journal of Operational Research. Diciembre, 2006.Vol. 183. p. 1230-1248. BLUM, Christian y ROLI, Andrea. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison [Metaheurísticas en Optimización Combinatoria: Presentación y comparación conceptual]. En: ACM Computing Surveys. Septiembre, 2003.Vol. 35, No. 3. p. 268-308. CHRISTOFIDES, N. y WHITLOCK, A. An algorithm for two dimensional cutting problems [Un algoritmo para problemas de corte de 2 dimensiones]. En: Operational Research. Enero, 1977. Vol. 25, No. 3. p. 30-44. 116 DEITEL, Harvey y DEITEL, Paul. Como Programar en C/C++ y Java. Cuarta edición. México: Person Educacion, 2004. 1152 páginas. ISBN 970-26-0531- 8. DOWSLAND, Kathryn. Some experiments with simulated annealing techniques for packing problems [Algunas experiencias con tecnicas de Recocido Simulado para problemas de empaquetamiento]. En: European Journal of Operational Research. Junio, 1993.Vol. 68, No. 3. p. 389-399. DYCKHOFF H. A typology of cutting and packing problems[Una tipología de los problemas de corte y empaquetamiento]. En: European Journal of Operational Research. 1990. Vol. 44. p. 145-160. GAREY, M. y JOHNSON, D. Computers and Intractability: A Guide to the Theory of NP-Completeness. Primera Edición. San francisco: W. H. Freeman, 1979. 340 p. ISBN 978-0716710455. GESTAL POSE, Marcos. Introducción a los algoritmos genéticos. España: Universidad de la Coruña. Dpto. tecnologías de la información y comunicación. 16 p. GESTAS MARCOS, Introducción a los Algoritmos Genéticos; Departamento de la Información y las Comunicaciones, universidad de Curuña. Página 10. GILMORE, P. y GOMORY, R. The theory and computation of knapsack functions [La teoría y el calculo de las funciones del problema de la mochila]. En: Operations Research. Marzo, 1966. Vol. 17. p. 1045-1074. GLOVER, F. Future paths for integer programming and links to artificial intelligence. En: Computers and Operations Research. 1986. Vol. 13, No. 5. p. 533-549. GOLDBERG, D. Genetic Algorithms in Search, Optimization and Machine Learning [Algoritmos Genéticos en la búsqueda, Optimización y Aprendizaje Automático].Addison-Wesley. 1989. HERNANDEZ, Sampier y FERNANDEZ, Carlos. Metodología de la investigación. Cuarta Edición. Mexico D.F.: McGraw Hill, 2006.p 103. ISBN 978-970-10-5753-7. HEVNER Alan, MARCH Salvatore, PARK Jinsoo Y RAM Sudha. Design Science InInformation Systems Research. En: MIS Quarterly. Marzo, 2004. Vol. 28. No.1 p. 75 - 105. 117 HOLLAND, J. Adaptation in Natural and Artificial Systems[Adaptación en sistemas naturales y artificiales]. Michigan: Universidad de Michigan. 1992. J. Dreo A. Petrowski, Metaheuristics for hard optimization, Springer-Verlag Berlin Heidelberg 2006; Página 83 LAI, K y CHAN, J. A evolutionary algorithm for the rectangular cutting stock problem [Un algoritmo evolutivo para el problema de empaquetamiento optimo de rectángulos en una placa]. En: International Journal of Industrial Engineering. Julio, 1997.Vol. 4. p. 130-139. LAI, Lee. A Genetic Algorithm for Two-Dimensional Bin Packing Problem[Un Algoritmo Genético para el problema de empaquetamiento en placas]. En: Research Bulletin of Institute for Mathematical Research. p.34 -39. LEUNG T. Y YUNG C. Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem [Aplicaciones de Algoritmo Geneticos y Recocido Simulado para el problema de empaquetamiento optimo en una placa en dos dimensiones]. En: Computers and Industrial Engineering. Julio, 2001. Vol. 40. p. 201-214. LODI A, MARTELLO S, y VIGO D. Heuristic and metaheurística approaches for a class of two-dimensional bin packing problems [Heurísticas y metaheurísticas enfoques para una clase de problema de empaquetamiento optimo en placas en dos dimensiones]. En: INFORMS J. Computing. 1999. Vol. 11. p. 345-357. MARTELLO, Silvano y VIGO, Daniele. Exact Solution of the Two- Dimensional Finite Bin Packing Problem [Solución exacto del problema de empaquetamiento optimo en placas en dos dimensiones]. En: Management Science. Marzo, 1998. Vol. 44, No. 3. p. 388-399. MARTELLO, Silvano y VIGO, Daniele. The Three Dimensional Bin Packing Problem [El problema de empaquetamiento en contenedores]. En: Operations Research. Marzo, 2000. Vol. 48, No. 2. p. 256-267. MARTELLO, Silvano. y VIGO, Daniele. An exact approach to the strip- packing problem [Una aproximación exacta del problema de empaquetamiento en rollos]. En: INFORMS Journalon Computing. Septiembre, 2003. Vol. 15, No. 3. p. 310-319. MITSUO Gen, Runweicheng, Genetic Algorithms and Engineering optimization. John Wiley & Sons, Inc.new York 2000. Página 65 118 OLIVEIRA, Jose y FERREIRA, Jose. An improved version of Wang's algorithm for two - dimensional Cutting Problems [Una versión mejorada del algoritmo de Wang´s para problemas de corte en dos dimensiones]. En: European Journal Operations Research. Febrero, 1990. Vol. 44, p. 256-266. OSMAN, I.H. y LAPORTE, G. Metaheuristics: A bibliography [Metaheuristica: una bibliografía]. En: 1996. No. 63. p. 513-623. PASHA, Arfath. Geometric bin packing algorithm for arbitrary shapes [Problemas de empaquetamiento optimo en placas para formas irregulares]. Trabajo de grado magíster en ciencias. Gainesville: Universidad Florida. 2003. 99 P. PARADA, Victor. Solution for the Constrained Guillotine Cutting Problem by Simulated Annealing [Solución del problema de corte con la restricción de guillotina mediante Recocido Simulado]. En: Journal on Computers and Operations Research. Enero, 1998.Vol. 25, No. 1. p. 37-47. PEFFERS, ken y TUUNANEN, tuure. A Design Science Research Methodology for Information Systems Research. En: Journal of Management Information Systems. Diciembre, 2006.Vol. 24.No.3 p. 45 - 77. RUMBAUGH, James y JACOBSON, Ivar. El lenguaje unificado de modelado. Manual de referencia. Primera edición. Madrid: Addison Wesley, 2000. 552 páginas. ISBN 84-7829-037-0. SOMMERVILLE, Ian. Ingeniería del software. Séptima Edición. México D.F.: Pearson Addisen Wesley, 2006. p 691. ISBN 84-7829-074-5. VASKO, F. Computational improvement to Wang's two-dimensional cutting stock algorithm [Mejoras computacionales al algoritmo de corte en dos dimensiones de Wang´s]. En: Computers and Industrial Engineering. Enero, 1989. Vol. 16, p. 109-115. VELEZ, Mario y MONTOYA, JOSÉ. Metaheurísticos: una alternativa para la solución de problemas combinatorios en administración de operaciones. En: EIA. Diciembre, 2007.No. 8. p. 99-115. ISSN 1794-1237. WANG, P. Two algorithms for constrained two dimensional cutting stock problems [Dos algoritmo para limitados problemas de corte en dos dimensiones]. En: Operational Research. Enero, 1983. Vol. 31, p. 573-586. 119 ANEXOS Anexo 1. Maquinaria industrial. Canteadora Sierra circular (Escolilladora) Cepillo Sierra sin fin Sierra Circular Trompo Fuente: Elaboración propia. 120 Anexo 2. Herramientas manuales. Lijadora Engrapadora Sierra circular manual Ruteadora pequeña Sierra caladora Taladro Ruteadora industrial Martillo Fuente: Elaboración propia. 121 Anexo 3. Resultado de la ejecución de la herramienta. PORCENTAJE DE DESPERDICIO (EJECUCIONES EN AG) Porcentaje No. Porcentaje No. Porcentaje No. de Ejecución de Ejecución de Ejecución desperdicio. desperdicio desperdicio. 1 22,31% 12 18,75% 23 22,13% 2 21,77% 13 24,79% 24 21,77% 3 21,77% 14 19,65% 25 22,13% 4 19,01% 15 19,65% 26 21,77% 5 19,65% 16 21,77% 27 24,79% 6 21,52% 17 21,52% 28 21,52% 7 22,13% 18 19,65% 29 22,13% 8 22,13% 19 18,26% 30 21,77% 9 19,65% 20 21,95% 31 21,95% 10 21,95% 21 21,77% 32 21,52% 11 19,65% 22 22,13% 33 19,46% Promedio 21,25% Desviación estándar 1,53% Fuente: Elaboración propia. Anexo 4. Área utilizada distribuciones obtenidas con la herramienta. ÁREA UTILIZADA EN LAS DISTRIBUCIONES (EJECUCIONES EN AG) No. Porcentaje Área Porcentaje No. Área 2 Ejecución de utilizada de Ejecución Utilizada (m ) 2 desperdicio (m ) desperdicio. 1 15,6360 12 14,9520 23 15,6000 2 15,5280 13 16,1520 24 15,5280 3 15,5280 14 15,1200 25 15,6000 4 15,0000 15 15,1200 26 15,5280 5 15,1200 16 15,5280 27 16,1520 6 15,4800 17 15,4800 28 15,4800 7 15,6000 18 15,1200 29 15,6000 8 15,6000 19 14,8620 30 15,5280 9 15,1200 20 15,5640 31 15,5640 10 15,5640 21 15,5280 32 15,4800 11 15,1200 22 15,6000 33 15,0840 Promedio 15,4383 Desviación estándar 0,2968 Fuente: Elaboración propia. 122 Anexo 5. Distribución manual de las piezas. Lamina 1 Lamina 2 Lamina 3 Lamina 4 123 Lamina 5 Lamina 6 Lamina 7 Fuente: Elaboracion propia. 124 Anexo 6. Distribución promedio en la herramienta. Lamina 1 Lamina 2 Lamina 3 Lamina 4 125 Lamina 5 Fuente: Elaboracion propia. 126 Anexo 7.Diagrama de clases p kg Diagrama de clases El Algoritmo Genetico diseñado esta constituido fundamentalmente por parametros, operadores y una poblacion. Los parametros util izadados se encuentran como atributos de la clase AlgoritmoGenetico. SUSOperador «interface» Los operadores al igual que la heuristica tienen una relacion de OperadorSeleccion Archiv oDXF + calcularProbabilidades(ArrayList) : void Archiv o composicion con el algoritmo. + seleccionar(ArrayList) : Cromosoma - probabilidades: double[] + exportarArchivo(String) : void + exportarArchivo(String) : void - random: Random + importarArchivo(String) : List Finalmente la poblacion esta compuesta por una lista de + importarArchivo(String) : List Cromosomas, estos representan la secuencia u orden en que la RuedaDeRuletaOperador heuristica ubica las piezas en la lamina.+ calcularProbabilidades(ArrayList) : void + seleccionar(ArrayList) : Cromosoma + calcularProbabilidades(ArrayList) : void + seleccionar(ArrayList) : Cromosoma 1 AlgoritmoGenetico RuedaDeRuletaFabrica 1 TwoOptFabrica - numeroGeneraciones: int OperadorMutacionFabrica + crearOperador(Random) : OperadorSeleccion OperadorSeleccionFabrica - porcentajeMutacion: double + crearOperador(Random) : OperadorMutacion - tamannoPoblacion: int + crearOperador(Random) : OperadorMutacion + crearOperador(Random) : OperadorSeleccion 1 + ejecutar() : void 1 SUSFabrica 1 p1oblacion + crearOperador(Random) : OperadorSeleccion 0..* OperadorMutacion TwoOptOperador 1 - random: Random Cromosoma + mutar(Cromosoma) : Cromosoma - aptitup: double + mutar(Cromosoma) : Cromosoma - genes: ArrayList Poligono - cantidad: int - descripcion: String Linea - id: int - validez: boolean + buscarLineaContigua(Point2D, LinkedList) : Linea 1 + isHorizontal() : boolean + addPoint(double, double) : void + isVertical() : boolean OperadorCruce OperadorCruceFabrica + calcularAltura() : double + recortar(Linea) : Linea + calcularAnchura() : double - random: Random + interseccion(ArrayList) : boolean + crearOperador(Random) : OperadorCruce + translate(double, double) : void + cruce(Cromosoma, Cromosoma) : Cromosoma[] 0..* Piezas 1 1 UnPuntoOperador UnPuntoFabrica Heuristica + cruce(Cromosoma, Cromosoma) : Cromosoma[] + crearOperador(Random) : OperadorCruce - areaTotal: double HeuristicaFabrica - demandas: ArrayList - lamina: Rectangle2D + crearHeuristica() : Heuristica + calcularAreaTotal() : void + colocarPieza(ArrayList, Linea, ArrayList, Poligono) : void OXOperador OXFabrica + heuristica(Cromosoma) + reconstruirLimites(Poligono, ArrayList) : ArrayList + cruce(Cromosoma, Cromosoma) : Cromosoma[] + crearOperador(Random) : OperadorCruce BottomLeftPoligonoHeuristica BottomLeftPoligonoFabrica + calcularAreaTotal() : void + crearHeuristica() : Heuristica + colocarPieza(ArrayList, Linea, ArrayList, Poligono) : void + heuristica(Cromosoma) + reconstruirLimites(Poligono, ArrayList) : ArrayList Fuente: Elaboración propia. 127 Anexo 8.Diagrama de paquetes pkg Diagrama de paquetes comunicacion Archiv o + escribirArchivo(String) : void Archiv oDXF + leerArchivo(String) : List + escribirArchivo(String) : void + leerArchivo(String) : List procesamiento operadores seleccion SUSOperador OperadorSeleccion + calcularProbabilidades(ArrayList) : void + seleccionar(ArrayList) : Cromosoma - probabilidades: double[] - random: Random RuedaDeRuletaOperador + calcularProbabilidades(ArrayList) : void + seleccionar(ArrayList) : Cromosoma + calcularProbabilidades(ArrayList) : void algoritmo 1 + seleccionar(ArrayList) : Cromosoma RuedaDeRuletaFabrica AlgoritmoGenetico Cromosoma + crearOperador(Random) : OperadorSeleccion OperadorSeleccionFabrica 1 - numeroGeneraciones: int poblacion - porcentajeMutacion: double - aptitup: double 0..* + crearOperador(Random) : OperadorSeleccion 1- tamannoPoblacion: int - genes: ArrayList 1 SUSFabrica + ejecutar() : void + crearOperador(Random) : OperadorSeleccion 1 1 cruce OperadorCruce 1 OperadorCruceFabrica heuristica - random: Random + crearOperador(Random) : OperadorCruce + cruce(Cromosoma, Cromosoma) : Cromosoma[] Poligono HeuristicaFabrica - cantidad: int - descripcion: String UnPuntoOperador + crearHeuristica() : Heuristica - id: intUnPuntoFabrica - validez: boolean + cruce(Cromosoma, Cromosoma) : Cromosoma[] + crearOperador(Random) : OperadorCruce + addPoint(double, double) : void + calcularAltura() : double 1 Piezas 0..* + calcularAnchura() : double + interseccion(ArrayList) : boolean Heuristica 1 + translate(double, double) : void - areaTotal: double OXOperador OXFabrica - demandas: ArrayList - lamina: Rectangle2D + cruce(Cromosoma, Cromosoma) : Cromosoma[] + crearOperador(Random) : OperadorCruce + calcularAreaTotal() : void + colocarPieza(ArrayList, Linea, ArrayList, Poligono) : void + heuristica(Cromosoma) + reconstruirLimites(Poligono, ArrayList) : ArrayList mutacion 1 Linea OperadorMutacion OperadorMutacionFabrica + buscarLineaContigua(Point2D, LinkedList) : Linea + isHorizontal() : boolean - random: Random + isVertical() : boolean + crearOperador(Random) : OperadorMutacion + recortar(Linea) : Linea + mutar(Cromosoma) : Cromosoma BottomLeftPoligonoHeuristica BottomLeftPoligonoFabrica TwoOptOperador TwoOptFabrica + calcularAreaTotal() : void+ crearHeuristica() : Heuristica + colocarPieza(ArrayList, Linea, ArrayList, Poligono) : void + mutar(Cromosoma) : Cromosoma + crearOperador(Random) : OperadorMutacion + heuristica(Cromosoma) + reconstruirLimites(Poligono, ArrayList) : ArrayList Fuente: Elaboración propia. 128 Anexo 9. Formato validación de la herramienta prototipo. VALIDACIÓN DE LAS FUNCIONALIDADES DE LA HERRAMIENTA COMPUTACIONAL. 1. ELABORACIÓN. Nombre trabajador: Cargo: 2. CRITERIOS DE EVALUACIÓN. a) Supera las expectativas b) Cumple las expectativas c) Necesita mejorar d) No cumple las expectativas e) Sin implementar. 3. EVALUACIÓN. No. Características Evaluación. Importar piezas creadas en programas de 1 diseño asistido por computadora. 2 Diseñar pieza en la herramienta. 3 Validación piezas creadas o importadas. 4 Visualizar galería de piezas 5 Visualizar características de una pieza. 6 Seleccionar demanda de una pieza. 7 Seleccionar dimensiones de la lámina. Búsqueda de distribución de un conjunto 8 de piezas. Calidad de las distribuciones, en cuanto 9 al porcentaje de desperdicio. Visualizar la distribución encontrada por 10 la herramienta. 11 Exportar distribución encontrada. Reacomodar distribución de forma 12 manual. Anexo 10.Resultados de la encuesta de validación VALIDACIÓN DE LAS FUNCIONALIDADES DE LA HERRAMIENTA COMPUTACIONAL. 4. ELABORACIÓN. Nombre trabajador: Justo Padilla Barros. Cargo: Gerente. 5. CRITERIOS DE EVALUACIÓN. a) Supera las expectativas b) Cumple las expectativas c) Necesita mejorar d) No cumple las expectativas e) Sin implementar. 6. EVALUACIÓN. No. Características Evaluación. Importar piezas creadas en programas de 1 b. diseño asistido por computadora. 2 Diseñar pieza en la herramienta. e. 3 Validación piezas creadas o importadas. a. 4 Visualizar galería de piezas a. 5 Visualizar características de una pieza. a. 6 Seleccionar demanda de una pieza. b. 7 Seleccionar dimensiones de la lámina. b. Búsqueda de distribución de un conjunto 8 b. de piezas. Calidad de las distribuciones, en cuanto 9 a. al porcentaje de desperdicio. Visualizar la distribución encontrada por 10 a. la herramienta. 11 Exportar distribución encontrada. b. Reacomodar distribución de forma 12 a. manual. 130 Anexo 11 Tiempos empleados en la distribución manual. Muestras LAMINA 1 2 3 4 5 6 7 8 9 10 1 5,2 4,99 5,11 5,33 5,32 5,6 5,2 5,47 5,32 5,46 2 4,69 5,23 5,19 5,23 5,31 5,2 5,32 5,32 5,43 5,39 3 5,13 5,21 5,34 5,21 5,01 5,3 5,43 5,11 5,21 5,14 4 4,5 5,32 5,49 4,98 5,43 4,6 5,18 5,12 5,18 5,17 5 5,43 5,46 5,3 5,3 5,6 5,5 5,01 4,23 5,31 5,34 6 5,32 5,7 5,51 5,4 4,6 5,3 4,4 5,23 5,49 5,42 7 1 1,2 1,1 1,23 1 1,2 1,6 1,5 1,3 1,3 TOTAL 31,27 33,11 33,04 32,68 32,27 32,7 32,14 31,98 33,24 33,22 PROMEDIO 32,565 Fuente: Elaboración propia. Anexo 12. Tiempos empleados en la distribución por la herramienta computacional Tiempos empleados en la búsqueda de distribuciones. Tiempo Tiempo No. No. Área Utilizada Tiempo empleado empleado (mili empleado (mili 2 Ejecución Ejecución (m ) (mili segundos) segundos) segundos) 1 12 23 473,598 744,36 451,799 2 13 24 405,471 815,124 448,776 3 14 25 466,136 807,329 403,294 4 15 26 424,751 603,259 392,63 5 16 27 481,642 577,807 453,138 6 17 28 470,745 871,499 445,262 7 18 29 465,379 578,545 428,085 8 19 30 531,938 895,797 388,262 9 20 31 431,449 661,071 404,758 10 21 32 489,422 455,954 414,788 11 22 33 861,27 430,11 435,179 Promedio (min) 8,893 Desviación estándar (min) 2,620257871 Fuente: Elaboración propia. 131 Anexo 13 Utilidades anuales por productos. PRODUCTO UTILIDAD Porcentaje Porcentaje acumulado (Anual) utilidad por producto Cocina $ 13.198.949,00 43% 43% Closet $ 4.689.564,00 15% 58% Mesas $ 4.300.000,00 14% 72% Escaparates $ 4.000.200,00 13% 85% Tocador y $ 2.013.349,00 7% 91% multimuebles Sillas $ 1.200.000,00 4% 95% Ventana $ 1.000.000,00 3% 99% Puerta $ 427.971,76 1% 100% TOTAL $ 30.830.033,76 100% Fuente: Elaboración propia. 132 Anexo 14: Manual de usuario Distribución de piezas en laminas Sergio Leottau Sanmiguel – Juan Carlos Rodríguez Jairo Rafael Coronado 1. Ventana Principal Figura. 1 Ventana principal Abri Exportar Galería Distribución Ejecutar Configurar Fuente: Elaboración propia La ventana principal esta compuesta por seis iconos que realizan las siguientes funciones:  Abrir: Permite seleccionar el archivo en el cual se encuentran las piezas que se van a distribuir en la lamina.  Exportar: Esta opción, guarda en un archivo con formato DXF la ultima distribución encontrada por el Algoritmo Genético.  Galería: Se pueden observar las piezas del producto que se desea distribuir.  Distribución: Al seleccionar el icono se muestran la última distribución de las piezas en láminas encontrada.  Ejecutar: Este botón permite al usuario ejecutar el Algoritmo Genético, y de esta manera encontrar una distribución para las 134 piezas importadas (Previamente se deben haber importado las piezas y realizado la configuración).  Configurar: Permite ingresar la información relacionada con la configuración de los parámetros y operadores del algoritmo genético al igual que la información relacionada con las dimensiones de la lamina y el tamaño del lote. Nota: Los botones 2, 3, 4 y 5 aparecen en primera instancia deshabilitados debido a que no se ha seleccionado el archivo que contiene las piezas que se van a distribuir. Importar archivo. Para realizar la importación del archivo que contiene las piezas diseñadas previamente en un programa de diseño asistido por computadora, se selecciona el primer icono ( ) de la ventana principal. Inmediatamente este permitirá seleccionar el archivo que debe estar en formato DXF, debido a que es uno de los formatos de Auto CAD. Como se observa en la imagen. Figura. 2 Importación de archivos Fuente: Elaboración propia 135 2. Galería de piezas. Una vez se ha abierto el archivo seleccionado en el paso anterior se visualizan las piezas del producto que se van a distribuir posteriormente. Como se observa en la siguiente figura. Figura. 3 Galería de piezas Fuente: Elaboración propia Puede seleccionar las piezas para observar las propiedades y las cotas, como se aprecia en el siguiente ejemplo, en el cual se selecciona la figura numero 1. 136 Figura. 4Detalle de la pieza numero 1 Fuente: Elaboración propia Para regresar a la galería de todas las figuras se selecciona el botón de galería. Figura. 5 Galería de figuras 137 Fuente: Elaboración propia 3. Configurar. Permite ingresar la información relacionada con la configuración de los parámetros y operadores del algoritmo genético, al igual que la información relacionada con las dimensiones de la lámina y el tamaño del lote. En la figura que se observa a continuación es la que aparecerá en el software cuando se requiera ingresar la configuración. Figura. 6 Configuración Estos tres datos son los parámetros del algoritmo genético. Estos datos son los operadores del algoritmo genético. Se ingresan las dimensiones de la lámina de Triplex que se va a utilizar Fuente: Elaboración propia 138 4. Ejecutar. El icono de ejecutar tiene como funcionalidad realizar la distribución requerida. Una ves se termina de ejecutar se podrá apreciar la distribución y la información relacionada. Figura. 7Distribución encontrada por la herramienta. Fuente: Elaboración propia En la siguiente figura se podrá apreciar de manera más detallada la información que acompaña la distribución de las piezas en la lámina de Triplex. 5. Ver distribución. Si el usuario se encuentra en otra ventana que no sea en la de distribución como por ejemplo en galería, y quiere observar la última distribución realizada se da clic en el icono de distribución. Como se presenta en los siguientes pasos: 139 Figura. 8 Información detallada de la pieza Fuente: Elaboración propia La herramienta también permite que el usuario pueda reacomodar las piezas una vez finaliza la búsqueda de una distribución por parte del Algoritmo Genético. Para reacomodar una pieza el usuario debe seleccionarla, y esta se trasladara de acuerdo a los movimientos del mouse, finalmente el usuario deberá hacer clic donde desea ubicar a la pieza, teniendo en cuenta que debe ser dentro de los limites de la lamina, y sin sobreponer otra pieza. 140 Figura. 9 Galería de las piezas Fuente: Elaboración propia Figura. 10 Distribución de las piezas Fuente: Elaboración propia 141 6. Exportar distribución. Una vez se ha ejecutado el Algoritmo Genético, y este ha encontrado una distribución la opción de Exportar es habilita, permitiendo al usuario almacenar la distribución en un archivo DXF. El usuario deberá escoger el lugar donde desea almacenar el archivo, tal como se muestra en la siguiente figura. Figura 11. Exportar distribución. Fuente: Elaboración propia 142