Teoria de Colas1

8/13/2019 Teoria de Colas1

1/38

Introduccin 11

1 Introduccin

1.1 Contenido de la obra

En este libro se desarrollan los contenidos de la asignatura deMtodos Cuantitativos de OrganizacinIndustrial II, correspondiente a la titulacin de Ingeniera en Organizacin Industrial en la ETSEIT. Enlo que se refiere a adquisicin de conocimientos, se pretende que una vez cursada la asignatura elalumno conozca las aplicaciones y procedimientos de resolucin de las siguientes tcnicas de mtodoscuantitativos de gestin:

Modelos de lneas de espera (tambin llamada teora de colas) Cadenas de Markov y procesos de decisin markovianos Programacin dinmicaLa agrupacin de estas tcnicas en una misma asignatura se debe a la existencia de diversos puntoscomunes entre estas tcnicas, lo cual puede facilitar su proceso de aprendizaje. Dichos puntoscomunes pueden concretarse del modo siguiente:

Se trata de modelos dinmicos, esto es, que representan la evolucin de determinadas magnitudesde la realidad observada a lo largo del tiempo. Al evolucionar a lo largo del tiempo, podremoscaracterizar a la realidad as observada como un proceso. En ocasiones se examinar elcomportamiento del proceso a intervalos regulares (o etapas): tendremos entonces modelos detiempo discreto. Otras veces podr ser til aproximar indefinidamente las etapas, y los modelossern de tiempo continuo.

En cada uno de los instantes de tiempo considerados, el proceso podr encontrarse en alguno delos posibles estados. Un estado es una variable, cuantitativa o cualitativa, descriptiva delcomportamiento del proceso. El conjunto de estados podr ser finito o infinito, dependiendo de lanaturaleza del proceso. La evolucin de dicho proceso se podr caracterizar por los estados que

vaya tomando a lo largo del tiempo.

Si la evolucin del proceso a partir de un determinado instante de tiempo no est determinada,sino que sigue una determinada ley probabilstica, deber caracterizarse por un modelo estocsticoo aleatorio. Si la evolucin es conocida, el modelo a utilizar ser de tipo determinista.

Puede suceder que, al principio de cada una de las etapas, podamos tomar una decisin. Dicha

evolucin influir en la evolucin futura del proceso, bien forzando una evolucin a undeterminado estado con toda certeza (proceso decisional determinista) o influyendo sobre la

Los autores, 2002; Edicions UPC, 2002


2/38

Mtodos cuantitativos de organizacin industrial II12

naturaleza de la ley de probabilidad que regir la evolucin del proceso en la etapa siguiente(proceso decisional estocstico).

Finalmente, a diferencia de los modelos de programacin lineal desarrollados en MtodosCuantitativos de Organizacin Industrial I, las magnitudes relevantes del sistema pueden

evolucionar de forma no lineal. Esto puede permitirnos resolver algunos modelos no lineales aun coste relativamente reducido.

Las tcnicas cuantitativas de gestin que se desarrollan en esta obra permitirn tratar algunos modelosdinmicos, de tiempo discreto o continuo. Dichos modelos podrn ser deterministas o estocsticos, y

pueden contemplar la posibilidad de tomar decisiones en cada una de las etapas.

1.2 Teora de colas

Se trata de modelos descriptivos de situaciones en las que se producen esperas. Estas situaciones son

muy frecuentes en el contexto organizativo, y pueden encontrarse en diversas situaciones. Algunas destas son muy evidentes: la gestin de las cajas de un supermercado, las cabinas de peaje en una

autopista o una cola de impresin. Otras, como los problemas de asignacin de mquinas a operarios,no lo son tanto, pero tambin son susceptibles de ser representadas de esta manera.

Una cola determinista, en la que se conocen con exactitud la forma en que se producen las llegadas ylos tiempos de servicio, es relativamente sencilla de resolver. Una situacin ms compleja (y frecuenteen situaciones como las descritas ms arriba) tiene lugar cuando llegadas y servicios tienen lugar demanera aleatoria. Por tanto, los modelos descriptivos de las lneas de espera son en su abrumadoramayora de tipo estocstico. En cuanto a la secuencia temporal, se trata en la mayora de los casos de

modelos de tiempo continuo, aunque en ocasiones (sobre todo en simulacin) puedan realizarseaproximaciones de tiempo discreto.

En un sistema de colas puede darse el caso de que existan normas de decisin(es el caso, por ejemplo,de las colas con prioridades). Sin embargo, es ms frecuente plantear problemas de diseo del sistema,de manera que se minimicen los costes asociados a la cola: costes de servicio, de espera y deabandono.

1.3 Cadenas de Markov

Las cadenas de Markov son un modelo representativo de procesos estocsticos, caracterizados

precisamente por lapropiedad markoviana: la ley de probabilidad que rige la evolucin del proceso deun instante ta otro t+ 1 viene determinada por el estado en que se encuentre el modelo en ese instante.Pueden describirse de esta manera procesos de tiempo continuo o de tiempo discreto. Una cola en la

que las leyes de probabilidad de las tasas de llegada y servicio sea de tipo Poisson puede tratarse comouna cadena de Markov de tiempo continuo.

En ocasiones, podremos asociar un valor de utilidad a cada una de las transiciones posibles, ydeterminar el valor esperado de dicha utilidad en el largo plazo: se trata de un modelo de cadenas deMarkov con remuneracin.

Tambin podemos plantearnos la posibilidad de tomar una decisin al principio de cada una de lasetapas de un proceso de tipo markoviano. Con esta decisin, podremos hacer que el modelo

evolucione segn una u otra cadena de Markov. Para estos procesos, interesar conocer la poltica(decisiones a tomar para cada etapa si nos encontramos en alguno de los estados) para optimizar el



3/38

Introduccin 13

valor esperado de la utilidad del proceso. Se trata entonces de un modelo de cadenas de Markov conremuneracin y decisin, o tambin un modelo deprocesos markovianos de decisin.

1.4 Programacin dinmica

Se trata de una metodologa que permite optimizar el comportamiento de procesos polietpicos dedecision. En los modelos de programacin dinmica podemos tomar una decisin al principio de cadaetapa. Dicha decisin afecta a la evolucin futura del modelo. El valor de la magnitud a optimizar enuna determinada etapa depender del estadoen que se encuentre el proceso y de la naturaleza de la

decisin. Se trata de encontrar polticas en el sentido descrito para las cadenas de Markov queoptimicen el comportamiento del sistema para un determinado nmero de etapas (si el modelo es

determinista) o el valor esperado de dicho comportamiento (si el modelo es estocstico).

Los procesos markovianos de decisin descritos anteriormente pueden ser resueltos medianteprogramacin dinmica. Otros problemas, como el de distribucin de esfuerzos, los de renovacin ymantenimiento y planificacin de inventarios son tambin susceptibles de ser tratados con

programacin dinmica.

1.5 Notacin y conocimientos previos

En las expresiones matemticas, se ha seguido la siguiente notacin:

Las variables escalares se han representado en cursiva, mayscula o minscula segn convenga.Especialmente en teora de colas, se han usado letras griegas para representar escalares. Por

ejemplo: n, k,p,N, , , .

Los vectores se representan en minscula negrita. Si no se indica lo contrario, se trata devectores columna. Por ejemplo: v, g. Las matrices se representan en mayscula negrita. Por ejemplo: P, A.

En cuanto a conocimientos previos, se recomienda revisar las siguientes materias:

Distribuciones de probabilidad, especialmente las propiedades de las distribuciones exponencialy de Poisson.

Clculo matricial: producto de matrices, y significado de los valores y vectores propios. Obtencin de races complejas de un nmero real.



4/38

Teora de colas 15

2 Teora de colas

2.1 Modelos de lnea de espera

Tanto en la vida cotidiana como en el contexto organizativo, podemos encontrarnos con situacionesdel tipo siguiente:

Determinadas unidades acuden a un sistema a recibir un determinado servicio. Dichas unidadesproceden de un centro emisory aparecen en el sistema de forma aleatoria, con una tasa de llegadas(unidades que llegan por unidad de tiempo) que sigue una determinada distribucin de probabilidad(ley de llegada). Una vez en el sistema, puede suceder que sean servidas en alguno de los servidoresocanales, o bien que esperen turno (entrando entonces en una cola). Si esto sucede, accedern alservicio segn una determinada disciplina de cola. El sistema servir las unidades con una tasa de

servicio(servicios por unidad de tiempo) aleatoria, caracterizada por una distribucin de probabilidad(ley de servicio).

Fig. 2.1.a Componentes de un modelo de lneas de espera

SISTEMA DE LNEAS DE ESPERA

SISTEMA

CENTRO EMISOR(finito / infinito)

LEY DE LLEGADALEY DE SERVICIO

COLA(finita / infinita)

SERVICIO(s servidores)



5/38


En la tabla se muestran algunos ejemplos de situaciones asimilables a sistemas de lneas de espera:

Tabla 2.1.a Ejemplos de modelos de lnea de espera

Situacin Unidades Servidores Servicio

Espera de clientes en unsupermercado.

Clientes que esperanpara pagar.

Cajas registradoras. Cobro de la compra.

Automviles en untaller.

Automviles averiados.Mecnicos o equipos demecnicos.

Reparacin delautomvil.

Servicio demantenimiento.

Mquinas averiadas o enmantenimiento.

Unidades o equipos demantenimiento.

Reparacin de lamquina.

Todas estas situaciones pueden ser analizadas como un sistema de lneas de espera. Dicho sistema

abarca: Las unidades que estn recibiendo servicio en ese momento. Las unidades que estn esperando recibir servicio en la cola. Los canales o servidores que suministran el servicio.

2.2 Parmetros de un sistema de lneas de espera

Estos sistemas pueden ser analizados y diseados utilizando modelos matemticos de lneas de espera.El modelo de lnea de espera a considerar para analizar una determinada situacin debe caracterizarsea partir de las propiedades de:

El centro emisorde las unidades a servir. Las caractersticas delservicio. Las condiciones en las que se desarrolla elproceso de esperaen la cola.

Centro emisor

Como se ha indicado, se supone que las unidades proceden de un centro emisor y acceden a sistemacon una tasa de llegadas aleatoria que sigue una determinada ley de probabilidad, denominada ley dellegada. En ocasiones, puede ser ms conveniente definir la ley de llegada por los tiempos entrellegadas. En un caso general, la tasa media de llegadas al sistema puede ser funcin de los nunidadesque se encuentren en el interior del sistema y se representa por n.

Cuando el nmero de unidades en el centro emisor es muy grande, la probabilidad de que una unidadllegue al sistema no se ve afectada por las unidades que hayan salido del centro emisor (y que, portanto, estn dentro del sistema). Esto supone que la tasa media de llegadas al sistema seaindependiente de ny tengamos n= . Cuando esto sucede, decimos que nos encontramos ante unsistema de colas de universo infinito.

Cuando el nmero de clientes en el sistema es un nmero relativamente pequeo m, entonces s que laprobabilidad de que una unidad llegue al sistema depender de las unidades que estn presentes en l.En este caso, tendremos un sistema de colas de universo finito.



6/38

Teora de colas 17

Servicio

Una vez las unidades han entrado en el sistema, ms tarde o ms temprano recibirn un determinado

servicio. Dependiendo de las caractersticas del servicio, podremos tener dos situaciones:

Se realizan sobre la unidad varios servicios de forma secuencial. Tendremos entonces un conjuntodeservidores en serie.

Determinado servicio puede ser realizado por uno cualquiera de varios servidores. Tendremosentoncesservidores en paraleloo canales de servicio.

Fig. 2.2.a Disposicin de los servidores en los modelos de lnea de espera

En esta obra, consideraremos sistemas de colas sin servidores en serie. Dicha situacin, cuando ocurre,es un caso particular de un problema ms general (redes de colas) de gran complejidad, cuyotratamiento excede los objetivos de la presente unidad. Es habitual, sin embargo, considerar laposibilidad de que el sistema tengasservidores en paralelo.

Tal como se ha hecho con las llegadas, podemos describir el comportamiento del sistema en lo relativo

al servicio con n, la tasa media de servicio del sistema cuando su estado es n. Para un sistema con sservidores idnticos en paralelo, cada uno de ellos con una tasa de servicio de canal igual a , la tasade servicio del sistemavaldr:

Si n s n= nSi n s n= s

Cola

La cola del sistema est formada por las unidades que llegan al sistema y no pueden recibir servicio demanera inmediata, por encontrarse todos los servidores ocupados. Existen dos caractersticas de la colarelevantes para la definicin del modelo a aplicar.

TIPOS DE SERVICIO

SERVIDORES SERIE (red de colas):

SERVIDORES PARALELO (s canales de servicio):



7/38


Al definir el sistema, podemos establecer la condicin siguiente: si en el sistema, entre unidades queestn siendo servidas y unidades en espera, tenemos un nmero de unidades igual a k y llega unanueva unidad al sistema, dicha unidad debe abandonar el sistema y volver al centro emisor, sin recibir

servicio. Un modelo de este tipo es un modelo de cola limitada, porque limita el tamao de la cola a ksunidades. Cuando la condicin definida ms arriba no sea aplicable, tendremos un sistema de colainfinita (hay que precisar que la infinitud se refiere al nmero posible de unidades en el sistema, nonecesariamente al nmero realmente existente, el cual es deseable que sea finito). Mediante modelosde cola limitada podemos representar situaciones como:

El comportamiento de los clientes de un supermercado que, al observar una larga cola parapagar, abandonan el local sin comprar.La situacin de un taller de reparacin de automviles que no puede recibir ms vehculos porfalta de espacio.

Un segundo parmetro a determinar es la disciplina de cola, que describe la regla con la que se decidequ unidad, de las que estn en la cola, pasar a ser servida una vez quede alguno de los servidoreslibre. Lo ms habitual es suponer una disciplina FIFO, o una distribucin cualquiera (distribucingeneral o GD) en la que todas las unidades tengan la misma prioridad. En algunos casos, puede ser tilencontrar modelos en los que se establezca un sistema de prioridades. Para definir una cola conprioridades es necesario:

a) Definir varios grupos de unidades a servir. Cada unidad que llegue al sistema debe asignarse a unode los grupos establecidos.

b) Establecer las prioridades: en primer lugar, se atendern las unidades del grupo de prioridadmxima. Slo cuando no haya ninguna unidad de ese grupo por atender, se pasar a atender a lasunidades del segundo grupo, y as sucesivamente.

El comportamiento que se acaba de describir es el de una sistema de colas con prioridades sininterrupcin. Puede definirse tambin un sistema de colas con prioridades con interrupcin: en estecaso, si se estn atendiendo unidades de grupos de baja prioridad y llega una unidad de un grupo deprioridad ms alta, se interrumpe el servicio de la unidad de baja prioridad para atender a la de alta.Una vez atendida sta, se sigue sirviendo (si no llegan ms de alta prioridad) a la unidad de bajaprioridad.

De todo lo dicho, podemos decir que un sistema de lneas de espera puede caracterizarse a partir deseis parmetros:

La ley de llegada y el valor medio de la tasa de llegadas cuando hay nunidades en el sistema n. La ley de servicio y el valor medio de la tasa de servicios cuando hay nunidades en el sistema n. El nmero de servidores en paralelo (canales de servicio)s. La disciplina de cola (GD, FIFO, prioridades con o sin interrupcin, etc.) El tamao mximo de cola permitido k(infinito si el modelo es de cola infinita). El tamao del centro emisor m(infinito si el modelo es de universo infinito).De forma compacta, un modelo de colas se representa por la siguiente notacin

ley llegada /ley servicio /servidoress:disciplina cola /tamao mximo k/tamao centro emisor m

Leyes de llegada y servicio

Para las leyes de llegada y servicio, se aplica la siguiente notacin:



8/38

Teora de colas 19

Ley markoviana (M)

Se aplica a las leyes de probabilidad que cumplen la propiedad markoviana. Dicha propiedad consiste

en que la probabilidad de que ocurra un evento (llegada de una unidad o finalizacin de un servicio) esslo funcin del momento presente (esto es, del estado actual del sistema). Cuando esto sucede,tenemos que:

La tasa de eventos por unidad de tiempo seguir una ley de Poisson de media . El tiempo transcurrido entre dos eventos seguir una ley exponencial de media 1/.Para la caracterizacin de las llegadas, tendremos que = , y para los servicios tendremos = (para un servidor). La mayora de modelos de colas asumen una ley de llegadas de tipo Poisson.Cuando las leyes de probabilidad de las tasas de llegada y servicio para sean Poisson, el sistema puedeser representado mediante un proceso de nacimiento y muerte (se dice a veces que tenemos colasexponenciales).

Distribucin de probabilidad genrica (G)

Se trata de una distribucin de probabilidad cualquiera, caracterizada por su media 1y su desviacinestndar . Para una distribucin de probabilidad de tiempos entre eventos exponencial, tenemos =1/.

Distribucin degenerada (D)

Representa una ley de llegadas determinista. Es un caso particular de la distribucin general, en la quesi desviacin estndar cumple = 0.

Distribucin Erlang k (Ek)

La variable aleatoria resultante de sumar kvariables aleatorias exponenciales de media 1/(k) es unavariable aleatoria Erlang kde media 1/. Es particularmente til para representar un conjunto de kservicios en serie.

A modo de ejemplo, uno de los modelos de colas ms sencillo (modelo de Kendall) se representar porla siguiente notacin:

M/M/1 :GD//

Se trata de un sistema de lneas de espera, en el que tanto las llegadas como los servicios siguen unaley Poisson, existe un solo servidor, la disciplina de cola es una cualquiera (sin establecimiento deprioridades) y tanto la cola como el tamao del centro emisor son infinitos.

2.3 Resultados del modelo

Qu puede interesarnos conocer de un sistema de lneas de espera? Bsicamente dos cosas:

Una estimacin de la cantidad de unidades en el sistema o en espera de servicio.1En este caso, representa el valor de la media de la poblacin, y no la tasa de servicios de un canal, como en elresto del texto.



9/38


Una estimacin del tiempo que las unidades permanecen en el sistema o esperan servicio.Dichas estimaciones se obtienen para el funcionamiento de la cola en rgimen permanente (esto es,

cuando haya pasado un tiempo lo suficientemente largo desde el inicio del funcionamiento del sistemacomo para que se observe un comportamiento regular). En particular, suelen buscarse los siguientescuatro parmetros.

Nmero esperado de unidades en el sistema (L)

Podra obtenerse de modo experimental observando el nmero de unidades en el sistema (que incluyetanto las que estn siendo servidas como las que esperan servicio) en diferentes instantes de tiempo. Elvalor promedio de los valores obtenidos en las observaciones sera una estimacin experimental deL.

Longitud esperada de cola (Lq)

Se obtendra de modo similar aL, pero observando nicamente las unidades en espera de servicio.

Tiempo de espera en el sistema (W)

Podra observarse experimentalmente registrando el tiempo que cada una de las unidades pasa en elsistema. Dicho tiempo incluira tanto el tiempo de espera en cola, como el tiempo de servicio. Elpromedio de los tiempos as obtenidos sera una estimacin emprica de W.

Tiempo de espera en cola (Wq)

Se obtendra de la misma manera que W, pero considerando nicamente el tiempo de espera en cola.

Con estos valores, es posible evaluar los costes asociados al sistema, y poder as contar con elementoscuantitativos para disearlo.

En gran nmero de modelos de colas, los valores aqu descritos estn relacionados entre s, por lo quela obtencin de uno de ellos asegura, de forma ms o menos inmediata, la obtencin del resto. Larelacin entre los parmetros se establece a partir de las frmulas de Little.

2.4 Procesos de nacimiento y muerte

Cuando tenemos un sistema de colas con s servidores iguales en paralelo, en el que las tasas de

llegadas al sistema y las tasas de servicio de cada servidor son aleatorias, siguiendo una ley dePoisson, tenemos un modelo de colas exponencial, susceptible de ser representado por un modelo denacimiento y muerte. Se dice tambin que estos modelos son de tipo markoviano, o sistemas M/M(siguiendo la notacin de las leyes de llegada y servicio descrita en la seccin anterior).

En estos modelos, se define el estado del sistemacomo el nmero nde unidades presentes en dichosistema (en servicio o esperando servicio). Cuando llegue una nueva unidad al sistema tendremos unnacimiento, y el estado del sistema aumentar en uno. Cuando finalice el servicio realizado unaunidad, sta saldr del sistema: diremos que tenemos una muerte, y el estado del sistema disminuir enuno. Realizando ciertas suposiciones sobre el comportamiento del sistema, podemos hallar lasprobabilidades Pn de que el sistema est en el estado n (n = 0, 1, 2, ...). A partir de dichasprobabilidades (denominadas probabilidades de estado) podremos obtenerLy Lq. Una vez obtenidos

dichos valores, podremos conocer, mediante las frmulas de Little, los valores de Wy Wq.



10/38

Teora de colas 21

Hiptesis del modelo de nacimiento y muerte

El desarrollo de los modelos de nacimiento y muerte se basa en las siguientes hiptesis de partida.

1. Si el nmero de clientes en el sistema es igual a n, la distribucin de probabilidad del tiempo quefalta ver el prximo nacimiento sigue una ley exponencial de parmetro n.

2. Si el nmero de clientes en el sistema es igual a n, la distribucin de probabilidad del tiempo quefalta para la prxima muerte sigue una ley exponencial de parmetro n.

3. Las variables aleatorias de (1) y (2) son independientes. Dependiendo de qu variable resulte serms pequea, las transiciones posibles son:

n n + 1 (un nacimiento)n n 1 (una muerte)

A partir de stas hiptesis, podremos calcular las probabilidades Pnde que el sistema se encuentre encada uno de los diferentes estados posibles n. A partir de lasPn, ser posible determinar expresiones,ms o menos complejas de Ly Lq, as como de la tasa media de llegadas. Una vez obtenidos estosdatos, podremos obtener Wy Wqa partir de las frmulas de Little.

Fig. 2.4.a Modelo de nacimiento y muerte (caso general)

Clculo de las probabilidades de estado Pn

Para calcular las probabilidades de estadoPncomenzaremos definiendo: En(t) = nmero de veces que el proceso ha entrado en el estado ndesde el inicio hasta el tiempo t. Ln(t) = nmero de veces que el proceso ha salido en el estado ndesde el inicio hasta el tiempo t.Como no se puede entrar en (o salir de) un estado sin haber salido de (o entrado en) l antes,tendremos:

MODELO DE NACIMIENTO Y MUERTECASO GENERAL

0 nn-11 32

0 1 2 n-1

1 2 3 n

Estado: nmero de elementos en el sistema (cola + servicio).Nacimiento: llegada de una nueva unidad (tasa n).Muerte: servicio a una unidad (tasa n).

... ...



11/38


0

1n

i

i

P=

=

En(t)Ln(t)1

Si dividimos por t a ambos lados y pasamos al lmite (esto es, al estado estacionario del sistema),

tenemos:

( ) ( ) 1lim

nn

t

E t L t

t t t <

( ) ( )lim 0

nn

t

E t L t

t t <

Esto es, la tasa media de entradas a un estado es igual a la tasa media de salidas de un estado, enrgimen permanente.

Este hecho nos permite relacionar las probabilidades de estadoPn. Efectivamente, se puede acceder alestado nmediante un nacimiento desde n1, o bien mediante una muerte desde n+1:

n-1Pn-1 + n+1Pn+1

De la misma manera que slo se podr salir del sistema mediante un nacimiento a n+1, o bienmediante una muerte a n-1:

n+1Pn+1 + n-1Pn-1

De modo que la igualdad de tasas medias de entrada y salida puede escribirse como:

n-1Pn-1 + n+1Pn+1 = n+1Pn+1 + n-1Pn-1

Contamos con necuaciones para determinar n+1probabilidades de estado. La ecuacin que falta es la

que iguala a 1 el total de probabilidades:

La regularidad del sistema de ecuaciones resultante da lugar a una solucin compacta del sistema. Enprimer lugar se procede a calcular los coeficientes:

1 2 0

1 1

...

...n n

n

n n

C

=

Con el total de coeficientes, se halla la probabilidad de que no haya ninguna elemento en el sistema:

0

0

1

nn

P

C

=

=

( ) ( )n nE t L t

t t=



12/38

Teora de colas 23

Y entonces, las otras probabilidades se obtienen como:

0n nP C P=

Una vez obtenidas las probabilidades de los diferentes estados, podemos calcularLcomo la esperanzamatemtica de los estados del sistema:

0n

n

L nP

=

=

Para un sistema consservidores en paralelo, la longitud esperada de cola se calcular como:

( )q nn s

L n s P

=

=

Otro parmetro interesante es la tasa de llegadas efectivaal sistema. Se trata del promedio de las tasasde llegada para todos los estados, ponderada por la probabilidad de cada estado.

0n n

n

P

=

=

Cuando n= para todos los (infinitos) estados posibles del sistema, tendremos:

=

Frmulas de Little

La relacin entre el nmero de unidades en el sistema Ly el tiempo de espera en el sistema Wquedaestablecida mediante las frmulas de Little.

Cuando la tasa de llegadas al sistema tiene un valor constante para cualquier valor de nmero deunidades en el sistema, existen las siguientes relaciones entre las longitudes de cola y los tiempos deservicio:

L W= q qL W=

Estas expresiones se conocen como frmulas de Little. Pueden relacionarse los valores para el sistema

y los valores de cola a travs de los tiempos de servicio:

La condicin de constante hace que estas expresiones no sean aplicables a modelos de lneas deespera con tamao de cola limitado o universo finito. Para estas situaciones, deben emplearse lasexpresiones:

L W= q qL W=

1qW W

= +



13/38


donde la relacin entreLy Wes la tasa de llegadas efectiva, parmetro que debe calcularse para cadamodelo de colas, y que depender de los valores tomados por n.

Otro parmetro interesante en modelos de colas es el factor de utilizacin de cada servidor. Es unparmetro cuyo valor se encuentra entre 0 y 1, y que representa la fraccin de tiempo que funcionacada uno de los servidores del sistema. El factor de utilizacin se calcula como:

s

=

2.5 Modelos basados en procesos de nacimiento y muerte

Seguidamente, se proceder a obtener las frmulas de algunos modelos basados en el proceso denacimiento y muerte. Concretamente se caracterizarn los modelos siguientes:

un servidor ms de un servidor

Modelos de cola infinita yuniverso infinito M/M/1 :GD// M/M/s :GD//

Modelos de cola limitada M/M/1 :GD/k/ M/M/s :GD/k/

Modelos de universo finito M/M/1 :GD//m M/M/s :GD//m

Para cada uno de los modelos se establecer el modelo de nacimiento y muerte correspondiente, para

pasar luego a detallar las expresiones deL,Lq, Wy Wq.

2.5.1 Modelo de Kendall: M/M/1 : GD//

Se trata del modelo de colas ms sencillo: cola infinita, con un nico servidor. Esto supone que paratodos los estados, tengamos:

n= n=

MODELO DE NACIMIENTO Y MUERTEM/M/1 : GD/ / (MODELO DE KENDALL)

0 nn-11 32

... ...



14/38


15/38


Otros resultados de inters:

Dada su sencillez, podemos obtener otros resultados adicionales. Por ejemplo, puede obtenerse el

valor de la probabilidad de que el tiempo de espera en el sistema Wsea mayor que un determinadovalor t:

P(W> t) = e-(1-)t

Existe tambin una expresin similar para el tiempo de espera en cola Wq:

P(Wq> t) = e-(1-)t

Finalmente, la probabilidad de que el estado del sistema tenga un valor mayor que un determinadovalor kvale:

Pn>k= k+1

Ejemplo 2.5.1.a TALLER MANOLO (A)

Manolo Gimnez, reconocido miembro del gremio de los profesionales de la reparacin de vehculos,est preocupado por la marcha de su negocio: las expectativas son demasiado buenas y el taller

parece demasiado pequeo. Para ver qu puede hacer para resolver el problema, le pide ayuda a unexperto en teora de colas. Despus de una primera entrevista con el sr. Manolo acerca de lasexpectativas de negocio, obtiene la siguiente informacin:

Las llegadas al taller se producirn de forma aleatoria, segn una ley de Poisson de media 4llegadas al da (para este ejemplo, 1 da = 8 horas de jornada laboral). El tiempo que se tarda en reparar los automviles sigue una ley exponencial de media 1,75 horas

(esto es, 1 hora y 45 minutos). El sr. Manolo cuenta con un solo equipo para reparar los automviles. Adems del coche que est reparando, slo caben 3 coches ms en el taller. Si llegan ms, debe

estacionarlos en la va pblica, con el consiguiente deterioro en la calidad de servicio. Los coches se retiran del taller inmediatamente despus de ser reparados.Con estos datos, el sr. Manolo demanda al experto un anlisis inicial de la situacin. Msconcretamente, le pregunta:a) Qu fraccin de tiempo estar el taller en funcionamiento?b) Cul es el nmero promedio de clientes en espera de reparacin de su vehculo (suponiendo un

coche en reparacin por cliente?c) Cul es el nmero promedio de coches esperando a ser reparados?d) Cul es la probabilidad de que deban estacionarse coches en la calle?e) Cunto tiempo transcurrir, por trmino medio, desde que el coche llega al taller hasta que se

acaba la reparacin?f) Cunto tiempo transcurrir, por trmino medio, desde que el coche llega al taller hasta que

comienza la reparacin?

a) Qu fraccin de tiempo estar el taller en funcionamiento?

La pregunta se responde hallando el factor de utilizacin del sistema, que para el modelo de Kendall esigual al parmetro . Para ello necesitamos las tasas de llegada y de servicio.



16/38

Teora de colas 27

La tasa de llegada vale: = 4 llegadas / da = 0,5 llegadas / hora (recordemos que la jornadadel taller es de 8 horas)En cuanto a la tasa de servicio: = 1 servicio / 1,75 horas = 0,5714 servicios /hora.

Por lo que el factor de utilizacin valdr: = / = 0,5 / 0,5714 = 0,875.

El taller funciona el 87,5% de tiempo. Se trata de un factor de utilizacin muy elevado, que haceprever valores de tiempo de servicio y de unidades en el sistema bastante elevados.

b) Cul es el nmero promedio de clientes en espera de reparacin de su vehculo (suponiendo uncoche en reparacin por cliente)?

Lo que aqu se nos pide es el nmero promedio total de vehculos en el sistema, estn en cola (tantodentro como fuera del taller) o en servicio. Dicho valor se obtiene a partir del parmetroL, que vale:

0,57

0,5714 0,5L

= = =

De modo que el nmero promedio de unidades en el sistema (en este caso, de coches en el taller) es de7. El resultado obtenido con la frmula se expresa en unidades (en este caso, coches).

c) Cul es el nmero promedio de coches esperando a ser reparados?

Ahora nos piden los coches en espera, tanto si estn dentro como fuera del taller:

( )

2 20,56,125

( ) 0,5714 0,5714 0,5qL

= = =

El nmero promedio de unidades en cola (en este caso, de coches en espera para ser reparados) es de6,125. Recordemos que es un nmero promedio de unidades, por lo que puede ser un nmero noentero. Ntese que L Lq= 0,875: es inferior a uno porque el sistema no est funcionando todo eltiempo. Como se ha visto en a), funciona el 87,5% del tiempo como promedio.

d) Cul es la probabilidad de que deban estacionarse coches en la calle?

Tendremos coches en la calle cuando el estado del sistema sea superior a 4 (estado 4 3 coches enespera, y uno en reparacin). De hecho, se nos pide la probabilidad:

Pn>4= 5= 0,8755= 0,5129 51,29%

e) Cunto tiempo transcurrir, por trmino medio, desde que el coche llega al taller hasta que seacaba la reparacin?

Por lo que se pregunta es por el tiempo medio que pasa una unidad en el sistema (en espera yreparacin). En el modelo de Kendall, viene dado por la expresin:

1 1 140,5714 0, 5W = = =



17/38


As, el tiempo promedio que pasar una unidad en el sistema, desde que entra hasta que ha sidoservida es de 14 horas. En este caso, representa el tiempo que pasar, por trmino medio, desde que elcoche llega al taller hasta que concluye la reparacin. El valor de Wtiene como unidades la unidad de

tiempo en que estn expresadas y . Como estas magnitudes, en este caso, estn expresadas enllegadas por hora y servicios por hora, respectivamente, Westar expresada en horas.

f) Cunto tiempo transcurrir, por trmino medio, desde que el coche llega al taller hasta quecomienza la reparacin?

El valor pedido viene representado por el parmetro Wq(tiempo medio de espera en cola):

( )0,5

12,25( ) 0,5714 0,5714 0,5q

W

= = =

Esto indica que una unidad que llegue al sistema estar en espera un tiempo promedio de 12,25 horas,esto es 12 horas y 15 minutos. Para Wq son aplicables las mismas observaciones relativas a lasunidades que las hechas para W. En este caso, esto nos permite afirmar que un coche que llega al tallertarda un promedio de 12 horas y 15 minutos en entrar a ser reparado.

2.5.2 Modelo M/M/s : GD//

El modelo se diferencia del modelo de Kendall por el hecho de que ahora tenemos s servidores enparalelo, cada uno de los cuales tiene una ley de servicio Poisson de media . Por tanto la tasa delservicio del sistema ser igual a , siendo el nmero de servidores ocupados.

De este modo, el modelo de nacimiento y muerte que tendremos ser:

El factor de ocupacin de un servidor para este modelo es tambin igual a :

s

=

Con lo que podemos hacer que el sistema pueda responder a una determinada afluencia de llegadas,aadiendo el nmero de servidores en paralelo necesario para que


18/38

Teora de colas 29

El clculo de los valores del sistema reviste mayor complejidad. Los Cn toman diferentes valoressegn el estado del sistema:

( )!

n

nC n= para n


19/38


d) Cul es la probabilidad de que deban estacionarse coches en la calle?e) Cunto tiempo transcurrir, por trmino medio, desde que el coche llega al taller hasta que se

acaba la reparacin?


a) Qu fraccin de tiempo estar el taller en funcionamiento?

Ahora tenemos dos servidores, con lo que el factor de ocupacin se reduce a la mitad:

0,50,4375

2 0,5714s

= = =

En relacin con el ejemplo 2.5.1.a., vemos ahora que cada uno de los equipos trabaja el 43,75% del

tiempo. Ntese que el nmero promedio de coches que se est reparando es el mismo que en el casoanterior. Como tenemos dos equipos en paralelo, ese nmero vale ahora: 20,4375 = 0,875. La mejoradel comportamiento del sistema vendr dada por la reduccin del nmero de unidades en espera, comose ver en las secciones siguientes.

b) Cul es el nmero promedio de coches que tendr dentro del taller?

Comos=2, debemos calcular primeroP0, despusLq, y finalmenteL:

( ) ( )0

1

0

1

/ 1

! ! 1

n ss

n

P

n s

=

=

+

Haciendos=2 tenemos la siguiente expresin paraP0:

A partir de aqu, ya podemos obtenerLq, con la frmula siguiente:

1

02

(1 ) !

s s

q

sL P

s

+

=

Sustituyendo los valores obtenidos paraP0, tenemos:

2 3

2

2 0,43750,3913 0,2071

(1 0,4375) 2!qL = =

Finalmente, ya podemos obtener el valor de L, a travs de la expresin:

0, 2071 0, 4375 2 1, 0821qL L s= + = + =

Al introducir un nuevo servidor, se mejorado notablemente el comportamiento del sistema. De lassiete unidades que tenamos como promedio con un servidor (cfr. ejemplo 2.5.1.a), pasamos a 1,0821unidades.

0

1 10,3913

1 0,875 0, 38281, 777 2, 555P= = =

+ +



20/38

Teora de colas 31

c) Cul es el nmero promedio de coches esperando a ser reparados?

Ya hemos obtenido en el apartado anterior que Lq = 0,2071 coches de promedio. La mejora de

comportamiento en el sistema viene dada por la notable reduccin de Lq, que ha pasado de 6,125 a0,2071. En ambos casos, la diferenciaLLq= 0,875.

d) Cul es la probabilidad de que deban estacionarse coches en la calle?

El valor de la probabilidad a hallar ser:

1 (P0+ P1+ P2+ P3+ P4)

Aplicando las frmulas, obtenemos las probabilidades P1a P4(ya hemos obtenidoP0al calcularLyLq).

P1= 0,3424P2= 0,1498P3= 0,0655P4= 0,0287

De modo que la probabilidad buscada es: 0,0292, esto es, un 2,92%.

e) Cunto tiempo transcurrir, por trmino medio, desde que el coche llega al taller hasta que seacaba la reparacin?

El valor de Wse obtiene mediante la frmula de Little:1,0821

2,16420,5

LW

= = =

La reduccin deLprovoca una reduccin proporcional de W, que en este caso es algo ms de 2 horas.


0,20710,4142

0,5

qq

LW

= = =

El tiempo promedio de espera en cola valdr, en este caso, 0,4142 horas (unos 25 minutos).

Puede apreciarse que, desde cualquier punto de vista, se ha obtenido una notable mejora en el servicioal aadir un nuevo servidor.

2.5.3 Modelo de cola limitada y un servidor: M/M/1 : GD/k/

En el modelo de cola limitada, imponemos que el tamao mximo del sistema sea k. Esto significa quepodemos tener k 1 unidades en la cola y otro en servicio. Si se registra una llegada habiendo k

unidades, no se permite la entrada de la unidad, que debe abandonar el sistema.



21/38


Los coeficientes Cnson los mismos que el modelo de Kendall cuando el estado del sistema es inferioro igual a k. Para estados tales que n> k, el coeficiente es nulo:

n

nnC

= =

para n k

0nC = para n > k

De modo que la expresin deP0es la siguiente:

( )0 1 1

0

1 1 1

1 11

n k kk

n

P

+ +

=

= = =

Las probabilidades de que el sistema est en un estado n(siempre que nk) tienen la expresin:

1

1

1n

n kP

+

=

Una vez obtenidas lasPn, podemos obtener L como la esperanza matemtica de los estados del

sistema:

1

1

( 1)

1 1

k

k

kL

+

+

+=

(Ntese que cuando k , la expresin de L coincide con la obtenida para el modelo de Kendall). Laexpresin de la longitud media de la cola es:

(1 )q oL L P=

Para obtener los tiempos de espera no pueden usarse las frmulas de Little, puesto que las nno soniguales para toda n (= 0, si n > k). Debe obtenerse la tasa de llegadas al sistema, que vale:

MODELO DE NACIMIENTO Y MUERTEM/M/1 : GD/k/ (COLA LIMITADA)

0 kk-11 32

...



22/38

Teora de colas 33

(1 )kP =

Y por lo tanto, los tiempos medios en el sistema y de espera en cola valen:

LW

= qq

LW

=

De la expresin de la tasa media de llegadas podemos deducir adems que la tasa de unidadesrechazadas ser:

kP

Ello se debe a que las llegadas totales pueden entrar al sistema, o bien ser rechazadas por ste.

Una diferencia con este modelo y los descritos en las secciones 2.5.1 y 2.5.2 es que las colas limitadas,por su propia definicin, siempre tienen un nmero finito de elementos. En consecuencia, sonadmisibles a priorisistemas en los que > 1. En estos casos, no es igual al factor de ocupacin deun servidor. El factor de ocupacin debe calcularse, en este caso, a partir de la tasa de llegadasefectiva:

=

As, aunque > 1, el factor de ocupacin del sistema estar siempre entre cero y uno.

Las expresiones dadas anteriormente son vlidas para cualquier valor del parmetro , excepto para = 1. Para este caso, tendremos:

1

1nP

k=

+

2

kL=

2.5.4 Modelo de cola limitada y varios servidores: M/M/s : GD/k/

Se trata ahora de un modelo consservidores en paralelo, con la cola limitada a kelementos. A pesarde que el sistema pueda tener efectivamente ms servidores, tendremos como mximo kservidores

tiles, por lo quesk. Tal como suceda con el modelo de cola no limitada, el factor de utilizacinvaldr:

s

=

Para estos modelos, las frmulas que caracterizan al sistema para un caso general tienen unacomplejidad apreciable. Por tanto, puede resultar til, si k es lo bastante pequeo, resolverdirectamente el proceso de nacimiento y muerte concreto.

Las probabilidades de estado del sistema se calculan a partir deP0, con las expresiones:



23/38


Las probabilidades de estado para n= 1, 2, ...,svalen:

Las probabilidades de estado para n=s,s+1, ..., k

( )0!

n

n n sP Ps s

=

A partir de la expresin de P0pueden obtenerse las de la longitud esperada de cola y la de tamaoesperado del sistema:

En cuanto a Wy Wq, se obtienen del mismo modo que en el modelo con un solo servidor.

Dado que el tamao de la cola est limitado, pueden admitirse situaciones en las que >s. A medidaque aumenta, tendremos que L k, y que Pk1, por lo que los tiempos de espera tendern aaumentar.

Ejemplo 2.5.4.a RESTAURANTE EL TNEL DE JOSEP (A)

El propietario del restaurante El tunel de Josep desea evaluar la calidad de su servicio en lo relativoa esperas de los clientes. Actualmente el restaurante cuenta con 6 mesas, que se llenan en cuantollegan los clientes (no hay reserva previa). Se estima que llega un promedio de 3,5 grupos cada hora yque cada grupo permanece en el restaurante durante 1,5 horas.

La poltica actual es la de dejar esperar solamente a dos grupos cuando todas las mesas estn llenas.Cuando hay dos grupos esperando, la poltica del restaurante (poltica A) es la de indicar a losclientes que puedan llegar que no pueden ser servidos, por lo que stos abandonan el sistema. Sedesea saber:

a) Cul es el nmero medio de grupos esperando?b) Cul es el nmero medio de grupos en el restaurante (tanto los que esperan como los que son

servidos)?c) Cul es el tiempo medio de espera, antes de entrar a comer?d) Qu probabilidad existe de denegar el servicio a un grupo?

( ) ( )1

00 1

/ /

! !

n ss kn s

n n s

Pn s

= = +

= +

( )0

/

!

n

nP Pn

=

( )

( )( )0 2

/1 ( ) 1

! 1

s

k s k sq

PL k s

s

=

1 1

0 0

1s s

n q nn n

L nP L s P

= =

= + +



24/38

Teora de colas 35

Tambin se desea saber cul sera el efecto de cambiar la poltica de espera a los clientes. Msconcretamente, cmo se veran afectados los valores anteriores si:

Se deja esperar cinco grupos de clientes, en vez de dos (poltica B). Se deja esperar a todos los grupos de clientes que lleguen. Dada la calidad del restaurante, se

supone que ninguno de ellos abandonar, por larga que sea la cola (poltica C).

SOLUCIN:

En primer lugar, indicar que los parmetros comunes a las tres polticas son:

Nmero de servidores s = 6 mesasTasa de llegadas = 3,5 llegadas/horaTasa de servicio por mesa = 1/1,5 = 0,6667 servicios/hora

Cada una de las polticas responde a un modelo de colas diferente:

Poltica A: M/M/6 : GD/8/Poltica B: M/M/6 : GD/11/Poltica C: M/M/6 : GD//

Ntese como en cada caso k = tamao mximo del sistema = 6 + tamao mximo de la cola

En los apartados del enunciado se nos piden los siguientes parmetros:

a) Lq

b) Lc) Wqd) Pk

Los resultados para cada una de las polticas se muestran en la tabla siguiente:

Poltica A Poltica B Poltica C

Lq 0,3766 1,1429 4,7662L 4,9975 6,0629 10,01

Wq 0,1222 0,3484 2,8618Pk 0,1198 0,0629 -

De los resultados obtenidos, cabe hacer la siguiente interpretacin:

La poltica actual permite un tiempo medio de espera en cola muy satisfactorio: 0,1222 horas (unos 7minutos), a costa de tener que rechazar el 11,9 % de clientes que llegan al establecimiento. La polticaB reduce a casi la mitad el porcentaje de rechazos (6,29%), a coste de aumentar el tiempo de espera encola (0,3484 horas, unos 20 minutos) de forma muy significativa. En cualquier caso, ambasalternativas parecen mejores que C, que obliga a los clientes a soportar un tiempo de espera antes decomer de 2,8616 horas (2 horas y 51 minutos) francamente inaceptable en trminos de calidad deservicio.



25/38


2.5.5 Modelos de universo finito: M/M/s : GD//m

En los modelos anteriores, se ha supuesto que el tamao del centro emisor es infinito. Esto significa,

en lo que afecta a los modelos de colas, que la llegada de una unidad al sistema no afecta a laprobabilidad de que las otras unidades lleguen al sistema. Para todos los modelos descritos hastaahora, la probabilidad de determinado nmero de llegadas por unidad de tiempo vena caracterizadapor una ley de Poisson de tasa media .

Ahora la situacin es diferente: tenemos un sistema de universo finito, compuesto de m elementos.Una consecuencia inmediata es que el sistema tiene slo m+1estados posibles: ningn elemento o unnmero entre 1 y melementos. Si ahora se entiende que el tiempo que pasa un elemento cualquierafuera del sistema sigue una ley exponencial 1/, el tiempo que falta para que llegue un elemento alsistema es el mnimo de los tiempos de llegada de alguno de los m n elementos que en un casogeneral, estn fuera del sistema. Dicho tiempo, segn las propiedades de la ley exponencial, sigue una

ley exponencial de media el inverso de n= (m n) . Aqu obtenemos la diferencia fundamentalentre las colas de universo finito y los otros modelos vistos hasta el momento: en estas colas, n esdiferente para cada estado n.

El sentido de la tasa de llegada de los modelos de universo finito es diferente de la tasa de losmodelos de universo infinito:

Para los modelos de universo finito, tal como acaba de indicarse, se define como la tasa deentradas al sistema de una unidad concreta. Se asume, por tanto, que todas las unidades secomportan de la misma manera, y que una vez ha finalizado el servicio vuelven al centro emisor.

En los modelos de universo infinito es la tasa de llegadas al sistema desde el centro emisor deuna unidad cualquiera (no de una unidad concreta). Tambin se asume un comportamiento

homogneo del centro emisor a lo largo del tiempo, pero en este caso no es relevante conocer si launidad servida regresa o no al centro emisor, ya que ste dispone de un nmero infinito deunidades.

En consecuencia, mientras que la transicin de los modelos de cola limitada a los de cola ilimitadatiene lugar cuando k(hecho que puede comprobar el lector pasando al lmite las frmulas de colalimitada), la transicin de universo finito a infinito exige hacer simultneamente my 0

MODELO DE NACIMIENTO Y MUERTEM/M/1 : GD//m (UNIVERSO FINITO)

0 mm-11 32

m (m-1) (m-2)

...



26/38

Teora de colas 37

2.5.5.1 Modelo M/M/1 : GD//m

Para un servidor, tenemos que la probabilidad de que el sistema est vaco vale:

Las otras probabilidades de estado (para nm) se obtienen como:

Finalmente, obtenemos los parmetros del sistema a partir de las expresiones:

0(1 )qL m P

+

=

0(1 )L m P

=

En cuanto a los tiempos medios en el sistema y en cola, hay que considerar que, tal como suceda conlos modelos de cola finita, debe calcularse la tasa media de llegadas al sistema, que vale:

( )m L =

Y en consecuencia, los tiempos valdrn:

LW

= qq

LW

=

2.5.5.2 Modelo M/M/s : GD//m

Una vez ms, cabe hacer la advertencia de que el nmero de servidores efectivos en el sistema ha de

ser igual o inferior al tamao mdel centro emisor. A continuacin se muestran las frmulas para estemodelo, en una secuencia similar a la del modelo con un servidor.

La expresin de la probabilidad de que el sistema est vaco es:

11

00

! !

( )! ! ( )! !

n ns N

n sn n s

m mP

m n n m n s s

= =

= +

Las probabilidades de estado del sistema se obtienen a partir de las expresiones siguientes:

1

00

!

( )!

nm

n

mP

m n

=

=

0

!

( )!

n

n

mP P

m n

=



27/38


28/38

Teora de colas 39

=1 / 2 = 0,5 reparaciones/hora

Los modelos de colas a aplicar son de universo finito:

Para un operario: M/M/1 : GD//10Para dos operarios: M/M/2 : GD//10

Los parmetros por los que se pregunta son:

a) L(nmero medio de unidades en el sistema)b) W(tiempo medio en el sistema)Los resultados obtenidos son los que se muestran a continuacin:

Un operario Dos operarios

m 10 10s 1 2L 0,9608 0,5625W 3,5238 2,1060

Como era de esperar, los resultados mejoran notablemente cuando aadimos un nuevo equipo.

Los resultados empeoran rpidamente cuando aumentamos el nmero de elementos del centro emisor.Para el caso d), el modelo aplicable es:

M/M/1 : GD//50

Y los resultados son:

L= 32,33 mquinasW= 64,66 horas

Los resultados son inadmisibles desde cualquier punto de vista, y debera aumentarse notablemente elnmero de equipos.

2.6 Costes de un sistema de lnea de espera

La obtencin de L, Lq, W y Wq a travs de los modelos de nacimiento y muerte permite tomardecisiones de diseo de sistemas de lneas de espera. Estas decisiones suelen expresarse en trminosde minimizacin de los costes asociados a la espera. Para cualquier sistema de espera tendremos dostipos de costes: costes de servicioy costes de espera. Si el tamao de la cola est limitado, tendremostambin costes de abandono.

Costes de servicio

Sern directamente proporcionales al nmero de servidores en paralelo que establezcamos en elsistema. Suelen caracterizarse con el parmetro cs, que expresa los costes de servicio por servidor paraun determinado periodo de tiempo. De este modo, tenemos:

Costes de servicio = css [um / periodo]



29/38


Al expresar los costes de servicio de este modo, suponemos que incurrimos en costes de servicio por elhecho de disponer de servidor, independientemente de que efectivamente est en servicio o no. Siincurrimos en estos costes slo cuando el servidor est ocupado, tendremos:

Costes de servicio = tasa de utilizacin del servidor css [um / periodo]

Dicha tasa de utilizacin ser igual a para los modelos de universo infinito y cola no limitada. Parael resto de modelos, deber calcularse en cada caso.

Costes de espera

La preocupacin por el diseo de un sistema de lneas de espera supone la existencia de ciertos costesde espera, asociados al nmero medio de unidades en el sistema. Dichos costes pueden interpretarse entrminos de prdida de calidad de servicio, posibles reducciones de ventas futuras debido al largotiempo de espera en experiencias anteriores, etc. Se caracterizan por el parmetro ce, que no es msque los costes de servicio por unidad en el sistema para un determinado periodo de tiempo. Dichoscostes de espera valdrn:

Costes de espera = ceL [um / periodo]

Los costes de espera tambin dependen del nmero de servidores, pero de manera indirecta: unaumento del nmero de servidores inducir una reduccin del nmero promedio de unidades en elsistemaL, en funcin del sistema que estemos tratando.

Costes de abandono

Entre otras utilidades, los modelos de cola finita permiten representar un comportamiento de abandonodel sistema por parte de las unidades, si el tamao de la cola es demasiado grande. Ms concretamente,se supone que las unidades abandonarn el sistema si, cuando stas llegan al sistema, el tamao de lacola es de ks. Se trata de unos costes de naturaleza parecida a los de espera, aunque en ocasionespueden interpretarse como reducciones de ventas actuales (por abandono). Se caracterizan por ca, quees el coste de abandono por unidad para un periodo de tiempo determinado.

Para un determinado periodo de tiempo, las unidades que abandonan el sistema valdrn:

Unidades que abandonan = Pk

Donde representa la tasa de llegadas al sistema referida al periodo considerado. La tasa de entradas

al sistema ser (1 Pk).

Los costes de abandono sern, entonces:

Costes de abandono = ca Pk [um / periodo]

Diseo del sistema

Las circunstancias para las que se optimiza el sistema variarn en cada caso, pero es habitual tomarcomo parmetro el nmero sde servidores en paralelo. Se trata entonces de encontrar el nmero deservidores que minimiza los costes totales:

Costes totales = costes de servicio + costes de espera + costes de abandono



30/38

Teora de colas 41

EJEMPLO 2.6.a TALLERES MANOLO (C)

En los ejemplos 2.5.1.a y 2.5.2.b, se detallaron las condiciones de funcionamiento del taller Manolo:

llegaban coches a razn de uno cada media hora de promedio, y se tardaba 1,75 horas en reparar unautomvil. El sr. Manolo desea saber con cuntos operarios debe contar. Para ello, estima que cadaoperario le supone un coste de 12 um/hora, y que cada cliente que espera a que se repare su coche le

supone un coste de 36 um en costes de almacenamiento. Con estos datos, se pregunta:

a) Con cuntos operarios se optimiza la suma de costes de servicio y de espera?b) Si ahora se supone que el operario slo cobra cuando trabaja, cmo se ve afectado el resultado

anterior?c) Para la solucin adoptada en a),cules son los costes totales si los coches que esperan en la

calle tienen un coste de espera de12 um y los que esperan dentro del taller 36 um?

a) Con cuntos operarios se optimiza la suma de costes de servicio y de espera?

De modo tentativo, se ha optado por calcular los costes para uno, dos y tres operarios. El modelo decolas aplicado ha sido el de M/M/s : GD//, donde s toma los valores 1, 2 y 3, respectivamente.

Para cada situacin, tenemos los resultados siguientes:

Un operario Dos operarios Tres operarios

s 1 2 3cs 12 12 12L 7 1,0821 0,9091ce 36 36 36

Costes servicio 12 24 36Costes espera 252 38,95 32,73Costes totales 264 62,95 68,73

Los costes mnimos se obtienen contratando dos operarios. La reduccin de costes de espera obtenidacon el tercer operario no compensa el aumento de costes de servicio.

b) Si ahora se supone que el operario slo cobra cuando trabaja, cmo se ve afectado el resultadoanterior?

En este caso, tendremos que los costes de servicio sern iguales a:

Costes servicio = css = (/)csEsto es, los costes de servicio son constantes: las llegadas al sistema son siempre las mismas, por loque el conjunto de operarios siempre trabaja lo mismo. Obviamente, cuanto ms operarios secontraten, menos trabajar (y cobrar) cada uno de ellos.

Un operario Dos operarios Tres operarios

0,875 0,4375 0,29166s 1 2 3cs 12 12 12L 7 1,0821 0,9091ce 36 36 36

Costes servicio 10,50 10,50 10,50Costes espera 252 38,96 32,73Costes totales 262,50 49,46 43,23



31/38


Ahora los operarios adicionales van reduciendo la tasa de servicio, por lo que los costes disminuyen demanera continua. Desde el punto de vista del empresario, el nmero de operarios a contratar esinfinito. La limitacin vendr en este caso por el salario mnimo a cobrar por cada uno de los

operarios.

c) Para la solucin adoptada en a),cules son los costes totales si los coches que esperan en lacalle tienen un coste de espera de 12 um y los que esperan dentro del taller 36 um?

Del ejemplo 2 sabemos que si contratamos dos operarios, tenemos dos puestos de trabajo, y por tantotenemos 4 coches dentro del taller. El coste de esos cuatro coches es de 12, y el de los que esperanfuera 36. Puede ser conveniente, a efectos de resolucin, ver el problema como una situacin en la quetodos los coches tienen un coste de espera de 36, excepto los cuatro primeros, que tienen unabonificacin de 24. De este modo, y para este caso particular, los costes de espera valdrn:

Costes de espera = 36L 24(1P1+ 2P2+ 3P3+ 4P4)

Las probabilidades de estado se encontraron en el ejercicio 2:

P1= 0,3424P2= 0,1498P3= 0,0655P4= 0,0287

De donde los costes de espera valen:

Costes de espera = 361,0821 24(10,3424 + 20,1498 + 30,0655 + 40,0287) = 16,07 um.Y los costes totales:

Costes totales = costes de servicio + costes de espera = 4.000 + 2.679 = 6.679

Ejemplo 2.6.b Restaurante EL TNEL DE JOSEP (B)

Para valorar con mayor precisin las diferentes polticas, se han valorado los costes del restaurantedel ejemplo 2.5.4.a, en lo que afecta a la espera, del modo siguiente:

Costes de servicio (asociados a poner una mesa en el restaurante): 0,6 um por mesa y hora. Costes de espera: 3 um por grupo de clientes en cola y hora. Costes de denegacin de servicio: 4,2 um por cliente que abandona el local sin ser servido.Se trata de valorar cul de las tres polticas (dejar atender a dos grupos, a cinco o a todos) resultams econmica en conjunto.

A partir de los datos del ejemplo 3 podemos establecer la comparativa de costes por hora. Laoriginalidad de este modelo es que los costes de espera son proporcionales a la longitud de la cola, noa la longitud total del sistema.



32/38

Teora de colas 43

Poltica A Poltica B Poltica C

s 6 6 6cs 0,6 0,6 0,6

Costes servicio 3,6 3,6 3,6Lq 0,3766 1,1429 4,7662ce 3 3 3

Costes espera 1,13 3,43 14,3Pk 0,1198 0,0629 3,5 3,5ca 4,2 4,2

Costes abandono 1,76 0,92Costes totales 6,46 7,95 5,03

Los resultados confirman el anlisis realizado en el ejemplo 3: no resulta viable, en estas condiciones,no limitar la cola. En este caso, conviene limitar la cola a 2 grupos (k= 8), dado que aumentar la cola a

5 grupos (k= 11) aumenta los costes de espera en mayor medida que los costes de servicio.

2.7 Problemas resueltos

2.7.1 La fotocopiadora

Como experto en investigacin operativa, se le ha encargado el diseo de la capacidad de un serviciode fotocopiadoras para un bufete de abogados, que actualmente cuenta con una fotocopiadora.Despus de un intenso trabajo de campo, ha obtenido los siguientes datos:

El tiempo de servicio de la fotocopiadora sigue una ley exponencial de media 3 minutos. Las llegadas a la fotocopiadora siguen una ley Poisson de 16 llegadas por hora de promedio. El coste de una persona haciendo fotocopias, o esperando para hacerlas, es de 80 um por hora. La jornada laboral en el bufete es de 40 horas semanales. El coste de posesin de una fotocopiadora est estimado en 100 um por hora laborable.Suponiendo que el nmero de personas es lo bastante grande para considerar universo infinito, y queno hay limitaciones para el nmero de personas que pueden esperar para hacer fotocopias, encontrar:

a) Tiempo medio de espera hasta que se pueda utilizar la fotocopiadorab) Probabilidades de que:

No haya nadie en la mquina

No haya nadie esperando para hacer fotocopiasc) Costes totales asociados al sistemaSi se dan instrucciones para que, si se encuentran tres personas haciendo cola para hacer fotocopias(adems de la que est fotocopiando), los trabajadores no se pongan a la cola y dejen las fotocopiaspara ms adelante, encontrar:

d) Nmero promedio de personas esperando para hacer fotocopiase) Nmero promedio de veces que se utiliza la fotocopiadora en una horaOtra alternativa es instalar una fotocopiadora adicional (de las mismas caractersticas que la primera) yeliminar la restriccin de nmero mximo de personas en la cola.



33/38


f) La instalacin de una nueva fotocopiadora supone un ahorro en costes respecto de la situacininicial? Jusfitique cuantitativamente la respuesta.

g) Cul de las dos alternativas (una o dos fotocopiadoras) se ha de escoger si aumenta la frecuenciade uso del servicio de fotocopias hasta 25 llegadas por hora? Justificar cuantitativamente larespuesta.

Solucin a la fotocopiadora

Suponiendo que el nmero de personas es lo bastante grande para considerar universo infinito, y queno hay limitaciones para el nmero de personas que pueden esperar para hacer fotocopias,encontrar:

a) Tiempo medio de espera hasta que se pueda utilizar la fotocopiadora

La situacin descrita puede modelizarse como un sistema de lneas de espera M/M/1:GD//, con losparmetros:

= 16 servicios/hora= 20 servicios/hora

= /= 0,8

El parmetro que se pide es Wq, que vale:

Wq= / (- ) = 0,8/(20-16) = 0,2 horas = 12 minutos.

b) Probabilidades de que:No haya nadie en la mquinaNo haya nadie esperando para hacer fotocopias

La primera probabilidad esP0, que vale:

P0= 1 - = 1 0,8 = 0,2

La segunda es igual aP0+P1. Como antes se ha calculadoP0, bastar esta vez con calcularP1:

P1= P0 = 0,8 0,2 = 0,16P0+ P1= 0,2 + 0,16 = 0,36

c) Costes totales asociados al sistema

Conocemos los costes de espera y de servicio por hora:

Coste espera (Ce) = 80 um/(personahora)Coste servicio (Cs) = 100 um/hora

Como la semana tiene 40 horas, los costes totales vendrn dados por la expresin:

COSTE = 40 (Cs + L Ce)



34/38

Teora de colas 45

El valor deLes, en este caso:

L = / (1 - ) = 4 personas.

Los costes totales son:

COSTE = 40 (100 + 4 80) = 16.800 um

Si se dan instrucciones para que, si se encuentran tres personas haciendo cola para hacer fotocopias(adems de la que est fotocopiando), los trabajadores no se pongan a la cola y dejen las fotocopias

para ms adelante, encontrar:

d) Nmero promedio de personas esperando para hacer fotocopias

Ahora la situacin puede representarse como un modelo de colas M/M/1:GD/k/con k = 4 (el tamaodel sistema es de 4: 3 puestos de espera y el que fotocopia), i el parmetro a buscar es Lq. As,tenemos:

L = / (1 ) (k+1) k+1/(1 k+1) = ... = 1,5631 personasP0= (1 ) /(1 k+1) = ... = 0,2974Lq= L (1 P0) = 1,3474 personas

e) Nmero promedio de veces que se utiliza la fotocopiadora en una hora

Dado que no todos los que llegan al sistema son servidos, el nmero de veces que se utiliza la mquinaes inferior a 16 (valor de ). Este valor es igual a (1 P4):

P4= P0 k= 0,1218 (probabilidad de abandonar el sistema). (1 P4) = 16 (1 0,1218) = 14,05 personas / hora

Otra alternativa es instalar una fotocopiadora adicional (de las mismas caractersticas que la primera),y eliminar la restriccin de nmero mximo de personas en la cola.

f) La instalacin de una nueva fotocopiadora supone un ahorro en costes respecto de la situacininicial? Jusfitique cuantitativamente la respuesta.

Ahora el modelo representativo es M/M/2:GD//, y se trata de valorar los costes en esta situacin.En consecuencia, hemos de hallar L, que vale:

P0= 0,4285Lq= 0,1523L = 0,9523

A continuacin, podemos encontrar los costes:

COSTE = 40 (2Cs + L Ce)

COSTE = 40 (2100 + 0,9523 80) = 11.047,36El ahorro en costes de aadir una nueva fotocopiadora (nuevo servidor) es de un 34,24 %.



35/38


g) Cul de las dos alternativas (una o dos fotocopiadoras) se ha de escoger si aumenta lafrecuencia de uso del servicio de fotocopias hasta 25 llegadas por hora? Justificarcuantitativamente la respuesta.

Con un solo servidor, tenemos: = 25/20 > 1, razn per la cual la alternativa no es viable. Con dosservidores el sistema ya lo es, dado que: = 25/(220) = 0,625.

2.7.2 Baile de los pringaos

El acto principal de las fiestas de Villarriba es el baile de los pringaos, consistente en un baileorganizado por la Comisin de Festejos del Ayuntamiento, en la que todo el pueblo come, bebe, cantay baila hasta el amanecer.

Dicho baile tiene lugar en un terreno propiedad de uno de los vecinos del pueblo. ste lo cede de buengrado para el festejo, pero desde hace algunos aos se viene quejando de que los subproductosresultantes de la apreciable ingesta alcohlica de los vecinos dejan el terreno en un estado lamentable.Por este motivo, el concejal de festejos del pueblo ha decidido instalar en el terreno cuatro lavabosporttiles. El problema que se le plantea es el de asignar el nmero de lavabos a hombres y mujeresque minimice los costes medios por hora de espera totales. Para resolver el problema realiza lassiguientes suposiciones:

Los hombres y las mujeres irn solo a los lavabos que tengan asignados (suposicin aceptable si elsistema est bien dimensionado).

A efectos de clculo, el nmero de asistentes es suficientemente grande como para consideraruniverso infinito.

De experiencias realizadas en discotecas locales, ha podido determinar que el tiempo de estanciaen el lavabo sigue una ley exponencial de media 3 minutos para los hombres y de 6 minutos paralas mujeres.

Se espera que las visitas al servicio sigan una ley Poisson de media 15 por hora para los hombres,y 18 por hora para las mujeres.

El coste de espera por persona y hora (productos que dejan de consumir, por lo que el tiempoincluye tanto la espera como la estancia en el servicio) es de 6 euros por hora y hombre y de 4euros por hora y mujer, respectivamente.

Con estos datos, se pregunta:

a) Cul es el nmero mnimo de lavabos para hombres y mujeres?b) Cul es el nmero de lavabos a asignar a hombres y mujeres que minimice los costes de espera

por hora?c) Probabilidad de que el lavabo (o lavabos) de hombres est(n) vaco(s).d) Tiempo medio de espera de hombres y mujeres antes de entrar al servicio.

Solucin a Baile de los pringaos2

a) Cul es el nmero mnimo de lavabos para hombres y mujeres?

Debemos uniformizar parmetros para hombres y mujeres:

2Para resolver este problema, se han realizado los clculos con el programa STORM.



36/38

Teora de colas 47

HOMBRES:= 15 hombres/hora

1/= 3 minutos/hombre = 0,05 horas/hombre

= 20 hombres/hora

MUJERES:= 18 mujeres/hora

1/= 6 minutos/mujer = 0,1 horas/mujer= 10 mujeres/hora

Comparando tasas de servicio y de llegada, y dado que para que una cola no se haga infinita < ,tenemos que las mujeres necesitan un mnimo de 2 lavabos y los hombres un mnimo de un lavabo.

b) Cul es el nmero de lavabos a asignar a hombres y mujeres que minimice los costes de espera

por hora?

Con lo visto anteriormente, slo hay dos posibilidades:

Dos lavabos de hombres y dos de mujeres (2H 2M). Un lavabo de hombres y tres de mujeres (1H 3M).Los costes de cada alternativa sern proporcionales a la longitud media del sistema L:

Ctotal= 6Lhombres+ 4Lmujeres

Los resultados para las diferentes alternativas se muestran en las tablas siguientes:

2 H 2 M

0,375 0,9L (unidades) 0,8727 9,4737Wq(horas) 0,000818 0,4263Cespera(euros/hora) 5,24 37,89Po 0,4545 0,0526

El coste total de esta alternativa es de: 5,24 + 37,89 = 43,13 euros/hora

1 H 3 M

0,75 0,6L (unidades) 3 2,3321Wq(horas) 0,15 0,0296Cespera(euros/hora) 18 9,33Po 0,25 0,146

El coste total de esta alternativa es de: 18 + 9,33 = 27,33 euros/hora.

Por lo que la mejor solucin es reservar tres lavabos a las mujeres y uno a los hombres. El resto dedatos que se preguntan puede encontrarse en la tabla.



37/38


2.7.3 PANS CON PANS

La empresa PANS CON PANS se dedica al sector de la hostelera y dispone de una cadena de

establecimientos de comida rpida basada en mens de bocadillos y refrescos. Nos ha solicitado unestudio con la intencin de generar unos estndares de calidad de atencin al pblico para todos susestablecimientos.

Se informa de que, aunque tienen un horario de atencin al pblico bastante amplio, el 85% de la cifrade negocio se obtiene durante las horas punta de comida y cena, periodos que conjuntamente ocupanseis horas de la jornada laboral. Durante estos periodos de mxima afluencia de pblico, los clientesllegan con un tiempo medio entre llegadas de 3 minutos, siguiendo una ley de Poisson, y piden comopromedio 1,2 bocadillos por persona.

Como los establecimientos son de poco aforo, acostumbra a haber slo un cajero que, debidamenteentrenado, es capaz de atender un pedido y pasarlo a la cocina en un tiempo de 20 segundos de media.Una vez ha llegado el pedido a la cocina, el tiempo que un cocinero necesita para elaborar unbocadillo es de un promedio de 2 minutos. Despus, el cajero toma el bocadillo, lo deposita en labandeja y le desea al cliente buen provecho. Estas operaciones se realizan en un tiempo promedio de15 segundos. (Los tiempos de servir las bebidas y cobrar no deben tenerse en cuenta, pues sonoperaciones simultneas y de menor duracin que la elaboracin de los bocadillos.)

El conjunto de tiempos para realizan un servicio se puede considerar exponencial para la suma detiempos en las diferentes operaciones. Por otra parte, estara mal visto que el cajero iniciara un nuevopedido hasta que el cliente anterior no se encontrara totalmente servido.

PANS CON PANS desea establecer un estndar de calidad que impida que en la cola haya ms de

tres clientes durante un 5% del tiempo en horas punta. Dado que el nmero de cajeros es limitado yslo puede aumentarse el nmero de cocineros, se desea saber cuntos cocineros deberamos contratarsimultneamente en un mismo servicio, con estos datos.

Solucin a PANS CON PANS

Nos encontramos con un modelo de colas M/M/1:FIFO//

Pondremos en segundos toda la informacin relativa al tiempo:

La tasa de llegadas es de 1/180 segundos-1

El tiempo de servicio 1/es de 20 + 15 + 1,2120/NC, siendo NC el nmeroo de cocineros:

La tasa de servicio es de 1/179 con 1 cocinero1/107 con 2 cocineros1/83 con 3 cocineros1/71 con 4 cocineros

La es por tanto: 0.9944 con 1 cocinero0.5944 con 2 cocineros0.4611 con 3 cocineros0.3944 con 4 cocineros



38/38

Teoria de Colas1

Documents

Transcript of Teoria de Colas1