Diseño LayoutTeoría de Grafos y otros Metodos

Cesar Huaman BernaReynaldo Benavides valdivia

INTRODUCCIONDentro de el diseño Layout, encontramos herramientas que

nos facilitaran el objetivo principal, la disposición física de la planta.

TEORIA DE GRAFOS Herramienta matemática heurística de diseño layout.

Grafo: Grafica constituida por nodos y arcos.

La nomenclatura de un grafo es G(N,A).

El nodo representa a los departamentos.

El arco representa el flujo de recursos.

TEORIA DE GRAFOS Superficie: Área encerradas pon un grafo, o área exterior al grafo.

TEORIA DE GRAFOS Grafo Plano: grafo de dos dimensiones sin intersección de sus arcos.

No posee cruce de relaciones.

Número máximo de arcos=3N-6 con N>2

PROPIEDADES Grafo de peso máximo(MPGW): tiene 2N-4 superficies, las cuales son triangulares.

Puede tener 3N-6 relaciones y no ser plano

PROPIEDADES El grafo plano es limitado.

En un grafo se busca evitar cruce de relaciones.

El cruce de relaciones ocasiona interrupción en flujo de recursos.

PROPIEDADES Para un grafo máximo:

GRAFO DUAL Variación del grafo principal. Se obtiene colocando un nodo en cada superficie.

Un grafo puede tener varios grafos duales.

El grafo dual también es plano.

GRAFO DUAL El grafo dual y principal tienen en mismo numero de arcos.

# nodos del grafo principal=# superficies del grafo dual.

# nodos del grafo dual=# superficies del grafo principal.

PROCEDIMIENTO Encontrar un MPGW usando los pesos de la matriz REL.

Prioridad:

PROCEDIMIENTO Luego se encuentra el grafo dual MPGW.

Convertir el grafo dual a un plano de bloques.

PROCEDIMIENTO Incluir arcos de mayor peso, manteniendo el grafo plano.

Se define el Grado total de dependencia.

*i: numero de departamentos(Se excluyen la relaciones X)

* V(rij): valor arbitrario.

PROCEDIMIENTO Clasificar los departamentos de acuerdo a TCR.

Se forma un tetraedro inicial con los 4 primeros lugares.

Se insertan los departamentos por su peso y en orden decreciente.

Finalmente se forma el grafo dual.

Ventajas del método heurístico:• Es simple• Garantiza planaridad (superficies planas)

Desventajas del método heurístico:• No necesariamente llega al layout óptimo

SÍNTESIS DEL METODO HEURISTICO

Mecanismos para mejorar el método heurístico de la teoría de grafos

•Reemplazo del borde crítico •Relocalización de los nodos o vértices

Al establecerse la dimensión física de cada

superficie, hay que respetar varios elementos:

• Superficies correspondientes a cada departamento

• Condiciones de terreno previamente seleccionadas

• Fronteras del grafo dual

• Vías de acceso

• Otras consideraciones de cada caso particular

DIMENSIONAMIENTO

OTRAS HERRAMIENTAS DE DISEÑO DE LAYOUT

• Esencialmente constituidos por algoritmos

implementados a través de los computadores.

Estos algoritmos se clasifican en:

– Algoritmos Constructivos

– Algoritmos Optimizadores

– Algoritmos Apoyados en la Teoría de Grafos

ALGORITMOS CONSTRUCTIVOS

• En ellos se realiza una selección sucesiva de la

ubicación de los distintos departamentos hasta

lograr un Layout final

Ejemplos :

– CORELAP (1967)• “Computarized Relationship Layout Planning”

– ALDEP (1967)• “Automated Layout Design Program”

– Otros : PLANET, RMA, LSP, LAYOPT

CORELAP (1967)

“Computarized Relationship Layout Planning”

Puede ordenar hasta 45 departamentosRequiere como inputs la especificación de los tamaños de aquellos y algunas dimensiones de la planta. En lo que será el centro de la distribución sitúa el departamento que está más interrelacionado con el resto y, en sucesivas iteraciones, Va colocando los demás en función de su necesidad de cercanía con los ya colocados. Las soluciones obtenidas se caracterizan por la irregularidad en las formas.

ALDEP (1967)

“Automated Layout Design Program”

Tiene una capacidad para distribuir 63 departamentos. Usa una matriz de código de letras similar a las especificaciones de prioridad de cercanía de Muther.Los inputs del programa son la planta del edificio y la situación de elementos fijos Utiliza un algoritmo de barrido, de forma que selecciona aleatoriamente un primer departamento y lo sitúa en la esquina noroeste de la planta, colocando los demás de forma sucesiva en función de las especificaciones de proximidad dadas.

ALGORITMOS OPTIMIZADORES

Se parte de un layout inicial, luego se evalúan distintos

intercambios entre los departamentos, según algún criterio y, si

el cambio es favorable, se hace permanente

programa heurístico que puede operar hasta con 40

departamentos

El algoritmo más conocido de este tipo es el CRAFT

(“Computarized relative allocation of facilities technique”)

METODO CRAFT

• Programa heurístico

• No garantiza el óptimo

• El resultado está condicionado por el layout

inicial que se le da como punto de partida

• Lo usual es correrlo con varios layouts iniciales

distintos

• Maneja hasta 40 departamentos, y rara vez

hace menos de 10 iteraciones

PROGRAMA CRAFT

• Compara parejas de departamentos, y los permuta si

se logra disminuir el costo total de la instalación

• Se cuantifica el costo total como:

– Cij : Costo unitario de transporte entre “i” y “j”

– Aij : Flujo de recursos entre “i” y “j”

– dij : Distancia entre departamentos de “i” y “j”

C = {Cij Aij}dij

PROGRAMA CRAFT

• Es uno de los programas más eficiente en los

cálculos para obtener una solución heurística en

problemas cuadráticos de asignación de recursos

• Requiere la siguiente información:

– Layout inicial

– Flujo de recursos entre departamentos

– Costo de transporte entre departamentos

– Número y ubicación de departamentos fijos

INPUTS DEL CRAFT: LAYOUT INICIAL

A B

C D

5O ‘ 30 ‘

40 ‘

20

‘

20 ‘

INPUTS DEL CRAFT : FLUJO DE MA-TERIALES ENTRE DEPARTAMENTOS

A B C D

A 2 4 4

B 1 1 3

C 2 1 2

D 4 1 0

HaciaDesde

Cantidades en Ton / hora

INPUTS DEL CRAFT : DISTANCIAS ENTRE DEPARTAMENTOS

A B C D

A 40 25 55

B 40 65 25

C 25 65 40

D 55 25 40

HaciaDesde

Distancias en metros

INPUTS DEL CRAFT : DEPARTAMENTOS FIJOS

C

40 ‘

20

‘

Conclusión El método presentado es de gran aporte ya que interactúa con otras metodologías del diseño Layout para lograr el objetivo de disposición de planta, y así optimizar la función del sistema productivo al cual prestan servicio. Los programas de diseño de layout facilitan el trabajo y la distribusion Una aplicación de la teoría de grafos es la SECTORIZACION DE REDES AGUA POTABLE