Site hosted by Angelfire.com: Build your free website today!

ALGORITMOS PARA LA TOMA DE DESICIONES PARA PROBLEMAS TIPO RENTA-COMPRA

 

 

En un problema sencillo sin conocimiento a priori de la cantidad de tiempo durante la cual se utilizará un recurso dado que podemos rentar el recurso por 100 pesos o comprarlo por X cantidad.

 

En este escrito estudiaremos los algoritmos los cuales nos servirán para tomar una decisión en problemas del tipo renta-compra.

 

Hemos desarrollado un algoritmo que es tanto probabilística como computacionalmente es óptimo.

 

Nuestro algoritmo usa la función O(Öt) en tiempo y espacio, y es un costo esperado para el t-ésimo recurso que converge de valor óptimo como O(Ölog t/t).

 

Describiremos los resultados experimentales para la aplicación de nuestro algoritmo en uno de los problemas más motivantes : la pregunta es “when to spindown” a un disco para ahorrar energía en la computación móvil.

 

Simulaciones usando trazas de acceso al disco obtenidos de un ambiente HP Workstation sugiere que nuestro algoritmo provee significativas improvisaciones en cuanto al desempeño energía/tiempo de respuesta.

 

        

Introducción

 

Un problema sencillo del tipo rentar-comprar puede ser descrito de la siguiente manera:

 

Necesitamos un recurso para un lapso de tiempo desconocido. Tenemos la opción de rentarlo por 100 pesos por unidad de tiempo o comprarlo de una vez por X pesos.

 

Pero ¿qué tanto debemos rentar el recurso antes de comprarlo?

 

Compraremos el recursos inmediatamente si el recurso se requerirá por lo menos c unidades de tiempo y lo rentaremos en otro caso.

 

Un algoritmo en línea (es aquel en el cual no se tiene conocimiento a priori de qué tanto tiempo el recurso será necesario) que renta el recurso por c unidades de tiempo y entonces lo compra, incurre en un costo de más del doble del costo del mejor algoritmo que no está en línea.

 

Este factor de 2 unidades es el mejor posible (para un algoritmo determinismo) en el peor de los casos. Ahora bien, si conocemos la distribución de probabilidad del tiempo en el que el recurso será utilizado, entonces podremos encontrar una estrategia rentar-comprar con la cual esperaríamos reducir el costo de un algoritmo en línea en lugar de esperar c unidades de tiempo antes de comprarlo.

 

Problemas interesantes pueden ser modelados por una “secuencia” de un simple problema del tipo rentar-comprar. Para resolver, digamos el t-ésimo problema simple del tipo rentar-comprar (o la t-ésimo fase) el algoritmo en línea puede usarse cuando se ha aprendido de las t-1 fases.

 

Llamaremos a esta secuencia un problema secuencial del tipo rentar-comprar o simplemente del tipo rentar-comprar.

 

En situaciones de la vida real, asumiremos que el tiempo por el cual un recurso será necesario en cada fase está determinado por una distribución de probabilidad. Sin embargo, no es válido asumir que conocemos la distribución de probabilidad sin tener datos históricos.

Los 3 problemas que pueden ser modelados por una secuencia de desiciones del tipo rentar-comprar son:

 

 

1.     El “spindown disk problem” . El cual involucra tomar decisiones sobre cuándo “to spindown” un disco inactivo en el cómputo móvil para ahorrar energía.

 

 

2.     El problema de girar / bloquear. El cual involucra decidir qué tanto un hilo en la memoria compartida de un sistema multiprocesador debería esperar para bloquear datos y su vez ser liberarse antes del bloqueo, donde el bloqueo invulucra un switcheo excesivo.

 

 

3.     El problema del circuito virtual. El cual consiste en saber qué tanto tiempo un circuito virtual debe estar abierto mientras el tráfico del IP termina un ATM (Modo de transferencia asíncrono).

 

 

El problema del disco “spindown” es nuestra principal motivación para este estudio y se discutirá con detalle en la sección 5.

 

Un algoritmo para un problema del tipo rentar-comprar puede ser visto desde 2 enfoques:

 

 

1er. Enfoque : El algoritmo puede pensarse como la toma de una decisión binaria: ¿Debería comprarlo ahora?

 

2do. Enfoque : Pensar el algoritmo como un conjunto de cutoff (o cortes fuera del costo) que estarán formando parte de los resultados antes de comprarse y procediendo de acuerdo con esos cortes fuera del costo.

 

Estos 2 enfoques son trivialmente equivalentes y por razones de conveniencia adoptaremos el segundo enfoque. De cualquier forma un buen algoritmo en línea deberá cubrir los siguientes 2 requerimientos:

 

1.     El algoritmo deberá producir buenos cortes fuera del costo y deberá usar el menor tiempo posible para generarlos.

 

En este escrito desarrollaremos algoritmos en línea en ambientes probabilísticas para problemas del tipo rentar-comprar asumiendo que el recurso en cuestión usa tiempos que son aleatorios y totalmente independientes a determinar pero asumiendo que la distribución de probabilidad no es conocida.

 

 

2.     La solución recomendada deberá almacenar todos los tiempos en los que se usó un recurso y usar los cortes fuera del costo (puede ser uno sólo) -al quede denotaremos por b-  para la fase actual la cual deberá tener el menor costo total.

 

 

Desarrollaremos un algoritmo a saber, L para el problema del tipo rentar-comprar el cual, al estar ligado a una función de probabilidad tomará valores entre [0,M] para converger al óptimo. Es muy importante que si el t-ésimo redondeo de la última Xt usa O(cÖt) entonces genere los cortes fuera del costo en O(1) y además utilice O[(min{Xt,c})*s + log(cs)] para actualizar las estructuras y asegurar que converge al óptimo.

 

 

 

Denotamos los reales  por la R y los no reales por una R^+ y los enteros positivos por la N

 

Un algoritmo de renta en línea está dado por el costo relativo c >= 1 de la compra. Se rajará en fases donde el t-ésimo redondeo es el primero que se formula en un corte fuera de costo en una cantidad de tiempo que espera la compra.

 

 

Un algoritmo del tipo rentar-comprar define un mapeo de Un€N (R+)n (el cual refiere al recurso usado) a R+ (que el corte fuera de costo que se genera). En otras palabras, el vector A(x1, x2, …., xn) es el corte fuera de costo generado por el algoritmo A en el (t+1)-ésimo redondeo.

 

Si el recurso que se usa en cualquier redondeo es x, entonces el corte fuera de costo está dado por:

 

 

                  X                si x<= b

Costoc(x,b) =

                  b + c            en cualquier otro caso

 

 

Para el problema del spindown en los discos, el recurso usado en el redondeo t, corresponde al t-ésimo tiempo inactivo en el disco y el corte fuera de costo es un “spindown threshold”.

 

Teorema 1. Para cualquier c > 1, M > 1, se aplica el algoritmo L

 

 

3. El algoritmo AЄ

 

Toma como parámetros a Є y a M e intenta alcanzar un costo esperado y dar un redondeo, el cual es a lo más Є unidades mayor que el costo esperado. Cabe aclarar que nos referiremos a un recurso usado en el tiempo como un “ejemplo”

 

Este algoritmo trabaja en 2 etapas:

 

1era. Etapa: Se usa un número de ejemplos para generar un conjunto reducido de cortes fuera de costo. Para el t-ésimo redondeo en la segunda etapa, se evalúa el corte candidato en el t-1 ejemplo anterior y se escoge el corte fuera de costo que tenga un costo mínimo total. Un punto importante de estos pequeños números es que cuando se generan cuidadosamente son suficientes para lograr un costo lo suficientemente pequeño como se describe en la sección 4.2. Así mismo, la actualización de estos cortes fuera de costo pueden hacerlos eficientemente, como se describe en la sección 4.3. Llamaremos un Є tal que 0 < Є < 1/(ln2(M+c) * ln2(M+c)) como un Є

“modificable”. Note que el problema se vuelve trivial si c >= M.

 

3.1  Primera fase

 

En la primera fase, el algoritmo genera los cortes fuera de costo b0, b1, ….., bv al particionar el intervalo [0,M] en v intervalos. Intuitivamente, para que estas estimaciones nos conduzcan a una segunda fase, el algoritmo busca que esos cortes fuera de costo se acercan a 2 casos:

 

1.     Cada intervalo está al menos a una distancia de Є/2 y;

2.     Si un intervalo tiene longitud mayor a Є/2, entonces el más interior de los intervalos tiene al menos Є/2c.

 

Los puntos finales de los intervalos defines los cortes fuera de costo que serán candidatos.

 

 

Diremos que un intervalo satisface el criterio computacional si está a por lo menos a una distancia Є/2 , análogamente, diremos que satisface el criterio de densidad si la probabilidad del intervalo es de al menos Є/2c. En otras palabras, al final de la primera fase, el algoritmo asegura que cada intervalo satisface el criterio computacional y la distancia mayor del intervalo satisface el criterio de densidad). Conceptualmente, podemos pensar en el algoritmo como una generación de intervalos v’ y que cada uno satisface el criterio de densidad , y entonces se generan cortes fuera de costo independientes (descartando intervalos de tamaño cero), para hacer que los intervalos v sea <= que v’ intervalos tales que el criterio computacional se cumple para cada intervalo como resultado de la teoria  vC se obtiene una partición [o,m] dentro de los intervalos v que satisfacen con una probabilidad alta el criterio de densidad.

 

El proceso generate-cutoffs divide  un intervalo intervalo especifico en intervalos w, y se aseguraran de que el intervalo tenga los eficientes “ejemplos” para producirlo.

 

En una primera fase el algoritmo se comporta de manera eficiente en el espacio almacenando la mayor cantidad posible de O(v) para cualquier tiempo. La primera etapa se divide entonces en 3 fases:

 

1.El algoritmo hace particiones en el intervalo de [o,m] y se agrupan en intervalos mayores b.

 

2.En la segunda fase se refieren estos intervalos mayores uno a uno a razón de v’/B. Mientras se refina un intervalo especifico, el algoritmo descarta los “ejemplos” que no caen en un intervalo mayor.

 

3.En la tercera fase el algoritmo aparte los cortes fuera de costo para asegurar que el criterio computacional sea alcanzado.

 

3.2 segunda etapa

 

El algoritmo escoge repetidamente los cortes fuera de costo de entre estos y genera un vector  { bo, b1, ............,bv}. El cual contiene lo mejor de los datos históricos estudiaremos el desempeño del algoritmo en  términos del espacio usado, la tasa de covergencia y el tiempo requerido para las actualizaciones.

 

4.Análisis

 

en la sección 4.1 veremos como el algoritmo puede ser implementado con O(v) y generar cortes fuera de costo aceptables en términos de probabilidad. En la sección 4.2 veremos la distancia que el algoritmo toma  cuando Î tiende a t. En la sección 4.3 veremos una segunda etapa de estrategias que pueden ser actualizadas eficientemente con una estructura de datos tridimensional.

 

4.1 Garantías acerca de la primera etapa.

 

El algoritmo usado en la primera etapa esta dado por el numero de “ejemplos” a usarse en cualquier tiempo mas el número de cortes fuera de costo que se retienen.

 

Las operaciones en la tercera fase de la primera etapa aseguran que cada intervalo satisface el criterio computacional. Diremos que la primera etapa falla si se obtiene que la longitud de un intervalo es < que Î/2 lo cual no satisface el criterio de densidad. El evento que en la primera etapa falla es un subconjunto del evento que se hallara al final de la segunda fase, esto se debe a que un mismo intervalo no satisface los criterios de densidad.