Analisis Estatico y Dinamico De Los Procesos

Programación estocástica: análisis estático

Una sola maquina

Un asunto que no se ha mencionado todavía es la incertidumbre de los tiempos de procesamiento. En la practica es posible, y hasta probable, que no se pueda predecir el tiempo exacto de terminación de uno o mas trabajos.
Supondremos que lo tiempos de procesamiento son independientes entre si. Supóngase que deben procesarse ntrabajos en un sola maquina, que los tiempos de trabajo son t1, t2….tn y que son variables aleatorias. El objetivo es minimizar el tiempo promedio de flujo esperado

Minimizar E1ni=1nuiFi

Donde ui son los factores de ponderación o pesos, y F1 es el tiempo (aleatorio de flujo para el trabajo i.

Varias maquinas.

El requisito que los tiempos de procesamiento tengas distribución exponencial essevero el en contexto de la programación.
La propiedad de amnesia señala que la probabilidad de terminar un trabajo en el siguiente momento en el tiempo es independiente del intervalo de tiempo que ya ha pasado al procesar el trabajo. Hay algunas aplicaciones como en los sistemas telefónicos y se procesaran n trabajos en dos maquinas idénticas en paralelo. Cada trabajo necesita procesarse solo unavez en cualquiera de las maquinas. El objetivo es minimizar el tiempo esperado que transcurre desde el momento cero hasta terminar de procesar el ultimo trabajo. Esto se conoce como intervalo esperado de fabricación. Supondremos que los tiempos de procesamiento de los trabajos son t1, t2....tn que son variables aleatorias exponenciales con tasas μ1, μ 2…. μ n. Esto quiere decir que el tiempoesperado necesario para terminar el trabajo i es E(ti)=1/ μi .El procesamiento en paralelo es distinto del procesamiento en taller de flujo. En este último, los trabajos se procesan primero en maquina 1 y después en la maquina 2. En el procesamiento e paralelo; solo necesitan procesarse en una maquina, y cualquier trabajo se puede procesar en cualquier maquina. Supongamos que en momento t=0 lamaquina 1 esta ocupada con un trabajo anterior; el trabajo 0, y que el tiempo restante del procesamiento para el trabajo 0 es t0, los trabajos posteriores se procesaran como sigue: sea (1), (2),….,(n), una permutación de los n trabajos. Se programa el trabajo (1) en la maquina vacante. El trabajo (2) sigue el trabajo 0 en la maquina 1 o el trabajo (1) en la maquina (2) dependiendo de cual termineprimero.

Sean T0≤ T1 ≤... ≤ Tn los tiempos terminación de los trabajos sucesivos. El intervalo de fabricación es el tiempo de terminación del último trabajo, que es Tn.

En la figura se ve que

Tn+Tn-1=i=0nti

y que
Tn=Tn-1-1

Al despejar Tn-1 en la segunda ecuación y sustituyendo la primera se obtiene

Tn+Tn-1=i=0nti
Es decir que

2Tn= i=0nti+1

Como Σti, es fija eindependiente de la secuencia de procesamiento, entonces minimizar E (Tn) equivale a minimizar E (I). Como I se minimiza cuando se minimiza el tiempo del ultimo trabajo, se programan los trabajos en orden de tiempos esperados de procesamiento decrecientes.

El caso del taller de flujo con dos maquinas

Una ecuación interesante es si hay un análogo estocástico al algoritmo de Johnson para programar ntrabajos en dos maquinas, en un entorno de taller de flujo; esto es, cuando debe procesarse cada trabajo primero en la maquina 1, y después en la maquina 2; el algoritmo de Johnson afirma que el trabajo i precede al trabajo i+1 si

mín (Ai+Bi+1) <min (Ai+1,Bi)

E mínAi,Bi+1=1ai+bi+1

E mínAi+1,Bi= 1ai+1+bi

| Tiempos esperados | Tasas | |
Trabajo | A | B | A | B | Diferencias |
1| 5 | 2 | .20 | .500 | -.30 |
2 | 1 | 6 | 1.00 | .170 | .83 |
3 | 9 | 7 | .11 | .143 | -.033 |
4 | 3 | 8 | .33 | .125 | .21 |
5 | 10 | 4 | .10 | .250 | -.15 |

Al ordenar los trabajo según los valores decrecientes en la columna final se obtiene la secuencia.
2-4-3-5-1

Programación estocástica: análisis dinámico

Los algoritmos de programación aquí descritos se basan en el...