distribuciÓn de planta para una oficina bancaria …
TRANSCRIPT
DISTRIBUCIÓN DE PLANTA PARA UNA OFICINA BANCARIA POR MEDIO DE ALGORITMOS GENÉTICOS
GINA SIRLENY ROJAS BERNAL
UNIVERSIDAD DE LOS ANDES FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA INDUSTRIAL SANTAFÉ DE BOGOTÁ, D.C.
2005
2
DISTRIBUCIÓN DE PLANTA PARA UNA OFICINA BANCARIA POR MEDIO DE ALGORITMOS GENÉTICOS
GINA SIRLENY ROJAS BERNAL
Proyecto de Grado para optar por el título de Ingeniera Industrial
ASESOR JOSÉ FIDEL TORRES, Ph.D.
Profesor Asociado Departamento de Ingeniería Industrial
Universidad de los Andes
UNIVERSIDAD DE LOS ANDES FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA INDUSTRIAL SANTAFÉ DE BOGOTÁ, D.C.
2005
3
A mis padres, por enseñarme a vivir.
A Dios, por permitirnos alcanzar nuestros sueños.
Y a Javier, por ser la vela que me dio la marea.
4
AGRADECIMIENTOS
El autor expresa sus agradecimientos a:
Mi asesor de tesis y maestro, José Fidel Torres, Ph. D., quien me guió y
motivó a lo largo de este proyecto.
El profesor Eliécer Gutiérrez, por su dirección y el tiempo que cedió a la
lectura y evaluación de este documento.
Ing. Camilo Sánchez, por los valiosos aportes que recibí de su parte.
Mis amigos Gina Angueyra y Enrique Kook, de quienes nunca me ha faltado
su apoyo.
Todos aquellos que participaron activamente en el desarrollo de este trabajo.
5
TABLA DE CONTENIDO
1. INTRODUCCIÓN.......................................................................................................... 12
1.1 ANTEDECEDENTES............................................................................................. 13 1.2 DESCRIPCION DEL PROBLEMA....................................................................... 14 1.3 CONSIDERACIONES SOBRE LA OFICINA BANCARIA................................ 14 1.5 OBJETIVOS ............................................................................................................ 16
1.5.1 Objetivo General ............................................................................................. 16 1.5.2 Objetivos específicos...................................................................................... 17
2. MARCO TEÓRICO ....................................................................................................... 19
2.1 PROBLEMA DE CONFIGURACIÓN DE PLANTA ........................................... 19 2.1.1 OBJETIVOS DE UNA BUENA CONFIGURACIÓN DE PLANTA ........... 20 2.1.2 PRINCIPIOS BÁSICOS DE LA DISTRIBUCIÓN DE PLANTA................ 21
2.1.2.1 Principio de la integración de conjunto................................................ 21 2.1.2.2 Principio de la mínima distancia recorrida........................................... 21 2.1.2.3 Principios de la circulación o flujo de materiales................................ 21 2.1.2.4 Principio del espacio cúbico................................................................... 22 2.1.2.5 Principio de la satisfacción y de la seguridad..................................... 22 2.1.2.6 Principio de la flexibilidad....................................................................... 22
2.1.3 TIPOS DE DISTRIBUCIÓN DE PLANTA.................................................... 22 2.1.3.1 Distribución por posición fija .................................................................. 23 2.1.3.2 Distribución por proceso......................................................................... 24 2.1.3.3 Distribución por producto........................................................................ 24 2.1.3.4 Distribución celular.................................................................................. 25 2.1.3.5 Ventajas y limitaciones de los tipos básicos de distribución............ 26
2.1.4 MÉTODOS PARA EL DISEÑO DE DISTRIBUCIONES EN PLANTA.... 27 2.1.4.1 Procedimiento de Distribución de planta de Apple............................ 28 2.1.4.3 Procedimiento de Distribución de planta de Reed............................. 29 2.1.4.4 Procedimiento Sistemático de Distribución de planta (SLP) de Muther..................................................................................................................... 30
2.1.4.4.1 Análisis del Flujo de materiales.......................................................32 2.1.4.4.2 Relaciones entre actividades...........................................................32 2.1.4.4.3 Diagrama de relación de actividades.............................................34 2.1.4.4.4 Necesidades de espacio..................................................................34 2.1.4.4.5 Espacios disponibles ........................................................................35 2.1.4.4.6 Diagrama de relación de espacios .................................................35 2.1.4.4.7 Desarrollo de Soluciones .................................................................36 2.1.4.4.8 Evaluación y selección.....................................................................37
2.1.5 DISTRIBUCIÓN DE PLANTA AYUDADA POR COMPUTADORA ........ 38
6
2.1.5.1 CRAFT....................................................................................................... 40 2.1.5.2 BLOCPLAN............................................................................................... 41 2.1.5.3 MIP ............................................................................................................. 42 2.1.5.4 Enfriamiento Simulado (SA)................................................................... 45 2.1.5.5 Búsqueda Tabú........................................................................................ 46
2.2 ALGORITMOS GENÉTICOS ............................................................................... 48 2.2.1 Características de los Algoritmos Genéticos.............................................. 48 2.2.2 Etapas de los Algoritmos Genéticos............................................................ 50 2.2.3 Aplicación de AG para distribución en planta............................................. 52
3. ALGORITMO GENÉTICO PARA EL PROBLEMA DE CONFIGURACIÓN DE
PLANTA............................................................................................................................... 55
3.1 RECOLECCIÓN DE DATOS................................................................................ 55 3.1.1 Medición de las dimensiones de las oficinas y los departamentos ........ 55 3.1.2 Medición de flujos ........................................................................................... 56
3.2 DESCRIPCIÓN DEL MODELO............................................................................ 57 3.3 REPRESENTACIÓN DE LA SOLUCIÓN........................................................... 59 3.4 REALIZACIÓN DEL ALGORITMO...................................................................... 61
3.4.1 Parámetros de Entrada.................................................................................. 61 3.4.2 Estructura......................................................................................................... 62 3.4.3 Población Inicial .............................................................................................. 63 3.4.4 Función Objetivo y su evaluación................................................................. 63 3.4.5 Estrategia de selección.................................................................................. 65 3.4.6 Estrategia de cruce......................................................................................... 65 3.4.7 Estrategia de mutación.................................................................................. 67 3.4.8 Estrategias de reparación.............................................................................. 68 3.4.9 Obtención de la configuración...................................................................... 68
3.5 AG PARA LA CONFIGURACIÓN DE PLANTA DE UNA OFICINA VIRGEN73 3.5.1 Parámetros del modelo.................................................................................. 73 3.5.2 Población Inicial .............................................................................................. 74
3.6 DISEÑO DE EXPERIMENTOS............................................................................ 74 3.6.1 Oficina 1............................................................................................................ 77 3.6.2 Oficina 2............................................................................................................ 79 3.6.3 Oficina 3............................................................................................................ 81 3.6.4 Oficina 4............................................................................................................ 83 3.6.5 Oficina 5............................................................................................................ 85
3.7 DISTRIBUCIONES DE PLANTA FINALES........................................................ 87 3.7.1 Oficina 1............................................................................................................ 87 3.7.2 Oficina 2............................................................................................................ 90 3.7.3 Oficina 3............................................................................................................ 91
3.8 VALIDACIÓN DEL MODELO............................................................................... 99 4. CONCLUSIONES ........................................................................................................100
7
4.1 PROYECTOS FUTUROS ...................................................................................102 5. BIBLIOGRAFÍA............................................................................................................103
ANEXOS ...........................................................................................................................105
Anexo 1: Manual del Usuario para Opt-DOB .........................................................105 Anexo 2: Resultados obtenidos para la Función Objetivo de todas las instancias para 1000 iteraciones.................................................................................................110 Anexo 3: Datos............................................................................................................113
8
LISTA DE FIGURAS Figura 1: Distribución de planta por posición fija. Figura 2: Distribución de planta por proceso. Figura 3: Distribución de planta por producto. Figura 4: Distribución de planta celular. Figura 5: Esquema general del método SLP. Figura 6: Tabla de relaciones entre actividades. Figura 7: Diagrama de relación de actividades. Figura 8: Diagrama de relación de espacios correspondiente al de relación de actividades de la figura 7. Figura 9: Diagrama del algoritmo de SA. Figura 10: Diagrama del algoritmo de Búsqueda tabú. Figura 11: Estructura general de un algoritmo genético. Figura 12: Formato de la matriz de calificación. Figura 13: Distribución de planta correspondiente a la representación de la solución propuesta. Figura 14: Medición de distancia por métrica rectilínea. Figura 15: Ilustración para la terminología usada en el Algoritmo. Figura 16: Seudo código para hallar coordenadas. Figura 17: Ejemplo de convergencia del algoritmo
9
Figura 18: Relación entre FO, Combinación de parámetros y 200 iteraciones para la instancia 1. Figura 19: Relación entre FO, Combinación de parámetros y 1000 iteraciones para la instancia 1. Figura 20: Relación entre FO, Combinación de parámetros y 50 iteraciones para la instancia 2. Figura 21: Relación entre FO, Combinación de parámetros y 1000 iteraciones para la instancia 2 Figura 22: Relación entre FO, Combinación de parámetros y 50 iteraciones para la instancia 3. Figura 23: Relación entre FO, Combinación de parámetros y 1000 iteraciones para la instancia 3. Figura 24: Relación entre FO, Combinación de parámetros y 25 iteraciones para la instancia 4. Figura 25: Relación entre FO, Combinación de parámetros y 1000 iteraciones para la instancia 4. Figura 26: Relación entre FO, Combinación de parámetros y 100 iteraciones para la instancia 5. Figura 27: Relación entre FO, Combinación de parámetros y 1000 iteraciones para la instancia 5. Figura 28: Configuración actual, función objetivo y departamentos de la oficina 1. Figura 29: Configuración propuesta, función objetivo y departamentos para la oficina 1. Figura 30: Configuración actual, función objetivo y departamentos de la oficina 2. Figura 31: Configuración propuesta, función objetivo y departamentos para la oficina 2. Figura 32: Configuración actual, función objetivo y departamentos de la oficina 3. Figura 33: Configuración propuesta, función objetivo y departamentos para la oficina 3. Figura 34: Configuración actual, función objetivo y departamentos de la oficina 4.
10
Figura 35: Configuración propuesta, función objetivo y departamentos para la oficina 4. Figura 36: Configuración actual, función objetivo y departamentos de la oficina 5. Figura 37: Configuración propuesta, función objetivo y departamentos para la oficina 5.
11
LISTA DE TABLAS Tabla 1: Ventajas y limitaciones de los tipos básicos de distribución Tabla 2: Escala de los planos de cada oficina Tabla 3: Convenciones para las combinaciones de parámetros. Tabla 4: Comparación entre la distribución actual y la mejor encontrada por el algoritmo para cada oficina en términos de su F.O.
12
1. INTRODUCCIÓN El problema de configuración de planta se encuentra presente en diversos ámbitos
productivos de los sectores de manufactura y servicios. “La configuración de
planta determina cómo los activos fijos tangibles de una actividad son el mejor
soporte para la realización del objetivo de la misma” [5]. A partir de esto, la
importancia sobre la buena configuración de planta radica en la mejora directa
sobre la actividad productiva; así, una solución adecuada para este problema
puede representar mejoras en el rendimiento productivo y ahorros en términos
monetarios para la entidad que la aplique.
El problema abordado en este proyecto es el de distribución de planta para una
oficina bancaria, el cual ha sido muy poco tratado en la literatura académica, por lo
que este trabajo puede catalogarse como novedoso. En concreto, por medio de
esta tesis, se busca establecer una configuración de planta óptima para cuatro
oficinas de una red bancaria de la ciudad de Bogotá. Dada la complejidad del
problema, se escogió una técnica metaheurística de solución. La técnica
seleccionada fue Algoritmos Genéticos. La implementación fue codificada en
Visual Basic.
La primera parte de este trabajo muestra una introducción al problema, incluyendo
consideraciones sobre la oficina bancaria, la segunda parte presenta las bases
teóricas del tema de configuración de planta y los algoritmos genéticos, la tercera
parte contiene la descripción de la implementación del algoritmo genético para
resolver el modelo que representa el problema, el diseño del cromosoma que
representa la solución, las estrategias que se utilizaron dentro del algoritmo, la
descripción de la herramienta desarrollada para establecer el diseño de planta
13
para una oficina virgen, el diseño de experimentos para evaluar la eficiencia del
programa realizado, el planteamiento de las distribuciones de planta finales, el
análisis de los resultados obtenidos y una comparación entre la distribución actual
y la mejor distribución encontrada por medio de la metaheurística mencionada, en
términos de la función objetivo, con el objetivo de validar el modelo; y por último la
cuarta parte presenta las conclusiones de este proyecto. Como anexos se
presentan el manual de usuario de la herramienta desarrollada, los resultados
obtenidos de las instancias consideradas y los datos usados para el proyecto.
1.1 ANTEDECEDENTES
Hasta el momento el problema de configuración de planta se ha estudiado por
medio de diferentes metaheurísticas las cuales menciono mas adelante,
específicamente se ha estudiado usando algoritmos genéticos para solucionarlo.
Desde entonces se ha probado que es una metaheurística muy útil para resolver
este problema, dado que se han hecho comparaciones de los resultados arrojados
por esta con otros algoritmos como la Heurística Golany(1989), el promedio
CRAFT[5] y ha arrojado mejores resultados que estos últimos.[1]
Adicional a esto cabe anotar que en la Universidad se han elaborado varios
proyectos con respecto a este tema que han mostrado la robustez de los
algoritmos genéticos usados para solucionar el problema de la configuración de
planta, entre ellas se encuentran:
• Redistribución de planta hogar juvenil campesino, Duarte Paiba, Juan
Carlos
• Modelaje de distribución de planta para industrias Viba Ltda., Carrión Rivas,
David
• Configuración de planta por medio de algoritmos genéticos, García Pinilla,
Diana
• Configuración y rediseño de planta, Cuervo Ripe, Jenny.
14
1.2 DESCRIPCION DEL PROBLEMA
El proyecto está dirigido a establecer una configuración de planta óptima para
cuatro oficinas bancarias, de una red de esta índole de la ciudad de Bogotá. Las
oficinas fueron escogidas por ser representativas de diferentes tipos de
sucursales. El proceso de selección estuvo a cargo de un equipo de personas que
hace parte de la gerencia comercial de la institución bancaria.
La primera de las cuatro oficinas de la entidad financiera que se estudiará, consta
de dos plantas, por lo que para el desarrollo de este trabajo, cada una de éstas se
considerará como una oficina independiente. De manera que de aquí en adelante
se manejarán cinco oficinas que serán las instancias del problema.
1.3 CONSIDERACIONES SOBRE LA OFICINA BANCARIA [7][16]
Dado que la oficina bancaria no es un sistema de producción y montaje, que es a
lo que la mayoría de los textos de consulta hacen referencia, se deben tener en
cuenta sus diferencias y similitudes con los sistemas industriales.
Para el caso específico de las oficinas se debe alcanzar un equilibrio adecuado
entre los objetivos de comunicación y control – Como es el caso del área donde se
relacionan cajeros y asesores con los clientes –, por una parte, e intimidad o
asilamiento por otra – En el caso de los procesos que tienen que ver con la
bóveda y entrega de montos importantes de dinero. En las que se puede
denominar distribuciones en planta tradicionales, el equilibro entre los objetivos
contrapuestos se alcanza mediante puestos de trabajo aislados para ciertos
empleados y áreas abiertas para otros.
En las distribuciones –convencionalmente – consideradas cada puesto de trabajo
debe estar equipado de forma adecuada para las funciones que tiene asignadas
(teléfono, Terminal, ordenador, etc.). Tradicionalmente, el equipo de un puesto de
15
trabajo administrativo tenía un bajo coste, pero actualmente la inversión, aunque
no alcanza en general ni mucho menos la correspondiente a un puesto de trabajo
industrial, puede ser considerable; por otra parte, la utilización de los equipos
suele ser baja. De estas consideraciones surge un concepto, el de centro de
actividad, que da lugar a un nuevo enfoque de las distribuciones en planta en
oficinas, del cual son escasas hasta ahora las realizaciones prácticas. Se trata de
crear áreas con funciones específicas: reuniones, recepción de visitas, fotocopias,
terminales, etc. Los empleados disponen de un puesto base propio, pequeño y
poco equipado, y se desplazan de unos a otros centros de actividad a medida que
su trabajo se lo exige. Algunos inconvenientes de este tipo de solución parecen
evidentes, pero la utilización de los equipos será más alta y, por consiguiente, la
inversión, más reducida [7].
Dada la importancia de la atención al cliente en la oficina bancaria, también deben
hacerse algunas consideraciones al respecto. Dado que el sector servicios es muy
heterogéneo es difícil realizar afirmaciones que valgan de manera general. Dentro
de la oficina bancaria la circulación de materiales no es mayor, a diferencia de la
circulación de personas, por esta razón la oficina debe ser confortable para sus
usuarios y ha de garantizar la intimidad en las actividades que tienen lugar en la
instalación. También debe satisfacer exigencias estéticas y ergonómicas como las
que se citan en el siguiente párrafo.
A partir de los requerimientos de seguridad y servicio al cliente, una oficina
bancaria deberá tener en cuenta las siguientes restricciones de diseño:
1. Configuración en una Planta Rectangular
2. La zona de cajas debe estar al frente de la puerta
3. La oficina deberá ser más larga que ancha, para dejar espacio de colas al
frente de la zona de cajas.
16
4. Los elementos de servicio al cliente, tales como Mesa de consignación,
sillas de espera, etc., deben estar alrededor del hall – el cual es el área
destinada para el flujo de clientes –, a la izquierda o la derecha.
5. La zona de asesoras debe estar idealmente a la derecha de la puerta, por
motivos ergonómicos.
6. El gerente comercial debe estar cercano a la puerta, preferiblemente a la
derecha, al lado de la zona de asesoras (Los modelos dieron esta
configuración como óptima en la mayoría de los casos)
7. La bóveda debe estar atrás de los cajeros, y no debe estar accesible al hall,
ni tener muros colindantes con la calle, ni a ninguno de los lados de la
oficina
8. Los elementos de trabajo de cajeros y asesoras (impresoras, archivador de
chequeras, lámparas UV, etc.) deben estar al lado de ellos y no ser
accesibles al hall.
9. La cafetería y los baños deben estar al fondo de la oficina, lejos de los
objetos de trabajo. [16]
1.5 OBJETIVOS
1.5.1 Objetivo General Plantear un modelo óptimo de distribución de planta para cuatro oficinas bancarias
de una red de esta índole de la ciudad de Bogotá, a través de una implementación
computacional por medio de una técnica metaheurística, con el fin de aumentar la
eficiencia en el funcionamiento de la misma. La metaheurística seleccionada fue
Algoritmos Genéticos.
Para lograr lo expuesto anteriormente se requiere:
17
1.5.2 Objetivos específicos
1. Construir el marco teórico requerido para el desarrollo del proyecto. Las
actividades a desarrollar son:
• Obtener información general sobre el problema.
• Recopilar información teórica relacionada con los tipos de diseño
de planta.
• Investigar los métodos clásicos y ayudas computacionales para
solucionar el problema.
2. Definir la matriz de distancias entre localidades y la matriz de percepción o
de flujo entre departamentos para la oficina bancaria, que son datos
necesarios para resolver el problema de configuración de planta. Para ello
es necesario:
• Conseguir los planos de las oficinas de la red a las que se les
realizará el estudio.
• Obtener las medidas correspondientes a las dimensiones de las
oficinas y a los departamentos con la escala adecuada.
• Establecer las restricciones de espacio como zonas prohibidas,
restricciones de forma, etc.
• Obtener las encuestas realizadas a los gerentes de la entidad
bancaria sobre la deseabilidad de cercanía entre departamentos para
cada oficina.
• Interiorizar el conocimiento adquirido.
3. Adecuar el modelo de configuración de planta a las restricciones y
requerimientos de la entidad. Para ello es necesario:
18
• Implementar un algoritmo basado en algoritmos genéticos que tenga
en cuenta las condiciones específicas de la entidad.
• Correr el modelo y obtener la configuración de planta que éste arroje
para cada oficina estudiada.
• Validar el modelo.
4. Establecer las distribuciones de planta finales.
• Analizar el comportamiento del algoritmo para las diferentes
variaciones de parámetros y las soluciones que este arroja.
• Diagramar la distribución de planta final.
19
2. MARCO TEÓRICO
2.1 PROBLEMA DE CONFIGURACIÓN DE PLANTA
El problema de configuración de planta consiste en distribuir de manera óptima
todos los departamentos que intervengan en un proceso productivo, en búsqueda
de la economía de los recursos disponibles tales como: espacio y tiempo. Un
departamento o facilidad en el contexto de configuración de planta es una entidad
física que facilita el desarrollo de algún trabajo. Por ejemplo: Una celda de
manufactura o una máquina. Según Root y Rakshit (1993), el área es la única
característica común para todas las facilidades [2]. El área que cada facilidad
ocupe o se desee que ocupe, en el caso específico de los departamentos,
determinará gran parte de las restricciones del modelo que represente el
problema.
Los datos mínimos que se requieren para dar solución al problema son: Número
de departamentos, dimensiones físicas de la planta, área por departamento, matriz
de flujos entre departamentos, y los costos de transporte por unidad. La matriz de
flujos puede cambiarse por una matriz de percepción donde se representa la
deseabilidad de cercanía entre departamentos. Los costos de transporte pueden
ser hallados por medio de la multiplicación entre el flujo y la distancia para cada
par de departamentos. Como solución del problema se obtiene la posición óptima
de cada departamento dentro de la planta, el área óptima de cada departamento y
los costos óptimos de transporte.
20
2.1.1 OBJETIVOS DE UNA BUENA CONFIGURACIÓN DE PLANTA [4]:
De manera general se busca “hallar una ordenación de las áreas de trabajo y el
equipo, que sea la más económica para el trabajo, al mismo tiempo que la más
segura y satisfactoria para los empleados” 1. Adicional a esto, se quiere planear
una distribución que logre los objetivos de localización y de diseño. [5]
En específico, para alcanzar las ventajas de la buena configuración de planta que
son traducidas en la disminución de los costos de producción, se busca:
• Incremento de la producción.
• Reducción de riesgos para la salud y aumento de la seguridad para
los trabajadores.
• Elevación de la moral y satisfacción del obrero
• Satisfacción del trabajador.
• Disminución de los retrasos en la producción.
• Ahorro de área ocupada.
• Reducción del material del proceso.
• Mayor utilización de la maquinaria, de la mano de obra y/o de los
servicios.
• Acortamiento del tiempo de servicio o fabricación.
• Disminución de congestión.
• Mayor facilidad de ajuste a los cambios de condiciones.
• Reducción del trabajo administrativo y del trabajo indirecto en
general.
• Logro de una supervisión más fácil y mejor.
• Disminución del riesgo para el material o su calidad.
1 MUTHER, Richard. “DISTRIBUCION EN PLANTA. Ordenación racional de los elementos de producción industrial”. Cuarta ed. 1981
21
2.1.2 PRINCIPIOS BÁSICOS DE LA DISTRIBUCIÓN DE PLANTA [5]
2.1.2.1 Principio de la integración de conjunto Una buena distribución integra a los factores que influyen dentro de la actividad de
la planta: los hombres, los materiales, la maquinaria, las actividades auxiliares, en
una unidad de conjunto, de manera que cada uno de ellos se esté relacionando
con los otros, para cada conjunto de condiciones de seguridad y operativas.
2.1.2.2 Principio de la mínima distancia recorrida Dado que todo proceso industrial implica movimiento de material, y por más que
se intente disminuirlo no es posible suprimirlo del todo, es siempre mejor la
distribución que permite que la distancia a recorrer por el material entre
operaciones sea la más corta.
Dado que dichos traslados no añaden ningún valor al producto, se busca el ahorro
de los mismos reduciendo las distancias que el material deba recorrer, de manera
que se tratará de colocar las operaciones sucesivas inmediatamente adyacentes
unas a otras.
2.1.2.3 Principios de la circulación o flujo de materiales Este es un complemento del principio de la mínima distancia recorrida, ya que se
busca una distribución que ordene las áreas de trabajo de manera que cada
operación o proceso esté en el mismo orden o secuencia que se transforman
tratan o montan los materiales. Se debe tener en cuenta que no deben existir
retrocesos o movimientos transversales, para que no se presente congestión con
otros materiales o piezas del mismo conjunto. Lo anterior no limita el movimiento
del material a una forma lineal, los recorridos en zigzag, en círculo o en U, también
son propios de buenas configuraciones. En resumen el concepto de circulación es
un progreso constante hacia la finalización del trabajo, minimizando las
interrupciones, interferencias o congestiones.
22
2.1.2.4 Principio del espacio cúbico Todos los agentes que intervienen dentro de la actividad de la planta ocupan tres
dimensiones por lo que todas deben ser tenidas en cuenta a la hora de realizar la
configuración. De la misma manera el movimiento de los mismos puede darse en
estas tres, por lo que se busca un aprovechamiento del espacio libre en todo el
plano tridimensional.
2.1.2.5 Principio de la satisfacción y de la seguridad
Dos factores fundamentales para el buen desarrollo del trabajo son la satisfacción
de los empleados y la seguridad. El primero trae muchos otros beneficios como la
disminución de costos de operación y una moral mas elevada por parte de los
empleados. El segundo es de gran importancia en una distribución y en algunas
ocasiones vital, ya que nunca una distribución podrá ser efectiva si los
trabajadores están expuestos a riesgos o accidentes.
2.1.2.6 Principio de la flexibilidad
Dada la rapidez con que evolucionan los diferentes campos que respectan a la
empresa, como las comunicaciones, el transporte, etc., ésta debe tener la
habilidad para cambiar rápidamente tanto el diseño del producto, proceso, equipo,
producción o fechas de entrega, para evitar faltas en los pedidos y por ende
pérdida de los clientes. Por esta razón se busca una distribución que permita el
ajuste y reordenamiento de la misma con rapidez, menores costos e
inconvenientes.
2.1.3 TIPOS DE DISTRIBUCIÓN DE PLANTA [4] [5]
Los tres elementos básicos de la producción son: los hombres, los materiales y la
maquinaria; si los tres estuvieran estacionarios no podría haber producción en un
sentido industrial, el estudio sobre la distribución inicia analizando cuáles de estos
elementos deben moverse y la relación entre ellos:
23
Movimiento de material: El material es el elemento más comúnmente movido, éste
se mueve de una estación a otra en el orden en que deben realizarse las
operaciones.
Movimiento del hombre: Los operarios se mueven de una estación a otra en el
orden en que deben realizarse las operaciones y realizando las mismas sobre
cada pieza del material.
Movimiento de maquinaria: El operario mueve herramientas o máquinas para
operar sobre una pieza grande.
Movimiento de material y de hombres: El operario se mueve con el material y
realiza una operación sobre cada estación.
Movimiento de material y de maquinaria: Tanto los materiales como la maquinaria
se desplazan hacia los hombres quienes realizan las operaciones.
Movimiento de hombres y de maquinaria: Los trabajadores se mueven junto con la
maquinaria hacia el elemento sobre el cual están operando.
Movimiento de materiales, hombres y maquinaria: Todos los elementos se
mueven, puede ser costoso e innecesario.
A partir de lo anterior se muestran los cuatro tipos clásicos de distribución:
2.1.3.1 Distribución por posición fija En este tipo de distribución por posición, el material permanece en un lugar fijo; las
herramientas, la maquinaria, hombres y otros materiales concurren al producto
que se está elaborando. (Ver Figura1).
Figura 1: Distribución de planta por posición fija.
24
2.1.3.2 Distribución por proceso
También es llamada distribución por función donde todas las operaciones de un
mismo tipo de proceso están agrupadas. (Ver Figura 2).
Figura 2: Distribución de planta por proceso.
2.1.3.3 Distribución por producto
Esta distribución también es llamada como producción en línea o en cadena, en
ésta el material está en movimiento. Las máquinas o entidades que intervienen en
la elaboración del producto final están dispuestas una inmediatamente al lado de
la siguiente y están ordenadas en la secuencia de las operaciones del proceso.
(Ver Figura 3).
Figura 3: Distribución de planta por producto.
25
2.1.3.4 Distribución celular [5]
Este tipo de distribución, no es considerada entre las básicas ya que es una
combinación de las mencionadas anteriormente. Las celdas de manufactura
agrupan máquinas, empleados, materiales, herramientas, material, y equipo para
producir familias o partes de productos.
Los beneficios mas importantes de la manufactura celular son alcanzados cuando
las celdas de manufactura son diseñadas, controladas y operadas usando los
conceptos y técnicas de Just In time (JIT), Total Quality Management (TQM), y
Total Employee Involvement (TEI). (Ver Figura 4).
Figura 4: Distribución de planta celular.
La configuración de planta constituye entonces una combinación o variaciones
entre los cuatro tipos expuestos anteriormente.
26
2.1.3.5 Ventajas y limitaciones de los tipos básicos de distribución [5]
Distribución por posición fija
Ventajas Limitaciones
1. El movimiento del material es
reducido
2. Cuando se hace uso del acercamiento
del equipo, la continuidad de las
operaciones y la responsabilidad son
resultados
3. Provee oportunidades de
enriquecimiento del trabajo
4. Promueve el orgullo y la calidad
porque un individuo puede realizar
“todo el trabajo”
5. Altamente flexible; pueden
acomodarse cambios en el diseño del
producto y el volumen de producción
1. Aumenta el movimiento del
personal y del equipo
2. Puede resultar equipo
duplicado
3. Requiere personal con
mayores habilidades
4. Requiere supervisión
general
5. Puede resultar en aumento
del espacio y mayor
cantidad de trabajo en
proceso
6. Requiere control y
coordinación cercanos en la
programación de la
producción
Distribución por producto o en línea
Ventajas Limitaciones
1. Resultan líneas de flujo planas, simple
y lógicas
2. Resultan inventarios de trabajo en
proceso pequeños
3. El tiempo total de producción por
unidad es corto
4. La manipulación de material requerida
es reducida
5. Se requieren de menos habilidades
1. Una parada de máquina
detiene la línea
2. Si el diseño del producto
cambia, la distribución
actual se vuelve obsoleta
3. La estación mas lenta marca
el paso de la línea
4. Es requerida supervisión
general
27
para el personal
6. Es posible un control simple de la
producción
7. Puede ser usado equipo
especializado
5. Usualmente resulta en
mayor inversión en equipos
Distribución por proceso
Ventajas Limitaciones
1. Incrementa la utilización de
maquinaria
2. El equipo puede ser usado para un
propósito general
3. Altamente flexible en la ubicación de
equipo y personal
4. La manipulación del material es
reducida
5. Diversidad de tareas para el personal
6. Es posible la supervisión
especializada
1. Aumento de los
requerimientos para el
manejo del material
2. Ser requiere un control de la
producción mas complicado
3. Aumento del trabajo en
proceso
4. Líneas de producción mas
largas
5. Se requieren mayores
habilidades para acomodar
diversidad de tareas
Tabla 1: Ventajas y limitaciones de los tipos básicos de distribución
2.1.4 MÉTODOS PARA EL DISEÑO DE DISTRIBUCIONES EN PLANTA [5]
Se han desarrollado diferentes procedimientos para facilitar las distribuciones en
planta. Estos procedimientos pueden ser clasificados en dos grandes categorías:
• Tipo constructivo: Los métodos que pertenecen a esta categoría desarrollan
configuraciones de planta partiendo desde cero.
28
• Tipo Mejora: Estos métodos generan configuraciones alternativas basadas
en una configuración existente.
A continuación se muestran algunos de los procedimientos clásicos para resolver
el problema. Los conceptos de éstos han sido útiles para la creación de muchas
de las metodologías propuestas en la actualidad.
2.1.4.1 Procedimiento de Distribución de planta de Apple
Según Apple [6] el diseñador de plantas debe seguir un procedimiento ordenado.
La mayoría de las veces sin hacer caso del tipo de facilidades, el proceso de
diseño debe seguir de manera cercana la siguiente secuencia de pasos:
1. Obtener los datos básicos del problema.
2. Analizar los datos básicos obtenidos.
3. Diseñar el proceso productivo.
4. Planear el patrón de flujo de material.
5. Considerar un plan general de manejo de materiales.
6. Calcular los requerimientos del equipo.
7. Planear estaciones de trabajo individuales.
8. Seleccionar un equipo específico de manejo de materiales.
9. Coordinar lo grupos de operaciones relacionadas.
10. Diseñar las interrelaciones de las actividades.
11. Determinar los requerimientos de almacenamiento.
12. Planear actividades auxiliares y de servicio.
13. Determinar los requerimientos de espacio.
14. Asignar actividades al espacio total.
15. Considerar tipos de edificio.
16. Construir la distribución maestra.
17. Evaluar, ajustar y revisar la distribución con las personas apropiadas.
18. Obtener aprobaciones.
29
19. Instalar la distribución.
20. Realizar un seguimiento a la implementación de la distribución.
2.1.4.3 Procedimiento de Distribución de planta de Reed [5]
Reed recomendó el siguiente “plan de ataque sistemático” para la planeación y
preparación de a distribución.
1. Analizar el producto o productos que serán elaborados
2. Determinar el proceso requerido para manufacturar el producto
3. Preparar cartas de planeación de la distribución
4. Determinar las estaciones de trabajo
5. Analizar los requerimientos de las áreas de almacenamiento
6. Establecer los anchos mínimos para los pasillos de la planta
7. Establecer los requerimientos de la oficina
8. Considerar departamentos para el personal y servicios
9. Listar los servicios de la planta
10. Hacer provisión para la futura expansión
Para Reed las cartas de planeación de la distribución son el paso más importante
del proceso de distribución. Éstas contienen la siguiente información:
1. El flujo del proceso, incluyendo operaciones, transporte, almacenamiento,
e inspecciones.
2. Tiempos estándar para cada operación.
3. Selección y balance de máquinas.
4. Selección y balance de mano de obra.
5. Requerimientos del manejo de materiales.
30
2.1.4.4 Procedimiento Sistemático de Distribución de planta (SLP) de Muther
[5] [7]
Muther desarrolló un procedimiento para realizar la distribución de planta que él
denominó Procedimiento Sistemático de distribución de planta o SLP. El esquema
general de éste puede observarse en la Figura 5.
El procedimiento consta de tres fases, la primera de ellas es el análisis, la cual
inicia con la recolección de la información necesaria sobre productos, cantidades,
procesos y servicios. La primera fase tiene cinco pasos:
31
Figura 5: Esquema general del método SLP.
32
2.1.4.4.1 Análisis del Flujo de materiales
Este es un aspecto que aunque no es el único que se debe tener en cuenta es
clave en el planteamiento del problema. Para la realización del estudio se debe
partir de la descripción del proceso, para lo que existen diferentes herramientas
que pueden ser utilizadas según las necesidades del caso:
• Diagrama de Acoplamiento: Destaca los subconjuntos que se van
formando y reuniendo hasta obtener el producto.
• Diagrama analítico de operaciones del proceso: Incluye los símbolos
de transporte y de demora. Su representación es libre y puede ser
similar al diagrama de operaciones.
• Diagrama multiproducto: Es conveniente utilizarlo cuando hay
muchos productos, ya que permite tener una visión conjunta de los
procesos correspondientes a diversos productos.
• Matrices: Destaca los desplazamientos entre centros de actividad.
Cada fila y columna representan una actividad.
• Diagramas de recorrido y diagramas de hilos: Pueden ser utilizados
sobre una distribución existente. Estos dan información sobre las
trayectorias, las frecuencias de utilización de los diversos puntos de
paso y la posibilidad de interferencias entre distintos flujos.
2.1.4.4.2 Relaciones entre actividades
Lo que se debe tener en cuenta a la hora de realizar un estudio de configuración
de planta no sólo es el recorrido de los elementos materiales sino cualquier
relación que exista al interior del sistema productivo. Dentro de lo anterior se
encuentran las relaciones entre actividades las cuales pueden ser representadas
en buena forma por medio de una tabla como la de la Figura 6. En ella se
encuentra la simbología recomendada por Muther. Gracias a este tipo de
33
representación de una matriz simétrica (en la que los elementos de la diagonal son
nulos) se ahorra espacio y se omiten las redundancias.
1 Supervisión2 Contacto Frecuente
OrdinariaNo importante
Indeseable
Código Definición
DefiniciónAbsolutamente necesariaEspecialmente importante
ImportanteOUX
Código
Sala de reuniones
AEI
Fotocopias
Almacén
Biblioteca
Servicios
Recepción
Ventas
Dirección
Secretaría
Figura 6: Tabla de relaciones entre actividades.
34
2.1.4.4.3 Diagrama de relación de actividades Con la información recolectada hasta el momento ya se puede iniciar la
configuración de planta. Los dos pasos anteriores convergen a la realización del
diagrama de relación de actividades. En él se representa gráficamente cada centro
de actividad sin tener en cuenta el área que cada uno requiera. Los símbolos
utilizados son unidos por medio de líneas simples o múltiples que representan la
importancia de la relación entre ellos (puede ser expresada por medio del número
de líneas, color, grosor o números junto a la línea de unión). Para mayor
ilustración ver Figura 7.
Figura 7: Diagrama de relación de actividades.
2.1.4.4.4 Necesidades de espacio
Para este momento se requiere estimar la superficie necesaria para cada
departamento o centro de actividad. La forma como se determine las necesidades
de superficie debería ser precisa porque en general el espacio es caro, pero no se
debe ser en extremo justo, ya que es conveniente asignar cierto margen. Existen
diversos procedimientos para realizar la estimación que se está tratando y la
35
escogencia entre ellos depende del grado de detalle que se le quiera añadir al
estudio.
2.1.4.4.5 Espacios disponibles
Una vez obtenida la estimación sobre el área que se requiere para cada
departamento, se debe comparar esta información con el espacio del que se
dispone en la actualidad. Si no concuerdan entre sí se debe realizar un ajuste de
una de ellas o ambas.
La segunda fase de éste método es la búsqueda, sus principales pasos son los
que se tratan a continuación.
2.1.4.4.6 Diagrama de relación de espacios
Una vez se tenga la información mencionada anteriormente y se hayan realizado
los ajustes necesarios, se puede dar lugar a la representación gráfica de los
centros de actividad y de las relaciones de actividad, por medio de un diagrama
similar al de relación de actividades, con la diferencia de que en éste todos los
gráficos se realizan a escala y pueden tener la forma que se considere adecuada
para cada departamento. Un ejemplo de esta herramienta es mostrado a
continuación en la Figura 8.
36
Figura 8: Diagrama de relación de espacios correspondiente al de relación de
actividades de la figura 7.
2.1.4.4.7 Desarrollo de Soluciones
Una representación de cada una de las posibles soluciones es el diagrama de
relación de espacios. La comparación que se realice entre estas posibles
distribuciones debe tener en cuenta aspectos que posiblemente se hayan relegado
desde el principio y que pueden resultar muy difíciles de tener en cuenta desde el
principio de las consideraciones que se realizaron ya que posiblemente restrinjan
el modelo en extremo. Algunos ejemplos de los aspectos mencionados son:
características constructivas de los edificios, orientación, usos del suelo en las
áreas vecinas, recursos financieros, equipos de manutención, vigilancia, horarios
de trabajo, seguridad, etc. Siendo esta última, la seguridad de las personas y los
equipos, una de las consideraciones más importantes, para lo cual se deben tener
en cuenta las siguientes observaciones:
• Los accesos, pasillos y salidas sean amplios y bien señalizados.
• Los operarios no estén cerca de zonas peligrosas.
• Exista un acceso conocido y fácil para los equipos de emergencia.
37
• No haya elementos puntiagudos, cortantes, etc. en las áreas de trabajo y en
las de circulación.
En general, el desarrollo de soluciones es un proceso que demanda creatividad, y
aquellos que las plantean (los diseñadores de la distribución de planta) deben
hacer uso del método y la experiencia.
La tercera fase es selección la cual consta de un solo paso:
2.1.4.4.8 Evaluación y selección
Una vez se han desarrollado las alternativas sobre la distribución, se realiza la
selección entre ellas. De manera general en este punto intervienen personas que
no han hecho parte del estudio hasta el momento, por lo que una presentación
que muestre claramente lo que se propone es determinante para el buen
desarrollo del proyecto. Para esto se debe hacer uso de los diagramas vistos
anteriormente o maquetas que puedan ser modificadas rápida y económicamente,
planos, representaciones en una pantalla de computador, entre otras.
Algunos criterios para la elección de distribuciones en planta son (Vallhonrat y
Corominas, 1991):
• Facilidad de expansión
• Flexibilidad
• Eficacia en la manipulación de materiales
• Utilización del espacio
• Seguridad
• Condiciones de trabajo
• Aspecto, valor promocional
• Adaptación a las estructuras orgánicas
38
• Utilización de los equipos
• Facilidad de supervisión y control
• Inversión
• Coste de funcionamiento
2.1.5 DISTRIBUCIÓN DE PLANTA AYUDADA POR COMPUTADORA [5]
Los algoritmos computacionales son herramientas que pueden incrementar
significativamente la productividad del planeador de la distribución y la calidad de
la solución final gracias a la generación y evaluación numérica de un gran número
de alternativas de distribución en un corto tiempo. Cabe anotar que los algoritmos
que se encuentran actualmente no reemplazan el juicio ni la experiencia humana,
y por lo general no capturan las características cualitativas de la distribución.
La mayoría de los algoritmos pueden ser clasificados por el tipo de datos de
entrada que requieren, algunos pueden recibir solamente datos de tipo cualitativo,
mientras que otros aceptan datos de tipo cuantitativo. La clasificación de los
algoritmos también puede realizarse por el tipo de función objetivo, hay dos tipos
básicos de funciones objetivos:
• Minimizar la suma de flujos, tiempos y distancias: Es similar a la
correspondiente al problema cuadrático de asignación. Sean :
m : Número de departamentos
fij : Flujo del departamento i al j (expresado en número de cargas unitarias
movidas por unidad de tiempo)
cij : Costo de mover una unidad de carga, una unidad de distancia desde el
departamento i al departamento j
39
El objetivo es minimizar el costo por movimiento entre departamentos por
unidad de tiempo, puede ser expresado matemáticamente así:
ijij
m
i
m
jij dcfZ ∑∑
= =
=1 1
min (1)
Donde dij es la distancia del departamento i al j. De manera general dij es
medida por medio de métrica rectilínea entre los centroides de los
departamentos.
• Maximización del puntaje de adyacencia: Es basada en la suma del puntaje
de adyacencia, el cual es calculado como la suma de los flujos entre los
departamentos que son adyacentes en la distribución. Sea:
⎩⎨⎧
=casootroEn
comúnbordeuntienenadyacentessonjyitodepartamenelsixij 0
)(1
El objetivo es maximizar el puntaje de adyacencia que es:
(2)
Así como con la anterior ecuación (2) se comparó el puntaje de adyacencia
entre dos distribuciones, también es aconsejable calcular la eficiencia
relativa por medio del puntaje normalizado de adyacencia, el cual varía
entre 0 y 1, toma el valor de uno cuando todos las parejas de
departamentos con flujo positivo entre ellos son adyacentes en la
distribución. Matemáticamente se expresa de la siguiente manera:
ij
m
i
m
jij xfZ ∑∑
= =
=1 1
max
40
∑∑
∑∑
= =
= == m
i
m
jij
ij
m
i
m
jij
f
xfZ
1 1
1 1
Los algoritmos en mención también pueden ser clasificados de acuerdo al formato
que usan para representar distribución. Existen dos clasificaciones en relación a
este aspecto:
• Discreta: el área de cada departamento es aproximada a un número
discreto de cuadrillas.
• Continua: El área de los departamentos no está alineada con la cuadrilla
por lo que no es recomendable para construcciones rectangulares.
Por último los algoritmos de distribución pueden ser clasificados de acuerdo a su
función primaria:
• Algoritmos de mejora: Empiezan con una configuración inicial y buscan
mejorar la función objetivo correspondiente por medio de cambios a la
distribución.
• Algoritmos de construcción: Crean la distribución partiendo desde cero,
existen aquellos que pueden asumir las dimensiones del edificio dadas o
aquellos que no.
A continuación se presentan diferentes algoritmos para la distribución de planta.
2.1.5.1 CRAFT
CRAFT (Computer Relative Allocation Facilities Technique) es una de las primeras
técnicas conocidas para la configuración de planta en la literatura. El costo de la
distribución se haya por medio de la ecuación (1). Los departamentos nos están
41
restringidos a formas rectangulares y la representación que usa es del tipo
discreta. Los pasos de este algoritmo son:
1. Empieza con una distribución inicial, que representa la distribución inicial,
pero también puede representar la distribución hecha por otro algoritmo.
2. Determina los centroides de los departamentos en la distribución inicial.
3. Calcula la distancia rectilínea entre parejas de centroides de departamentos
y guarda los valores en una matriz de distancia.
4. Se calcula el costo de la distribución inicial (Ecuación 1).
5. Intercambia 2 o 3 departamentos e identifica el mejor intercambio, que será
el que represente una mayor disminución en costo de la distribución.
6. Actualiza la información de acuerdo al mejor intercambio encontrado y
termina la primera iteración.
7. Empieza la siguiente iteración con tomando como solución inicial la mejor
distribución que encontró en la iteración anterior.
La solución obtenida es conocida como distribución 2-opt (3-opt) ya que 2 formas
(tres formas) de intercambios pueden reducir el costo de la distribución.
2.1.5.2 BLOCPLAN
BLOCPLAN ubica los departamentos en bandas, cada uno es ubicado en una
banda por lo que tienen forma rectangular, usa una tabla de relación entre ellos
para representar el flujo como dato de entrada, el costo de la distribución también
es medido por medio de la ecuación (1) o la ecuación de adyacencia (2). Adicional
a esto, el algoritmo determina el número de bandas y el ancho de las mismas, usa
representación continua y suele ser usado tanto como algoritmo constructivo como
de mejora.
El algoritmo primero asigna cada departamento a una de las bandas, luego calcula
el ancho apropiado de la banda dividiendo el área total de los departamentos en
42
esa banda por la longitud del edificio. La distribución completa es formada gracias
al cálculo del ancho de cada banda tal como se describió y organizando los
departamentos en cada banda de acuerdo a una secuencia específica.
2.1.5.3 MIP
El problema de configuración de planta puede ser formulado como un problema de
programación mixta entera (Mixed Integer Programming, MIP) si todos los
departamentos se asumen como rectangulares. Este algoritmo usa representación
continua, su función objetivo es basada en la distancia (Ecuación 1) y de manera
general es del tipo constructivo. Las dimensiones de los departamentos son
tratadas como variables de decisión. Teniendo en cuenta lo anterior el problema
puede ser formulado así (Montreuil, 1987):
Parámetros del problema:
Bx = Longitud del edificio (medida a lo largo de la coordenada X)
By = Ancho del edificio (medida a lo largo de la coordenada Y)
Ai = Área del departamento i
Lli = Límite inferior de la longitud del departamento i
Lui = Límite superior de la longitud del departamento i
Wli = Límite inferior del ancho del departamento i
Wui = Límite superior del ancho del departamento i
M = un número grande
Variables de decisión:
αi = Coordenada X del centroide del departamento i.
βi = Coordenada Y del centroide del departamento i
43
X’i = Coordenada X del lado izquierdo (u oeste) del departamento i
X’’i = Coordenada X del lado derecho (o este) del departamento i
Y’i = Coordenada Y del lado inferior (o sur) del departamento i
Y’’i = Coordenada Y del lado superior (o norte) del departamento i
Zxij = 1 si el departamento i está estrictamente a la derecha (al este)
del departamento j y 0 en otro caso
Zyij = 1 si el departamento i está estrictamente arriba (al norte) del
departamento j y 0 en otro caso
El departamento i estaría estrictamente a la derecha del departamento j si y solo
si X’’j ≤ X’i, De igual manera, el departamento i estaría estrictamente al norte del
departamento j si y solo si Y’’j ≤ Y’i. Se garantiza que dos departamentos no se
sobreponen ya que están separados en la coordenada X y Y. Lo anterior conduce
al siguiente modelo:
Minimizar Z = ( )∑ ∑ −+−i j
jijiCijfij ββαα** (3)
Sujeto a:
Lli ≤ (X’’i- X’i) ≤ Lu
i i∀ (4)
Wli ≤ (Y’’i-Y’i) ≤ Wu
i i∀ (5)
(X’’i-X’i)(Y’’i-Y’i) = Ai i∀ (6)
0 ≤ X’i ≤ X’’i ≤ Bx i∀ (7)
0 ≤ Y’i ≤ Y’’i ≤ By i∀ (8)
αi = 0.5 X’i + 0.5 X’’i i∀ (9)
44
βi= 0.5 Y’i + 0.5 Y’’i i∀ (10)
X’’j ≤ X’j + M (1- Zxij) i∀ y j∀ , ji ≠ (11)
Y’’j ≤ Yj’+M (1- Zyij ) i∀ y j∀ , ji ≠ (12)
Zxij + Z x
ji + Zyij + Zy
ji ≥ 1 i∀ y j∀ , i < j (13)
α i , βi ≥ 0 i∀ (14)
X’i, X’’i, Y’i, Y’’i ≥ 0 i∀ (15)
Zxij, Zy
ij, entero {0, 1} i∀ y j∀ , ji ≠ (16)
La función objetivo dada por la ecuación 3, es la función objetivo mostrada en la
ecuación (1), las restricciones (4) y (5) aseguran que la longitud y el ancho de
cada departamento no supere los límites, la restricción (6) expresa el área
requerida por cada departamento, las restricciones (7) y (8) aseguran que los
lados de cada departamento estén definidos apropiadamente y que cada
departamento esté localizado dentro del piso de la planta en las coordenadas X y
Y, (9) y (10) definen las coordenadas X y Y respectivamente del centroide de cada
departamento. La restricción (11) asegura que el departamento i está
estrictamente a la derecha de j y se activa cuando Zxij = 1, (12) cumple el mismo
propósito de la anterior pero en la coordenada Y, (13) garantiza que dos
departamentos no se traslapen. Finalmente (14) y (15) son las restricciones de no
negatividad y (16) designa las variables binarias.
El anterior modelo “puede ser resuelto por medio de herramientas
computacionales, sin embargo los resultados pueden ser garantizados cuando se
trabaja con un intervalo de 7-8 departamentos. La ventaja de este modelo es que
la solución resultante está garantizada entre 5% a 10% del óptimo” [8].
45
2.1.5.4 Enfriamiento Simulado (SA)
SA (Simulated Annealing) es una metaheurística relativamente nueva, fue
formulado por Kirkpatrick, Gelat & Vecchi en 1983. Los conceptos fundamentales
detrás de SA están basados en una analogía entre mecánica estadística y
problemas de optimización combinatoria. Mecánica estadística es “la disciplina
central de la física de la materia condensada, una serie de métodos para analizar
propiedades agregadas de un gran número de átomos encontrados en muestras
de materia líquida o sólida” (Kirkpatrick, 1983). Una de las claves de esta disciplina
es el estado de la materia de acuerdo a como su temperatura es gradualmente
reducida hasta alcanzar el “punto de congelamiento”. De esta manera la analogía
relacionada con SA es el enfriamiento de los materiales, donde los átomos
presentan movimiento hasta que la materia llega al punto de enfriamiento. De esta
manera se realiza la búsqueda de la solución al problema de optimización
combinatoria que se esté resolviendo usando un parámetro de control, que es la
temperatura, partiendo de una solución inicial y una temperatura inicial. A
continuación se muestra un diagrama del algoritmo para un problema de
minimización [9]:
46
Figura 9: Diagrama del algoritmo de SA. 2.1.5.5 Búsqueda Tabú [10]
La búsqueda Tabú parte de una solución actual, a partir de esto inicializa la lista
tabú y realiza la búsqueda de mejores soluciones en la vecindad de la solución
47
inicial teniendo en cuenta las movidas prohibidas que se encuentran en la lista, tal
y como se muestra en el siguiente esquema:
Figura 10: Diagrama del algoritmo de Búsqueda tabú.
Los conceptos claves en la búsqueda tabú son:
• Memoria a corto plazo: La lista tabú es actualizada con política FIFO. El
objetivo de esto es evitar caer en óptimos locales.
• Criterio de aspiración: pasa por alto una movida tabú si ésta movida genera
una mejor solución que el mejor óptimo actual.
• Intensificación: Realiza una búsqueda local alrededor de la solución actual
(movidas tabú).
• Diversificación: Realiza una búsqueda por fuera de las restricciones de la
lista tabú.
48
2.2 ALGORITMOS GENÉTICOS [1][2] [3][11]
Los algoritmos genéticos (AG) son técnicas de búsqueda aleatoria dirigida [11].
Fueron inventados por John Holland, profesor de la Universidad de Michigan,
quien publicó su artículo “Adaptation in Natural and Artificial Systems” en 1975.
Surgen como una forma alternativa a los métodos de gradientes, los cuales
resultan imprácticos al realizar búsquedas en un espacio n-dimensional cuando se
presentan múltiples óptimos relativos [3]. Son inspirados en los procesos de
evolución y selección natural, de manera que sus operadores basados en métodos
evolutivos, actúan sobre los individuos pertenecientes a cada generación para
encontrar soluciones que representen mejoras en la función objetiva. Los
individuos (pertenecientes a la población) dentro de un AG son soluciones
factibles del problema La población es un subconjunto del espacio solución y el
tamaño (número de individuos que posea) depende del problema que se esté
tratando. Cada individuo de la población es representado por medio de un
cromosoma, el cual es una mezcla de símbolos conocidos como genes. Los dos
métodos básicos de representación de los individuos son:
• Vectores de números binarios
• Vectores de números enteros o reales
2.2.1 Características de los Algoritmos Genéticos [3]
Según Kook (2004) los algoritmos genéticos se caracterizan por:
• Estocásticos: Las transformaciones dadas para el proceso de búsqueda de la
solución y el paso de una generación a otra son probabilísticas.
• De Búsqueda múltiple: El proceso es realizado simultáneamente en un
conjunto de cromosomas, lo cual permite que no se llegue a una solución
única, sino posiblemente a varias –con un costo similar –en un período
49
relativamente corto de tiempo; Incrementando con ello la probabilidad de
hallazgo de múltiples soluciones diferentes.
• Exploratorios: De todos los algoritmos estocásticos, los algoritmos genéticos
son los que realizan una mayor exploración al subespacio de posibles
soluciones.
• Independientes de los Parámetros Iniciales: La convergencia del algoritmo es
relativamente independiente de la población inicial, a menos que ésta sea
realmente degenerada. Esto es particularmente cierto en poblaciones
relativamente grandes, escogidas de forma aleatoria.
• Robustez Paramétrica: El éxito del algoritmo depende de la codificación de los
parámetros; No de los parámetros en sí. Si la representación de los datos y las
operaciones de cruce y selección han sido bien escogidas, es muy difícil que el
algoritmo no converja. Esto es particularmente bueno para problemas muy
complejos, en los que no existen criterios para escoger una población inicial en
particular: Si el algoritmo está bien diseñado, convergerá más o menos
rápidamente a una solución relativamente aceptable.
• Paralelismo intrínseco: Independientemente de su implementación, los
algoritmos genéticos exploran el espacio en forma paralela.
• Independencia del Problema: El algoritmo genético no está ligado con el
problema particular. Esto hace al algoritmo bastante robusto, por ser útil para
cualquier problema, pero a la vez débil, por no estar especializado en ninguno.
Estas características, permiten considerar los algoritmos genéticos como un buen
método de solución para el problema.
50
2.2.2 Etapas de los Algoritmos Genéticos [11] [12] [13]
A continuación se presenta el esquema general de las etapas de un AG:
Figura 11: Estructura general de un algoritmo genético.
• Población inicial: El proceso de optimización parte de un conjunto de
soluciones iniciales que aplican para el problema tratado. Pueden usarse
cromosomas generados aleatoriamente o usar soluciones conocidas
previamente del problema.
• Evaluación de la función objetiva en la población actual: Cada individuo de
la población es evaluado para hallar el valor de la función objetivo. A
aquellos que violen restricciones del problema pueden ser penalizados en
su función objetivo. De acuerdo a la obtención de la F.O. puede
determinarse cuáles son los individuos mas adaptados, según sea el caso
de minimización (F.O. baja) o maximización (F.O. alta).
51
• Selección de los individuos más adaptados: Los individuos que representan
una mejor solución (en términos de la F.O.) son aquellos que tienen mayor
probabilidad de reproducirse. Existen diferentes criterios de selección como
el de ruleta donde cada individuo tiene una probabilidad de reproducirse
proporcional a su grado de adaptación, y el de rango que tiene en cuenta el
rango del mejor ajuste a la función objetiva y no la magnitud de esta.
• Cruce: Este operador diferencia los algoritmos genéticos de otros
algoritmos de optimización. Se realiza con el objetivo de crear –por lo
general- dos nuevos individuos (hijos) a partir de dos individuos existentes
(padres) seleccionados por el criterio de selección establecido para el
algoritmo. Por lo general se usa cruce por un punto. A continuación se
muestran diferentes tipos de cruce [11]:
o Cruce por un punto:
Padre 1: 1 0 0 0 1 0 0 1 1 1 1
Padre 2: 0 1 1 0 1 1 0 0 0 1 1
Hijo 1: 1 0 0 0 1 1 0 0 0 1 1
Hijo 2: 0 1 1 0 1 0 0 1 1 1 1
o Cruce por dos puntos:
Padre 1: 1 0 1 0 0 0 1 1 0 1 0
Padre 2: 0 1 1 0 1 1 1 1 0 1 1
Hijo 1: 1 0 1 0 1 1 1 1 0 1 0
Hijo 2: 0 1 1 0 0 0 1 1 0 1 1
o Cruce cíclico:
Padre 1: 1 2 3 4 5 6 7 8 9
Padre 2: a b c d e f g h i
52
Hijo 1: 1 b 3 d e f 7 h 9
Hijo 2: a 2 c 4 5 6 g 8 i
o Cruce uniforme:
Padre 1: 1 0 1 0 0 0 1 1 0 1 0
Padre 2: 0 1 1 0 1 1 1 1 0 1 1
Patrón: 1 1 0 1 0 0 1 1 0 1 0
Hijo 1: 1 0 1 0 1 1 1 1 0 1 1
Hijo 2: 0 1 1 0 0 0 1 1 0 1 0
• Mutación: Previamente definida una probabilidad de mutación, a cada
individuo le es cambiado uno o varios genes de manera aleatoria. Dado que
de un solo padre se genera un nuevo hijo, esta operación es llamada
monódica. Este operador permite una mayor exploración y evitar la caída
en óptimos locales. Cabe anotar que una probabilidad de mutación muy alta
puede generar demasiada aleatoriedad dentro del algoritmo dificultando así
el hallazgo de una buena solución.
2.2.3 Aplicación de AG para distribución en planta [2] [14]
Por medio de algoritmos genéticos es posible conseguir buenas distribuciones a
partir de una búsqueda guiada sobre una pequeña fracción del espacio de
soluciones, aunque tienen el problema de la dificultad en codificar los individuos o
soluciones factibles y de diseñar las estrategias de búsqueda, en las que es
fundamental la asignación de los parámetros específicos del problema, como por
ejemplo las probabilidades de cruzamiento, mutación o reproducción y el tamaño
de la población, aunque el problema más grave es el de la gestión de las
restricciones del problema (Michalewicz, 1994). Islier (1998), presenta un
algoritmo genético en el que se divide los centros de actividad en un número de
celdas de superficie unitaria y se valoran la forma tomada por cada actividad y por
el conjunto, así como los costes de transporte en el proceso productivo,
53
obteniendo resultados aceptables. [15]. A continuación se presentan
consideraciones generales del modelo propuesto por Islier, las cuales no se
tratarán con profundidad dado que este modelo no aplica para el problema tratado
en este proyecto.
Según Islier, el primer criterio de optimización para el problema de configuración
de planta para una fábrica de manufactura es minimizar la carga de transporte, el
segundo es maximizar el grado de compactación de las áreas de las estaciones
de trabajo o departamentos y el tercero es minimizar la diferencia entre las áreas
demandadas y las disponibles para cada estación de trabajo o departamento2, a
continuación se presenta una descripción de cada uno de ellos:
1. Minimizar la carga de transporte: [1]
La carga de transporte se puede calcular utilizando la información de flujo,
unidades de carga y las distancias rectilíneas entre los centroides de las
estaciones de trabajo. Por este motivo los datos de entrada para lograr
minimizar la carga de transporte son:
• Matriz de flujo
• Matriz de distancias
• Matriz de costos unitarios
El flujo representa el número de unidades de carga que son transportadas de
un sitio de trabajo a otro en un periodo de tiempo, los costos unitarios
representan los costos de mover una unidad de carga por unidad de longitud
de un departamento a otro; a su vez, las distancias en una planta de
manufactura representan la separación de los centroides de un departamento a
otro.
2 ISLIER A.A. “A genetic algorithm approach for multiple criteria facil ity layout design”, International Journal of Production Research, Vol.36, No.6, 1998, 1549-1569.
54
2. Maximizar el grado de compactación de las áreas de las estaciones de
trabajo [1]:
Consiste básicamente en encontrar la forma más adecuada para diseñar las
formas que tendrán las diferentes estaciones de trabajo de una compañía. Esto
con el fin de evitar pérdidas de espacio y diseños que generen incomodidad para
realizar el trabajo.
3. Minimizar la diferencia entre las áreas demandadas y disponibles [1]:
Se busca que por medio de la aclaración de cuáles son las áreas mínimas,
máximas y deseadas de cada departamento, se logre minimizar la desviación del
área de cada estación de trabajo con respecto a lo deseado.
55
3. ALGORITMO GENÉTICO PARA EL PROBLEMA DE CONFIGURACIÓN DE PLANTA
Para dar solución al problema descrito se usó la metaheurística de Algoritmos
Genéticos, la cual se programó en Visual Basic para Excel. En este capítulo se
describirá el proceso llevado a cabo para la elaboración del algoritmo, la
herramienta que se desarrolló para solucionar una variación del problema y los
resultados obtenidos.
3.1 RECOLECCIÓN DE DATOS
3.1.1 Medición de las dimensiones de las oficinas y los departamentos
A lo largo de este trabajo se le llamará departamentos a los diversos elementos
que integran el proceso productivo de la oficina bancaria.
Las medidas de la oficina y de los departamentos correspondientes a cada
sucursal estudiada fueron obtenidas a partir de los planos suministrados por la
entidad bancaria. A partir de estos, se realizaron las mediciones correspondientes
al ancho y largo de las oficinas y departamentos, conservando la escala de cada
plano. Las escalas utilizadas se relacionarán a continuación:
56
Oficina Escala
1 1:100
2 1:100
3 1:125
4 1:150
5 1:50
Tabla 2: Escala de los planos de cada oficina
Se consideraron los departamentos principales en cada oficina; es decir, aquellos
que participan en la finalidad productiva del banco. Se asumieron algunas medidas
de departamentos pequeños que no se especificaban en el plano, como el
tarjetero. Y se hicieron algunas generalidades sobre la forma de la oficina cuando
esta no era totalmente rectangular, como en el caso de la oficina 4.
3.1.2 Medición de flujos
A partir de entrevistas realizadas a los gerentes comerciales y operativos de la red
bancaria se obtuvieron encuestas en las cuales se calificó la importancia relativa
de la cercanía entre los departamentos de las oficinas. Las cuales tienen el
siguiente formato:
Depto. 1Depto. 2Depto. 3
…
Depto. N-1Depto. N
Depto. 1 Depto. 2 Depto. 3 … Depto. N-1 Depto. N
Figura 12: Formato de la matriz de calificación.
57
Este formato es una variación del diagrama de relación de actividades propuesto
por Muther. Las casillas en blanco se llenan con la calificación que los gerentes
consideren pertinente entre 0 y 5 bajo las siguientes convenciones:
5 = Completamente necesario que estén situados muy cerca
4 = Es especialmente importante que estén situados cerca una de la otra
3 = Es importante que estén situados cerca una de la otra
2 = No es muy importante que estén situados cerca una de la otra
1 = No es importante que estén situados cerca una de la otra
0 = Es indeseable que estén situados cerca una de la otra
Esta matriz de calificación, que desde ahora llamaremos matriz de percepción, es
análoga a la medición del flujo; ya que así, como entre mayor es el flujo entre dos
departamentos mayor es la deseabilidad de cercanía entre ellos, entre mayor sea
la importancia (o deseabilidad) de que estén situados cerca, mayor será la
calificación en la matriz de percepción.
Dado que la encuesta fue realizada a dos gerentes (comercial y operativo) por
oficina, se necesitaba concordar la información de estas dos matrices, por lo que
se hizo un promedio entre ellas, y cuando la diferencia entre los dos valores era
superior a 3 un experto definió la calificación.
3.2 DESCRIPCIÓN DEL MODELO
El modelo propuesto por Islier no se aplica al problema que se está tratando en
este proyecto, dado que si bien se quiere minimizar la carga de trabajo, no se
posee una matriz unitaria de costos; por otra parte, se tiene un área fija para cada
departamento, ya que las dimensiones de los mismos son establecidas desde el
principio del proceso del diseño de la configuración, a diferencia del modelo de
Islier donde se establecen áreas mínimas y máximas deseadas de cada
departamento. Por lo que se propone el siguiente modelo:
58
Dada la naturaleza del problema la Función Objetivo es:
( ) ( )[ ]∑∑=i j
jZiZdjifFO )(),(*,
[ ]Nji ,1, ∈
Sujeto a:
No se traslapen (sobrepongan) los departamentos entre sí.
Donde:
N es el número de departamentos.
( )jif , Representa el flujo entre el departamento i y el departamento j.
( ))(),( jZiZd Representa la distancia entre los centroides de los rectángulos (o
las posiciones) donde quedaron ubicados el departamento i y el departamento j
de acuerdo a la asignación definida por el cromosoma.
Dicha distancia es medida usando la métrica rectilínea así:
jijiij yyxxd −+−=
[ ]Nji ,1, ∈
Donde:
ijd Es la distancia entre los departamentos i y j
ix Es la coordenada horizontal del centroide del departamento i.
iy Es la coordenada vertical del centroide del departamento i.
jx Es la coordenada horizontal del centroide del departamento j.
jy Es la coordenada vertical del centroide del departamento j.
59
3.3 REPRESENTACIÓN DE LA SOLUCIÓN
La solución al problema planteado será representada por el siguiente cromosoma
Z:
Z(1) Z(2) Z(3) Z(4) Z(5) Z(6) Z(7) Z(8) Z(9) Z(10) … Z(N-3) Z(N-2) Z(N-1) Z(N)
Costado Occidente Costado Norte Costado Oriente Costado Sur Parte trasera
( ) .iordenelenasignadotoDepartameniZ =
[ ]Ni ,1∈
.tosdepartamendeNúmeroN =
El cromosoma está dividido en cinco partes, las primeras cuatro representan los
costados de la oficina (Oriente, Norte, Occidente y Sur), la quinta representa los
departamentos a los que el cliente no tiene acceso directo y se encuentran en la
parte trasera de la oficina. Cada una de las primeras cuatro partes del cromosoma
contiene los números de los departamentos en el orden en que son ubicados; se
está realizando un llenado en el orden del movimiento de las manecillas del reloj.
La quinta parte contiene los números de los departamentos ubicados en la parte
trasera de la oficina, en forma de “columnas”, que van de izquierda a derecha y
son llenadas de arriba hacia abajo. Para mayor ilustración, a continuación se
muestra un ejemplo:
60
El siguiente cromosoma:
1 3 2 13 14 9 12 15 16 11 6 4 5 8 7 10 18 17
Representa la distribución:
Atrás
Oriente
Cos
tado
Occ
iden
te
Costado Norte
Costado Sur
1
3
2
13
14 912 15 16
11
6
4587
10 17
18
Figura 13: Distribución de planta correspondiente a la representación de la solución propuesta.
Dada la forma de representación de la solución, cada departamento solo es
asignado en el ordenamiento de la planta una sola vez; adicional a esto, a lo largo
del algoritmo se garantiza que los individuos de la población no violan la
restricción de sobre-posición de los departamentos, ya que a partir del
cromosoma que se tiene, se hallan las nuevas coordenadas de los departamentos,
y posteriormente con esta información se realiza la nueva distribución.
61
3.4 REALIZACIÓN DEL ALGORITMO
El AG realizado para diseñar la distribución de planta de las oficinas bancarias,
parte de la configuración actual de éstas. Además, se tienen en cuenta los
departamentos que no deben ser cambiados de posición, como la puerta principal
de la sucursal y el cajero automático. También se conservan las dimensiones de
los departamentos que se encuentran en la configuración actual.
3.4.1 Parámetros de Entrada
Los parámetros que recibe referentes a la oficina, son:
• Número de Objetos que deben ir fijos
• Número de objetos no fijos
• Dimensión de la oficina en el sentido de la coordenada Y
• Dimensión de la oficina en el sentido de la coordenada X
• Matriz de flujos entre departamentos
• Para cada departamento recibe:
o Nombre
o Coordenada en X de la esquina superior izquierda
o Coordenada en Y de la esquina superior izquierda
o Dimensión del departamento en el sentido de la coordenada Y
o Dimensión del departamento en el sentido de la coordenada X
o 1 Si el departamento debe ir fijo y 0 de lo contrario
o Costado de la Oficina en el que debe ir ubicado (Oriente, Norte,
Occidente, Sur o Parte trasera)
Los parámetros que recibe para la ejecución del algoritmo genético son:
• Número de iteraciones
62
• Tamaño de la población
• Probabilidad de Mutación
• Porcentaje de mejores
• Porcentaje de generados por mejores
3.4.2 Estructura
El programa está construido de la siguiente manera:
1. Se genera una población inicial de tamaño n, es decir; se generan n
cromosomas de manera aleatoria, donde n es el tamaño de la población.
Para realizar las corridas del algoritmo se usó un tamaño de población de
100.
2. Evalúa el costo total de cada individuo, penalizando a aquellos que violan
una restricción.
3. Organiza los individuos de menor a mayor costo. Guarda el mejor costo
encontrado en cada iteración y su correspondiente cromosoma, el cual
pasará inmediatamente a la siguiente generación.
4. Encuentra el grupo de mejores que tienen menores costos (élite). El primer
individuo que corresponde a la élite es aquel que pertenece a la anterior
generación y tiene el menor costo asociado.
5. Se escogen dos cromosomas aleatoriamente dentro del grupo de mejores
cromosomas y se cruzan a través de la estrategia que se explica
detenidamente mas adelante, hasta completar el tamaño de la población
que corresponda al porcentaje de generados por mejores.
6. El resto de la población requerida para completar el tamaño de la población
para cada generación se genera a través de la escogencia aleatoria de dos
individuos dentro de la población de padres (incluyendo a la élite) y
cruzarlos con la estrategia escogida anteriormente.
7. Se realiza la mutación a la población como se explica mas adelante.
63
8. Para la nueva población generada se realiza lo enunciado en el punto 2 y
desde allí se repite el algoritmo el número de veces correspondiente al
número de generaciones que se desean.
Al finalizar el número de iteraciones, el programa arroja de manera gráfica la mejor
solución encontrada a lo largo de todas las generaciones, basado en las
coordenadas que se hallaron para la misma, junto con una tabla de convenciones
para identificar los departamentos que se encuentran en el diagrama y la función
objetivo correspondiente a la distribución.
3.4.3 Población Inicial
Como solución inicial para cada oficina, se tomó el cromosoma que representaba
la distribución actual. A cada una de las partes de este cromosoma se le realiza un
número aleatorio de intercambios entre departamentos, siempre y cuando estos
no hayan sido asignados previamente como fijos por parte del usuario. A partir de
este proceso se genera un nuevo cromosoma, que junto con otros generados de
la misma forma conforman la población inicial. De esta manera se generan
cromosomas factibles como población inicial, ya que no se repite ningún
departamento y los elementos fijos de la oficina no son cambiados de lugar.
3.4.4 Función Objetivo y su evaluación
La función objetivo del problema, tal y como es mostrada en el modelo, consiste
en la suma de la multiplicación del flujo entre departamentos por la distancia
rectilínea entre los centroides de estos.
Tal como se mencionó anteriormente, el flujo para este trabajo, es reemplazado
por la deseabilidad de cercanía entre departamentos, medida por medio de una
matriz de percepción que era llenada por los gerentes operativo y comercial de la
entidad financiera y posteriormente se realizaba una conciliación entre sus
64
diferentes percepciones que se plasmaba en una matriz final que fue la utilizada
para este proyecto. Esta matriz entra como parámetro al algoritmo.
La distancia rectilínea entre los centroides de los departamentos es hallada de la
siguiente manera:
• Se hallan las coordenadas para la esquina superior izquierda de cada
departamento.
• A partir de estas coordenadas y las dimensiones de cada departamento se
hallan sus centroides.
• Se halla la distancia entre cada par de departamentos sumando la
separación de sus centroides en las coordenadas X y Y, como se muestra a
continuación:
ΔY
ΔX
dep. i
dep. j
Figura 14: Medición de distancia por métrica rectilínea.
La distancia entre el departamento i y el departamento j será: ΔX + ΔY
Una vez se tienen los datos necesarios para evaluar la función objetivo se hacen
los cálculos correspondientes.
65
3.4.5 Estrategia de selección
Como estrategia de selección uso el elitismo, de manera que una vez generada la
población, se evalúa el costo de cada individuo. Se toma el porcentaje de mejores
(Este es un parámetro variable para el diseño de experimentos) y evalúa la
cantidad de individuos de la población que representa un menor costo, este grupo
de cromosomas es llamado la élite.
A partir de esto se genera la siguiente población escogiendo dos cromosomas
aleatoriamente dentro de la élite, que se cruzan de manera uniforme, generando
hijos, esto se hace hasta completar el tamaño de la población que corresponda al
porcentaje de generados por mejores (El cual es un parámetro variable para el
diseño de experimentos). El resto de la población requerida para completar el
tamaño de la población para cada generación se genera a través de escoger
aleatoriamente dos individuos dentro de la población de padres (incluyendo a la
élite) y cruzarlos con la estrategia escogida anteriormente. El mejor individuo, en
términos de costo, de una generación pasa intacto a la siguiente.
3.4.6 Estrategia de cruce
La estrategia de cruce utilizada es uniforme donde se obtiene un “vector patrón” el
cual es un vector de unos y ceros generado de manera aleatoria. A partir de allí
se multiplican los dígitos del “vector patrón” por los dígitos del primer papá y los
dígitos del segundo papá son multiplicados por los dígitos del vector resultado de
la resta entre un vector de unos y el “vector patrón”. A partir de esto se obtiene el
primer hijo, para obtener el segundo hijo, se multiplica el primer padre por el
vector resultado de la resta entre un vector de unos y el “vector patrón”, y el
segundo padre se multiplica por el “vector patrón”.
Ejemplo para la primera parte del cromosoma:
66
Patrón:
Vector “opuesto”: Es el vector resultado de restar al valor del arreglo “patrón” el
número 1:
Padre 1:
Padre 2:
Padre 1 por Vector Patrón:
Padre 2 por Vector opuesto:
Padre 1 por Vector opuesto:
Padre 2 por Vector Patrón:
Hijo 1:
Hijo 2:
0 0 1 0 1
1 1 0 1 0
1 3 2 13 14
13 1 14 3 2
0 0 2 0 14
13 1 0 3 0
1 3 0 13 0
0 0 14 0 2
13 1 2 3 14
1 3 14 13 2
67
Se escogió esta estrategia ya que así los departamentos de cada costado se
conservarán en ese lado después del cruce, de esta manera se evita la
reorganización del cromosoma una vez aplicado este operador.
3.4.7 Estrategia de mutación
Para cada cromosoma se genera un número aleatorio que es comparado con la
tasa de mutación (La cual es el tercer parámetro variable para el diseño de
experimentos), si el número aleatorio generado es menor que la tasa de mutación
entonces este individuo es mutado, de lo contrario no. El operador de mutación
funciona de la siguiente manera: Se obtienen dos números aleatorios entre 1 y el
número de departamentos que pertenecen a la parte del cromosoma que se está
mutando, e intercambia las posiciones en esa parte del cromosoma
correspondientes a estos números. La mutación se hace para cada una de las
cinco partes del cromosoma y solo se intercambian departamentos si estos no han
sido asignados como fijos dentro de la configuración previamente por el usuario;
así se garantiza que los cromosomas siguen siendo factibles después de la
mutación, por lo que a este operador no es necesario realizarle reparación.
Ejemplo:
Para una parte del cromosoma que debe ser mutada:
No. Aleatorio 1: 2
No. Aleatorio 2: 5
Significa que intercambiamos el contenido de la posición 2 con el de la posición 5,
se verifica si los departamentos de estas dos posiciones deben estar fijos, si la
respuesta es negativa se obtiene como resultado:
2 3 4 5 1
2 1 4 5 3
68
3.4.8 Estrategias de reparación
Como se explicó anteriormente el operador de mutación no necesita ser reparado.
Después de realizar el cruce entre dos cromosomas, se verifica que los hijos
generados sean factibles, de manera que ningún departamento esté ausente
dentro del cromosoma, si el cromosoma necesita reparación en alguna de sus
partes, se reemplaza el primer repetido por el primer ausente entre los
departamentos que pertenezcan a esa parte. A continuación se muestra un
ejemplo:
Cromosoma que debe ser reparado:
1 3 2 13 14 9 12 12 16 11 6 4 5 8 7 10
Cromosoma reparado:
1 3 2 13 14 9 15 12 16 11 6 4 5 8 7 10
3.4.9 Obtención de la configuración
Una vez se obtiene la población para cada generación, se evalúa la Función
Objetivo para cada uno de los cromosomas, para ello es necesario hallar las
coordenadas de cada departamento de acuerdo al ordenamiento que cada uno de
los cromosomas representa. Se encuentran nuevas coordenadas para todos los
departamentos del cromosoma. Los departamentos asignados como fijos,
conservan su posición dentro del vector y aunque sus coordenadas pueden variar
de acuerdo a la nueva asignación, conservan una posición fija relativa dentro de la
configuración.
El origen para las mediciones, se encuentra en la esquina superior izquierda del
plano de la oficina. La siguiente figura ayudará como ilustración para la
terminología que se usará mas adelante.
69
Figura 15: Ilustración para la terminología usada en el Algoritmo
La forma en como se hallan las coordenadas para cada uno de los costados de la
oficina es la siguiente:
• Costado Occidente
El llenado se realiza de abajo hacia arriba, por lo que la coordenada que varía
es la que está en el sentido del eje Y. Para cada departamento i perteneciente
a este costado:
o La coordenada en X es igual a cero
o La coordenada en Y es igual al alto total de la oficina, menos la suma
del alto de los departamentos que han sido asignados hasta i
(exclusive).
• Costado Norte
El llenado se realiza de izquierda a derecha, por lo que la coordenada que
varía es la que está en el sentido del eje X. El llenado en X empieza desde el
mayor ancho de los departamentos pertenecientes al costado occidente. Para
cada departamento i perteneciente a este costado:
70
o La coordenada en X es igual al mayor ancho de los departamentos del
costado occidente más la suma del ancho de los departamentos que han
sido asignados hasta i (exclusive).
o La coordenada en Y es igual al mayor alto de los departamentos de este
costado menos el alto del departamento i.
• Costado Oriente
El llenado se realiza de arriba hacia abajo, por lo que la coordenada que varía
es la que está en el sentido del eje Y. El llenado en Y empieza desde el punto
A, el cual equivale al mayor alto de los departamentos pertenecientes al
costado norte. Para cada departamento i perteneciente a este costado:
o La coordenada X es obtenida restando al ancho de la oficina, el ancho total
de la parte trasera y el ancho del departamento i; el ancho de la parte
trasera, es obtenido por medio de la suma de los anchos de la columnas
que la componen, estos anchos se obtienen basándose en el ordenamiento
que dicta el cromosoma.
o La coordenada en Y es igual al punto desde donde se empieza el llenado
mas la suma del alto de los departamentos que han sido asignados hasta i (exclusive).
• Costado Sur
El llenado se realiza de derecha a izquierda, por lo que la coordenada que
varía es la que está en el sentido del eje X. El llenado en X empieza desde el
punto donde inicia el llenado para el costado oriente. Para cada departamento i perteneciente a este costado:
o La coordenada en X es igual al punto donde inicia el llenado menos la suma
del ancho de los departamentos que han sido asignados hasta i (exclusive).
o La coordenada en Y es igual al alto de la oficina menos el mayor alto de los
departamentos de este costado.
• Parte trasera
71
El llenado se realiza en forma de columnas que van de izquierda a derecha, y
son llenadas de arriba hacia abajo. El llenado en X empieza desde el punto
obtenido restando al ancho de la oficina, el ancho total de la parte trasera. El
llenado en Y empieza en cero. Para cada departamento i perteneciente a este
costado:
o La coordenada en X es igual al punto donde inicia el llenado más la suma
del ancho de las columnas anteriores a la columna donde es asignado el
departamento i.
o La coordenada en Y es igual al punto desde donde se empieza el llenado
mas la suma del alto de los departamentos que han sido asignados hasta i
(exclusive).
Lo anterior se expone en el siguiente seudo código, donde EnX es una variable
que guarda la posición en la coordenada X y EnY realiza la misma función para la
coordenada Y. EnXahora es una variable que guarda la posición en la coordenada
X para la parte trasera.
72
Figura 16: Seudo código para hallar coordenadas
Algoritmo Hallar coordenadas; EnY = alto de la oficina EnX = 0 For all departamentos ∈ Costado Occidente do coordenada X = 0 coordenada Y = EnY - alto del departamento EnY = coordenada Y Next EnY = mayor alto de los departamentos del Costado Norte EnX = mayor ancho de los departamentos del Costado Occidente For all departamentos ∈ Costado Norte do coordenada X = EnX coordenada Y = EnY - alto del departamento EnX = EnX + ancho del departamento Next a = mayor ancho de los departamentos del Costado Oriente b = ancho de la oficina - ancho de la parte trasera de la oficina EnX = b - a EnY = mayor alto de los departamentos del Costado Norte For all departamentos ∈ Costado Oriente do coordenada X = EnX coordenada Y = EnY EnY = EnY + alto del departamento Next EnY = alto de la oficina - mayor alto de los departamentos del Costado Sur For all departamentos ∈ Costado Sur do EnX = EnX - ancho del departamento coordenada X = EnX coordenada Y = EnY Next EnX = b EnY = 0 EnXahora = 0 For all departamentos ∈ Atrás do
If (EnY + alto del departamento) > alto de la oficina then EnY = 0 EnX = EnX + EnXahora EnXahora = 0 End If coordenada X = EnX coordenada Y = EnY EnY = EnY + alto del departamento If ancho del departamento > EnXahora then EnXahora = ancho del departamento End If Next End;
73
3.5 AG PARA LA CONFIGURACIÓN DE PLANTA DE UNA OFICINA VIRGEN
Para establecer la distribución de la planta de una oficina desde cero, se propuso
una metaheurística basada en AG similar a la anterior.
La construcción, los operadores y la forma en como es arrojada la solución para
este algoritmo son iguales a los explicados en el algoritmo anterior, excepto en la
generación de la población inicial, la cual se explicita más adelante.
La explicación detallada sobre el manejo de la herramienta se encuentra en el
Anexo 1: Manual del Usuario.
3.5.1 Parámetros del modelo
Los parámetros del modelo son:
• De la oficina:
o Nombre de la oficina
o Costado en el que va la entrada
o Dimensiones de Frente y Fondo
o Número de departamentos
• De los departamentos:
o Nombre
o Dimensiones de frente y fondo
o Ubicación relativa a la entrada
• De los flujos:
o Deseabilidad de proximidad entre cada pareja de departamentos
74
• Del Algoritmo genético: Si el usuario no desea usar los parámetros
recomendados para el algoritmo genético debe ingresar:
o Número de iteraciones
o Tamaño de la población
o Probabilidad de Mutación
o Porcentaje de mejores
o Porcentaje de generados por mejores
3.5.2 Población Inicial
Debido a que este algoritmo no parte de una configuración actual, no se tiene una
solución inicial para el problema, de manera que se generó aleatoriamente,
teniendo en cuenta los costados a los que pertenece cada departamento, según la
información ingresada previamente por el usuario.
3.6 DISEÑO DE EXPERIMENTOS [17]
Con el objetivo de establecer la mejor combinación de parámetros de entrada para
el algoritmo, se desea realizar un diseño factorial 33. Donde los factores son:
• Probabilidad de Mutación
• Porcentaje de mejores
• Porcentaje de generados por mejores
El número de iteraciones para la corrida del programa se escogió por medio de
gráficos que muestran la convergencia del algoritmo como el que se muestra en la
Figura 17, se tomó un valor grande en relación al valor promedio de convergencia
en búsqueda de mejores soluciones.
75
Co m po rtam iento d el a lg or tim o - O fic ina 1
4 40 0,0 0
4 42 0,0 0
4 44 0,0 0
4 46 0,0 0
4 48 0,0 0
4 50 0,0 0
4 52 0,0 0
4 54 0,0 0
4 56 0,0 0
4 58 0,0 0
0 5 0 1 0 0 1 50 2 00 2 50
Nú m ero d e i te ra cio n es
Val
or d
e F
.O.
Figura 17: Ejemplo de convergencia del algoritmo
Los niveles correspondientes a los factores son:
• Probabilidad de Mutación: 0.01, 0.05 y 0.1.
• Porcentaje de mejores: 0.2, 0.45 y 0.7.
• Porcentaje de generados por mejores: 0.3, 0.6 y 0.8.
Los valores escogidos fueron acordados junto con el asesor de tesis y son
producto de experiencias anteriores con el uso de los algoritmos genéticos.
Tal como enuncia Montgomery (1991), el uso de la partición para probar
formalmente – dentro del diseño de experimentos – que no hay diferencias en las
medias de los tratamientos requiere que se satisfagan ciertos supuestos.
Específicamente estos supuestos son que el modelo describe de manera
adecuada las observaciones, y que los errores siguen una distribución normal e
76
independiente con media cero y varianza σ2 constante pero desconocida. No es
prudente confiar en el análisis de varianza hasta haber verificado estos supuestos
[17].
A partir de lo anterior se realizó la corrida del programa para las cinco instancias
estudiadas y todas las variaciones de parámetros propuestas. De los resultados
obtenidos, Ver Anexo 2., era claro que para cualquier combinación de parámetros
se obtenía el mismo valor para la F.O., lo cual nos deja ver que no hay cambios
que puedan observarse en la respuesta de salida; de esta manera, identificar las
razones que los produce, lo cual es el motivo para la realización del diseño de
experimentos, pierde sentido.
Se decidió hacer el análisis del efecto de las combinaciones de parámetros
gráficamente, para lo cual se diagramó el valor de la media, el mínimo y el máximo
encontrado a lo largo de 30 experimentos, contra las combinaciones de
parámetros (Ver tabla 3), para cada oficina.
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Combinación de parámetros 1 2 3 4 5 6 7 8 9
PM 1 = 0,01PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Combinación de parámetros 10 11 12 13 14 15 16 17 18
PM 2 = 0,05PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Combinación de parámetros 19 20 21 22 23 24 25 26 27
PGE 2 = 0,6 PGE 3 = 0,8PM 3 = 0,1
PGE 1 = 0,3
Tabla 3: Convenciones para las combinaciones de parámetros.
Adicional a esto, se quiere realizar una comparación del comportamiento del
algoritmo para dos números de iteraciones diferentes para cada instancia.
77
3.6.1 Oficina 1
La siguiente gráfica muestra el valor de la función objetivo para la oficina 1, frente
a todas las combinaciones de parámetros, para 200 iteraciones.
Co m p o rtam ien to d el Alg o ritm o fren te a la V ariaci ón de p arám et ro s: O f . 1, 20 0 iter.
44 00 ,00 0
44 50 ,00 0
45 00 ,00 0
45 50 ,00 0
46 00 ,00 0
46 50 ,00 0
47 00 ,00 0
0 3 6 9 12 1 5 1 8 21 2 4 2 7 30
Va r iac ión de par ám e tros
Va
lor
de
F.O
.
Me di aMín im oMá xi mo
Figura 18: Relación entre FO, Combinación de parámetros y 200 iteraciones
para la instancia 1.
De la anterior gráfica para 200 iteraciones, puede verse que para las primeras
combinaciones de parámetros se presentan variaciones importantes para el mayor
valor encontrado de la Función Objetivo a lo largo de todos los experimentos, por
lo que para una probabilidad de mutación de 0.01 (la más pequeña que se
consideró) y los demás niveles de porcentaje de mejores y porcentaje de
generados por mejores, existe la posibilidad de caer en óptimos locales. Por otra
parte, puede verse que en las 27 combinaciones se encontró el mismo mínimo, de
lo que se puede afirmar que representa un óptimo, pero sin certeza de que este
sea global. Por último se nota una estabilidad dentro del comportamiento de la
78
media frente a las variaciones. A continuación, se presenta el valor de la función
objetivo para la oficina 1, frente a todas las combinaciones de parámetros, para
1000 iteraciones.
Co m p o rtam ie nto d el Alg o ritm o fren te a la V ariaci ón de p arám et ro s : O f. 1, 1 000 i ter.
44 00 ,00 0
44 50 ,00 0
45 00 ,00 0
45 50 ,00 0
46 00 ,00 0
46 50 ,00 0
47 00 ,00 0
0 3 6 9 12 1 5 1 8 21 2 4 2 7 30
Va r iac ión de par ám e tros
Va
lor
de
F.O
.
Me di aMín im oMá xi mo
Figura 19: Relación entre FO, Combinación de parámetros y 1000
iteraciones para la instancia 1 La anterior gráfica, muestra claramente que para todas las combinaciones de
parámetros se encuentra el mismo valor máximo, mínimo y media a lo largo de
todos los experimentos, para 1000 iteraciones. El valor mínimo obtenido es igual al
correspondiente a 200 iteraciones. Por lo que se concluye que para un número
grande de iteraciones, el algoritmo siempre encontrará el mínimo conocido, para
cualquier combinación de parámetros.
De acuerdo a lo observado para esta instancia puede afirmarse que el algoritmo
es robusto, ya que a pesar de las variaciones en el número de iteraciones, tanto la
media como el valor mínimo obtenido presentan gran estabilidad frente a las
79
variaciones de los parámetros. Unido a esto, el valor máximo que se obtenga para
un número grande de experimentos puede variar de acuerdo al número de
iteraciones, por lo que se debe tener en cuenta que de la combinación de
parámetros de 10 en adelante resulta más conveniente para la corrida del
algoritmo.
3.6.2 Oficina 2
La figura 20 muestra el valor de la función objetivo para la oficina 2, frente a todas
las combinaciones de parámetros, para 50 iteraciones.
C om p o rta mi en to d el Al go ritm o fre nte a la Variac ió n d e p arám et ro s: O f. 2, 50 iter.
0,0 00
10 0,0 00
20 0,0 00
30 0,0 00
40 0,0 00
50 0,0 00
60 0,0 00
70 0,0 00
0 3 6 9 12 15 1 8 21 24 27 30
V ar iac ión de par á me tr os
Va
lor
de
F.O
.
Me di aMín im oMá xi mo
Figura 20: Relación entre FO, Combinación de parámetros y 50 iteraciones
para la instancia 2 En la anterior gráfica puede verse que para todas las combinaciones de
parámetros se encuentra el mismo valor máximo, mínimo y media a lo largo de
todos los experimentos, para 50 iteraciones. Por lo que se concluye que para un
80
número relativamente pequeño de iteraciones, el algoritmo siempre encontrará el
mínimo conocido, para cualquier combinación de parámetros. Puede verse que en
las 27 combinaciones de parámetros se encontró el mismo mínimo, de lo que se
puede afirmar que representa un óptimo, pero sin certeza de que este sea global.
A continuación, se presenta el valor de la función objetivo para la oficina 2, frente a
todas las combinaciones de parámetros, para 1000 iteraciones.
Co m p o rtam ie nto d el Alg o ritm o fren te a la V ariaci ón de p arám et ro s : O f. 2, 1 000 i ter.
0,0 00
10 0,0 00
20 0,0 00
30 0,0 00
40 0,0 00
50 0,0 00
60 0,0 00
70 0,0 00
0 3 6 9 12 15 1 8 21 24 27 30
V ar iac ión de par á me tr os
Va
lor
de
F.O
.
Me di aMín im oMá xi mo
Figura 21: Relación entre FO, Combinación de parámetros y 1000
iteraciones para la instancia 2 En igual forma que para la figura 20, se observa que para todas las combinaciones
de parámetros se encuentra el mismo valor máximo, mínimo y media a lo largo de
todos los experimentos, para 1000 iteraciones. El valor mínimo obtenido es igual al
correspondiente a 50 iteraciones. De manera que no se requiere de un número
alto de iteraciones para que el algoritmo encuentre el mínimo conocido, para
cualquier combinación de parámetros. Un factor que influye en este hecho es el
tamaño de este problema: 8 departamentos.
81
Como pudo verse para esta instancia el algoritmo conserva su robustez, ya que la
media, el valor mínimo y el valor máximo se conservan a lo largo de todas todos
los experimentos, a pesar de las variaciones en el número de iteraciones y
parámetros. Cualquier combinación de parámetros resulta conveniente para este
caso.
3.6.3 Oficina 3
A continuación, se presenta el valor de la función objetivo para la oficina 3, frente a
todas las combinaciones de parámetros, para 50 iteraciones.
C om p o rta mi en to d el Al go ritm o fre nte a la Variac ió n d e p arám et ro s: O f. 3, 50 iter.
42 00 ,00 0
42 10 ,00 0
42 20 ,00 0
42 30 ,00 0
42 40 ,00 0
42 50 ,00 0
42 60 ,00 0
42 70 ,00 0
42 80 ,00 0
0 3 6 9 12 1 5 1 8 21 2 4 2 7 30
Va r iac ión de par ám e tros
Va
lor
de
F.O
.
Me di aMín im oMá xi mo
Figura 22: Relación entre FO, Combinación de parámetros y 50 iteraciones
para la instancia 3.
Para este caso puede verse que se presentan variaciones para el valor máximo
obtenido a lo largo de los experimentos para diferentes combinaciones de
parámetros, en especial para las 9 primeras. En particular, para las primeras 4 se
obtiene el mismo valor, por lo que se puede pensar que éstas no son
recomendables para la corrida del algoritmo ya que posiblemente se puede
82
obtener como resultado un óptimo local. A pesar de esto, el mínimo que se
encuentra para todas las combinaciones es el mismo, y la media muestra un
comportamiento estable. Resultaría conveniente realizar la corrida del algoritmo
para esta instancia para un número mayor de iteraciones. Lo cual se muestra a
continuación:
Co m p o rtam ie nto d el Alg o ritm o fren te a la V ariaci ón de p arám et ro s : O f. 3, 1 000 i ter.
42 00 ,00 0
42 10 ,00 0
42 20 ,00 0
42 30 ,00 0
42 40 ,00 0
42 50 ,00 0
42 60 ,00 0
42 70 ,00 0
42 80 ,00 0
0 3 6 9 12 1 5 1 8 21 2 4 2 7 30
Va r iac ión de par ám e tros
Va
lor
de
F.O
.
Me di aMín im oMá xi mo
Figura 23: Relación entre FO, Combinación de parámetros y 1000
iteraciones para la instancia 3.
La figura 23, a diferencia de la anterior, muestra claramente que para todas las
combinaciones de parámetros se encuentra el mismo valor máximo, mínimo y
media a lo largo de todos los experimentos, para 1000 iteraciones. El valor mínimo
obtenido es igual al correspondiente a 50 iteraciones. El cual, al igual que en las
anteriores ocasiones, no se puede afirmar que es un óptimo global.
De acuerdo a lo anterior, puede afirmarse que para esta instancia resulta
recomendable correr el algoritmo para un número grande de iteraciones, de esta
manera se garantizará la obtención de la mejor solución conocida. A pesar de los
83
diferentes números de iteraciones, la media presenta estabilidad frente a las
variaciones de los parámetros y el mínimo encontrado se conserva.
3.6.4 Oficina 4
La siguiente gráfica muestra el valor de la función objetivo para la oficina 4, frente
a todas las combinaciones de parámetros, para 25 iteraciones.
C om p o rta mi en to d el Al go ritm o fre nte a la Variac ió n d e p arám et ro s: O f. 4, 25 iter.
36 98 ,00 0
37 00 ,00 0
37 02 ,00 0
37 04 ,00 0
37 06 ,00 0
37 08 ,00 0
37 10 ,00 0
37 12 ,00 0
37 14 ,00 0
37 16 ,00 0
37 18 ,00 0
37 20 ,00 0
0 3 6 9 12 1 5 1 8 21 2 4 2 7 30
Va r iac ión de par ám e tros
Va
lor
de
F.O
.
Me di aMín im oMá xi mo
Figura 24: Relación entre FO, Combinación de parámetros y 25 iteraciones
para la instancia 4.
De la anterior gráfica para 25 iteraciones, puede verse que para las primeras
combinaciones de parámetros se presentan variaciones de cerca de 20 unidades,
para el mayor valor encontrado de la Función Objetivo a lo largo de todos los
experimentos, por lo que para una probabilidad de mutación muy pequeña y los
demás niveles de porcentaje de mejores y porcentaje de generados por mejores,
existe la posibilidad de caer en óptimos locales. Por otra parte, puede verse que
en las 27 combinaciones se encontró el mismo mínimo, de lo que se puede afirmar
84
que representa un óptimo, pero sin certeza de que este sea global. Se recomienda
usar combinaciones de parámetros donde la probabilidad de mutación sea mayor
o igual a 0.05.
A continuación, se presenta el valor de la función objetivo para la oficina 4, frente a
todas las combinaciones de parámetros, para 1000 iteraciones.
C om p orta mien to d el A lgo rit mo fren te a la Variaci ón d e p ará met ro s: O f. 4, 1000 it er.
36 98 ,000
37 00 ,000
37 02 ,000
37 04 ,000
37 06 ,000
37 08 ,000
37 10 ,000
37 12 ,000
37 14 ,000
37 16 ,000
37 18 ,000
37 20 ,000
0 3 6 9 1 2 15 1 8 21 2 4 27 3 0
Var iac ió n de pa rá me tro s
Va
lor
de
F.O
.
Med iaMíni moMáx imo
Figura 25: Relación entre FO, Combinación de parámetros y 1000 iteraciones para la instancia 4.
La anterior gráfica, muestra que para todas las combinaciones de parámetros se
encuentra el mismo valor máximo, mínimo y media a lo largo de todos los
experimentos, para 1000 iteraciones. El valor mínimo obtenido es igual al
correspondiente a 25 iteraciones. Por lo que se concluye que para un número
grande de iteraciones, el algoritmo siempre encontrará el mínimo conocido, para
cualquier combinación de parámetros para esta instancia.
85
Frente a las variaciones en el número de iteraciones, tanto la media como el valor
mínimo obtenido presentan gran estabilidad frente a las variaciones de los
parámetros. Unido a esto, el valor máximo que se obtenga para un número grande
de experimentos puede variar de acuerdo al número de iteraciones, por lo que se
debe tener en cuenta que de la combinación de parámetros de 13 en adelante
resulta más conveniente para la corrida del algoritmo.
3.6.5 Oficina 5
La figura 26 muestra el valor de la función objetivo para la oficina 5, frente a todas
las combinaciones de parámetros, para 100 iteraciones.
Co m p o rt am ien t o d el Alg o rit m o fren t e a la V ariaci ón de p arám et ro s: O f . 5, 10 0 it er.
26 80 ,00 0
27 00 ,00 0
27 20 ,00 0
27 40 ,00 0
27 60 ,00 0
27 80 ,00 0
28 00 ,00 0
28 20 ,00 0
0 3 6 9 12 1 5 1 8 21 2 4 2 7 30
Va r iac ión d e p ar ám e tro s
Va
lor
de
F.O
.
Me di aMín im oMá xi mo
Figura 26: Relación entre FO, Combinación de parámetros y 100 iteraciones
para la instancia 5.
Esta gráfica muestra que para esta instancia se producen muchas variaciones
para el valor máximo encontrado en las primeras 10 combinaciones, y algunas
otras para las combinaciones 16 y 17, y una variación importante para la 25.
86
Aunque el mínimo encontrado para los 27 casos es el mismo y la media conserva
estabilidad se recomendaría evaluar esta instancia para un mayor número de
iteraciones, de lo contrario, posiblemente se obtenga un óptimo local como
solución. A continuación, se presenta el valor de la función objetivo para la oficina
5, frente a todas las combinaciones de parámetros, para 1000 iteraciones.
Co m p o rtam ie nt o d el Alg o rit m o fren t e a la V ariaci ón de p arám et ro s : O f. 5, 1 000 i ter.
26 80 ,00 0
27 00 ,00 0
27 20 ,00 0
27 40 ,00 0
27 60 ,00 0
27 80 ,00 0
28 00 ,00 0
28 20 ,00 0
0 3 6 9 12 1 5 1 8 21 2 4 2 7 30
Va r iac ión d e p ar ám e tro s
Va
lor
de
F.O
.
Me di aMín im oMá xi mo
Figura 27: Relación entre FO, Combinación de parámetros y 1000
iteraciones para la instancia 5.
A diferencia de todos lo casos anteriores donde se utilizaron 1000 iteraciones, la
figura 27 refleja que para todas las combinaciones de parámetros se encuentra el
mismo valor máximo, mínimo y media a lo largo de todos los experimentos,
excepto para dos casos. Lo cual lleva a pensar que el hecho de que se use un
número alto de generaciones no es un método infalible para obtener siempre la
mejor solución conocida. Por otra parte, el valor mínimo obtenido es igual al
correspondiente a 100 iteraciones, lo cual es la mejor solución conocida hasta el
momento. La media se comporta de manera estable.
87
La observación del comportamiento de esta instancia, permitió llegar a la
conclusión de que un número grande de iteraciones, junto con la aplicación del
conjunto conformado desde la combinación 10 en adelante; es decir, una
probabilidad de mutación superior a 0.05 y todos los demás niveles del porcentaje
de mejores y el porcentaje de generados por mejores, arrojará muy buenas
soluciones al problema estudiado.
3.7 DISTRIBUCIONES DE PLANTA FINALES
Para establecer las distribuciones de planta finales para cada una de las oficinas
estudiadas, se realizará una comparación entre las configuraciones actuales y los
mejores diseños de planta arrojados por el algoritmo a lo largo de todas las
iteraciones y todos los experimentos, en términos de la función objetivo y los
parámetros de diseño y seguridad para la oficina bancaria, comentados en el
primer capítulo de este documento.
Las configuraciones de planta que arroja el algoritmo son aproximaciones sobre la
distribución física óptima de la misma, de manera que son ayudas para el
diseñador del layout y en ningún momento pretenden ser una representación
exacta en el sentido arquitectónico del piso de la planta.
3.7.1 Oficina 1
Esta oficina es completamente rectangular, al igual que los departamentos que en
ella se encuentran. A continuación se muestran la configuración actual, su función
objetivo y los departamentos considerados dentro del estudio de esta oficina.
88
11
5
15
17 14 13 12 16
10
976
4
3
8
2
18
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Ejecutivos Junior
Convenciones
Depósito Archivo
Cafeteria
UPS comunicaciones
Baños
Dispensador
Multil inea
Capitalizadora
Entrada
Mesa consignaciones
F.O. = 4751,8
Sillas de espera
Director Operativo
Auxil iar Operativo
Cajas
Cajero Automático
Bòveda
Gerente Comercial
AsesoresComerciales y Archivador chequeras
Figura 28: Configuración actual, función ob jetivo y departamentos de la oficina 1.
89
Ahora se presenta la mejor configuración arrojada por el algoritmo:
11
5
15
14 13 17 16 12
7
10
96
1
4
3
8
18
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Ejecutivos Junior
Convenciones
Depósito Archivo
Cafeteria
UPS comunicac iones
Baños
Dispensador
Multil inea
Capital izadora
Entrada
Mesa consignaciones
F.O. = 4413,05
Sil las de espera
Direc tor Operativo
Aux iliar Operativo
Cajas
Cajero Automático
Bòveda
Gerente Comercial
AsesoresComerciales y Archivador chequeras
Figura 29: Configuración propuesta, función objetivo y departamentos para
la oficina 1.
Realizando una comparación entre las dos distribuciones presentadas, puede
verse que en la distribución actual, la bóveda colinda con un muro de la oficina, lo
cual es una violación a una de las restricciones de diseño expresadas en el ítem
1.3. Ligado a esto, puede verse que la distribución propuesta por el algoritmo no
presenta esta infracción, por lo que en términos de seguridad es mejor. Por otra
90
parte, la función objetivo es mejorada en un 7.13%, lo cual indica que el layout
propuesto no solo es mejor en cuanto a restricciones de diseño, sino que satisface
de una mejor manera las necesidades de proximidad entre los departamentos que
lo requieren, lo cual se verá reflejado en mayor agilidad y mejores condiciones de
servicio al cliente.
3.7.2 Oficina 2 Esta es la instancia mas pequeña dentro de las consideradas en este trabajo,
únicamente tiene 8 departamentos por lo que las opciones de distribución no son
muy variadas. La planta se trabajó omitiendo dos áreas correspondientes al
costado oriente y occidente que actualmente no son utilizadas. A continuación se
muestran la configuración actual, su función objetivo y los departamentos
considerados dentro del estudio de esta oficina.
1
2
3
4
5
6
7
8
Convenciones
F.O. = 622,4
Mul tilinea
Entrada
Mesa consignaciones
Sillas de espera
Cajas
AsesoresComerciales y Archivador chequeras
Bóveda
Dispensador
6
7
4
1
2
58
3
Figura 30: Configuración actual, función objetivo y departamentos de la
oficina 2.
91
Mejor configuración arrojada por el algoritmo:
1
2
3
4
5
6
7
8
Convenciones
Multilinea
Entrada
Mesa consignaciones
F.O. = 617,1
Sillas de espera
Cajas
AsesoresComerciales y Archivador chequeras
Bóveda
Dispensador
6
4
7
1
2
85
3
Figura 31: Configuración propuesta, función objetivo y departamentos para la oficina 2.
Al igual que en el caso anterior, la bóveda de la distribución actual colinda con un
muro de la oficina, pero debido al reducido tamaño de ésta, no es posible otra
solución, lo cual puede observarse en la configuración propuesta que también
presenta esta contravención. La opción para esta oficina es blindar el muro vecino
de la bóveda. En general pueden observarse pequeños cambios entre una
configuración y otra, debido al tamaño reducido de la misma, pero con la
configuración propuesta se logra una mejora del 0.85% para la función objetivo,
por lo que términos de costo el layout propuesto es mejor.
3.7.3 Oficina 3
Esta es una de las plantas grandes, con 16 departamentos. No fueron tenidos en
cuenta los lockers ni el cuarto de aseo dentro de la configuración, por no ser parte
importante de la actividad productiva del banco.
92
La siguiente gráfica muestra la configuración actual, su función objetivo y los
departamentos considerados dentro del estudio de esta oficina.
12
14
7 6 10 9 8
11
15135
3 16
4
2
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Comun icaciones
Bóveda
Baños
Subdir ecto r O pera t ivo
Auxilia r Ope rat ivo
Ca jas
Ca jero Au tomá t ico
Convenciones
Capit a lizado ra
En t rada
Mesa cons ignaciones
Geren te Comercia l
In form ador as y arch ivador cheque ras
Ej ecu t ivos Comercia les
Directo r Ope ra tivo
Ar chiv o
Ca fe te rí a
Figura 32: Configuración actual, función objetivo y departamentos de la oficina 3.
F.O. = 4322,75
93
Mejor configuración arrojada por el algoritmo:
2
1
12
14
67
8 10 9
11
135
15
16
4
3
F.O. = 4207,25
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Comunicaciones
Bóveda
Baños
Subdirector Operat ivo
Auxiliar Operativo
Cajas
Cajero Automático
Convenciones
Capitalizadora
Entrada
Mesa consignaciones
Gerente Comercial
Informadoras y archivador chequeras
Ejecutivos Comerciales
Director Operativo
Archivo
Cafetería
Figura 33: Configuración propuesta, función objetivo y departamentos de la
oficina 3.
En términos generales, la configuración actual es un diseño ergonómico y no viola
condiciones de seguridad, la configuración propuesta cumple estas mismas
condiciones, con la ventaja de que mejora la función objetivo en un 2.67%, por
esta razón el diseño realizado por medio del algoritmo es mejor que el actual.
94
3.7.4 Oficina 4
La planta de esta oficina no es del todo rectangular, por lo que se hicieron
generalizaciones reduciendo algunos espacios, para hacer la representación de la
distribución de esta instancia. Adicional a esto, el acceso principal se encuentra
sobre una esquina de la planta, por lo que se ingresó al algoritmo como un
rectángulo, que a escala, abarca el área que en la realidad está comprometida con
la entrada. A continuación se muestran la configuración actual, su función objetivo
y los departamentos considerados dentro del estudio de esta oficina.
1
2
3
1314 9 1215 16
11
4
6758
10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 Si llas de espera
Dispensador
Tele fono multi linea
Entrada
Mesa consignaciones
Cajas 1
Cajer o Automático
Cafetería
Gerente Comercia l
Ejecutivos Comerciales
Asesores y archivador chequeras
Director Operativo
Auxi liar Operativo
Convenciones
Archivo
Boveda
Comunicaciones
F.O . = 3 765 ,27 5
Figura 34: Configuración actual, función objetivo y departamentos de la oficina 4.
95
Mejor configuración arrojada por el algoritmo:
1
2
3
13
14 9 16 15 1211
4
6578
10
F.O. = 3700,375
Figura 35: Configuración propuesta,
función objetivo y departamentos
para la oficina 4.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 Sil las de espera
Dispe nsador
Telefono multi l inea
Entrada
Mesa con signac ione s
Cajas 1
Cajero Automát ico
Cafet erí a
Ge rent e Com erc ial
E jecutivos Comerc iales
Asesores y ar chivador chequeras
Director O perativo
Auxi l iar Operativo
Convenciones
Archivo
Boveda
Comunicaciones
96
La configuración actual de esta oficina presenta inconvenientes ergonómicos y de
seguridad, ya que las cajas no se encuentran directamente frente a la entrada y la
bóveda se encuentra contra un muro que está sobre la calle. Por esta razón una
distribución radicalmente diferente en estos dos aspectos sería conveniente. El
programa implementado, da una solución similar a la configuración actual, ya que
éste no cambia los departamentos de costado, que es lo que solucionaría los
problemas que se presentan actualmente. Bajo las mismas condiciones, la
distribución propuesta mejora la actual, gracias a una disminución de la función
objetivo en 1.72%.
3.7.5 Oficina 5
Esta oficina tiene un área muy pequeña, cabe anotar que la escala de este plano
es 1:50 (ver Tabla 2), por lo que las opciones sobre posibles diseños son muy
reducidas. Adicional a esto, no tiene una forma completamente rectangular, por lo
que el área donde no se podían ubicar departamentos se ingresó al algoritmo
como una zona prohibida representada en un departamento fijo.
97
La Figura 36 muestra la configuración actual, su función objetivo y los
departamentos considerados dentro del estudio de esta oficina.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
F.O. = 2860,425
Archivadorchequeras
Mesa consignaciones
Zona prohibida
Convenciones
Cajas
Cajero Automático
Dispensador
Entrada
Bóveda
Gerente Comercial
Informadoras
Director Operativo
Archivo
Cafetería
Comunicaciones
Tarjetero
12
1411
10
6
8
7
9
15
1
13
2
5
3
4
Figura 36: Configuración actual, función objetivo
y departamentos de la oficina 5.
98
Mejor configuración arrojada por el algoritmo:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
F.O. = 2702,125
Archivo
Cafetería
Comunicaciones
Tarjetero
Bóveda
Gerente Comercial
Informadoras
Director Operativo
Archivadorchequeras
Mesa consignaciones
Zona prohibida
Convenciones
Cajas
Cajero Automático
Dispensador
Entrada
12
1114
10
7
8
6
9
15
2
5
13
1
3
4
Figura 37: Configuración propuesta, función objetivo y departamentos
para la oficina 5.
Ambas distribuciones cumplen con las condiciones de seguridad mencionadas
anteriormente, por lo que la mejora del diseño propuesto radica en una
disminución del 5.53% en la función objetivo.
A lo largo de esta evaluación, que se realizó con el objetivo de establecer las
mejores distribuciones para cada oficina, se encontraron configuraciones que
mejoraban la función objetivo y/o integraban condiciones de diseño, que el layout
actual no consideraba. Hasta este punto, dichas configuraciones son denominadas
99
“buenas”, pero es necesario realizar una evaluación financiera, por parte de la
entidad, a los proyectos que se requieran llevar a cabo para realizar las
transformaciones de las oficinas. De esta manera se determinará la viabilidad de
las propuestas.
3.8 VALIDACIÓN DEL MODELO
Al ser este un problema poco tratado hasta el momento, no se dispone de librerías
de problemas para comparar las soluciones que éstas exponen con las arrojadas
por el algoritmo propuesto en este proyecto. Por esta razón se validará el modelo
realizando una comparación entre la función objetivo que representa las
configuraciones actuales de las oficinas y la función objetivo de las soluciones
arrojadas por el programa.
En la siguiente tabla se relacionan el número de departamentos, los valores
obtenidos para las funciones objetivo para las distribuciones actuales y las
mejores distribuciones encontradas por medio del algoritmo para cada oficina;
siendo estas dos últimas medidas de la misma manera y por lo tanto comparables.
1 18 4751,900 4413,050 7,13%2 8 622,400 617,100 0,85%3 16 4322,750 4207,250 2,67%4 16 3765,275 3700,375 1,72%5 15 2860,425 2702,125 5,53%
F.O. Dist. Actual
F.O. Dist. Encontrada
Porcentaje de Mejora
Oficina No. de deptos.
Tabla 4: Comparación entre la distribución actual y la mejor encontrada por el
algoritmo para cada oficina en términos de su F.O. De lo anterior, puede verse claramente que en todas las instancias tratadas se
mejoró la función objetivo del problema. De lo que se deduce, que el algoritmo es
capaz de diseñar mejores distribuciones a pesar de las limitaciones de espacio y
número de soluciones factibles que un problema pequeño, en términos de número
de departamentos, pueda representar. De esta manera queda validado el modelo.
100
4. CONCLUSIONES
La falta de exploración a la hora de desarrollar un proyecto de re-distribución de
planta puede ser muy poco beneficiosa, ya que en este caso tenderá a imponerse
la distribución actual, lo que conlleva a avances limitados en la solución del
problema que se está tratando. Gracias a la característica exploratoria de los AG,
se pueden lograr distribuciones de planta confiables, en sectores orientados a
servicios como las oficinas bancarias.
Los resultados y propuestas planteados en este proyecto, son producto de la
aplicación de métodos de Investigación Operativa, lo cual es un acercamiento
científico a la solución de problemas en el sector de servicios, que a pesar de su
tamaño, tal como enuncia Vallhonrat (1991), sigue siendo objeto en ocasiones de
una gestión artesanal.
La configuración de planta de una oficina bancaria tiene un gran número de
restricciones que están directamente ligadas con el servicio, condiciones de
seguridad y características físicas del edificio, por lo que los grados de libertad se
reducen y se disminuye el espacio de soluciones factibles. Por esta razón resulta
conveniente tener un grupo de posibles buenas soluciones, para que a partir de
estas se elija la distribución final.
La decisión sobre el diseño de layout más adecuado es un problema multicriterio,
por lo que se debe recurrir a las técnicas de análisis financiero, la experiencia y la
intuición de acuerdo a la importancia que la empresa o entidad le otorgue a cada
una.
101
Un número alto de generaciones no es un método infalible para obtener siempre la
mejor solución conocida. Así, en la búsqueda de buenas soluciones para el
problema estudiado, se recomienda utilizar un número grande de generaciones,
junto con una probabilidad de mutación superior a 0.05.
El algoritmo realizado presenta gran flexibilidad, ya que partiendo de una
configuración actual se pueden considerar objetos fijos, zonas prohibidas, y
limitaciones sobre el contorno de la oficina, asumiendo a estas dos últimas como
un departamento fijo dentro de la planta.
A partir de los resultados obtenidos, pudo observarse que para instancias con un
mayor número de departamentos, se lograron mejoras de la función objetivo que
representa la distribución actual, superiores a las obtenidas para la instancia de
menor número de departamentos.
Los diseños de distribuciones de planta obtenidos por medio del algoritmo
genético, son mejores en términos de las restricciones de diseño citadas al
principio de este trabajo, y satisfacen de una mejor manera la deseabilidad de
cercanía entre los departamentos que deben estar próximos; estando esta última,
representada en la función objetivo del modelo planteado.
De acuerdo a lo observado durante el desempeño del algoritmo en cada instancia,
puede afirmarse que el algoritmo es robusto, ya que a pesar de las variaciones en
el número de iteraciones y de parámetros de entrada, la media presenta una
notable estabilidad y en todos los casos se obtuvo el mínimo conocido para cada
instancia del problema.
102
4.1 PROYECTOS FUTUROS
La investigación futura deberá ser orientada a construir modelos robustos que
solucionen el problema de distribución de planta en una oficina bancaria teniendo
en cuenta otras restricciones que no fueron consideradas en este trabajo, tales
como:
• Oficinas que tengan varios pisos.
• Planta de la oficina no rectangular
• Tamaño de planta variable
• Tamaño de planta desconocido
• Zonas prohibidas dentro del hall destinado para los clientes
• Áreas mínimas y máximas para los departamentos
• Diseño tridimensional
Como alternativas sobre la metodología de solución está el uso de otras
metaheurísticas como Enfriamiento Simulado, Búsqueda Tabú e Híbridos que
integren heurísticas como búsqueda local, para aumentar la exploración y evitar
soluciones que correspondan a óptimos locales. Adicional a esto, resulta
interesante resolver el problema con enfoque multiobjetivo, generando una familia
de soluciones en la frontera eficiente. Y por último extender la aplicación a
cualquier otro tipo de entidad de servicios.
103
5. BIBLIOGRAFÍA
[6] APPLE, James M. “Plant layout and material handling”. Tercera ed. 1977
[12] CARRIÓN, D. (2003). Modelaje de distribución de planta para industrias Viba Ltda. Tesis de pregrado no publicada. Universidad de los Andes, Bogotá, Colombia.
[8] CUERVO, J. (2002).Configuración y rediseño de planta, Tesis de pregrado no publicada. Universidad de los Andes, Bogotá, Colombia.
[13] DUARTE, J. C. (2004). Redistribución de planta hogar juvenil campesino. Tesis de pregrado no publicada. Universidad de los Andes, Bogotá, Colombia.
[1] GARCÍA, D. (2001). Configuración de planta por medio de algoritmos
genéticos. Tesis de maestría no publicada. Universidad de los Andes, Bogotá,
Colombia.
[2] ISLIER A.A. “A genetic algorithm approach for multiple criteria facility layout
design”, International Journal of Production Research, Vol.36, No.6, 1998, 1549-
1569
[3] KOOK, W. (2004). Análisis de Estado del arte en algoritmos genéticos. Tesis de
pregrado no publicada. Universidad de los Andes, Bogotá, Colombia.
[14] MICHALEWICZ, Zbigniew. “Genetic algorithms + data STRUCTURES =
evolution programs”, New York: Springer. Tercera ed. 1996
104
[17] MONTGOMERY, Douglas C. “Diseño y análisis de experimentos”. 1991
[4] MUTHER Richard. “Distribución en planta. Ordenación racional de los
elementos de producción industrial”, Cuarta ed. 1981
[15] Salas, M., Cubero A., Hervás M., Pérez A., & Sanz T. (Sin Fecha). Aproximación al diseño de distribución en planta por medio de algoritmos tradicionales y genéticos. Recuperado el 17 Julio 2005, del Sitio Web de la Universidad de Zaragoza: <http://www.unizar.es/aeipro/finder/METODOLOGIA %20> DE%20PROYECTOS/AA06.htm>
[5] TOMPKINS J.A., WHITE J., BOZER Y., FRAZELLE E., TANCHOCO J. y
TREVINO J. “Facilities Planning”, John Wiley & Sons Inc. 1996
[11] TORRES, F. (2005). Presentación Algoritmos Genéticos. Curso Modelos de Sistemas Logísticos. Universidad de los Andes, Bogotá, Colombia. [10] TORRES, F. (2005). Presentación Búsqueda Tabú. Curso Modelos de Sistemas Logísticos. Universidad de los Andes, Bogotá, Colombia. [9] TORRES, F. (2005). Presentación Simulated Annealing. Curso Modelos de Sistemas Logísticos. Universidad de los Andes, Bogotá, Colombia.
[16] TORRES, F., RIAÑO, G. y SARMIENTO A. (2005). Estudio de Colas y distribución Física en Multibanca Colpatria. Documento no publicado. Universidad de los Andes, Bogotá, Colombia.
[7] VALLHONRAT Joseph M. y COROMINAS Albert. “Localización, distribución en
planta y manutención”. 1991
105
ANEXOS
Anexo 1: Manual del Usuario para Opt-DOB Ingreso de datos Al ingresar al programa, aparecerá lo siguiente:
Pulse el botón “Ingresar Datos” y saldrá un formulario que tiene cuatro pestañas.
106
Primera pestaña: Oficina
Ingrese el Nombre de la Oficina, el Punto cardinal
hacia donde está dirigida la entrada, las dimensiones
en metros del frente, fondo y el número de
departamentos. A continuación haga clic sobre la
siguiente pestaña.
Segunda pestaña: Departamentos
Para el ingreso de datos sobre los
departamentos tenga en cuenta que:
1. La suma de las áreas de los
departamentos no debe exceder
el área total de la planta
2. Las dimensiones deben ser
ingresadas en metros
3. La entrada es un departamento,
al que se le pueden asignar
medidas pequeñas.
4. La primera de las dimensiones
que se pide, corresponde a la
longitud del departamento en el
sentido del eje Y y la segunda en X.
107
5. La ubicación de los departamentos debe seleccionarse con respecto a la entrada. La
“Parte trasera” corresponde al área donde el cliente no tiene acceso, generalmente
está ubicada detrás de las cajas.
6. Las dimensiones de los departamentos no deben exceder la longitud del costado
donde se encuentran
A continuación haga clic en la siguiente pestaña.
Tercera Pestaña: Flujos
Aquí se llena la información
sobre la deseabilidad de
cercanía entre
departamentos, por lo que
aparecerá cada pareja de
ellos junto con una opción a
la derecha, donde podrá
seleccionar la deseabilidad
de proximidad entre ellos, tal
y como se muestra en la
siguiente figura
Si desea cambiar los parámetros del algoritmo genético haga clic en la siguiente
pestaña, de lo contrario presione “Ejecutar” y obtendrá la configuración de planta
para si oficina.
108
Pestaña 5: Avanzadas
Aquí podrá cambiar
parámetros para el algoritmo
genético, tal como se muestra
en la siguiente figura, si desea
conservar los parámetros
sugeridos de clic en “Usar
valores recomendados”. A
continuación presione
“Ejecutar” para obtener la
distribución de planta de su
oficina.
Salida de Resultados
Una vez se presiona el
botón “Ejecutar” deberá
esperar un tiempo, que
dependerá del número
de departamentos de la
oficina y el número de
iteraciones. Si alguno de
estos dos (o ambos), es
un parámetro muy
grande, es posible que
la pantalla de su
computador se ponga en
blanco. Dentro de un tiempo prudencial, aparecerá en la hoja “Plano”, el diseño de
planta encontrado por la aplicación.
109
Podrá observar un esquema del plano de la oficina, las convenciones para los
departamentos y el valor de la función objetivo que representa esa configuración.
Esta última, puede ser usada como criterio para comparar diferentes soluciones.
Entre mas pequeño el valor de F.O., la distribución satisface mejor la deseabilidad
de proximidad entre departamentos.
110
Anexo 2: Resultados obtenidos para la Función Objetivo de todas las instancias para 1000 iteraciones Oficina 1
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7 PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050Máximo 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050Combinaci 1 2 3 4 5 6 7 8 9
PM 1 = 0,01PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2 PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050Máximo 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050Combinaci 10 11 12 13 14 15 16 17 18
PM 2 = 0,05PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050Máximo 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050 4413,050Combinaci 19 20 21 22 23 24 25 26 27
PM 3 = 0,1PGE 3 = 0,8PGE 1 = 0,3 PGE 2 = 0,6
Oficina 2
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7 PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100Máximo 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100Combinaci 1 2 3 4 5 6 7 8 9
PM 1 = 0,01PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2 PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100Máximo 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100Combinaci 10 11 12 13 14 15 16 17 18
PM 2 = 0,05PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
111
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100Máximo 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100 617,100Combinaci 19 20 21 22 23 24 25 26 27
PM 3 = 0,1PGE 3 = 0,8PGE 1 = 0,3 PGE 2 = 0,6
Oficina 3
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7 PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250Máximo 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250Combinaci 1 2 3 4 5 6 7 8 9
PM 1 = 0,01PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2PE 2 =
0,45PE 3 =
0,7PE 1 =
0,2PE 2 =
0,45PE 3 =
0,7PE 1 =
0,2PE 2 =
0,45PE 3 =
0,7Media 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250Máximo 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250Combinaci 10 11 12 13 14 15 16 17 18
PM 2 = 0,05PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250Máximo 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250 4207,250Combinaci 19 20 21 22 23 24 25 26 27
PM 3 = 0,1PGE 3 = 0,8PGE 1 = 0,3 PGE 2 = 0,6
Oficina 4
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7 PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375Máximo 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375Combinaci 1 2 3 4 5 6 7 8 9
PM 1 = 0,01PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
112
PE 1 = 0,2 PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375Máximo 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375Combinaci 10 11 12 13 14 15 16 17 18
PM 2 = 0,05PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375Máximo 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375 3700,375Combinaci 19 20 21 22 23 24 25 26 27
PM 3 = 0,1PGE 3 = 0,8PGE 1 = 0,3 PGE 2 = 0,6
Oficina 5
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7 PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 2702,125 2702,125 2702,125 2702,125 2705,300 2702,125 2705,300 2702,125 2702,125Desviación 0,000 0,000 0,000 0,000 17,390 0,000 17,390 0,000 0,000Mínimo 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125Máximo 2702,125 2702,125 2702,125 2702,125 2797,375 2702,125 2797,375 2702,125 2702,125Combinaci 1 2 3 4 5 6 7 8 9
PM 1 = 0,01PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2 PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125Máximo 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125Combinaci 10 11 12 13 14 15 16 17 18
PM 2 = 0,05PGE 1 = 0,3 PGE 2 = 0,6 PGE 3 = 0,8
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
PE 1 = 0,2
PE 2 = 0,45
PE 3 = 0,7
Media 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125Desviación 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000Mínimo 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125Máximo 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125 2702,125Combinaci 19 20 21 22 23 24 25 26 27
PM 3 = 0,1PGE 3 = 0,8PGE 1 = 0,3 PGE 2 = 0,6
113
Anexo 3: Datos A continuación se presentan los datos utilizados en este proyecto en forma de
archivo plano. El nombre de cada archivo corresponde al número de la oficina y al
tamaño de la instancia. Las medidas están en metros. El formato para la lectura de
cada archivo es:
El primer número corresponde al número de departamentos.
Los dos números siguientes corresponden a las medidas en metros de frente y
fondo de la oficina respectivamente.
Posteriormente se observa una matriz de datos que corresponden a los
departamentos. Cada fila corresponde a los datos del departamento i. Las
columnas corresponden de izquierda a derecha a: la coordenada en X de la
esquina superior izquierda, la coordenada en Y de la esquina superior izquierda, la
longitud del fondo, la longitud del frente, condición (1 si es fijo, 0 d.l.c.), nombre, y
costado donde se encuentra (1: Occidente, 2: Norte, 3: Oriente, 4: Sur, 5: Parte
trasera).
Por último se observa la matriz correspondiente a los flujos entre departamentos.
El valor de la posición (i, j) corresponde al flujo entre el departamento i y el
departamento j.
114
OF1_DEP18 18 9 24.7 21 5 2 1.5 0 Depósito Archivo 5 21 0 3.5 2.05 0 Cafetería 5 18.5 6.1 1 0.5 0 UPS comunicaciones 5 18.5 0 2.5 1.5 0 Bóveda 5 0 4.4 5.4 2.5 0 Gerente Comercial 1 5.3 6.2 4.05 2.8 0 Asesores comerciales y Archivador chequeras 4 10 6.2 3.6 2.8 0 Ejecutivos Junior 4 18.5 6.5 1.5 1.5 0 Director Operativo 5 13.6 6.5 2.4 2.3 0 Auxiliar Operativo 4 16.2 0 2.2 6.5 0 Cajas 3 0 7.1 5.4 2 1 Cajero Automático 1 9 0 1 1 0 Dispensador 2 7 0 1 1 0 Multilínea 2 5.3 0 1 1 0 Capitalizadora 2 0 1.9 3.4 2.2 1 Entrada 1 10 0 1 1 0 Mesa consignaciones 2 3.8 0 1.4 1.2 0 Sillas de espera 2 21 2.05 2.05 2.7 0 Baños 5
115
0 0.5 0 0.5 0 0 1 0 1 0 1 0.5 1 0.5 0 3.5 0.5 1 0.5 4.5 0 1.5 0.5 1 0.5 4.5 4.5 0 2.5 0.5 3 4 3 3 3 0 3 1 2.5 1 1.5 2 1 5 0 2 0 1 5 1.5 4 2.5 4 5 0 0.5 0.5 1.5 0 0.5 0.5 0.5 1 0 0 0 0.5 1 0.5 0.5 4 5 4.5 3.5 5 2 0 0 0.5 0 1 0 2 3.5 2.5 0 0 0 0.5 1 0 0 0 0 0 0.5 0.5 0.5 0 0 0.5 0.5 0.5 0.5 0 0.5 0 0 0 3.5 4.5 3 0 0 0 4 4 5 2 0 1 0.5 0.5 0 2 2 0.5 0 0 3.5 0.5 5 0 1 5 0 1 1 0 0 3 5 5 0.5 0.5 1 0.5 1 0 0.5 4.5 5 0 0 0 0 0 5 5 5 5 5 5 0 0 0 0 0 0 0 0
116
OF2_DEP8 8 8.2 10.4 5.7 0 2.5 5.6 0 Cajas 3 5.7 5.6 2 2.5 0 Asesores comerciales y Archivador chequeras 3 8.2 0 2.2 2.6 0 Bóveda 5 0 5.7 0.5 0.5 0 Dispensador 1 5.2 7.7 0.5 0.5 0 Multilínea 4 0 6.2 0.5 2 1 Entrada 1 0 4.5 0.5 1.2 0 Mesa consignaciones 1 3.7 7.7 1.5 0.5 0 Sillas de espera 4 0 4 0 5 1 0 2 1 0.5 0 0 3.5 0 1 0 0 4.5 0 4 5 0 3.5 2 0 5 0 5 0 1 5 0 1 0 4.5 5 0
117
OF3_DEP16 16 8.5 24 20.2 2.6 3.5 5.6 0 Archivo 5 20.2 0 3.4 2.5 0 Cafetería 5 17.3 0 2 1.5 0 Comunicaciones 5 17.3 4.8 1.3 0.6 0 Bóveda 5 2.8 5.3 2.5 2.8 0 Gerente Comercial 4 3.2 0 4.8 2.3 0 Informadoras y archivador chequeras 2 0 0 2.7 1.9 0 Ejecutivos Comerciales 2 12.2 0 2.8 2.5 0 Director Operativo 2 10.8 0 1.4 2.5 0 Subdirector Operativo 2 8 0 2 2.5 0 Auxiliar Operativo 2 15.2 2.8 2.4 5.3 0 Cajas 3 0 5.5 0.3 2.8 1 Cajero Automático 1 5.2 7.7 0.5 0.5 0 Capitalizadora 4 0 3.3 0.3 2 1 Entrada 1 5.7 7.7 2.4 0.3 0 Mesa consignaciones 4 17.3 2.4 2.6 2.1 0 Baños 5
118
0 1.5 0 2 1 0 1 0.5 1 0 1 2 1 0 0 3 2 1 2 4 0 1 2 1 0.5 4 4 0 3 1 3 3 1 2.5 1 0 3 1 3 3 1 2.5 1 4.5 0 3.5 1 3 2 1 2.5 1 4.5 4.5 0 3 1 3 5 0.5 3 1 4.5 4.5 2.5 0 1 1 3 1 0.5 1 1 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 3.5 3 3 1 1 1 1 4 0 0 1 1 1 1 2 2 2 1 1 1 1.5 1 0 3 0 0 0 0 0 5 5 5 5 5 5 5 0 0 0 0 0
119
OF4_DEP16 16 5.5 17 0 3.9 1.23 1.2 0 Archivo 1 0 2.6 1.23 1.2 0 Bóveda 1 0 1.3 1.1 1.5 0 Comunicaciones 1 12.7 1.5 1.7 1.4 0 Gerente Comercial 3 7.8 3.3 3.45 2 0 Asesores y archivador chequeras 4 12.9 3.9 1.6 1.4 0 Director Operativo 3 12 4.3 0.85 1 0 Auxiliar Operativo 4 1.5 3.5 6.4 1.8 0 Cajas 4 3.5 0 1.1 0.9 1 Cajero Automático 2 14.6 4 1.1 1.4 0 Cafetería 5 12.7 1 1.7 1.4 0 Ejecutivos Comerciales 3 5.8 0 0.5 0.5 0 Dispensador 2 0 0.9 1 0.6 0 Teléfono multilínea 1 0 0 3.5 1 1 Entrada 1 6.5 0 0.5 0.5 0 Mesa consignaciones 2 10.1 1.1 1.55 0.5 0 Sillas de espera 2
120
0 4 0 1 2 0 1 0.5 1.5 0 1.5 0 0 5 0 4 4.5 4.5 4.5 3.5 0 4 3.5 4 4 4.5 5 0 4.5 5 3.5 0.5 5 4.5 3 0 0.5 0.5 1 0.5 2 1 2 1.5 0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0 1 1 1 5 4 3 2 0.5 1 2 0 0 2 1 0.5 2 2 2 1.5 0.5 1 1 0 1 1 0 2 3 2 0.5 1 5 1 1 1 0 0 0 1 3 3.5 2.5 2 4 4 1 3.5 1 4 0 0 0.5 1 1.5 1 1 0.5 3 1 1 0.5 1 2 2 0 2 0.5 1 3 5 0.5 0.5 0.5 0.5 1 3.5 0.5 0 4 4 0
121
OF5_DEP_15 15 20.3 11.1 8.2 3.3 2.2 4.2 0 Archivo 5 8.2 8.1 2.2 1 0 Cafetería 5 8.2 11.6 2.2 1.8 0 Comunicaciones 5 9.1 13.4 1.5 5.9 0 Tarjetero 5 8.2 10.5 1.7 1.2 0 Bóveda 5 4.2 0 4 3.3 0 Gerente Comercial 3 4 7.5 2.9 3.8 0 Informadoras 3 4 5.1 2.9 2.4 0 Director Operativo 3 4 11.3 2.8 8 0 Cajas 3 0 0 4.1 3.3 1 Cajero Automático 1 1.2 3.3 0.5 0.5 0 Dispensador 1 0 4.6 0.25 13.5 1 Entrada 1 8.2 6.3 1 0.5 0 Archivador chequeras 5 0 3.8 0.75 0.65 0 Mesa consignaciones 1 8.2 0 2.2 3.3 1 Zona prohibida 5
122
0 0.5 0 0.5 0 0 1 0 1 0 1 0.5 1 0.5 0 3.5 0.5 1 0.5 4.5 0 1.5 0.5 1 0.5 4.5 4.5 0 1.5 0.5 1 0.5 4.5 4.5 4.5 0 2.5 0.5 3 4 3 3 1 3 0 3 0.5 3 4 3 3 1 3 4.5 0 2 0 1 5 1.5 4 3 2.5 4 4 0 0.5 0.5 1.5 0 0.5 0.5 0.5 0.5 1 2 0 0 0.5 1 0.5 0.5 4 5 4.5 4.5 3.5 4 2 0 0 0 0 1 0 1 1 0.5 0.5 1 0 0.5 1 0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0