Optimizacion De Redes

UNIDAD 1.- Programación dinámica

1.1 Características de los problemas de programación dinámica: etapas, estados, fórmula recursiva, programación en avance y en retroceso

1.2 Algunos ejemplos de modelos de P.D.

1.3 Programación dinámica determinística.

1.4 Programación dinámica probabilística.

1.5 Problema de dimensionalidad en P. D.

1.6 Uso de programas de computación

UNIDAD 2.- Teoría de Colas

2.1 Introducción y casos de aplicación.

Las líneas de espera generan malestar, ineficiencia, retraso y otros problemas, lo que origina un coste de tiempo y económico. Es muy importante evaluar el balance entre el aumento del nivel de servicio y el tamaño de las colas de espera. Por tanto, es necesario entender la relación entre el número de servidores en un sistema (o eficacia de los mismos) y la cantidad de tiempo gastado en la cola (o cantidad de clientes en la misma).

En sistemas de colas sencillos dichas relaciones se pueden encontrar analíticamente. En sistemas más complejos se pueden analizar mediante simulación.

Elementos más importantes en un sistema de colas: clientes y servicio.

Los clientes se caracterizan por los intervalos de tiempo que separan sus llegadas.

El servicio se caracteriza por el tipo y tiempo de servicio, además de por el número de servidores. El tipo de servicio o disciplina representa el orden en el que los clientes se seleccionan de la cola.

Las llegadas de clientes pueden ser deterministas o aleatorios (en este caso se modelan mediante una distribución estadística).

Los tiempos de servicio también pueden ser deterministas o aleatorios (distribución estadística).

Teoría de Colas: Parte de la Investigación Operativa que estudia el comportamiento de sistemas cuyos elementos incluyen líneas de espera (colas).

Teoría de Colas: ejemplos

• Personas esperando por un servicio (bibliotecas, bancos, gasolineras, urgencias en hospital, . . . ),

• Máquinas esperando por una reparación, piezas de un producto esperando a ser ensambladas,

• Programas de ordenador esperando a ser ejecutados por un procesador,

• Información de Internet esperando en un nodo para ser transferida a su destino,

• Aviones esperando a despegar o aterrizar,

Teoría de Colas: historia

Se inicio con A. K. Erlang, en la compañía telefónica estatal de Dinamarca (principios del siglo XX).

Se analizaron los tiempos de espera de llamadas a centralitas automáticas (congestión de tráfico).

• Objetivo: satisfacer la demanda incierta en el sistema telefónico con el menor coste para la compañía.

Aplicaciones de Teoría de Colas

Se pueden usar los resultados de Teor´ıa de Colas para la toma de decisiones: ¿Cuántos servidores emplear en el sistema? ¿Es mejor usar un único servidor rápido o muchos servidores más lentos? ¿Es mejor usar servidores idénticos o servidores específicos?

Objetivo: minimizar el coste total = coste de servicio + coste de espera.

• Coste de servicio: coste al aumentar la capacidad de servicio.

La capacidad del servicio se puede aumentar añadiendo más servidores, s, o haciendo servidores más eficientes, µ , etc.

Habitualmente, la función de coste de servicio viene dada por Css, donde Cs representa el coste por unidad de tiempo y servidor. También se utiliza Cµµ, donde Cµ representa el coste por unidad de tiempo y unidad de tasa de servicio.

• Coste de espera: coste asociado a la espera de los clientes. La espera de clientes genera tiempo perdido, pérdida de los mismos, etc. Habitualmente, la función de coste de espera viene dada por ClL(s), donde Cl denota el coste de espera por unidad de tiempo y cliente y L(s) es el valor esperado del número de clientes en el sistema para s servidores. También se utiliza CwW(µ), donde Cw denota el coste de espera por unidad de tiempo y cliente y W(µ) es el valor esperado del tiempo medio de espera en el sistema para una tasa de servicio de µ unidades.

Ejemplo: ¿cu´antos servidores utilizar?

Un banco dispone de 3 ventanillas de atenci ´on. Los clientes llegan al banco a una tasa de 40 por hora. El tiempo de servicio es de 3 minutos por persona. El banco se plantea si le conviene aumentar el n´umero de ventanillas para satisfacer mejor a los clientes.

El coste que le supone abrir una nueva ventanilla es de 6 euros la hora. El coste de espera se ha estimado en 18 euros la hora.

• Datos: λ = 40 (tasa de llegadas), µ = 60/3 = 20 (tasa de servicio), s = 3 (número de servidores), Cs = 6, Cl = 18.

Ejemplo: ¿un servidor rápido o muchos lentos?

En un servidor de Internet existen 5 nodos que atienden peticiones a razón de 50 por minuto. El tiempo medio de servicio de cada nodo es de 3 segundos por petición. En el servidor se plantean la posibilidad de instalar un único nodo con tiempo de servicio de 1 segundo por petición. ¿Es conveniente esta opción para reducir el tiempo medio de espera en el sistema?

• Datos: λ = 50 (tasa de llegadas), µ = 20 (tasa de servicio) con s = 3 (número de servidores), y µ = 60 con s = 1.

2.2 Definiciones, características y suposiciones.

Elementos de un sistema: Llegadas

Pueden existir una o varias fuentes. Se suele asumir independencia entre llegadas. Intervalos entre llegadas: deterministas o aleatorios. Tasa de llegadas:

λ ≡ n´umero medio de clientes que acceden al sistema por unidad de tiempo. Tiempo medio entre llegadas: 1

λ.

Fuente de entrada

Puede ser infinita o finita (sistemas abiertos o cerrados, respectivamente). Ejemplo de sistema abierto: un banco, ya que es pr´acticamente imposible que todos los posibles clientes coincidan en su llegada. Ejemplo de sistema cerrado: un servidor de Internet con un número relativamente pequeño de usuarios autorizados (es posible que en un momento determinado se conecten todos los usuarios al servidor).

Si la fuente es finita, entonces el número de clientes en la cola afecta al número de clientes fuera del sistema. La llegada puede ser en bloque o de forma unitaria. Frecuentemente el bloque se trata como un solo cliente.

Clientes

Pueden ser impacientes. Por tanto, los clientes se pueden perder, bien porque no entran en el sistema, bien porque abandonan tras un tiempo en el sistema. También, los clientes pueden percibir un ritmo mas acelerado en una cola distinta y por tanto decidir cambiarse.

Cola o canal de espera

Puede ser de uno o varios canales. Puede existir interferencia entre canales. Puede ser de capacidad limitada.

Disciplina de la cola: orden de selección en el servicio (FIFO, LIFO, aleatorio, orden de prioridad, etc.).

Servicio

Pueden existir uno o varios servidores. Se suele asumir independencia entre tiempos de servicio. Duración de los servicios: deterministas o aleatorios.

Tasa de servicio: µ ≡ número medio de clientes que son atendidos por unidad de tiempo.

Tiempo medio de servicio: 1

µ.

Análisis de sistemas de colas

Una vez caracterizado el sistema, se pueden contestar a las siguientes preguntas:

¿Qué proporción de tiempo están los servidores desocupados?

¿Cuál es el tiempo medio de espera para un cliente?, ¿es este un tiempo razonable?, ¿se pierden clientes por tiempos de espera largos?

¿Es conveniente añadir más servidores para reducir el tiempo medio de espera?

¿Cuál es el número medio de clientes en cola? ¿Cual es la probabilidad de que la espera sea mayor que una determinada longitud en un tiempo determinado?

Notación de Kendall: las características del sistema se especifican por los

símbolos:

A/B/s/k/t/d/

Donde A y B denotan las distribuciones de los tiempos entre llegadas y de servicio, respectivamente. s denota el número de servidores en paralelo o canales, k denota la capacidad del sistema, t denota el tamaño de la fuente de entrada, y d es la disciplina de la cola.

La distribución puede ser M Exponencial D Constante o determinista Ek Erlang de parámetro k G Gen´ erica e independiente

• La disciplina puede ser FCFS First come, first served

LCFS Last come, first served

SIRO Service in random order

GD General discipline

Por ejemplo, un sistema que se describe como M/M/1/∞/∞/FCFS denota un sistema abierto que contiene un único servidor con tiempos de llegada y servicios exponenciales, capacidad infinita y disciplina primero que entra, primero que se sirve.

Solo un número pequeño de sistemas se puede resolver analíticamente.

Modelos sencillos: M/M/1/, M/M/s/, M/M/1/k.

Distribuciones

En los sistemas de colas normalmente se asume que tanto las llegadas de clientes como los tiempos de servicio son aleatorios. Es usual suponer que los tiempos entre llegadas y los de servicio se distribuyan de forma exponencial. En este caso, la probabilidad instantánea de ocurrencia de un suceso en la siguiente t unidades de tiempo es:

f(t) = λe−λt para t ≥ 0,

Donde λ denota la tasa de llegadas.

Esta distribución es útil ya que tiene la propiedad de falta de memoria y estacionariedad (el sistema se comporta, transcurrido un plazo, de forma estable e independientemente

...