Aplicación del esquema algorítmico voraz (greedy) a planificación de tareas. Casos, demostraciones y ejemplos
- 1. ESQUEMA VORAZPlanificacin de tareas
- http://tecnoacademy.blogspot.com
TECNO ACADEMY Salvador Fernndez Fernndez 2. Planificacin de
tareas
- Un sistema da servicio a n tareas, cada una con un tiempo de
ejecucint iparaientre1yn . Se desea minimizar el tiempo medio de
estancia de una tarea en el sistema, esto es, el tiempo
transcurrido desde el comienzo de todo el proceso hasta que la
tarea termina de ejecutarse. Resolver el problema cuando
- se dispone de un nico procesador
- se tienensprocesadores idnticos
3. a) Se dispone de un nico procesador
- El problema consiste en minimizar
- dondeT ies el tiempo en el sistema de la tareai , y comones
constante, esto equivale a minimizar el tiempo total
- parala tareai ,T i es la suma de su tiempo de ejecucint i ms
todos los tiempos de ejecucin de las tareas que se ejecutan antes
que ella.La planificacin ptima se consigue cuando se atiende a las
tareas por orden creciente de tiempo de ejecucin .
4. a) Se dispone de un nico procesador
- En efecto, supongamos un orden cualquiera de tareas dondenose
considere un orden creciente de tiempos:
- El tiempo total correspondiente a esta permutacin sera:
- Por tanto, la contribucin del tiempo de cada tarea al tiempo
total depende del nmero de tareas que la siguen.
5. a) Se dispone de un nico procesador
- Ya que enIno se ha empleado la estrategia voraz propuesta,
podramos suponer posicionesaybtales queat ib , esto es, posiciones
a y b que siguen un orden decreciente segn su tiempo de ejecucin.
Si las intercambiamos obtenemos una nueva permutacinI
- Ahora el tiempo total queda como
6. a) Se dispone de un nico procesador
- Si restamos los tiempos de la permutacin que no sigue la
estrategia voraz para las posicionesaybde la que s sigue la
estrategia voraz de ordenaraybpor orden creciente de sus tiempos de
ejecucin, determinaremos cul es mejor.
TODA PERMUTACIN QUE COLOCA LAS TAREAS PORORDEN CRECIENTE DE
TIEMPOS DE EJECUCIN ES PTIMA 7. b) Se dispone de s procesadores
idnticos
- Del apartado a) podemos extraer un par de consecuencias tiles
para el caso de varios procesadores. Recordemos.Para
- Hemos demostrado que el tiempo total correspondiente a esta
permutacin sera mnimo cuando ordenamos lost ik por orden
creciente:
LEMA 8. b) Se dispone de s procesadores idnticos
- Adems del lema anterior, debemos recordar que cada tarea
contribuye al tiempo total multiplicando su tiempo de ejecucin por
un factor igual al nmero de tareas pendientes ms uno.
- Observamos que si a un procesadorpse le asignanmtareas y a otro
procesadorpse le asignanm+wtareas, conw> 1 , entonces, el tiempo
de servicio de la primera tarea asignada apse multiplica por un
factorm+w , mientras que si se traslada al primer puesto
enp(desplazando lasmtareas) tendra un factorm+ 1
- Por tanto, cualquier planificacin ptima debe mantener
equilibrada la carga de todos los procesadores, de forma quela
diferencia en el nmero de tareas asignadas sea a lo sumo uno, es
decir, la carga de cada procesador sern div sn div s +1 . Adems, en
caso de que unos procesadores tengan una tarea ms que el resto,
stos sern los primeros.
9. b) Se dispone de s procesadores idnticos El algoritmo voraz
ptimo consistira en considerar de nuevo las tareas ordenadas por
orden creciente de tiempo de ejecucin y repartirlas entre los
procesadores como si de naipes se tratara. s = n de procesadores n
= n total de tareas p i= procesador i n j= n de tareas asignadas a
p j t i j= tarea i-sima dentro de p j 10. Planificacin de
tareas
- Tenemos que ejecutar un conjunto de n tareas, cada una de las
cuales requiere un tiempo unitario. La tareaiproduce unos
beneficiosb i >0slo en el caso de que sea ejecutada en un
instante menor o igual ap i
- Disea una estrategia voraz para maximizar el beneficio total
teniendo en cuenta que pueden quedar tareas sin ejecutar.
- Sera vlida la misma estrategia si el tiempo de ejecucin de cada
tarea fuese arbitrario?
VUELTA ATRS Y RAMIFICACIN Y PODA 11. a) Estrategia voraz para
maximizar el beneficio total
- Diremos que unconjunto de tareas es factiblesi existe alguna
secuencia de ejecucin admisible que permita ejecutar todas las
tareas del conjunto respetando sus respectivos plazos.
- La estrategia voraz que proponemos consiste en ir seleccionando
las tareas de forma que, en cada etapa,se escoja la tarea an no
considerada con mayor beneficio, con la condicin de que el
subconjunto formado siga siendo factible
- Demostracin de optimalidad:
-
- Supondremos las tareas ordenadas por beneficio de forma
decreciente
-
- La estrategia voraz obtiene un conjunto de ndicesI
-
- Otra estrategia ptima, diferente de la voraz, consiste en un
subconjunto de ndicesJ
-
- SeanS iyS jlas secuencias admisibles de tareas de los
subconjuntosIyJ , respectivamente
-
- En general, habr tareas comunes enIy enJ
-
- TransformamosS ienS jde tal forma que dichas tareas comunes se
ejecuten en los mismos instantes, obteniendo secuenciasS i yS j .
Esto siempre es posible ya que:
-
-
- Si la tareaase ejecuta ms tarde enS jque enS i , podemos
modificarS ide la siguiente manera:
-
-
-
- Si en el instanteden el que la tarea a se ejecuta enS j no se
ejecuta ninguna tarea enS ipodemos retrasar la ejecucin deahasta el
instanteden la secuenciaS i , obteniendo una secuencia tambin
admisible
-
-
-
- Si en el instantedya se ejecuta una tareabenS i , podemos
intercambiar las tareasaybobteniendo otra secuencia admisible, ya
que la ejecucin de toda tarea se puede adelantar sin mayor
problema.
-
-
- Si la tareaase ejecuta ms tarde enS ique enS j ,podemos hacer
la misma modificacin pero enS j
12. a) Estrategia voraz para maximizar el beneficio total
- Comparemos ahora las secuenciasS iyS j hasta encontrar una
posicinkdonde difieran:
-
- No puede ocurrir que enS i se ejecute una tarea en el
instanteky ninguna enS j ,porque aadiendo dicha tarea aJobtendremos
un conjunto factible con una suma de beneficios mayor,yJes
ptima.
-
- Tampoco puede ocurrir que se ejecute una tarea enS jy ninguna
enS i ,porque la estrategia voraz al considerar dicha tarea la
habra aadido aI,ya que haba hueco para recolectarla
-
- Por lo tanto, se ejecuta una tareaaenS iy una tareabenS j
.Veamos qu relacin puede haber entre los beneficiosb a yb b
-
-
- Sifuera mayor el beneficiob a ,cambiandoaporbenJobtendramos una
solucin mejor y eso no es posible, ya queJes ptima.
-
-
- Tampoco puede ocurrir queb b >b aporque la estrategia voraz
considera las tareas en orden decreciente de beneficios y habra
considerado antesbquea .
-
-
- Es decir, el nico caso posible esb a= b b
- Se deduce, por tanto, que siS i yS jejecutan tareas distintas
en un mismo instante, estas tareas tienen que producir el mismo
beneficio. Se puede cambiarbporaenJy el beneficio total de ambas
soluciones es el mismo. Sucesivas transformaciones de este estilo
nos llevan a una solucin ptima igual que la solucin voraz.
13. a) Estrategia voraz para maximizar el beneficio total
-
- Un conjunto de tareas T es factible si y slo si la secuencia de
la tareas de T ordenadas de forma creciente segn plazo es
admisible.
- Demostracin de(por reduccin al absurdo):
-
- SeaT = {t 1 , t 2 , , t k } con p 1 p 2 p k tal que la
secuenciat 1 ,t 2 , ,t k no es admisible, es decir, existe alguna
tareat r , r{1,,k}tal quep r< r . Pero entonces se cumple quep 1
p 2 p r-1 p r r-1
-
- Esto demuestra que hayrtareas cuyos plazos son menores o
iguales quer-1y, por tanto, es imposible ejecutar todas las tareas
dentro de su plazo; en otras palabras, el conjunto T no es
factible.Llegada la contradiccin queda demostrado el lema.
- El test de factibilidad consistir en comprobar si la secuencia
de tareas ordenadas por plazos es admisible. Es decir,hay que
comprobar que la tarea ejecutada en la i-sima posicin tenga un
plazo de i o ms . En la implementacin del algoritmo, aunque
suponemos que las tareas vienen ordenadas por beneficio
decreciente, las tareas seleccionadas para su ejecucin se mantendrn
ordenadas por plazo creciente.
14. a) Algoritmo 1
-
- fun planificar(p[1..n], b[1..n] de nat + ) dev (tarea[1..n] de
1..k, k:1..n)
-
- /* tarea[i] es la tarea ejecutada en el instante i, para i
entre 1 y k */
-
- /* k es el nmero total de tareas ejecutadas */
-
- var aux[1..n] de 1..n/* secuencia auxiliar ordenada por plazos
*/
-
- k:=1;aux[1]:=1/* la primera tarea siempre se ejecuta */
-
- /* buscar hueco lo ms tarde posible */
-
- mientras d>0 AND* (p[aux[d]]>=p[i]AND p[aux[d]]>d)
hacer
-
- /* d=0 OR p[aux[d]]max(P[i],d) */
-
- si p[i]>d entonces/* puede ejecutarse */
-
- /* desplazar una unidad de tiempo las tareas posteriores
*/
-
- para j=k hasta d+1 paso -1 hacer
Al margen de la ordenacin de las tareas por beneficio
decreciente (que puede hacerse con un coste en (nlogn)), el coste
del algoritmo est en( n 2 ), ya que en el caso peor hay que
ejecutar todas las tareas, y para cada una de ellas desplazar un
lugar todas las anteriores, lo que equivale a una ordenacin por
insercin de las tareas por plazo creciente 15. a) Estrategia voraz
para maximizar el beneficio total
- Podemos obtener una implementacin ms eficiente basndonos en
este otro LEMA:
-
- Un conjunto de tareas T es factible si y slo si la secuencia de
la tareas de T donde stas se ejecutan lo ms tarde posible es
admisible. Lo ms tarde posible se refiere a que para cada tarea se
elige el instante libre ms tardo que no se pase de plazo, es decir
para cada tarea t iel instante elegido ser
- Demostracin de(por contrarrecproco):
-
- Supongamos que existe alguna tarea enTtal que todos los
instantes antes de que expire su plazopestn ocupados.
Paraw=min{n,p}sear>wel primer instante libre; entonces enThay al
menosrtareas ( r-1puestas ms la que se est intentando colocar) con
plazo menor quer , siendo por tanto imposible ejecutar todas las
tareas deTdentro de su plazo, por lo que el conjuntoTno es
factible.
- Para implementar este test de factibilidaddefinimos una relacin
de equivalencia sobre los instantes de ejecucin . Si
definimoslibre(i)=max {di | d libre},es decir el primer predecesor
libre dei,entoncesiyjestarn en la misma clase si y slo
silibre(i)=libre(j) .Para quelibre(i)est definido incluso si todos
los instantes estn ocupados, se considera tambin el instante 0, que
permanecer siempre libre.La idea es que cada tareat i debera
ejecutarse en el instantelibre(p i ),porque representa el ltimo
instante libre que respeta su plazo.
16. a) Estrategia voraz para maximizar el beneficio total
- libre(i)va cambiando a medida que se va planificando la
ejecucin de las tareas.Inicialmente , como no se ha planificado
ninguna ejecucin, se tiene que para todo i entre1 yn ,libre(i)=i(
cada instante est en una clase de equivalencia diferente );si
ejecutamos la tarea ti en el instantelibre(p i )(siempre que ste no
sea 0), al ocupar dicho instante hay quefusionar la clase de
equivalenciaa la que pertenecelibre(p i )con la correspondiente al
da anterior.
- Para obtener una implementacin eficiente de esta relacin de
equivalencia dinmica recurrimos a una estructura de particin. Como
la implementacin de la estructura de particin no garantiza que el
representante de la clase de equivalencia que devuelve la
operacinbuscarsea el mnimo,que es lo que necesitamos,utilizaremos
un vectorL[0..n]tal queL[i]=libre[i]para todoique sea representante
de una clase de equivalencia.
- Nos limitaremos a considerar los instantes de tiempo que no
sobrepasen los plazos mximos de forma que, aunque declaremos el
conjunto base de la particin como{0,,n} ,la parte til es{0,w} para
w=min{n, max 1i n {p i }}
17. a) Algoritmo 2
-
- fun planificar2(p[1..n], b[1..n] de nat + ) dev (tarea[1..n] de
1..k, k:1..n)
-
- var L[0..n], aux[1..n] de 0..n, particion: particion[0..n]
-
- particion:=crear_particion()
-
- c1:=buscar(p[i],particion)
-
- c2:=buscar(m-1,particion)
-
- fusionar(c1,c2,particion);L[c1]:=L[c2]
/* comprimir solucin */ k:=0 para i=1 hasta l hacer si
aux[i]>0 entonces k:=k+1 aux[k]:=aux[i] fsi fpara
tarea[1..k]:=aux[1..k] ffun 18. a) Algoritmo 2
-
- proc fusionar(a, b: nat + , conjunto[0..n] de nat + )
-
- si altura[a]=altura[b] entonces
-
- si no si altura[a]>altura[b] entonces
-
- fun buscar(x: nat + ,conjunto[0..n] de nat + ) dev (r:nat +
)
-
- /* buscar el rtulo del conjunto que
-
- contiene el elemento x */
-
- mientras conjunto[r]r hacer
-
- /* r es la raz del rbol */
El coste de la fase de inicializacin de este segundo algoritmo,
incluyendo la creacin de la particin, est en (n). En cuanto al
coste del bucle principal se observa que en el peor caso, cuando se
planifican todas las tareas, se realizan 2n bsquedas en la particin
y n fusiones de coste prcticamente lineal, hasta obtener una nica
clase de equivalencia. El coste total del algoritmo est en( nlogn),
una vez considera la ordenacin previa de las tareas. 19. a) Ejemplo
algoritmo 2 Primero, hay que ordenar la matriz segn orden
decreciente de los beneficios a i t i g i b[i] d ip[i] j[ ] aux[ ]
20. a) Ejemplo algoritmo 2 21. a) Ejemplo algoritmo 2 22. b) Es
vlida la estrategia voraz para planificacin con plazo variable?
-
- Supongamos que el beneficio de una tarea slo puede
contabilizarse si la tarea termina su ejecucin dentro del plazo
correspondiente, es decir, si una tarea tiene plazo 4 y su ejecucin
dura dos unidades de tiempo, entonces ha de empezar a ejecutarse en
los tres primeros das.
-
- La estrategia del apartado a) yano es vlidaen este caso. Veamos
un contraejemplo: tenemos 3 tareas, todas con plazo 4, pero
mientras la primera tarda 3 unidades de tiempo en ejecutarse, las
otras dos necesitan 2 das. Supongamos que los beneficios son 10, 8
y 6 respectivamente. Entonces, la estrategia voraz anterior escoger
la primera tarea para empezar a ejecutarla en el primer instante,
por lo que las otras dos tareas jams se ejecutarn y el beneficio se
reduce a10. Sin embargo, es posible ejecutar las otras dos en
cualquier orden y obtener un beneficio de 14
-
- La nica forma de resolver este problema es medianteVuelta Atrs
y Ramificacin y Poda.
23. Estructuras de datos y mtodos algortmicos. Ejercicios
resueltos. Narciso Mart Oliet, Yolanda Ortega Malln y Jos Alberto
Verdejo Lpez. Pearson. Prentice Hall Fundamentos de algoritmia.G.
Brassard y P. Bratley. Prentice Hall Referencias