Post on 06-Jan-2016
description
transcript
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 1/20
Teoría de Colas
Una cola es una línea de espera. Las colas son frecuentesen nuestra vida cotidiana: en un banco, en un restaurant, enla universidad entre otras.
El fenómeno de las colas surge cuando unos recursoscompartidos necesitan ser accedidos para dar servicio a unelevado número de trabajos o clientes.
En general, a nadie le gusta esperar. Cuando la pacienciallega a su límite, la gente se va a otro lugar. Sin embargo, unservicio mu r!pido tendría un costo mu elevado
Es necesario encontrar un balance adecuado
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 2/20
Teoría de Colas
La teoría de colas es el estudio matem!tico delcomportamiento de líneas de espera. Esta se presenta,cuando los "clientes" llegan a un "lugar" demandandoun servicio a un "servidor", el cual tiene una ciertacapacidad de atención. Si el servidor no est!disponible inmediatamente el cliente decide esperar,entonces se forma la línea de espera.
Los sistemas de colas son modelos de sistemas #ueproporcionan servicio. Como modelo, puedenrepresentar cual#uier sistema en donde los trabajos oclientes llegan buscando un servicio de algún tipo salen despu$s de #ue dic%o servicio %aa sidoatendido. &odemos modelar los sistemas de este tipo
tanto como colas sencillas o como un sistema de colasinterconectadas formando una red de colas.
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 3/20
Teoría de Colas
El origen de la Teoría de Colas está en el esfuerzode Agner Kraup Erlang (Dinamarca, 1878 1!"!#
en 1!$! para analizar la congesti%n de trá&co
telef%nico con el o'eti)o de cumplir la demandaincierta de ser)icios en el sistema telef%nico de
Copen*ague+ us in)estigaciones aca'aron en unanue)a teoría denominada teoría de colas o de
líneas de espera+ Esta teoría es a*ora una*erramienta de )alor en negocios de'ido a -ue ungran n.mero de pro'lemas pueden caracterizarse,
como pro'lemas de congesti%n llegadasalida+
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 4/20
'bjetivos de la (eoría de Colas
/os o'eti)os de la teoría de colas consisten en0
denti&car el ni)el %ptimo de capacidad del sistema -ue
minimiza el coste glo'al del mismo+ E)aluar el impacto -ue las posi'les alternati)as de
modi&caci%n de la capacidad del sistema tendrían en el costetotal del mismo+
Esta'lecer un 'alance e-uili'rado (2%ptimo2# entre lasconsideraciones cuantitati)as de costes 3 las cualitati)as deser)icio+
4a3 -ue prestar atenci%n al tiempo de permanencia en elsistema o en la cola0 la 2paciencia2 de los clientes dependedel tipo de ser)icio especí&co considerado 3 eso puede *acer-ue un cliente 2a'andone2 el sistema+
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 5/20
Elementos e)istentes en un modelo decolas
*uente de entrada o población potencial0 Es un conunto deindi)iduos (no necesariamente seres )i)os# -ue pueden llegar asolicitar el ser)icio en cuesti%n+ 5odemos considerarla &nita o in&nita+
Cliente0 Es todo indi)iduo de la po'laci%n potencial -ue solicitaser)icio+ uponiendo -ue los tiempos de llegada de clientesconsecuti)os son $6t16t"6+++, será importante conocer el patr%n depro'a'ilidad seg.n el cual la fuente de entrada genera clientes+ /omás *a'itual es tomar como referencia los tiempos entre las llegadasde dos clientes consecuti)os0 consecuti)os0 clientes consecuti)os0
T9 : t t1, &ando su distri'uci%n de pro'a'ilidad+
Capacidad de la cola: Es el má;imo n.mero de clientes -uepueden estar *aciendo cola (antes de comenzar a ser ser)idos#+ De
nue)o, puede suponerse &nita o in&nita+ /o más sencillo, a efectos desimplicidad en los cálculos, es suponerla in&nita
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 6/20
Elementos e)istentes en un modelo decolas
+isciplina de la cola: Es el modo en el -ue los clientesson seleccionados para ser ser)idos+ /as disciplinas más*a'ituales son0
/a disciplina <<= (&rst in &rst out#, tam'i>n llamada<C< (&rst come &rst ser)ed#0 seg.n la cual se atiendeprimero al cliente -ue antes *a3a llegado+
/a disciplina /<= (last in &rst out#, tam'i>n conocidacomo /C< (last come &rst ser)ed# o pila0 -ue consiste
en atender primero al cliente -ue *a llegado el .ltimo+ /a ? (random selection of ser)ice#, o ?= (ser)ice
in random order#, -ue selecciona a los clientes deforma aleatoria+
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 7/20
ecanismo de servicio: Es el procedimiento por el cual se daser)icio a los clientes -ue lo solicitan+ 5ara determinartotalmente el mecanismo de ser)icio de'emos conocer eln.mero de ser)idores de dic*o mecanismo (si dic*o n.merofuese aleatorio, la distri'uci%n de pro'a'ilidad del mismo# 3 la
distri'uci%n de pro'a'ilidad del tiempo -ue le lle)a a cadaser)idor dar un ser)icio+
La cola, propiamente dic*a, es el conunto de clientes -ue*acen espera, es decir los clientes -ue 3a *an solicitado elser)icio pero -ue a.n no *an pasado al mecanismo de ser)icio+
El sistema de la cola0 es el conunto formado por la cola 3 elmecanismo de ser)icio, unto con la disciplina de la cola, -ue eslo -ue nos indica el criterio de -u> cliente de la cola elegir parapasar al mecanismo de ser)icio
Elementos e)istentes en un modelo decolas
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 8/20
istemas de colas0odelo 'ásico
LlegadasCola
Instalación
del
servicio
Disciplina
de la cola
Salidas
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 9/20
istemas de colas0Bna línea, Bn ser)idor
LlegadasCola Servidor
Salidas
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 10/20
istemas de colas0Bna línea, m.ltiples ser)idores
LlegadasCola
er)ido
r
Salidas
er)idor
er)idor
Salidas
Salidas
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 11/20
istemas de colas0arias líneas, m.ltiples ser)idores
Llegadas
Cola er)idor Salidas
er)idor
er)idor
Salidas
Salidas
Cola
Cola
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 12/20
istemas de colas0Bna línea, ser)idores secuenciales
LlegadasCola
er)idor
Salidas
Cola
er)ido
r
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 13/20
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 14/20
Como medir el rendimiento de
un sistema
En cual-uier caso, para poder tomardecisiones *acen falta datos -ue la teoría decolas puede
dar en alguno de los siguientes tres aspectos0 a# tiempo de espera (en el total del sistema
o en la cola#
'# cantidad de clientes esperando (en elsistema o en las colas#
c# tiempo ocioso de los ser)idores (total oparticular de cada ser)icio#
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 15/20
/as llegadas GDistri'uci%n e;ponencial
Media Tiempo0
P(t) /a forma alge'raica de la distri'uci%ne;ponencial es0
Donde t representa una cantidade;presada en de tiempo unidades detiempo (*oras, minutos, etc+#
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 16/20
/as llegadas GDistri'uci%n e;ponencial
/a distri'uci%n e;ponencial suponeuna ma3or pro'a'ilidad para
tiempos entre llegadas pe-ueos En general, se considera -ue las
llegadas son aleatorias
/a .ltima llegada no inHu3e en lapro'a'ilidad de llegada de lasiguiente
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 17/20
/as llegadas G Distri'uci%n de 5oisson
P
Llegadas por unidad de tiempo
u forma alge'raica es0
Donde05(# 0 pro'a'ilidad de llegadas porunidad de tiempoλ 0 tasa media de llegadase : ",718"818I
!)(
k
ek P
k λ λ
−
=
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 18/20
/as llegadas G Distri'uci%n de 5oisson
Es una distri'uci%n discretaempleada con muc*a frecuencia
para descri'ir el patr%n de lasllegadas a un sistema de colas
5ara tasas medias de llegadas
pe-ueas es asim>trica 3 se *acemás sim>trica 3 se apro;ima a la'inomial para tasas de llegadas altas
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 19/20
istemas de colas0 Elser)icio
El ser)icio puede ser 'rindado por un ser)idoro por ser)idores m.ltiples
El tiempo de ser)icio )aría de cliente a cliente El tiempo esperado de ser)icio depende de la
tasa media de ser)icio (µ# El tiempo esperado de ser)icio e-ui)ale a 1J(µ#
5or eemplo, si la tasa media de ser)icio es de" clientes por *ora Entonces el tiempo esperado de ser)icio es 1J
(µ# : 1J" : $+$L *oras, o "+L minutos
7/17/2019 Teoria de Colas
http://slidepdf.com/reader/full/teoria-de-colas-568d267ba24ca 20/20
istemas de colas0 El ser)icioDistri'uci%n Erlang
Media Tiempo0
P(t)k = ∞
k = 1k = 2
k = 8
• i : 1, entonces la distri'uci%n
Erlang es igual a la e;ponencial• i : M, entonces la distri'uci%nErlang es igual a la distri'uci%ndegenerada con tiemposconstantes
• /a forma de la distri'uci%n Erlang
)aría de acuerdo con