Problema de la Ejecución de las n tareas

De Wikipedia, la enciclopedia libre

El presente artículo se encuadra en la Programación dinámica (computación). Para otros enfoques de la Programación dinámica ver Programación dinámica (investigacición operativa)

Este artículo debería estar en Wikilibros ya que es una guía o manual en vez de un verdadero artículo enciclopédico.
Si modificas este artículo dándole una orientación enciclopédica, elimina por favor esta plantilla.

[editar] Descripción detallada del problema

Una serie de n tareas ha de ser procesada en un sistema que cuenta con dos procesadores A y B. Para cada tarea i se conocen los tiempos ai, bi que cada procesador tardaría en procesar. Una tarea no puede dividirse entre los dos procesadores. Obtener un procedimiento para organizar las tareas entre los dos procesadores de forma que el tiempo total de ejecución de las mismas sea el mínimo.

[editar] Una primera aproximación

En primer lugar, definimos la función

tiempo(i, $T A$ , $T B$ ) = tMin

siendo tMin el tiempo mínimo para procesar las i primeras tareas, cuando el procesador A está ocupado un tiempo $T A$ y el procesador B un tiempo $T B$ .

El valor buscado con este planteamiento sería, por tanto, tiempo(n,0,0). Cuando asignamos la tarea i podermos asegnarla a uno u otro procesador, y quedarnos con la mejor opción. El resto del reparto se tiene que hacer de forma óptima, es decir, se cumple el principio de optimalidad de Bellman, por lo que

tiempo(i, $T A$ , $T B$ ) = mín{tiempo(i-1, $T A$ +ai, $T B$ ), tiempo(i-1, $T A$ , $T B$ +bi)}

con $1 \le i \le n, 0 \le TA \le \sum_{l=1}^n a_l$ y $0 \le \sum_{l=1}^n b_l$ (los límites de $T A$ y $T B$ habrán de redefinirse en la implementación).

El caso básico se presenta cuando ya no quedan tareas que asignar, en cuyo caso el tiempo necesario para terminar todas las tareas será el máximo de los tiempos de proceso en cada procesador,

tiempo(0,TA,TB) = máx{TA,TB}

En este caso, utilizaríamos una matriz tridimensional tiempo[0..n, 0..SA, 0..SB] donde SA=Sumatorio y SB=Sumatorio, siendo, como apuntábamos anteriormente, cuidadoso con los rangos de los índices en la implementación.

El coste del algoritmo está en 0(n SA SB) tanto en tiempo (por los tres bucles necesarios en su implementación) como en espacio adicional (por la matriz tridimensional).

[editar] Una solución más eficiente

Para abordar este problema, usaremos una idea más sofisticada para optimizar el tiempo y espacio adicional del algoritmo. Lo que guardaremos será la diferencia entre el tiempo ocupado en el procesador A y el tiempo ocupado en el procesador B. Si A tarda más que B en ejecutar las tareas que tiene asignadas la diferencia será positiva, siendo negativa en el caso contrario.

En este supuesto, la función que definimos será la siguiente:

tiempo(i, d) = tMin2

siendo tMin2 = tiempo mínimo para procesar las i primeras tareas, partiendo del tiempo inicial (d,0) si $d \le 0$ , o del tiempo inicial (0,-d) si $d < 0$ .

Hay que notar que solo guardamos como argumento la diferencia entre los tiempos de los procesadores. Esto habrá que tenerlo en cuenta a la hora de efectuar las llamadas recursivas.

El valor buscado es tiempo(n,0), el tiempo óptimo que tardan en ejecutarse todas las tareas cuando los dos procesadores están inicialmente libres, y por tanto la diferencia de tiempos es 0.

Veamos qué posibilidades hay al asignar la tarea i. Distinguimos casos según el signo de d:

si (el procesador A va por delante), entonces podemos
- asignar la tarea i al procesador A, por lo que la diferencia de tiempos aumenta y no cambia el tiempo acumulado (porque sigue siendo igual en ambos procesadores)
- asignar la tarea i al procesador B, por lo que la diferencia disminuye (pudiendo llegar a ser negativa), y el tiempo acumulado tiene que incrementarse.

Por tanto, en este caso, y ya que el resto de las tareas tiene que asignarse de forma óptima (cumpliendo el principio de optimalidad), la función se define de la siguiente manera:

tiempo(i,d) = mín {tiempo(i-1,d+ai), tiempo(i-1,d-bi)+mín{d,bi}}

si $d < 0$ la distinción de casos es análoga y simétrica a la anterior, pero ahora hay que tener cuidado con el signo de d. La función se define como:

tiempo(i,d) = mín {tiempo(i-1,d+ai)+mín{d,ai}, tiempo(i-1,d-bi)}

El caso básico se presenta cuando ya no hay más tareas que asignar. En ese caso, definimos

tiempo(0,d) = |d|

dado que si no hay tareas que asignarr, el tiempo consumido es el máximo entre los tiempos de los dos procesadores, pero como la situación ahora es (d,0) o (0,-d) (dependiendo del signo de d), el máximo es el valor absoluto de d.

Utilizamos una matriz tiempo[0..n,-SB..SA] donde SA=Sumatorio y SB=sumatorio, que rellenaremos por filas y de arriba abajo y por columnas de izquierda a derecha. Igual que en el apartado anterior, habrá que ser cuidadoso con los índices, para no hacer accesos fuera de la matriz. No podemos reducir el espacio adicional a un vector, porque querremos recuperar la asignación de tareas.

El algoritmo sería de coste 0(n (SA+SB)), tanto en tiempo como en espacio.

[editar] Implementación

fun dos-procesadores(A[1..n], B[1..n] de nat+, SA,SB : nat+) dev (tiempo-optimo : nat, asignacion[1..n] de procesador)
// el programa i se procesará en la asignación [i]
var tiempo[0..n,-SB..SA] de nat
  // inicializacion
  para j= -SB hasta SA hacer
    tiempo[0,j]:= abs(j);
  fpara
  // rellenar la matriz
  suma-A := SA; suma-B := SB;
  para i=1 hasta n hacer
    suma-A:=suma-A - A[i];
    suma-B:=suma-B - B[i];
    para j=suma-B hasta -1 paso -1 hacer
      tiempo[i,j]:=min(tiempo[i-1, j+A[i]]+min(-j,A[i]),tiempo[i-1,j-B[i]]);
    fpara
    para j=0 hasta suma-A hacer
      tiempo[i,j]:=min(tiempo[i-1, j+A[i]],tiempo[i-1,j-B[i]]+min(j,B[i]));
    fpara
  fpara
  tiempo-optimo:=tiempo[n,0];
  // cálculo de la solución
  d:=0;
  para i=n hasta 1 paso -1 hacer
    si d>= 0 entonces
      si tiempo[i,d]=tiempo[i-1,d+A[i]] entonces
        asignacion[i]:=proc-a; 
        d:=d+A[i];
      sino
        asignacion[i]:=proc-b;
        d:=d-B[i];
      fsi
    sino
      si tiempo[i,d]=tiempo[i-1,d-B[i]] entonces
        asignacion[i]:=proc-b;
        d:=d-B[i];
      sino
        asingacion[i]:=proc-a;
        d:=d+A[i];
      fsi
    fsi
  fpara
 ffun