• Author / Uploaded
• meryl herndz

Citation preview

INGENIERIA DE SISTEMAS “U.N.T”

MODELO DE COLAS

SISTEMA DE COLAS SIMPLE:

1 Servidor Línea de espera Población potencial de clientes

SISTEMA DE COLAS CON MÚLTIPLE SERVICIO:

1 2 . . . Línea de espera Población potencial de clientes

EDUARDO PORTAL MARTINEZ

C C Servidores en paralelo

INGENIERIA DE SISTEMAS “U.N.T”

NOTACION:

(A:B:S)(D:E:P) Donde: A: B: S: D:

E: P:

Representa la distribución de probabilidad de las llegadas (Distribución de Poisson o Exponencial). Representa la distribución de probabilidad del tiempo de atención. Representa al número de servidores en el sistema. Representa a la disciplina de la cola: FCFS Primero en llegar primero en salir. LCFS Ultimo en llegar primero en salir. SIRO Atención en orden aleatorio. Disciplina general (Soporta los tres casos GD anteriores). Capacidad máxima de clientes en el modelo. Población potencial de clientes (Que puede ser infinita o finita)

NOMENCLATURA BASICA PARA UN SISTEMA DE COLAS λ:

Tasa de llegadas o de arribo de clientes al sistema.

µ:

Tasa de servicio o atencion en el sistema de colas.

L:

Número de clientes en promedio en el sistema de colas.

L q:

Número de clientes en promedio en cola (No incluye clientes en servicio)

W:

Tiempo promedio de permanencia de clientes en el sistema.

Wq:

Tiempo promedio de los clientes en la cola.

NOTA: CUANDO SE TRATA DE INGRESAR UN VALOR EN N? ME ESTOY REFIRIENDO AL NÚMERO DE ITERACIONES QUE SE VAN A VER, ES DECIR PARA UN PN.

EDUARDO PORTAL M.

2

INGENIERIA DE SISTEMAS “U.N.T”

CARACTERISTICAS EL PROCESO DE LLEGADA. Este símbolo describe la distribución de tiempo entre llegadas, que es uno de los siguientes: a. D para denotar que el tiempo entre llegadas es determinístico. b. M para denotar que los tiempos entre llegadas son probabilísticos y sigue una distribución exponencial. c. G para denotar que los tiempos entre llegadas son probabilísticos y sigue una distribución general diferente a la exponencial. EL PROCESO DE SERVICIO. Este símbolo describe la distribución de tiempos de servicio, que es uno de los siguientes: a. D para describir un tiempo de servicio determinístico. b. M para denotar que los tiempos de servicio son probabilísticos y sigue una distribución exponencial. c. G para denotar que los tiempos de servicio son probabilísticos y sigue una distribución general diferente a la exponencial. EL PROCESO DE COLAS. Este número s, representa cuantas estaciones o canales paralelos existen en el sistema (Suponiendo que los servidores son idénticos en su rapidez de servicio.)

RELACION DE PROGRAMAS PARA CASIO CFX-9850GB PLUS

NOTA: CALCULADORAS DE VERSIÓN INFERIOR A ESTA, LOS PROGRAMAS NO CORREN...AL IGUAL QUE EN LAS CALCULADORAS ALGEBRAICAS; ESPACIO MINIMO PARA LOS PROGRAMAS 10300KB.

EDUARDO PORTAL MARTINEZ

3

INGENIERIA DE SISTEMAS “U.N.T” RECUERDA QUE ALGUNOS VALORES SON ADIMENSIONALES COMO POR EJEMPLO LA UTILIZACIÓN QUE PARA ALGUNOS CASOS ES:

ρ=

λ µ

Clientes Hora = 60 * Clientes * Hora = 60 = 0.909090 ρ= Clientes 66 * Clientes * Hora 66 66 Hora 60

ES DECIR QUE SI TRABAJAMOS EN MINUTOS LA TASA DE LLEGADA, TAMBIEN DEBEREMOS TRABAJAR LA TASA DE SERVICIO EN MINUTOS, PERO USUALMENTE SE UTILIZA HORAS EN VEZ DE MINUTOS, ES DECIR TODO SE CONVIERTE A HORAS.

MODELO DE ERLANG:

M/EK/1

Suppose thet service times have the Erlang distribution of order k with mean 1/µ, and variance σ = 1/kµ . 2

2

The standart deviation of an Erlang distribution of order

k is equal to its mean divided by √k, and this the Erlang model for service times may be useful for aproximating service times which have a skewed distribution with the mean greater than the standart deviation.

For k>10, an Erlang random

variable approaches a constant value of 1/µ.

MODELO:

M/D/1

Assume now that service times have no variability, that is, σ =0, which means 2

that all service times assume the constant value 1/µ

MODELO:

M/G/∞

MODELO:

1/∞ /∞

(M:M:1)(GD:∞:∞ )

EDUARDO PORTAL M.

4

INGENIERIA DE SISTEMAS “U.N.T”

Ejemplo 13.1 Pag 724: La comision de la autopista de Ohio 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 vehiculos cumplen con las regulaciones federales.

La administracion esta considerando mejorar la calidad del servicio

en sus estaciones de pesado y ha seleccionado una de las estaciones como modelo a estudiar, antes de instrumentar los cambios.

La

administracion

desea analizar y entender el desempeño del sistema actual durante las horas pico, cuando llega a la bascula el mayor Número de camiones, suponiendo que el sistema puede desempeñarse bien durante ese periodo, el servicion en cualquier otro momento sera aun mejor. Suponga que los valores son los siguientes: :

Número promedio de camiones que llegan por hora=60

:

Número promedio de camiones que pueden ser pesados por

hora=66.

El valor de

> , denota que es un estado estable, de modo que es posible hacer

el análisis. λ µ 60 ρ= = 0.90909090 ≅ 0.9091 66

ρ=

Mientras mas cercano este

de 1, mas cargado estara el sistema, lo cual

tiene como resultado colas mas largas y tiempos de espera mas grandes. En terminos de , , , las medidas de rendimiento, para el problema de OCT se calcula de la siguiente manera: 1. Probabilidad de que no haya clientes en el sistema (Po P[0]) Po = 1-

= 1-0.9091 = 0.0909

Este valor indica que aproximadamente 9% del tiempo un camion que llega no tiene que esperar a que se le proporcione el servicion porque la estacion de pesado esta vacia. Dicho de otra manera, aproximadamente el 91% del tiempo un camion que llega tiene que esperar. EDUARDO PORTAL MARTINEZ

5

INGENIERIA DE SISTEMAS “U.N.T”

2. Número promedio en la Fila (Lq):

Lq =

ρ2 = 1− ρ

(09091) 2 = 1 − 0.9091 Lq = 9.0909 Lq =

En otras palabras, en el estado estable, en promedio, la estacion de pesado puede esperar tener aproximadamente nueve camiones esperando para obtener el servicio (Sin incluir al que se esta pesando). 3. Tiempo promedio de espera en la cola (Wq):

Wq =

Lq λ

=

9.0909 = 0.1515 60

Este valor significa qu en promedio, un camion tiene que esperar 0.1515 horas, paroximadamente 9 miniutos, en la fila antes de que empiece el proceso de pesado. 4. Tiempo promedio de espera en el sistema (W): W = Wq +

1 1 = 0.1515 + = 0.1667 66 µ

Este valor indica que en promedio, un camion invierte 0.1667 horas, 10 minutos, desde que llega hasta que sale. 5. Número promedio en el sistema (L):

L = λ ∗ µ = 60 ∗ 0.1667 = 10 Este valor indica que en promedio, existe un total de 10 camiones en la estacion de pesado, ya sea en la bascula o esperando a ser atendidos. 6. Probabilidad de que haya n (n: Indica el número de iteraciones N en la caluladora)clientes en el sistema:

N

P[N]

0

0.09090909090

1

0.0826446281

2

0.07513148009

3

0.06830134554

4

0.06209213231

EDUARDO PORTAL M.

6

INGENIERIA DE SISTEMAS “U.N.T”

5

0.05644739301

.

.

.

.

EL VALOR QUE MUESTRA LA CALCULADORA SE MUESTRA EN UNA LISTA, PERO RECORDEMOS QUE LA CALCULADORA CASIO, SOPORTA 256 ESPACIOS EN COLUMNA DE LA LISTA, ES DECIR QUE PARA VALORES DE PN MAYORES A 256 LA CALCULADORA DARA UN ERROR

7.Utilizacion (U=

PARA ESTE CASO):

U= =0.9091 Este valor indica que aproximadamente 91% del tiempo las instalaciones de pesado estan en uso (un camion esta siendo pesado). De manera equivalente 9% del tiempo la estacion esta sin funcionar, sin que haya camiones que se esten pesando.

MODELO:

S/∞ /∞

(M:M:S)(GD:∞:∞ )

Siguiendo con el ejemplo anterior, cuando: S

: 2 servidores. : Número promedio de camiones que llegan por hora=70 : Número promedio de camiones que pueden ser pesados por hora=40.

El valor de *S > , denota que es un estado estable, de modo que es posible hacer el análisis.

Corremos el programa: S 00 00 y nos sale lo siguiente:

======= MODELO DE COLAS (M:M:S)(GD:00:00) EDUARDO PORTAL MARTINEZ

7

INGENIERIA DE SISTEMAS “U.N.T”

=======

Pulsamos el Botón:

y sale la siguiente ventana:

En la cual nos pide el valor de λ (Lanbda) (NOTA: Para ciertos casos el valor de Lanbda es un valor entero, dependiendo del modelo, ya que se trata de la Tasa de llegadas o de arribo de clientes al sistema, lo cual seria ilogico decir , λ=0,2 personas/hora, esto es dependiendo del sistema)

L =L EFEC? 70 NU (µ)? 40 S? 2

Al finalizar el anterior ingreso los valores obtenidos seran los siguientes: UTILIZACION= 0.875 N? 5

P[0]=0,0666666666666

ES DECIR QUE QUEREMOS HALLAR:

P[0] P[1] P[2] P[3] P[4] P[5]= P[N]

En este modelo, la ecuación para hallar los P[N] à 0. . .5, no es la misma para todos los P[N]; se utilizará una ecuación para hallar : P[0], P[1], P[2]; y otra ecuación para hallar los restantes P[N], es decir: P[3], P[4], P[5]; esto es porque el modelo asi lo calcula, dependiendo del Número de Servidores. Entonces

los

siguientes valores que mostrara el programa sera:

- - - - - - P[N] - [0,S] - - - - - - - 0.06666666666 0.11666666666 EDUARDO PORTAL M.

8

INGENIERIA DE SISTEMAS “U.N.T”

0.10208333333

Es decir que los valores hallados anteriormente son los P[N] que van desde 0 hasta el número de servidores (2) . P[0] = 0.06666666666 P[1] = 0.11666666666 P[2] = 0.10208333333 Luego los siguientes valores seran - - - - - P[N] ⇒ ESTO ES DEPENDIENDO DEL SISTEMA DE COLAS EN EL CUAL NOS ENCONTRAMOS, Ademas, voy a tomar otro ejemplo: P0 =

1  ρ   ρs   s   ∑  +   ∗    i= 0 n!   n!   s − ρ  s −1

i

Por Logica, para este ejemplo , vamos a suponer

que no tenemos en cuenta ciertas restricciones como por ejemplo, vemos en el denominador una resta: s- , vamos a suponer dos cosas: Primero: que s= , entonces habria una division por cero y por lo tanto Po, no tendria un valor logico. Segundo: que s< , entonces Po tendria un valor negativo, el cual no denota un significado logico. POR LO TANTO, ESTE TIPO DE CASOS Y DE RESTRICCIONES QUE A LA HORA DE UN EXAMEN NO SE TOMAN EN CUENTA CONLLEVA AL INGRESO ERRONEO DE DATOS CON LO CUAL LOS VALORES OBTENIDOS TAMBIEN SERAN ERRONEOS.

Volviendo al ejemplo de colas con iterrupcion y sin interrupcion: Correr el programa CCI CSI, luego ingresar los siguientes valores: Lanbda (λ)? Nu (µ)? S (SERVIDORES)? NUM DE L[I] de λi? L[I] λ1? L[I] λ2? L[I] λ3? . EDUARDO PORTAL M.

14

INGENIERIA DE SISTEMAS “U.N.T”

. L[I] λk? Luego del ingreso arroja los siguientes valores: A= 36

SIN INTERRUPCION: λk

Bk

Wk

Lk

wqk

Lqk

↓

↓

↓

↓

↓

↓

0.2

0.966

0.362

0.07240

0.287

0.0057

0.6

0.866

0.3664

0.2198

0.0331

0.0198

1.2

0.666

0.3814

0.4576

0.04807

0.05769

CON INTERRUPCION: λk

Bk

Wk

Lk

wqk

Lqk

↓

↓

↓

↓

↓

↓

0.3448

0.0689

0.0114

0.3978

0.2387

0.0645

0.5769

0.6923

0.2435

SIN

CON

INTERRUPCION

INTERRUPCION

wqk

wqk

↓

↓

0.287

0.0114

0.0331

0.0645

0.04807

0.2435

EDUARDO PORTAL MARTINEZ

15

INGENIERIA DE SISTEMAS “U.N.T”

PROBLEMAS PROPUESTOS: Un gerente de un supermercado local, como parte de su operación, alquila equipo para que los clientes dueños limpien sus propias alfombras, y para ello recibe solicitudes para alquilar estas unidades a una tasa de dos por día, (es decir, la media de tiempo entre llegadas es de medio día). Las solicitudes para las máquinas siguen un proceso Markov. Se dispone de dos máquinas. Los clientes los alquilan por un período máximo de 2 días, pero en promedio la devuelven un día después. Suponer que si no se tiene una máquina para alquilar, el cliente va a otro lugar para hacerlo. (a) ¿Cuál es la probabilidad de que un cliente solicite una máquina cuando no hay disponibles? (b) ¿Cuántas máquinas se necesitan tener disponibles para reducir a menos de 0.05 la probabilidad de que el cliente se marche? 1. En un taller los trabajos llegan según un proceso de Poisson con una tasa media de ocho por día. Aún cuando las tareas llegan son de tres tipos distintos, el tiempo requerido para efectuar cualquiera de ellas tiene la misma distribución exponencial con media 0.1 día de trabajo. La práctica a sido realizar el trabajo según FCFS, sin embargo, el trabajo tipo 1, no debe de esperar demasiado, mientras que los trabajos tipo 2 le siguen en prioridad y los de tipo tres no tienen importancia relativa. La llegada media es de 2, 4 y 2 respectivamente. Como los tres tipos de trabajo han experimentado, en promedio retrasos un poco largos, se ha propuesto que los trabajos se seleccionen según una disciplina apropiada de prioridad. Compárese y comentar los resultados obtenidos si la disciplina fuera a) FCFS, b) Prioridad sin interrupción, c) prioridad con interrupción. 2. Se sabe que en una oficina estatal en la que atiende una recepcionista, el 25% de su tiempo está desocupada. Como la prioridad de atención es según criterio personal de ella, muchas personas se han quejado pues no siempre respeta en atender a quien le corresponde en su momento. Su jefe no sabe que hacer por lo que ha encargado determinar cuantas personas se espera habrán en la cola el 1% del tiempo? 3. Una línea de ensamblaje de automóviles tiene dos tipos de servicio: pintura y luego instalación de motor. Cada hora 22.4 módulos de chasis en promedio entran en la línea. Un vehículo se puede pintar en 2.4 min. y se le puede instalar su motor en 3.75 min. en promedio. Se tiene una estación para pintura y dos de instalación de motor. (a) En promedio ¿cuántos autos sin motor habrá en la planta? (b) En promedio ¿Cuánto debe de esperar un carro pintado hasta que empiece la instalación de motor? (c) ¿Cuál es la probabilidad de que no exista un vehículo en la planta? (d) Cuál es la probabilidad de que hallan dos vehículos en la planta? 4. Un grifo tiene capacidad para cuatro vehículos incluyendo a los que se encuentran en atención. Se tiene dos surtidores. Se atiende a un vehículo en cinco minutos en promedio, y llegan al grifo un promedio de 20 vehículos por hora. Se tiene la posibilidad de alquilar un terreno adyacente con capacidad para que esperen dos vehículos más a un costo de S/.150.00 mensuales. También existe la alternativa de un surtidor más (se EDUARDO PORTAL M.

16

INGENIERIA DE SISTEMAS “U.N.T”

tienen ya las conexiones listas)., Si se trabaja 20 H durante 365 días al año, ¿Cuánto se debe de perder por vehículo no atendido como para considerar el alquiler del terreno?. ¿Hasta cuánto se podría pagar por el alquiler de este surtidor como alternativa al alquiler del terreno? PROBLEMAS RESUELTOS. 1. En una peluquería existen tres peluqueros que se encargan de atender a los clientes. Actualmente, los clientes llegan a una tasa promedio de seis por hora. Cada peluquero puede hacer un corte de pelo en 20 min. Los intervalos de llegada parecen seguir una distribución de Poisson y los tiempos de servicio siguen una distribución exponencial. a. Si fueran dos peluqueros de vacaciones y en reemplazo sólo entrara un peluquero, ¿cuántos asientos de espera deben de haber en la peluquería, para que tengan los peluqueros la misma sensación que si estuviera el equipo completo, suponiendo que la gente no espera de pie. SOLUCION: En el modelo orginal la capacidad infinita, en promedio trabajan P1+P2*2+(1P0+P1+P3)*3=2 peluqueros en la jornada que trabajan 3, es decir ρ, es decir, cada peluquero trabaja 66.67% de la jornada. En el modelo orginal la capacidad finita para 2 peluqueros, el ρef=0.6667, por lo que el ρef=2*0.6667*3=4clientes/hora ρef=λ*(1-PM) siendo M, la capacidad del sistema, por lo tanto 4=6*(1- PM) de lo que tenemos PM =1-2/3=1/3, por lo que probando para diferentes M, tenemos: con M=2, PM =0.4, con M=3, PM =0.2857, entonces debe de haber tan solo un asiento(valor mas cercano al objetivo planteado) 2. Los trabajos llegan a un centro particular de acuerdo a un proceso de entrada de Poisson a una tasa media de dos por día, y el tiempo de operación tiene una distribución exponencial con una media de ¼ de día. En el centro se tiene espacio suficiente como para recibir tres trabajos, además del que está procesando. Determinar la proporción del tiempo en que este espacio resultará adecuado para acomodar todos los trabajos. SOLUCION: La capacidad del sistema es de 4 unidades(incluyendo el que esta siendo procesado).Cada vez que ingrese una unidad, sera aceptadapor el sistema en los espacios 1,2,3 o 4, en caso contrario sera rechazada. Sim embargo esto puede ser tratado como una cola infinita en la que el espacio es adecuado para: P0+ P1+ P2+ P3+ P4=.9687, de manera aproximada se podria calcular tomando en cuenta que el λef, es lo que se procesa y lo que ingresa al sistema, y el porcentaje sera λef /λ =(1-PM)=0.9677 3. Se tiene a un mecánico al cual se le ha asignado el mantenimiento de tres máquinas. Para cada máquina, la distribución de probabilidad del tiempo de funcionamiento, antes de una descompostura, es exponencial, con una media de 9 horas. El tiempo de reparación también tiene una distribución exponencial con una media de dos horas. a. Calcúlese la distribución de probabilidad de estado estacionario y el número esperado de máquinas que no estén funcionando. b. Como una aproximación burda, podría suponerse que la población potencial es infinita, de modo que el proceso de entrada es de Poisson, con una tasa media de llegadas de 3 cada 9 horas. Compárese el resultado del inciso a) con el que obtiene EDUARDO PORTAL MARTINEZ

17

INGENIERIA DE SISTEMAS “U.N.T”

al hacer una aproximación utilizando i) el modelo correspondiente a cola infinita ii) el modelo correspondiente a cola finita. c. Supóngase que ahora se dispone de un segundo mecánico, siempre que más de una de estas tres máquinas necesite reparación. Calcúlese la información que se especifique en el inciso a) SOLUCION: λ =1/9, µ=1/2, (M/M/1)(FCFS/3/3) a. La distribución de probabilidad es: X F(X)

0 0.4929

1 0.3286

2 0.1460

3 0.0325

Número de máquinas que no están funcionando L=0.7181 máquinas. O también se puede calcular el promedio de máquinas que no funcionan = ΣxiF(X)i b. λ =3/9, µ=1/2 i. (M/M/1)(GD/ω/ω) X F(X)

0 0.333

1 0.2222

2 0.14815

3 0.09877

Número de máquinas que no funcionan: L= 2 máquinas, Se obtiene un error bastante grande por no haber el ajuste en la población potencial, a medida de que quedan M-n máquinas, como posibles clientes, además considera la posibilidad de p4,p5,... ii. (M/M/1)(GD/3/ω) X F(X)

0 0.41538

1 0.27672

2 0.18462

3 0.12308

Número de máquinas que no funcionan: L= 1.0154 máquinas. Se acerca mas al valor obtenido en a. Y es porque no considera P4,P5,..., lo que significa que hay perdida de ingreso en el λ, sin embargo el error es de aproximadamente de 40% c. (M/M/2)(FCFS/3/3) X F(X)

0 0.54607

1 0.36404

2 0.0809

3 0.00899

Número de máquinas que no funcionan: L= 0.55281 máquinas

4. Los pacientes llegan a una clínica según una distribución de Poisson con una tasa de 30 por hora. El cupo de la sala de espera es de 14 pacientes. El tiempo de examen por persona es exponencial con tasa media de 20 por hora. a. Encontrar la tasa de llegada efectiva en la clínica. b. ¿Cuál es la probabilidad de que un paciente no espere o encuentre un asiento desocupado en la sala? EDUARDO PORTAL M.

18

INGENIERIA DE SISTEMAS “U.N.T”

c. d.

¿Cuál es el tiempo promedio de espera hasta que el cliente salga de la clínica? Si la atención fuera distribuida normalmente con desviación estándar 0.5 min. ¿Qué tiempo esperaría el paciente hasta ser atendido suponiendo que halla capacidad ilimitada en la sala de espera? SOLUCION: (M/M/1)(GD/15/ω) a. λef =30(1-0.3338)=19.98 pacientes/hora b. P0+P14 =0.2233 podría haberse tomado como que halla 1, 2 ... asientos pero la pregunta es un asiento y no ocupa al menos. c. W=39.10 minutos. d. No se llegaría a estabilizar el sistema de colas porque crecería indefinidamente.

5. Se están desarrollando planes para una nueva fábrica. A un departamento se le ha asignado un gran número de máquinas automáticas de un cierto tipo, y ahora se desea determinar cuántas máquinas se le debe de asignar a cada operador para que les dé servicio (carga, descarga, ajuste arranque, etc.). Para los fines de análisis se ha proporcionado la siguiente información: El tiempo de operación, (tiempo entre completar el servicio y requerirlo nuevamente) de cada máquina tiene una distribución exponencial, con una media de 100 min. El tiempo de servicio tiene una distribución exponencial con una media de 10 min. Un operador debe de atender sus propias máquinas; no puede ayudar a los demás operadores, o recibir ayuda de ellos. Para que el departamento logre la tasa de producción requerida, las máquinas deben de estar en operación en promedio al menos el 80% del tiempo. ¿Cuál es el número máximo de máquinas que pueden asignarse a un operador en tanto todavía se logre la tasa de producción requerida? SOLUCION: (M/M/1)(FCFS/M/M) Máquinas funcionando en promedio = (M-L), total de máquinas M: promedio funcionando=(M-L)/M para Para M=2, 0.90 Para M=3, 0.89 Para M=4, 0.88 Para M=5, 0.87 Para M=6, 0.86 Para M=7, 0.84 Para M=8, 0.83 Para M=9, 0.81 Para M=10, 0.79, por lo tanto se le asignara no mas de 9 máquinas.

EDUARDO PORTAL MARTINEZ

19