Heurística

. Método de solución por enumeración exhaustiva de J. R. Jackson.

Para empezar a hablar de este método primero debemos saber que este y el tercer método son métodos de la heurística, creados por diferentes personas, por lo cual es importante abordar algo acerca de la heurística.

Heurística

La optimización heurística busca soluciones admisibles para la optimización de problemas en circunstancias donde la complejidad del problema o el tiempo limitado para su resolución no permiten la obtención de resultados exactos. Aunque el análisis de algoritmos de probabilidad y de peor escenario han dado una visión más profunda de los modelos clásicos, la mayoría de los modelos heurísticos desarrollados para problemas de optimización deben ser evaluados empíricamente aplicando procedimientos a un grupo de instancias específicas y comparando la calidad de las soluciones observadas y el costo (monetario y de tiempo) de implementar equipo informático.

El ejemplo en este método es un cambio de llantas, ya que en el ámbito de la industria este puede ser un ejemplo muy utilizado y un poco más complejo de lo normal.

Para realizar el balanceo de línea óptimo, se debe dividir este trabajo en estaciones de trabajo. Para lograr esto usamos el siguiente método:

Si ni n, ni c, nos son dados, es necesario determinar el valor, o valores, de c y n, para los cuales el retraso del balanceo sea cero.

Para determinar los tiempos de ciclo para los cuales ∑iti/ c sea un entero, es conveniente escribir ∑iti como el producto de números primos, esto es:

∑iti = 708 = 2 * 2 * 3 * 59

c1 =2 * 2 * 3 * 59 = 708

c2 = 2 * 3 * 59 = 354

c3 = 2 * 2 * 59 = 236

c4 = 3 * 59 = 177

c5 = 2 * 59 = 118

El balanceo perfecto puede conseguirse con:

n1 = 708/708 = 1 estación

n2 = 708/354 = 2 estaciones

n3 = 708/236 = 3 estaciones

n4 = 708/117 = 4 estaciones

n5 = 708/118 = 6 estaciones

De esta forma se puede observar que los tiempos por estación son:

Estación 1 = 168 segundos

Estación 2 = 180 segundos

Estación 3 = 185 segundos

Estación 4 = 175 segundos

El promedio aritmético de estos tiempos es 177 segundos.

Esta solución no es óptima, pues las estaciones de trabajo tienen ciertas variaciones en el tiempo de trabajo.

Aún así, esta solución entrega mejores resultados que una línea no balanceada. Se requeriría hacer un balance más profundo para lograr mejores resultados.

Este método consiste en términos generales en enumerar todas las soluciones posibles, a partir de los valores tomados para las variables enteras y realizar todas las combinaciones posibles hasta encontrar una combinación que nos proporcione el valor óptimo de la función objetivo y que cumpla con todas las restricciones del problema.

Una de las objeciones principales que presenta éste método es el número de variables, ya que se presentan demasiadas combinaciones antes de encontrar la solución óptima.

El doctor Jackson ha simplificado el procedimiento de solución de balanceo de líneas al sugerir la eliminación sistemática de las alternativas de menor valor conforme se va llegando a la solución. Es muy frecuente que al vender una solución de balanceo a personas son sin la preparación técnica, el poner así disposición la solución en forma gráfica de presencias. Además de que se pueden indicar las estaciones circulando los elementos de cada uno con líneas punteadas. Esto se muestra a continuación.

REGLAS DEL MÉTODO DE ENUMERACIÓN EXHAUSTIVA:

Quitar de la gráfica de precedencias todas las operaciones incluidas en las secuencias {x(1)…x(n-1)} y todas las líneas de precedencia que salen de estos elementos {a,b,c}

Listar todos los conjuntos x de elementos del paso 1 tal que:

1) Si un elemento dado esta x, entonces también deberá estar cada elemento del cual una línea de precedencia se dirige a este método dado

2) La suma de los tiempos de ejecución de los elementos en x no sean mayor que el límite superior del tiempo de ciclo.

PASOS PARA LA ELABORACION DE ESTE METODO:

PASO 1.- construir la colección de asignaciones siguientes después de {} usando a subrutina.

PASO 2.- Escribir la lista 1, lista de secuencias {x(1)} de un solo conjunto de elementos, con x(1) dentro de colección obtenida en el paso 1-a

PASO 2-1.- escribir la lista de 2-b, la lista de secuencias {x(1),…x(n-1),x(1)} con {x(1)…x(n-1)} es la lista (n-1), y x(n) en la colección de asignaciones siguientes después de {x(1)…x(n-1)}

PASO 2.1.2.- obtener la lista n apartir de la lista 2-b al estar cruzando sucesivamente la secuencias {x(1….x(n)} para las cuales hay otra secuencia {y(1…..y(n)} en la lista ( a un no cruzada), tal que cada elemento incluido en cualquier x (1) sea incluido en algún y(1) (pudiera haber operaciones incluidas en algún y(1) que no estén en cualquier x(1)

AL final del paso 3 los posibles conjuntos son los siguientes:

{A} {C} {BGE} {FI} {DH}

{A} {C} {BGE} {DI} {FH}

{A} {C} {BF} {GEI} {DH}

{A} {C} {FGI} {BE} {DH}

{A} {C} {BG} {FEI} {DH}

{A} {C} {FG} {BI} {DH}

El objetivo de este método es minimizar el tiempo ocioso de las estaciones sujeto a las restricciones de precedencia y a la limitación de que ninguna estación se puede exceder del tiempo de ciclo.

* Las reglas del método de enumeración exhaustiva son las siguientes:

1. Dada una secuencia donde X(1) es un conjunto de elementos, la colección de asignaciones siguientes después de x(1) … X(n-1) es la colección de conjuntos de elementos.

2. Quitar de la gráfica de precedencia todas las operaciones incluidas en la secuencia x(1)…x(n-1) y todas las líneas de precedencia que salen de estos elementos.

3. Listar los conjuntos x de elementos del paso 2 tales que:

a). Si un elemento dado está en x, entonces también deberá estar cada elemento del cual una línea de precedencia se dirige a este elemento dado.

b). La suma de los tiempos de ejecución de los elementos en X no sea mayor que el límite superior del tiempo de ciclo.

c). Ninguna operación se puede agregar a X sin violar los puntos a y b.

4. Cruzar la lista de conjuntos x del paso 3 para los cuales hay otro conjunto y en la lista (aún no cruzado). Este punto puede ser omitido, pero generalmente esto puede dar como resultado un incremento en el número sustancioso en el número de iteraciones.

5. Cruzar el elemento tal que :

a. Haya sólo un elemento x en x que no esté también en y

b. Exista algún elemento y en y que no esté en x, tal que las líneas de precedencia puedan ser seguidas directamente de y hacia cualquier elemento z del cual haya una línea de precedencia de x a z.

6. Cuando ya no haya más conjuntos que puedan ser cruzados del paso 5, la subrutina que aquí se describe estaría completa.

Método de enumeración exhaustiva

Supongamos que el problema de decisión tiene S políticas estacionarias, y supondremos que Ps y Rs son las matrices de transición y de ingreso (de un paso) correspondientes a la política, s=1, 2,3…, S. Los pasos de enumeración son los siguientes:

Paso 1. Calcule Vis, el ingreso esperado de un paso (un periodo) de la política s, dado el estado i, i 1, 2,..., m.

Paso 2. Calcule πsi, las probabilidades estacionarias a largo plazo de la matriz de transición Ps asociadas con la política s. Estas probabilidades, cuando existen, se calculan con las ecuaciones:

Paso 3. Determine Es, el ingreso esperado de la política s por paso (periodo) de transición, con la fórmula:

Paso 4. Se determina la política óptima s* tal que:

Es* = máx (Es)

Ejemplo:

El problema del jardinero tiene un total de ocho políticas estacionarias, como se ve en la siguiente tabla:

Política estacionaria, s Acción

1 No fertiliza.

2 Fertiliza a pesar del estado.

3 Fertiliza si está en estado 1.

4 Fertiliza si está en estado 2.

5 Fertiliza si está en estado 3.

6 Fertiliza si está en estado 1 o 2.

7 Fertiliza si está en estado 1 o 3.

8 Fertiliza si está en estado 2 o 3.

Los cálculos de las probabilidades estacionarias se hacen con las ecuaciones:

Por ejemplo, si s = 2, las ecuaciones correspondientes son:

(Observe que una de las tres primeras ecuaciones es redundante.) La solución es:

En este caso, el ingreso anual esperado es:

En la tabla siguiente se resumen πsy Espara todas las políticas estacionarias. (Aunque no afectará esto a los cálculos en modo alguno, observe que cada una de las políticas 1, 3, 4 y 6 tiene un estado absorbente: el estado 3. Es la razón por la que π1=π2=0 y π=1 para todas esas políticas.)

La política 2 produce el máximo ingreso anual esperado. La política óptima a largo plazo es aplicar fertilizante independientemente del estado del sistema.

Tecnica de ponderación por rango posicional de W.B. Hegelson y D.P. Bernie

Consiste en estimar el peso posicional de cada tarea como la suma de su tiempo más los de aquellas que la siguen.

CONCLUSION

Al término de este trabajo el equipo pudo concluir que todos los métodos para la solución del balanceo de líneas son importantes incluyendo los que se nos fueron asignados a investigar.

Y que todos tienen un mismo objetivo el de minimizar el tiempo de producción para así poder mejorar la producción, disminuir mano de obra y obtener mayores guanacias dentro de una empresa.

...