INVESTIGACION de OPERACIONES

Monday, October 09, 2006

UNIDAD 7. MODELOS DE LÍNEAS DE ESPERA
La teoría de las colas es el estudio matemático de las colas o líneas de espera. La formación de colas es, por supuesto, un fenómeno común que ocurre siempre que la demanda efectiva de un servicio excede a la oferta efectiva.
Con frecuencia, las empresas deben tomar decisiones respecto al caudal de servicios que debe estar preparada para ofrecer. Sin embargo, muchas veces es imposible predecir con exactitud cuándo llegarán los clientes que demandan el servicio y/o cuanto tiempo será necesario para dar ese servicio; es por eso que esas decisiones implican dilemas que hay que resolver con información escasa. Estar preparados para ofrecer todo servicio que se nos solicite en cualquier momento puede implicar mantener recursos ociosos y costos excesivos. Pero, por otro lado, carecer de la capacidad de servicio suficiente causa colas excesivamente largas en ciertos momentos. Cuando los clientes tienen que esperar en una cola para recibir nuestros servicios, están pagando un coste, en tiempo, más alto del que esperaban. Las líneas de espera largas también son costosas por tanto para la empresa ya que producen pérdida de prestigio y pérdida de clientes.
La teoría de las colas en si no resuelve directamente el problema, pero contribuye con la información vital que se requiere para tomar las decisiones concernientes prediciendo algunas características sobre la línea de espera: probabilidad de que se formen, el tiempo de espera promedio.
Pero si utilizamos el concepto de "clientes internos" en la organización de la empresa, asociándolo a la teoría de las colas, nos estaremos aproximando al modelo de organización empresarial "just in time" en el que se trata de minimizar el costo asociado a la ociosidad de recursos en la cadena productiva.


7.1Requisitos para la formulación de un modelo de líneas de espera.
Características de un sistema de colas
Para analizar un sistema de colas, es mejor primero identificar las características importantes que aparecen en la siguiente sección características claves, y que se ilustran en la figura 1.1
Características claves
Las siguientes características se aplican a los sistemas de colas:
Una población de clientes, que es el conjunto de los clientes posibles.
Un proceso de llegada, que es la forma en que llegan los clientes de esa población
Un proceso de colas, que está conformado por (a) la manera que los clientes esperan para ser atendidos y (b) la disciplina de colas, que es la forma en que son elegidos para proporcionarles el servicio.
Un proceso de servicios, que es la forma y la rapidez con la que es atendido el cliente
Proceso de salida, que son de los siguientes dos tipos:
a. 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 como se muestra en la figura 1.2 (a) los clientes de un banco esperan en una sola fila, son atendidos por uno de los tres cajeros y, después que son atendidos abandonan el sistema.









7.2 Sistemas de tiempos uniformes de llegada y de servicio de líneas de espera.
MODELO M / D / 1

Descripción.
Sistema de líneas de espera con llegadas aleatorias, tiempo de servicio constante, una línea de servicio y una línea de espera.
En este modelo los tiempos de servicio son determinísticos, este es un caso especial de la situación M / G / 1 que se analizó con anterioridad, en donde la desviación estándar es igual a cero. En este caso se puede conocer el numero de unidades que están esperando a ser atendidas (Lq), a través de la siguiente ecuación:


Todas las demás características de operación pueden determinarse a partir de este valor. Si utilizamos Lq podemos determinar el valor de L, por medio de la siguiente ecuación:

Al igual que las características de operación de los modelos M / M / 1 y M / S / 1, podemos calcular el tiempo esperado en el sistema de líneas de espera (W), y el tiempo que se invierte antes de ser atendido (Wq), esto lo podemos realizar por medio de las siguientes ecuaciones:






7.3 Modelos de líneas de espera en un solo canal.
MODELO M / G / 1

Descripción.
Sistema de líneas de espera con llegadas aleatorias, distribución general de los tiempos de servicio(para el cual se supone conocida la desviación estándar), un canal de servicio y una línea de espera.
En este modelo las llegadas se distribuyen de acuerdo con la distribución de Poisson, al igual a los casos anteriores, pero los tiempos de servicio no necesariamente se distribuyen de acuerdo con la distribución exponencial negativa. Si consideramos el caso en que solo existe un solo canal, estamos considerando el caso M / G / 1, es decir, llegadas de tipo Markov, tiempo de servicio general y un canal de servicio.
La razón por la que podemos considerar el caso M / G / 1 es que las formulas que se utilizan para calcular sus característicasde operación son bastantes simples. Al igual queen el caso M / M / S, no es posible calcular en forma directa el numero esperado de unidades en el sistema(L). Para esto primero debe de calcularse el numerode unidades que están esperando a ser atendidas(Lq), y utilizar este resultado para calcular el valor de L. Para calcular el valor de Lq debemos de conocer le valor de la desviación(s ) estándarde la distribución que distingue los tiempos de servicio. Si no se conoce la distribución de los tiempos de servicio no es posible determinar las características de operación.
Ahora si conocemos la desviación estándar y la media de la distribución de los tiempos de servicio, puede obtenerse formula para el valor de Lq a partirde la siguiente ecuación.

Si utilizamos Lq podemos determinar el valor de L, por medio de la siguiente ecuación:

Al igual que las características de operación de los modelos M / M / 1 y M / S / 1, podemos calcular el tiempo esperado en el sistema de lineas de espera (W), y el tiempo que se invierte antes de ser atendido(Wq), esto lo podemos realizar por medio de las siguientes ecuaciones:






7.4 Llegadas de poisson de un solo canal con servició exponencial.
MODELO M / M / 1

Este sistema trata de una distribución de llegada Markoviano, tiempo de servicio Markoviano, y un servidor.
Llegadas aleatorias (M / M / 1)
En las situaciones cotidianas es fácil encontrar ejemplos de llegadas aleatorias, puesto que las llegadas serán aleatorias en cualquier caso en la que una de ellas no afecte a las otras. Un ejemplo clásico de llegadas aleatorias son las llamadas que arriban a un conmutador telefónico o un servicio de emergencia.
Se ha determinada que las ocurrencias aleatorias de un tipo especial pueden describirse a través de una distribución discreta de probabilidad bien conocida, la distribución de Poisson. Este tipo especial de llegadas aleatorias supone características acerca de la corriente de entrada. En primer lugar, se supone que las llegadas son por completo independientes entre sí y con respecto al estado del sistema.
En segundo lugar la probabilidad de llegada durante un periodo especifico no depende de cuando ocurre el periodo, sino más bien, depende solo de la longitud del intervalo. Se dicen que estas ocurrencias carecen de memoria".
Si conocemos el numero promedio de ocurrencias por periodo, podemos calcular las probabilidades acerca del numero de eventos que ocurrirán en un periodo determinado, utilizando las probabilidades conocidas de la distribución de Poisson.
En particular, existe un promedio de l llegadas en un periodo, T, la probabilidad de llegadas en el mismo periodo esta dado por:

P[n llegadas en le tiempo T] =
Por ejemplo si existe un promedio de 6 llegadas aleatorias por hora, la probabilidad de que haya solo 3 llegadas durante una hora esta dada por:
P[6 llegadas en le tiempo en una hora] = = 0.0892
Tiempo de servicio aleatorio(M / M / 1)
Al igual que las llegadas aleatorias, la ocurrencia de tiempos de servicios aleatorios, carentes de memoria, es suceso bastante común en las situaciones cotidianasde lineas de espera. Y al igual que las llegadas aleatorias los tiempos de servicio carentes de memoria se describen a través de una distribución de probabilidad.
La diferencia entre las llegadas aleatorias y los tiempos de servicio aleatorios es que estos se describen a través de una distribución continua en tanto que las llegadas se describen a través de una distribución de Poisson, que es discreta. Si la duración de los tiempos de servicio es aleatoria, la distribución exponencial negativa describe ese tipo de servicio. Si la m es la tasa promedio de servicio entonces la distribución esta dada por:
F(t) = m e-m t
Es posible emplear esta formula para calcular la probabilidad de que el servicio sea mas prolongado que alguna duración especificada de tiempo T. En la siguiente figura se representa es modelo.
Características de operación
Para calcular las características de operación de una cola M / M / 1, primero debemos de observar que sí l = tasa promedio de llegadas y m = tasa promedio de servicio, entonces l debe de ser menor que m . Si esto no ocurriera el promedio de llegadas sería superior al numero promedio que se atienden y el numero de unidades que están esperando se volvería infinitamente grande. Si hacemos que r = l / m puede denominarse a r como factor de utilización. Este valor es la fracción promedio de que el sistema este ocupado, también sería el numero promedio de unidades que están siendo atendidas en cualquier momento. En términos de probabilidad tendríamos que:
Pw = probabilidad de que el sistema esté ocupado.

Entonces la probabilidad de que el sistema no esté trabajando, o esté vacío, P0, puede obtenerse por medio de:

A partir de esto podemos obtener la probabilidad de que haya n unidades en el sistema, Pn, mediante:

en donde n es cualquier entero no negativo. Este importante resultado nos permite calcular las características de operación de las líneas de espera.
La primera característica de operación que calculamos es el numero promedio de unidades que se encuentran en el sistema, ya sea esperando o siendo atendidas. Denominaremos a este número promedio de unidades promedio, L. Entonces tenemos que:

Con estos valores obtenidos podemos calcular el numero promedio de unidades que esperan ser atendidas, Lq. Dado que L es el numero de unidades que están esperando o están siendo atendidas, y r es el numero promedio de unidades que están siendo atendidas en algún momento dado entonces:
L = Lq + r
A partir de esto es fácil observar que
Lq = L - r
O también podríamos decir que

Ahora examinaremos el tiempo de espera. Utilizaremos W para representar el tiempo promedio o esperado que una unidad se encuentra en el sistema. Para encontrar W, observaremos que se L el numero esperado de unidades de en le sistema y l es el numero promedio de unidades que llegan para ser atendidas por periodo, entonces el tiempo promedio de cualquier unidad que llega debe estar en le sistema está dado por:
W = tiempo promedio de una unidad en el sistema

De manera similar, el tiempo esperado o promedio que una unidad tiene que esperar antes de ser atendida, Wq, esta dado por:

En la siguiente figura se representa este modelo.

Ejercicio.
A una línea de espera llegan 20 unidades por hora y el tiempo promedio de servicio es de 30 unidades por hora, realizar un análisis de esta línea de espera.
Datos
l = 20 unidades por hora
m = 30 unidades por hora
Con los datos anteriores podemos calcular la probabilidad de que el sistema esté ocupado:
Pw = 20 / 30 = 2 /3
r = Pw
Entonces la probabilidad de que el sistema no esté ocupado:
Po = 1 - r = 1 / 3
El numero esperado de unidades en el sistema quedará definido por:
= 2 Unidades
El numero esperado de unidades que esperan ser atendidas quedará definido por:

Entonces en promedio habrá 4 / 3 de unidades esperando ser atendidas y 2 / 3 de unidad siendo atendida.
de hora
W = 6 minutos
De manera similar, el tiempo promedio que una unidad espera para ser atendida estará definido por:
de hora
Wq = 4 minutos


7.5 Tasa de servicio de costo mínimo de un solo canal (aleatorio) en las líneas de espera.

Al analizar los méritos de contratar personal de reparación adicional en American Weavers, Inc., se deben identificar dos componentes importantes:
1. Un costo por hora basado en el tamaño del personal.
2. Costo total de = Costo por hora para * Numero de personal por hora cada reparador reparadores
3. Un costo por hora basado en el numero de maquinas fuera de operación.
Costo total por = Costo por hora para cada * Numero promedio la espera maquina fuera de operación máquina fuera de operación
Para seguir adelante, se necesita ahora conocer el costo por hora de cada miembro del personal de reparación ( denotado con Cs ) y el costo por hora de una maquina fuera de operación ( denotado Ce ), que es el costo de una hora de producción perdida. Suponga que el departamento de contabilidad le informa que cada reparador le cuesta a la compañía $ 50 por hora, incluyendo impuestos, prestaciones, etc. El costo de una hora de producción perdida deberá incluir costos explícitos, como la cantidad de ganancias no obtenidas, y costos implícitos, como la perdida de voluntad del cliente no se cumple con la fecha limite de entrega.
Sin embargo, suponga que el departamento de contabilidad estima que la compañía pierde $ 100 por cada hora que una maquina este fuera de operación.
Ahora se puede calcular un costo total para cada uno de los tamaños de personal. Para un personal de 7 reparadores, el numero esperado de maquinas en el sistema es 12. 0973.
Costo total = Costo del personal + Costo de la espera
Costo por hora por * Numero de + Costo por hora por * Número persona reparadores cada maquina fuera esperado de de operación máquinas fuera de operación = ( 50 * 7 ) + ( 100 * 12.0973 ) = $ 1559.73 por hora.
Realizando cálculos parecidos para cada uno de los tamaños de personal restantes se tiene como resultado los costos por hora de cada alternativa presentada en la TABLA 3.
De los resultados, se puede ver que la alternativa que tiene el menor costo por hora, $ 1128.63, es tener un total de 9 reparadores. En consecuencia, la recomendación a la gerencia de producción, es contratar a dos reparadores adicionales. Estos dos nuevos empleados tendrán un costo de $ 100 por hora, pero este costo adicional esta mas que justificado por los ahorros que se tendrán con menos maquinas fuera de operación. La recomendación reducirá el costo por hora de $1559.73 a $ 1128.63, un ahorro de aproximadamente $ 430 por hora, mayor que la cantidad que cubre sus honorarios.
TABLA 3: Costo por hora para diferentes tamaños de personal de reparación.
Tamaño de personal Numero esperado en el sistema Costo por hora ($)
7 12.0973 ( 50 * 7 ) + ( 100 * 12.0973 ) = 1559.73
8 7.7436 ( 50 * 8 ) + ( 100 * 7.7436 ) = 1174.36
9 6.7863 ( 50 * 9 ) + ( 100 * 6.7863 ) = 1128.63
10 6.4594 ( 50 * 10 ) + ( 100 * 6.4594 ) = 1145.94
11 6.3330 ( 50 * 11 ) + ( 100 * 6.3330 ) = 1183.30
Características claves
En resumen, para evaluar un sistema de colas en el que usted controla el número servidores o su tasa de servicio, se necesitan las siguientes estimaciones de costos y medidas de rendimiento:
• El costo por servidor por unidad de tiempo (Cs)
• El costo por unidad de tiempo por cliente esperando en el sistema (Ce)
• El número promedio de clientes en el sistema (L)

7.6 Método de Montecarlo.
El Método de Montecarlo
El método de Montecarlo consiste en tomar una solución válida, provocar una pequeña variación aleatoria y, si la nueva configuración es mejor que la anterior y cumple las restricciones, nos quedamos con la nueva; si no, nos quedamos con la antigua. Este metodo planteado de esta forma no convege -aunque llege a un mínimo, sigue operando-. Para que converja, se va haciendo cada vez más pequeña la variación aleatoria. El metodo de Montecarlo puede ni converger en un mínimo, pero el coste es razonable y puede ser aceptado para problemas de mucha complejidad. Otra optimización tradicional es provocar la variación aleatoria de forma que la nueva configuración ya sea válida, mas esto no siempre es posible.

En una fábrica la descompostura entre máquinas es la siguiente.

Tiempo Frecuencia Probabilidad
2 8 0.16
3 10 0.20
4 5 0.10
5 7 0.14
6 11 0.22
7 9 0.18



Generar 10 números aleatorios y obtener el resultado de la simulación respecto del tiempo más probable entre descompostura.


SOLUCIÓN:
Los números aleatorios son los siguientes: 69,92,13,25,34,64,84,31,21,91. (estos datos fueron tomados de la tabla 5 de números aleatorios enteros de dos dígitos de la sección 23-3, Pág. 1201 del libro de Winston Wayne).


Tiempo (min) Frecuencia Probabilidad Probabilidad
Acumulada Rangos
2 8 0.16 0.16 0-15
3 10 0.2 0.36 16-35
4 5 0.10 0.46 36-45
5 7 0.14 0.6 46-59
6 11 0.22 0.82 60-81
7 9 0.18 1 82-99




Número
Aleatorio
Tiempo entre
Descompostura
69 6
92 7
13 2
25 3
34 3
64 6
84 7
31 3
21 3
91 7


Tiempo en Descompostura Frecuencia Porcentaje
Frecuencia/10 *100
2 1 10%
3 4 40%
6 2 20%
7 3 30%



Como se logra ver el tiempo más probable en descompostura es 3 min porque es el porcentaje que nos dio.
Se podrían simular con más números aleatorios digamos 100 y ver que sucede.

SOLUCION: el tiempo promedio o probable de que se descomponga es de 3 min. Según los resultados obtenidos.

7.7 Distribuciones de llegadas y tiempos de espera de un solo canal.

Se ha visto que distribuciones poissonianas de llegada y de tiempo de servicio exponenciales negativas, originan ecuaciones relativamente simples equilibrio para las probabilidades de estado estable. Sin embargo, existen muchas situaciones de la vida real donde tanto la distribución de tiempo entre llegadas como la de tiempo de servicios son apreciablemente diferentes del exponencial.
Aún cuando se han realizado notables avances para describir el comportamiento probabilístico de sistemas de líneas de espera con distribuciones arbitrarias, se han obtenido expresiones relativamente simples para las características de operación sólo para sistemas M/G/1.

Como se dijo anteriormente, en la vida real tanto los tiempos entre llegadas como los tiempos de servicio responden a distribuciones tales como:

- - Poisson
- - Normal
- - Determinístico

Y, según sea el caso, el valor de la varianza de la distribución que regula el ingreso de clientes al sistema ) y el valor de la varianza de la distribución que regula la velocidad de despacho ), asumen los siguientes valores:




Indicadores para Evaluar el Rendimiento de un Sistema de Colas

RELACIONADOS CON EL TIEMPO :
W = Tiempo promedio en el sistema
Wq = Tiempo promedio de espera

RELACIONADOS CON EL NUMERO DE CLIENTES :
L = Número promedio de clientes en el sistema
Lq = Número promedio de clientes en la cola
Pw = Probabilidad de que un cliente que llega tenga que esperar
Pn = Probabilidad de que existan "n" clientes en el sistema
Pn; n = 0, 1, 2, 3.......

Po = Probabilidad de que no hayan clientes en el sistema
Pd = Probabilidad de negación de servicio, o probabilidad de que un cliente que llega no pueda entrar al sistema
debido que la "cola está llena"


7.8 Método de Montecarlo de varios canales usando números aleatorios.
USO DEL MÉTODO DE MONTE CARLO (simulación sobre una muestra artificial)
Explicamos el método valiéndonos de un ejemplo.
Ejemplo 1 – Simulación del número de mostradores de servicio.
El Gerente de una empresa desea determinar el número óptimo de mostradores para un nuevo restaurante. El procedimiento que va a utilizar es el de muestreo simulado aleatorio. Ha decidido simular treinta periodos pico de 1 minuto. Por hipótesis ha supuesto las siguientes distribuciones de llegada y de servicio en el mostrador.
Sean A1, A2, …, A30 el número de clientes que llegan a un mostrador solicitando servicio en el minuto 1, 2, ..., 30. Entonces
P{A1=1} = 1/2 , P{A1=0} = 1/2
P{A2=1} = 1/2 , P{A2=0} = 1/2
.
.
.
P{A30=1} = 1/2 , P{A30=0} = 1/2
Esto es, espera ó 0 ó 1 llegada cada minuto y el número total de llegadas en un período de 30 minutos tiene una distribución binomial.
Para cada período simulará las llegadas lanzando una moneda. Una cara (=1) denota una llegada y un sello (=0) denotará no llegada. De acuerdo a la experiencia pasada, él conoce que el tiempo S que un cliente gasta (invierte) en el mostrador está entre 1 y 6 minutos. El gerente está incierto en la distribución exacta de los
tiempos de servicio. De acuerdo a esto, postula que la distribución del tiempo de servicio es discreta uniforme entre 1 y 6 minutos. Figura

Como se mencionó previamente, se ha decidido simular el tiempo de servicio para cada cliente lanzando un dado. La Tabla 1 da el resultado de simular para un mostrador de servicio. La Columna 2 (debajo de Ai) de la Tabla 1 da el resultado de simular la distribución de llegada para cada período i de 1 minuto. Por ejemplo, llegadas que ocurren en los períodos 1, 2, 4, 6, 7, 9, 11, y así sucesivamente. La Columna 3 (debajo de Si) da el resultado de simular los tiempos de servicio para cada cliente que llega. Por ejemplo, el cliente que llega en el período 1 tiene un tiempo de servicio de 1 minuto, en el período 2 de 3 minutos, en el período 4 de 6 minutos, en el período 6 de 3 minutos y así sucesivamente.


Además,
(En la Columna 4): Bi = tiempo en el cual el cliente que llegó en el período i empieza a recibir servicio.
(En la Columna 5): Ei = tiempo en el cual el cliente que llegó en el periodo i completó su servicio (o dejó el sistema).
Por ejemplo, para el período 1 tenemos
B1 = 1 y E1 = S1 = 1
B2 = 2 puesto que el cliente que llegó al principio del período 1 completó el servicio al final del período 1.
E2 = E1 + S2 = 1 + 3 = 4= (tiempo en que se terminó el servicio del último cliente) +
(tiempo de servicio del cliente 3).
B3 y S3 no tienen valores, pues ningún cliente llegó al principio del período 3.
B4 = E2 + 1 = 4 + 1 = 5
E4 = E2 + S4 = 4 + 6 = 10
En general, para un cliente que llega al principio del período i:
Si él es el único cliente en la cola
Ei - 1 + 1 Si hay un cliente en la cola
y el cliente llegó al comenzar
el período i -1.
También,
Ei = Ei –1 + Si si un cliente que llegó al comenzar el período i – 1, (en la Columna 6 à Wq): Wi denota el tiempo de espera para el i-ésimo cliente.
Ahora
Wi = Bi – i
= (tiempo que el cliente llegó en el período i empezó a recibir servicio) – (tiempo en el que llegó al mostrador).
(En la Columna 7 à Ws): Ti denota el tiempo que el i-ésimo cliente gastó en el sistema = Si + Wi.
Después de completar la simulación estamos en capacidad de estimar las estadísticas importantes que describen el comportamiento de un mostrador, con un servidor como se muestra a continuación.
Tiempo esperado en cola:




Tiempo esperado total de permanencia en el sistema:



La Tabla 2 da el resultado de la simulación del sistema con dos mostradores de verificación. Las primeras tres columnas de la Tabla 2 son idénticas a las columnas correspondientes de la Tabla 1. Las otras fórmulas de cálculo para Ei, Wi y Ti también se aplican al sistema de dos mostradores excepto para la determinación de Bi, el tiempo en que el i-ésimo cliente empieza a recibir servicio.
Ahora Bi se determina por Ei –1 y Ei –2, los dos tiempos de servicio precedentes. Si i > Ei –1 ó i > Ei –2, entonces Bi=i. Si i  Ei –1 o i  Ei –2, entonces Bi=min(Ei –1, Ei –2) + 1.

Tiempo esperado en cola:



Tiempo esperado total de permanencia en el sistema:

Notamos que un mostrador de dos servicios tiene sustancialmente tiempo de espera y tiempo de espera más servicio más bajo por cliente (Tabla 3).

Tabla 3 ESTADÍSTICAS DE SIMULACIÓN
Un mostrador Dos mostradores
Tiempo estimado 10,19 minutos 0,44 minutos
De espera por cliente por minutos
Tiempo en el 13,56 minutos 3,81 minutos
Sistema por cliente por minutos

0 Comments:

Post a Comment

<< Home