Expo De Teoria Colas (version Ppt)

Teoría de Colas (2009 I) Integrantes: Johana Alcalde Diego Cueva César Pacherres

Profesora: Dra. María Isabel Landeras Pilco

“No importa en qué cola se sitúe: La otra siempre avanzará más rápido” (Primera Ley de Harper) “Y si se cambia de cola, aquélla en la que estaba al principio empezará a ir más deprisa” (Segunda Ley de Harper)

Las colas son una cosa normal en nuestra sociedad

Siempre que existe más de un usuario de un recurso limitado se puede formar una cola o línea de espera. Cuando la cola se compone de objetos inanimados

(materiales) que esperan algún tipo de procesamiento, el problema es básicamente económico, cuánto equipo hay que comprar y otras preguntas similares. Cuando la cola está formada por personas que esperan un servicio, el problema tiene aspectos psicológicos además de los económicos, que además son bastante más difíciles de cuantificar.

Precios:

Precios:

Servicio: Malo

Servicio: Bueno

Teoría de Colas Es el estudio matemático del comportamiento de

líneas de espera. Se presenta una cuando los “clientes” llegan a un “lugar” demandando un servicio a un “servidor”, el cual tiene una cierta capacidad de atención. Si el servidor no está disponible inmediatamente y el cliente decide esperar, entonces se forma la línea de espera. La teoría de colas en sí no resuelve este problema,

sólo proporciona información para la toma de decisiones

Es una formulación matemática para la

optimización de sistemas en que interactúan dos procesos normalmente aleatorios: un proceso de “llegada de clientes” y un proceso de “servicio a los clientes”, en los que existen fenómenos de “acumulación de clientes en espera del servicio”, y donde existen reglas definidas (prioridades) para la “prestación del servicio”.

El origen de la Teoría de Colas está en el esfuerzo de Agner Kraup Erlang (Dinamarca, 1878 - 1929) en 1909 para analizar la congestión de tráfico telefónico con el objetivo de cumplir la demanda incierta de servicios en el sistema telefónico de Copenhague

Problemas Administrativos Relacionados Problemas de análisis: análisis Necesita responder una o más de las siguientes preguntas:  ¿Cuál es el tiempo promedio que un …  ¿Qué fracción del tiempo toma atender …  ¿Cuáles son el número promedio … Se tomaran decisiones como emplear o no a más gente; agregar una estación de trabajo adicional para mejorar el nivel de servicio; o si es necesario o no aumentar el tamaño de área de espera.

Problemas de diseño: Diseñar las características de un sistema puede implicar el planteamiento de preguntas como las siguientes:  ¿Cuántas personas o estaciones deben empelarse …  ¿Deberán los clientes esperar en un sola fila o en diferentes …  ¿Qué tanto espacio se necesita para que los clientes o los productos puedan esperar… Estas decisiones de diseño se toman mediante la evaluación de los meritos de las diferentes alternativas.

Costes Asociados a un S. de colas a) Los costes asociados a la espera de los clientes  Por ejemplo, el valor del tiempo perdido o la gasolina malgastada en los atascos o los semáforos, o las horas perdidas en las Colas de las urnas electorales (valor normalmente estimado). b) Los costes asociados a la expansión de la capacidad de servicio  El coste asociado a incrementar la capacidad de servicio crezca con alguna proporcionalidad en relación a esta capacidad; por ejemplo anterior, los costes de salarios, despachos, ayudantes, etc.

c) Los costes totales del sistema de servicio La suma de los dos costes anteriores da una función de costes totales del sistema en función de la capacidad, que tendrá una forma similar a la siguiente:

Costo de servidor por unidad de tiempo * número de servidores + Costo por cliente por unidad de tiempo * número esperado de clientes en el sistema

Estado Transitorio y Estado Estable

Estructura Básica de la Línea de Espera El fenómeno de colas se compone,

básicamente de seis elementos principales:

Fuente de entrada o población potencial: Es un conjunto de individuos (no

necesariamente seres vivos) que pueden llegar a solicitar el servicio en cuestión. Podemos considerarla finita o infinita. Aunque el caso de infinitud no es realista, sí permite (por extraño que parezca) resolver de forma más sencilla muchas situaciones en las que, en realidad, la población es finita pero muy grande. Cliente es todo individuo de la población

potencial que solicita servicio.

Proceso de llegada El proceso de llegada es la forma en que los clientes llegan a solicitar un servicio. La característica más importante del proceso de llegada es el tiempo entre llegadas, que es la cantidad de tiempo entre dos llegadas sucesivas. Este lapso es importante porque mientras menor sea el intervalo de tiempo, con más frecuencia llegan los clientes, lo cual aumenta la demanda de servidores disponibles.

Proceso de llegada Existen dos clases básicas de tiempos entre llegadas: Determinísticos, en el cual clientes sucesivos llegan en un mismo intervalo de tiempo, fijo y conocido. Un ejemplo clásico es el caso de una línea de ensamblaje, en donde los artículos llegan a una estación en intervalos de tiempo invariables (conocidos como ciclos de tiempo). Probabilístico, en el cual el tiempo entre llegadas sucesivas es

incierto y variable. Los tiempos entre llegadas probabilísticas se describen mediante una distribución de probabilidad.

Cola La cola, propiamente dicha, es el conjunto de clientes

que hacen espera, es decir los clientes que ya han solicitado el servicio pero que aún no han pasado al mecanismo de servicio. Los tipos de cliente en relación a la conducta se denominan: Impaciente Si hay Cola abandona el Sistema Paciente / rechazo

Si la Cola supera un límite definido para cada cliente, abandona el Sistema

Paciente / abandono

Aguanta la Cola durante un cierto tiempo

Paciente / Permanencia

Aguanta hasta ser atendido

Disciplina de la cola Es el modo en el que los clientes son seleccionados para ser servidos. Las disciplinas más habituales son: La disciplina FIFO (first in first out), también llamada

FCFS (first come first served): según la cual se atiende primero al cliente que antes haya llegado. La disciplina LIFO (last in first out), también conocida como LCFS (last come first served) o pila: que consiste en atender primero al cliente que ha llegado el último. La RSS (random selection of service), o SIRO (service in random order), que selecciona a los clientes de forma aleatoria.

Mecanismo de Servicio Es el procedimiento por el cual se da servicio a los

clientes que lo solicitan. Para determinar totalmente el mecanismo de servicio debemos conocer el número de servidores de dicho mecanismo (si dicho número fuese aleatorio, la distribución de probabilidad del mismo) y la distribución de probabilidad del tiempo que le lleva a cada servidor dar un servicio. En caso de que los servidores tengan distinta destreza para dar el servicio, se debe especificar la distribución del tiempo de servicio para cada uno.

En función del número de estaciones (canales) de

servicio y de las fases del proceso de servicio, tenemos los siguientes tipos de problemas de Colas: Canales

Fases

Ejemplos típicos

Uno

Una

Kiosco de prensa con un empleado

Uno

Varias

Lavado / secado de coches

Varios

Una

Oficina bancaria con varios cajeros

Varios

Varias

Centro de servicios radiológicos de hospital

Salida Los procesos de salida son de los siguientes dos tipos: Los elementos abandonan completamente el sistema después de ser atendidos, lo que tiene como resultado un sistema de colas de un paso. Por ejemplo, los clientes de un banco esperan en una sola fila, son atendidos por uno de los tres cajeros y, después de que son atendidos, abandonan el sistema. Los productos, ya que son procesados en una estación de trabajo, son trasladados a alguna otra para someterlos a otro tipo de proceso, lo que tiene como resultado una red de colas. Por ejemplo, los productos primero son procesados en la estación de trabajo A y después enviados a la estación B o C. Los productos terminados en ambas estaciones, B y C, luego son procesados en la estación D, antes de abandonar el sistema.

El sistema de la cola es el conjunto formado por

la cola y el mecanismo de servicio, junto con la disciplina de la cola, que es lo que nos indica el criterio de qué cliente de la cola elegir para pasar al mecanismo de servicio.

Notación Kendall David Kendall introdujo una notación de colas

A/B/C en 1953. La notación de Kendall se utiliza para describir un sistema de colas, definiendo sus características:

(a/b/c):(d/e/f)

(a/b/c):(d/e/f) Distribución de llegadas: Un código que describe el proceso de llegada. Los códigos usados son:  M para “Makoviano” (la tasa de llegadas sigue una distribución de Poisson), significando una distribución exponencial para los tiempos entre llegadas.  D para unos tiempos entre llegadas "deterministas".  G para una "distribución general" de los tiempos entre llegadas, o del régimen de llegadas.º

(a/b/c):(d/e/f) Distribución de tiempo de servicio (o de salidas): Un código similar que representa el proceso de servicio (tiempo de servicio). Se usan los mismos símbolos. La distribución exponencial es generalmente utilizada para describir el tiempo de servicio, esto es, debido a su propiedad memoryless.

(a/b/c):(d/e/f) Número de canales de servicio (o servidores): Es el número de servidores en paralelo (c=1,2,….,n). El sistema más simple considera un sólo servidor, es decir c=1, por lo tanto, el sistema atiende sólo a un cliente a la vez. En cambio, para uno multiservidor, con c=s, se pueden atender s clientes simultáneamente. En un sistema con infinitos servidores, cada cliente que arriba al sistema es atendido inmediatamente.

(a/b/c):(d/e/f) Disciplina de servicio: El orden de prioridad en la que los trabajos en la cola son servidos, la regla con que se seleccionará al próximo cliente que recibirá servicio, son:  First Come First Served (FCFS) ó First In First Out

(FIFO)  Last Come First Served (LCFS) o Last In First Out (LIFO)  Service In Random Order (SIRO)  Prioridad (PRI)

(a/b/c):(d/e/f) Número máximo admitido en el sistema (línea de espera+servicio ): La capacidad del sistema, o el número máximo de clientes permitidos en el sistema incluyendo esos en servicio. Cuando el número está al máximo, las llegadas siguientes son rechazadas. Puede haber n recursos (servidores) y hasta n usuarios como máximo; si llega el usuario n+1, es rechazado. Este modelo es el que se aplica en telefonía convencional. Otro caso particular es donde la capacidad del sistema es ilimitada, aunque haya sólo n recursos; en caso de llegar el recurso número n+1, pasará a una cola de espera, pero no es rechazado.

(a/b/c):(d/e/f) El tamaño del origen: El tamaño de la población desde donde los clientes vienen. Esto limita la tasa de llegadas. Puede ser infinita (se considera infinita cuando son cantidades muy grandes por simplicidad) o haber un número establecido de clientes para el sistema que requieren un servicio.

La distribución Poisson

Esta distribución es muy frecuente en los problemas relacionados con la investigación operativa, sobre todo en el área de la gestión de colas. Suele describir, por ejemplo, la llegada de pacientes a un ambulatorio, las llamadas a una centralita telefónica, la llegada de coches a un túnel de lavado, el número de accidentes en un cruce, etc. Todos estos ejemplos tienen un punto en común: todos ellos pueden ser descritos por una variable aleatoria discreta que tiene valores no negativos enteros (0,1,2,3,4…). El número de pacientes que llegan al ambulatorio en un intervalo de 15 minutos puede ser igual, a 0, 1, 2 3.

La distribución Exponencial Mientras que la distribución de Poisson describe las llegadas por unidad de tiempo, la distribución exponencial estudia el tiempo entre cada una de estas llegadas. Esta distribución se utiliza mucho para describir el tiempo entre eventos, más específicamente, la variable aleatoria que representa el tiempo necesario para servir a la llegada. Ejemplos típicos de esta situación son el tiempo que un médico dedica a una exploración, el tiempo de servir una medicina en una farmacia, o el tiempo de atender a una urgencia. El uso de la distribución exponencial supone que los tiempos de servicio son aleatorios, es decir, que un tiempo de servicio determinado no depende de otro servicio realizado anteriormente, ni de la posible cola que pueda estar formándose.

Medidas de Rendimiento Comunes Existen muchas medidas de rendimiento

diferentes que se utilizan para evaluar un sistema de colas en estado estable. Para diseñar y poner en operación un sistema de colas, por lo general, los administradores se preocupan por el nivel de servicio que recibe un cliente, así como el uso apropiado de las instalaciones de servicio de la empresa.

Preguntas relacionadas con el tiempo, centradas en el cliente ¿Cuál es el tiempo promedio que un cliente recién llegado tiene que esperar en la fila antes de ser atendido? Medida de rendimiento Asociada : tiempo promedio de espera(Wq ) ¿Cuál es el tiempo que un cliente invierte en el sistema entero, incluyendo el tiempo de espera y el de servicio?. Medida de rendimiento Asociada: tiempo promedio en el sistema(W )

Preguntas cuantitativas relacionadas al número de cliente En promedio ¿cuántos clientes están esperando en la cola para ser atendidos? Medida de rendimiento Asociada : longitud media de la cola(Lq ). ¿Cuál es el número promedio de clientes en el sistema?. Medida de rendimiento Asociada : número medio en el sistema(L)

Preguntas probabilísticas que implican tanto a los clientes como a los servidores ¿Cuál es la probabilidad de que un cliente tenga que esperar a ser atendido?. Medida de rendimiento Asociada : Probabilidad de bloqueo(pw ) En cualquier tiempo particular, ¿cuál es la probabilidad de que un servidor esté ocupado?. Medida de rendimiento Asociada : la utilización (U.) ¿Cuál es la probabilidad de que existan n clientes en el sistema?. Medida de rendimiento Asociada : la probabilidad Po, probabilidad Pi

Si el espacio de espera es finito, ¿Cuál es la

probabilidad de que la cola esté llena y que un cliente que llega no sea atendido?. Medida de rendimiento Asociada : probabilidad de negación del servicio(Pd )

Preguntas relacionadas con los costos ¿Cuál es el costo por unidad de tiempo por

operar el sistema? ¿Cuántas estaciones de trabajo se necesitan para lograr mayor efectividad en los costos? El cálculo específico de estas medidas de rendimiento depende de la clase de sistema de colas.

Relación entre medidas de rendimiento El cálculo de muchas de las medidas de

rendimiento depende de los procesos de llegadas y de servicio del sistema de colas en específico. Estos procesos son descritos matemáticamente mediante distribuciones de llegada y de servicio. λ = número promedio de llegadas por unidad de

tiempo  µ = número promedio de clientes atendidos por unidad de tiempo en una sección

Terminología Estándar Estado del Sistema

=

Número de clientes en el sistema

Longitud de la Cola

=

Número de clientes que esperan servicio

N(t)

=

Número de clientes en el sistema de colas en el instante t

Pn(t)

=

Probabilidad de que exactamente n clientes estén en el sistema en el instante t

s

=

Número de servidores (canales de servicio en paralelo)

λ

=

Tasa media de llegadas (número esperado de llegadas por unidad de tiempo) de nuevos cientes cuando hay n clientes en el sistema

µn

=

Tasa media de servicio para todo el sistema (número esperado de clientes que completan su servicio por unidad de tiempo) cuando hay n clientes en el sistema

Pn

=

Probabilidad de que exactamente n clientes se encuentren en el sistema.

L Lq

= =

Número esperado de clientes en el sistema Longitud esperada de la cola (excluye los clientes que estén en servicio)

W

=

n

Wq

Tiempo de espera en el sistema (incluido el tiempo de servicio), para cada cliente. = Tiempo de espera en la cola (se excluye el tiempo de servicio), para cada cliente.

Se puede relacionar los últimos términos de esta forma: L= λ ∗W Lq = λ ∗Wq W= Wq+ 1/µ ρ : Es el factor de utilización para la instalación se servicio (fracción esperada de tiempo fue los servidores individuales están ocupados). También puede interpretarse como número promedio de personas siendo atendidas. En la práctica se usa:

ρ =

λ sµ

En la práctica se usa: λ: Cuando λ n es constante µ : Cuando µ n es constante

Objetivos de la Teoría de Colas Identificar el nivel óptimo de capacidad del sistema que

minimiza el coste global del mismo. Evaluar el impacto que las posibles alternativas de modificación de la capacidad del sistema . Establecer un balance equilibrado (“óptimo”). Se suelen plantear aspectos medibles y hay otros valorar externamente; algunas medidas típicas son: Tasa de ocupación de las estaciones de servicio.  Número de clientes en el sistema o en la Cola. 

Hay que prestar atención al tiempo de permanencia en

el sistema o en la cola.

Modelos de Colas 1. (M/M/1);(FIFO/∞ /∞ ) 2. (M/M/1);(FIFO/N/∞ ) 3. (M/M/S);(FIFO/∞ /∞ ) 4. (M/M/S);(FIFO/N/∞ ) 5. (M/M/1) ;(FIFO/K/K) 6. (M/M/S) ;(FIFO/K/K)

(M/M/1);(FIFO/∞ /∞ ) El Banco Nacional de Occidente piensa abrir

una ventanilla de servicio en automóvil para servicio a los clientes. La gerencia estima que los clientes llegarán a una tasa de 15 por hora. El cajero estará en ventanilla puede atender clientes a una tasa de uno cada tres minutos.

(M/M/1);(FIFO/∞ /∞ )

(M/M/1);(FIFO/N/∞ ) Una tienda de bebidas ha determinado que es

económicamente factible añadir una ventanilla para dar servicio a los automóviles, con espacio para dos vehículos: uno en la ventanilla y otro esperando. El dueño quiere saber si le conviene alquilar más espacio de espera.

(M/M/1);(FIFO/N/∞ )

(M/M/S);(FIFO/∞ /∞ ) En un banco, se tiene 4 ventanillas que atiende

a sus clientes para hacer las operaciones financieras que necesiten, ellos en una hora determinada llegan según una distribución de Poisson de 5 clientes por minuto y aproximadamente son atendidos 25 clientes por hora. Se quiere hacer un análisis de colas para ver si se brinda un buen servicio o si es necesario abrir una ventanilla más para atender mejor a los clientes.

(M/M/S);(FIFO/∞ /∞ )

(M/M/S);(FIFO/N/∞ ) Una compañía que brinda el servicio de pintar autos,

tiene 2 equipos que atienden a los autos. Actualmente el local puede albergar a 9 autos, es por ello que se la empresa se ve forzado a rechazar algunos trabajos, pero al lado del local hay un local baldío, que con el cual la capacidad de albergar autos aumentaría a 20 autos en total. El taller ahora tiene una demanda de 21 autos por día, y pueden ser atendidos a 24 autos por día. Se quisiera saber si es conveniente alquilar dicho terreno si o no.

(M/M/S);(FIFO/N/∞ )

(M/M/1) ;(FIFO/K/K) Una empresa de ingeniería, contrata a un

experto técnico, el cual asesora y resuelve problemas a 5 ingenieros de la empresa. Algunos problemas son fáciles y se resuelve de forma rápido pero otras toman tiempo, investigación, cálculos y análisis. Es por ello que cada ingeniero tiene un tiempo limitado de poder consultar al experto, siempre y cuando este haya terminado de resolver un problema.

(M/M/1) ;(FIFO/K/K)

(M/M/S) ;(FIFO/K/K) En una escuela se ha tomado la regla que los

libros no deben salir de la biblioteca, es por ello que se ha puesto 2 fotocopiadoras que atenderá por tarjeta de seguridad a 60 alumnos en total. Se quiere analizar la situación actual y ver si es conveniente y factible el poner en servicio otra fotocopiadora más.

(M/M/S) ;(FIFO/K/K)

 Donde:

Ejemplo de La Comisión de Autopista de Ohio  La Comisión de Autopista de Ohio (Ohio Trunpike Commissiion, OTC) tiene un

número de estaciones para el pesado de camiones a lo largo de la autopista de cuota de Ohio, para verificar que el peso de los vehículos cumple con las regulaciones federales. En la figura se muestra una estación de pesado con dos básculas (servidores).  La administración de OTC está considerando mejorar la calidad del servicio en sus

estaciones de pesado y ha seleccionado una de las instalaciones como modelo a estudiar, antes de instrumentar los cambios.  La administración desea analizar y entender el desempeño del sistema actual

durante las horas pico, cuando llega a la báscula el mayor número de camiones, suponiendo que el sistema puede desempeñarse bien durante este periodo, el servicio en cualquier otro momento será mejor.  En dichas horas pico los camiones llegan en una distribución Poisson de 70 camiones

por hora y cada báscula puede atender a 40 camiones en una hora.

Ejemplo de La Comisión de Autopista de Ohio

Modelo: (M/M/C); (FIFO/∞ /∞ ) Tasa de Llegada

λ = 70 camiones / hora Tasa de Servicio

μ = 40 camiones / hora Factor de utilizacion

Medidas de Rendimiento  Probabilidad de que ningún cliente este en el sistema (P0):

 En este caso : ρ=1.75

y

c=2,

 

 Este valor de P0 indica que aproximadamente 7% del

tiempo, la estación de pesado esta vacía.

Número promedio en la fila (Lq):

Seis camiones esperando a ser atendidos (sin incluir al que ya

está en la báscula).

Tiempo promedio de espera en la cola (Wq):

Aproximadamente 5 minutos, en la fila antes de iniciar el proceso

de pesado.

Tiempo promedio de espera en el sistema (Ws):

Un camión tiene que esperar aproximadamente 7 minutos,

desde que llega hasta que sale de la estación.

Número promedio en el sistema (Ls):

En promedio, se tienen entre siete y ocho camiones

esperando en la estación, ya sea en al bascula o en espera de ser atendidos.

Probabilidad de que un cliente que llega tenga que esperar

(pw):

Este valor indica que aproximadamente 82% de las veces un

camión que llega tiene que esperar

Probabilidad de que haya n clientes en el sistema (Pn):

Si n ≤ c:

Si n > c:

n

Pn

0 1 2

0.06667 0.11667 0.10210

Sumando las dos primeras probabilidades n P de la tabla para n= 0 y 1, se obtiene la

respuesta: 0.18334.

n

3 4 . . .

0.08932 0.07816 . . .

CONCLUSIONES El éxito de una empresa depende del servicio que

brinda al cliente Es muy importante el tiempo que se demora la persona en realizar una operación. La teoría de colas es una gran ayuda para la toma de decisiones administrativas. El tener muchos clientes esperando en cola algún servicio, por largo tiempo, tiende a perder a esos clientes. Al plantear los modelos de colas, se puede analizar de forma precisa el rendimiento del sistema.