simulación dr. ignacio ponzoni clase x: sistemas de colas departamento de ciencias e ingeniería de...
TRANSCRIPT
Simulación Dr. Ignacio Ponzoni
Clase X: Sistemas de Colas
Departamento de Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Simulación 2 Prof. Dr. Ignacio Ponzoni
Modelos para Sistemas de Colas
La simulación es frecuentemente utilizada para analizar modelos de colas.
En estos sistemas, típicamente hay un conjunto de entidades que arriban a una o más colas del sistema y uno o más servidores que atienden a dichas entidades.
En general, este tipo de modelos resulta muy útil para estudiar sistemas de servicio, en donde el interés está en estimar distintas medidas de desempeño tales como tiempos de espera promedio, tiempos de servicio promedio, etc.
Simulación 3 Prof. Dr. Ignacio Ponzoni
Técnicas para Analizar Sistemas de Colas
Los modelos de colas pueden ser estudiados a través de métodos matemáticos basados en teoría de colas o empleando simulación.
Para sistemas relativamente simples, las medidas de desempeño del sistema pueden ser computadas más eficientemente usando modelos matemáticos. Sin embargo, para sistemas complejos, la simulación constituye la mejor alternativa.
Simulación 4 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Clientes y Servidores
Los modelos de colas se centran en las nociones de: “Clientes”, entidades que arriban al sistema, puede referir a
personas, máquinas, camiones, pacientes, aviones, e-mails, facturas, llamadas telefónicas, etc.
“Servidores”, son recursos del sistema que se encargan de atender a los clientes, pueden referirse a recepcionistas, mecánicos, personal médico, etc.
Población de Potenciales
Clientes
Población de Potenciales
Clientes
Cola de Espera de Clientes
ServidorClientes
Simulación 5 Prof. Dr. Ignacio Ponzoni
En general, las entidades de la población arriban a la cola en forma aleatoria.
Las entidades avanzan en la cola hasta eventualmente ser atendidas por el servidor.
Las entidades son atendidas usualmente en el orden en que arriban a la cola.
Los tiempos de servicio son usualmente aleatorios y siguen una distribución probabilística que no cambia en el tiempo.
Los arribos y servicios son definidos mediante una distribución de tiempo entre arribos y tiempos de servicios respectivamente.
Características de los Sistemas de Colas Funcionamiento
Simulación 6 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Modelado del transcurso del Tiempo
Conceptos claves: Estado del sistema: determinado por el número
de entidades que están circulando por el sistema y el estado del servidor (ocioso u ocupado).
Evento: es un conjunto de circunstancias que causan un cambio instantáneo en el estado del sistema.
Reloj de la simulación: es utilizado para marcar el progreso del tiempo en la simulación.
Simulación 7 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Eventos: Arribos y Partidas (o Fin de Servicio)
Arribo
Entidad entra a Servicio
Entidad entra a la Cola de espera
¿Servidor Ocupado?
SiNo
Evento ARRIBO Evento PARTIDA
Partida
Remover la entidad al frente de la Cola
¿Hay entidades en la Cola de espera?
Comienza el tiempo ocioso del servidor
Comienza un nuevo tiempo de servicio
No Si
Simulación 8 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Población de Potenciales Clientes La población de potenciales clientes puede ser finita o infinita. En general,
para problemas con una población muy grande, se asume que esta es infinita.
La principal diferencia entre un modelo de población infinita y uno de población finita está en como se define la tasa de arribos:
Con población infinita, la tasa de arribos es el número promedio de arribos por unidad de tiempo (por ejemplo, 8 arribos por minuto), y es independiente del número de clientes que ya estén en la cola o que ya hayan dejado la cola. Además, si el proceso de arribos es homogéneo, entonces la tasa de arribos se asume constante, es decir, en cada unidad de tiempo arriba aproximadamente igual cantidad de clientes.
Con población finita, la tasa de arribos depende de la cantidad de clientes que se encuentran en la cola y los clientes que ya han sido atendidos. En estos casos, la tasa de arribo varia a lo largo de la simulación en función del estado del sistema.
Simulación 9 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Capacidad del Sistema
En muchos sistemas existe una cantidad límite de clientes que pueden esperar en la cola. Esta limitación está generalmente relacionada con la capacidad de la cola en el sistema real que se está modelando.
Por ejemplo, la cola de clientes en un cine puede continuar en la vereda de las calles que lo circundan, luego está cola tiene una capacidad “potencialmente” infinita.
En cambio, la máxima cantidad de programas esperando ejecución en un buffer de memoria de una computadora depende de la capacidad de dicho buffer.
Simulación 10 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Proceso de Arribos
Los procesos de arribos para modelos de población infinita están usualmente caracterizados por los tiempos entre arribos de los sucesivos clientes.
Los arribos pueden ocurrir en forma planificada o aleatoriamente.
Cuando los arribos se producen en forma aleatoria, estos siguen alguna distribución de probabilidades.
Además, los clientes pueden arribar en forma individual o en grupos. El tamaño de dichos grupos puede ser una constante o un valor aleatorio.
Simulación 11 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Procesos de Arribos de Poisson
El proceso de arribos de Poisson es uno de los más empleados en problemas de colas.
Si el tiempo entre arribos An representa el tiempo en el arribo del cliente n-1 y el cliente n, luego, por tratarse de un proceso de Poisson, An está distribuido exponencialmente con media 1/ unidades de tiempo, es decir, arriban clientes por unidad de tiempo.
El número de arribos en un lapso de tiempo t, es decir N(t), tendrá distribución de Poisson con media t clientes.
Los procesos de Poisson se han utilizado con éxito en el modelado de arribos a colas de Bancos, Restaurantes y otros problemas de servicios tales como arribos de llamadas a centrales telefónicas.
Simulación 12 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Otros Procesos de Arribos Una categoría importante de arribos está formada por los arribos
planificados. Por ejemplo, los arribos a un consultorio médico o los arribos al check-in de una aerolínea en un aeropuerto.
En este tipo de modelos los tiempos entre arribos son constantes pero afectados por la suma o resta de un tiempo de “adelanto” o “demora” obtenido en forma aleatoria. Estos tiempos representan los arribos tempranos y tardíos a las colas de los sistemas.
Otra situación especial es cuando se asume que siempre hay al menos un cliente en la cola, con lo cual el servidor nunca está ocioso. Por ejemplo, la producción en serie de automóviles o el procesamiento de embotellado de gaseosas.
Simulación 13 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Arribos en Modelos de Población Finita
En los modelos de población finita los arribos son caracterizados en forma completamente diferente:
Se define un cliente como “pendiente” cuando es miembro de la potencial población de clientes y está afuera del sistema de colas.
El cliente deja estar “pendiente” mientras está en el sistema de colas.
En general, en estos sistemas un mismo cliente arriba y sale de la cola varias veces a lo largo de la simulación.
En estos modelos se denomina tiempo de corrida al lapso de tiempo transcurrido entre que un cliente deja la cola y vuelve a arribar a la misma.
Este tipo de modelos es utilizado en problemas de reparación de máquinas, donde un arribo corresponde al momento en que falla una máquina y una partida al momento en que es reparada.
Simulación 14 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas Comportamiento de Colas
El comportamiento de una cola refiere a las acciones que llevan adelante los clientes mientras esperan en la cola.
Existen distintos tipos de comportamiento, por ejemplo: cuando un cliente llega a una cola demasiado larga puede decidir
abandonar la cola inmediatamente,
otra alternativa es que un cliente decida irse luego de esperar un tiempo en la cola y observar que esta se mueve muy lentamente,
otra situación es cuando un cliente cambia de una cola a otra en función de cómo avanza cada una.
Simulación 15 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas Disciplina de Colas
La disciplina refiere al orden lógico en que los clientes se sitúan dentro de la cola y a la política seguida para determinar que cliente tomar de la cola.
Existen distintas alternativas:
FIFO: el primero en entrar es el primero en ser atendido.
LIFO: el último en entrar es el primero en ser atendido.
SIRO: servicio en orden aleatorio.
SPT: procesar primero al cliente con menor tiempo de servicio.
PR: servir según distintos órdenes de prioridad.
Simulación 16 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Tiempos de Servicio
Los tiempos de servicio para sucesivos arribos se denotan como S1, S2, S3, ..., y pueden ser constantes o aleatorios.
Si son aleatorios, en general la secuencia de tiempos es caracterizada mediante una secuencia de valores aleatorios independientes e igualmente distribuidos.
Las distribuciones más empleadas son: exponencial, Weibull, gama, lognormal y normal truncada.
Algunas veces, los tiempos de servicio pueden seguir distintas distribuciones en función del tipo de cliente, la hora del día que se está simulando, la longitud de la cola de espera, etc.
Simulación 17 Prof. Dr. Ignacio Ponzoni
Características de los Sistemas de Colas
Mecanismos de Servicio
En general, un sistema de colas consiste de un número de centros de servicios y colas interconectadas.
Cada centro de servicio consiste de cierto número de servidores, c, trabajando en paralelo:
Si c = 1, es un sistema de un servidor. Si 0 < c < , es un sistema multiple servidor. Si c = , es un sistema con cantidad de servidores no
limitada (por ejemplo los sistemas de autoservicio).
Simulación 18 Prof. Dr. Ignacio Ponzoni
Notación para Sistemas de Colas
Los sistemas de colas pueden ser denotados con el formato: A / B / c / N / K
Donde A representa la distribución entre arribos B representa la distribución para tiempos de servicio c representa el número de servidores paralelos N representa la capacidad del sistema K representa el tamaño de la potencial población de clientes
Para denotar las distribuciones en A y B, existen varios símbolos:
– M, exponencial o Markov
– D, constantes determinísticas
– Ek, Erlang de orden k
– G, arbitraria o general
Simulación 19 Prof. Dr. Ignacio Ponzoni
Notación para Sistemas de Colas
Otros aspectos de los sistemas de colas se denotan como sigue:
Pn, probabilidad en estado estacionario de tener n clientes en el sistema.
Pn(t), probabilidad de tener n clientes en el sistema en el instante de tiempo t.
, tasa de arribos.
e, tasa efectiva de arribos.
, tasa de servicio.
, utilización del servidor.
An, tiempo entre el arribo del n-1-ésimo cliente y el n-ésimo cliente.
Sn, tiempo de servicio del n-ésimo cliente.
Simulación 20 Prof. Dr. Ignacio Ponzoni
Notación para Sistemas de Colas
Wn, tiempo total que el n-ésimo cliente estuvo en el sistema.
WnQ, tiempo total de espera en la cola del n-ésimo cliente.
L(t), número de clientes en el sistema en el instante t.
LQ(t), número de clientes en la cola en el instante t.
L, número promedio de clientes en el sistema a lo largo de la corrida de la simulación.
LQ, número promedio de clientes en la cola del sistema a lo largo de la corrida de la simulación.
w, cantidad de tiempo promedio que los clientes estuvieron en el sistema a lo largo de la simulación.
wQ, cantidad de tiempo promedio que los clientes estuvieron en la cola a lo largo de la simulación.
Simulación 21 Prof. Dr. Ignacio Ponzoni
Medidas para Análisis de Desempeño
en Sistemas de Colas Las principales medidas de desempeño de sistemas de colas son:
L, número promedio de clientes en el sistema a lo largo de la corrida de la simulación.
LQ, número promedio de clientes en la cola del sistema a lo largo de la corrida de la simulación.
w, cantidad de tiempo promedio que los clientes estuvieron en el sistema a lo largo de la simulación.
wQ, cantidad de tiempo promedio que los clientes estuvieron en la cola a lo largo de la simulación.
, utilización del servidor.
Para estás medidas pueden ser calculadas analíticamente (para algunos sistemas) o estimadas a través de una simulación.
Existen dos tipos de estimadores: promedios ordinarios o ponderados.
Simulación 22 Prof. Dr. Ignacio Ponzoni
Medidas de DesempeñoEstimación de L
Sea T la cantidad total de tiempo que dura la simulación, y Ti la cantidad total de tiempo que el sistema contiene i clientes en el sistema a lo largo de toda la simulación, luego:
Este constituye un ejemplo de estimador de promedio ponderado.
00
)(1ˆ
i
i
ii T
TiTi
TL
TdttL
TL
0).(
1ˆ
Discreta Continua
Simulación 23 Prof. Dr. Ignacio Ponzoni
Medidas de DesempeñoEstimación de LQ
Sea T la cantidad total de tiempo que dura la simulación, y Ti
Q la cantidad total de tiempo en que hay exactamente i clientes esperando en la cola a lo largo de la simulación, luego:
Este constituye otro ejemplo de estimador de promedio ponderado.
Discreta Continua
00
)(1ˆ
i
Qi
i
QiQ T
TiTi
TL
T
QQ dttLT
L0
).(1ˆ
Simulación 24 Prof. Dr. Ignacio Ponzoni
Ejemplo: Planificación de Eventos
Estimación de L(t) y LQ(t)
Número deEvento
Tipo deEvento
Reloj deSimulación
Nº de Clientesen el Sistema
Nº Clientesen la Cola
EstadoServidor
TiempoOcioso
Servidor
1 Arribo 0 1 0 Ocupado 0
2 Arribo 1 2 1 Ocupado 0
3 F. Serv. 2 1 0 Ocupado 0
4 Arribo 3 2 1 Ocupado 0
5 Arribo 4 3 2 Ocupado 0
6 F. Serv. 5 2 1 Ocupado 0
7 Arribo 6 3 2 Ocupado 0
8 F. Serv. 7 2 1 Ocupado 0
9 F. Serv. 9 1 0 Ocupado 0
10 Arribo 10 2 1 Ocupado 0
11 F. Serv. 13 1 0 Ocupado 0
12 F. Serv. 15 0 0 Ocupado 0
Tiempo ocioso acumulado = 0
Simulación 25 Prof. Dr. Ignacio Ponzoni
Ejemplo: Gráfico L(t)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16t
L
1
2
3
Simulación 26 Prof. Dr. Ignacio Ponzoni
Ejemplo: Gráfico LQ(t)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16t
LQ
1
2
3
Simulación 27 Prof. Dr. Ignacio Ponzoni
Medidas de DesempeñoEstimación de w
Si simulamos un sistema de colas durante un período T, luego podemos registrar el tiempo que cada cliente paso en el sistema.
Sea Wi el tiempo que el i-ésimo cliente estuvo en el sistema, y sea N la cantidad de clientes que arribaron al sistema durante el período T, luego:
Este es un ejemplo de estimador de promedio ordinario.
N
iiW
Nw
1
1ˆ
Simulación 28 Prof. Dr. Ignacio Ponzoni
Medidas de DesempeñoEstimación de wQ
Si simulamos un sistema de colas durante un período T, luego podemos registrar el tiempo que cada cliente paso en la cola del sistema.
Sea Wi Q el tiempo de espera en la cola del i-ésimo cliente, y sea N la cantidad de clientes que arribaron al sistema durante el período T, luego:
Este es otro ejemplo de estimador de promedio ordinario.
N
i
QiQ W
Nw
1
1ˆ
Simulación 29 Prof. Dr. Ignacio Ponzoni
Medidas de DesempeñoEcuación de Conservación
La ecuación de la conservación es una propiedad que poseen la mayoría de los sistemas de colas.
Esta propiedad establece que la cantidad promedio de clientes en el sistema en un instante de tiempo t es igual a la cantidad promedio de arribos en una unidad de tiempo multiplicada por el tiempo promedio que un cliente pasa en el sistema.
En nuestra notación esto implica que:
L = .w
Simulación 30 Prof. Dr. Ignacio Ponzoni
Medidas de DesempeñoEstimación de la utilización del
Servidor
Este medida establece la proporción de tiempo que el servidor estuvo ocupado y se denota como .
Utilización del servidor en sistemas de colas G/G/1//
Utilización del servidor en sistemas de colas G/G/c//
donde c es la cantidad de servidores.
1
1.
c
Simulación 31 Prof. Dr. Ignacio Ponzoni
Medidas de DesempeñoCostos en Problemas de Colas
En varias situaciones existen costos asociados con los distintos elementos que conforman un sistema de colas.
Por ejemplo, si tenemos un costo de $x por cada unidad de tiempo que un cliente pasa en la cola, luego el costo promedio
por cliente es:
Por otra parte, si tenemos un costo de $x por cada unidad de tiempo que el servidor está ocupado, luego el costo en un sistema de colas multiservidor por unidad de tiempo será:
Qwx ˆ.$
..$ cx
Simulación 32 Prof. Dr. Ignacio Ponzoni
Redes de Colas
Todos los modelos que hemos considerado hasta ahora tienen una única cola de clientes.
No obstante, existen varios modelos para sistemas de múltiples colas en donde un cliente va pasando a través de distintas colas.
Un caso particular está formado por los sistemas denominados estables con población y capacidad infinita.
Simulación 33 Prof. Dr. Ignacio Ponzoni
Propiedades de las Redes de Colas Estables con Población y Capacidad
Infinita
Previendo que ningún cliente puede ser creado o destruido en la cola, luego, la tasa de partidas efectiva de clientes de una cola es igual a la tasa de arribos efectivos de clientes en la cola al finalizar la corrida.
Si los clientes arriban a la i-ésima cola con una tasa i , y una fracción pij ,0 < pij< 1, de ellos son ruteados a la cola j después de partir de la cola i, luego, la tasa de arribos a la cola j desde la cola i al finalizar la corrida es i .pij.
La tasa de arribo total en la cola j, j, será la suma de las tasas de arribo provenientes de las otras colas más los arribos provenientes del exterior del sistema, los cuales denotamos como aj:
)( ijiall
ijj pa
Simulación 34 Prof. Dr. Ignacio Ponzoni
Propiedades de las Redes de Colas Estables con Población y Capacidad
Infinita
Si la cola j tiene cj< servidores paralelos, con tasa de servicio j , luego la utilización de cada servidor es:
y j < 1 es requerido para que la cola sea estable.
Si, para cada cola j, los arribos desde el exterior de la red forman un proceso de Poisson con tasa aj , y hay cj servidores idénticos con tiempos de servicio distribuidos exponencialmente con media 1/j, luego cada cola j en estado estacionario se comporta como un sistema M/M/cj con tasa de arribos igual a:
jj
jj c
)( ijiall
ijj pa
Simulación 35 Prof. Dr. Ignacio Ponzoni
Recomendaciones
Lectura sugerida: Capítulo 6 (excluidas las secciones 6.4 y
6.5) del libro Discrete-Event System Simulation de Banks y co.
Ejercitación recomendada: Trabajo Práctico 7: Conceptos Básicos de
Simulación de Sistemas de Colas.