Filas de espera: transparências de apoio á leccionação de aulas teóricas

Slide 1 Filas de Espera Transparˆencias de apoio `a lecciona¸c˜ao de aulas te´oricas Vers˜ao 1 c °1998 Jos´e Fernando Oliveira – FEUP Filas de Espera 1 Slide 2 Introdu¸c˜ao •Fen´omeno corrente no dia-a-dia –clientes – pessoas, ve´ıculos ou outras entidades f´ısicas ou conceptuais – que necessitam de um –servi¸co, pelo qual podem ter que esperar numa fila f´ısica ou conceptual (a fila pode s´o existir conceptualmente, p.ex. senhas com n´umero de atendimento). •Trabalho pioneiro de A. K. Erlang (in´ıcio do s´ec. XX), cientista dinamarquˆes, sobre chamadas telef´onicas aguardando linha para serem encaminhadas. Slide 3 Estrutura de um sistema de fila de espera •Fonte ou popula¸c˜ao, que gera os clientes que v˜ao chegar ao sistema. •Fila, constitu´ıda pelos clientes `a espera de ser atendidos (n˜ao inclui o(s) cliente(s) em atendimento). •Servi¸co ou atendimento, que pode ser constitu´ıdo por um ou mais postos de atendimento. Fila +Servi¸co =Sistema N´umero de clientes no sistema (em cada instante) = estado do sistema Jos´e Fernando Oliveira – FEUP Filas de Espera 2 Slide 4 Fonte •Dimens˜ao da popula¸c˜ao –infinita: quando a probabilidade de ocorrer uma nova chegada n˜ao ´e influenciada pelo n´umero de clientes que j´a se encontram no sistema; –finita. •Dimens˜ao da chegada –clientes chegam um a um; –clientes chegam em grupo. •Controlo das chegadas –chegadas control´aveis (p.ex. inscri¸c˜oes em dias fixos); –chegadas incontrol´aveis (p.ex. urgˆencia de um hospital). Slide 5 •Distribui¸c˜ao das chegadas O padr˜ao das chegadas pode ser descrito pelo tempo entre duas chegadas consecutivas (tempo entre chegadas) ou pelo n´umero de chegadas por unidade de tempo (distribui¸c˜ao das chegadas). –constante: intervalos de tempo entre chegadas sucessivas fixos (p.ex. filas de montagem industriais); –aleat´orio: os intervalos de tempo entre chegadas sucessivas n˜ao podem ser previstos com certeza ⇒distribui¸c˜oes de probabilidade. •Taxa de chegada (λ) N´umero m´edio de clientes que procuram o servi¸co por unidade de tempo. –independente do estado do sistema; –dependente do estado do sistema: λn,n– n´umero de clientes no sistema. •Atitude dos clientes –paciente: permanecem na fila at´e serem atendidos −→ boa aproxima¸c˜ao quando h´a poucas desistˆencias; –impaciente: desistem de esperar ou simplesmente n˜ao se juntam `a fila se esta for muito grande ⇒utiliza¸c˜ao de modelos de simula¸c˜ao. Jos´e Fernando Oliveira – FEUP Filas de Espera 3 Slide 6 Fila •N´umero de filas –fila simples: uma ´unica fila mesmo que o servidor tenha v´arios postos de atendimento; –fila m´ultipla: uma fila por posto de atendimento ⇒cada conjunto fila/posto de atendimento constitui um sistema separado de fila de espera. ´ E usual repartir as chegadas igualmente pelas v´arias filas. •Comprimento da fila –infinito: a capacidade m´axima da fila ´e muito grande quando comparada com o n´umero de elementos que habitualmente a constituem; –finito: a fila pode acolher apenas um n´umero pequeno de clientes. •Disciplina da fila –FIFO – “First In First Out”; –prioridades: p.ex. reservas, idade, emergˆencia; –aleat´oria. Slide 7 Servi¸co •Configura¸c˜ao do servi¸co N´umero de servidores em paralelo (postos de atendimento) e n´umero de fases de atendimento: –um servidor, uma fase; –um servidor, m´ultiplas fases; –m´ultiplos servidores, uma fase; –m´ultiplos servidores, m´ultiplas fases; –redes de filas de espera. •Dimens˜ao do servi¸co –simples; –em grupo (p.ex. um elevador atende v´arios clientes em simultˆaneo). Jos´e Fernando Oliveira – FEUP Filas de Espera 4 Slide 8 •Distribui¸c˜ao do tempo de servi¸co: –constante; –aleat´orio: distribui¸c˜ao exponencial negativa, Erlang, outra. •Taxa de servi¸co (µ) N´umero m´edio de clientes que podem ser atendidos por cada servidor e por unidade de tempo. 1 µ= dura¸c˜ao m´edia do servi¸co. N´umero m´edio de clientes efectivamente atendidos ≤µ→pode haver momentos de inactividade. –dependente do estado do sistema (µn, n – n´umero de clientes no sistema), p.ex. servi¸co de reclama¸c˜oes que atendesse mais depressa as reclama¸c˜oes quando a fila ´e maior: maior produtividade ou degrada¸c˜ao da qualidade do servi¸co? –independente do estado do sistema. Slide 9 Modeliza¸c˜ao de sistemas de filas de espera – Objectivo “Optimizar” o funcionamento das filas de espera, encontrando solu¸c˜oes equilibradas entre dois extremos: Congestionamento – os clientes tˆem que esperar demasiado tempo na fila →taxa de ocupa¸c˜ao dos servidores pr´oxima dos 100%. S´o aceit´avel quando o custo do servidor ´e muito maior do que o custo de espera do cliente. Rarefac¸c˜ao – os servidores permanecem inactivos durante uma percentagem de tempo elevada (situa¸c˜ao por vezes desej´avel, p.ex. servi¸cos de bombeiros). Estabelecimento de trade-offs entre o custo do servi¸co e o “custo” do tempo perdido pelos clientes na fila de espera →crescimento acentuado para tempos de espera elevados. Jos´e Fernando Oliveira – FEUP Filas de Espera 5 Slide 10 Medidas de desempenho •comprimento m´edio da fila (Lq) •n´umero m´edio de clientes no sistema (L) •tempo m´edio de espera na fila (Wq) •tempo m´edio de espera no sistema (W) •taxa m´edia de ocupa¸c˜ao (e desocupa¸c˜ao) do servi¸co (percentagem de tempo durante o qual o servi¸co est´a ocupado) Outras medidas (mais pormenorizadas) ´uteis: •Pn= probabilidade de existirem nclientes no sistema •P(n≥k) = P∞ n=kPn= probabilidade de existirem no sistema kou mais clientes •P(Wq= 0) = probabilidade de o tempo de espera na fila ser zero •P(Wq> t) = probabilidade de o tempo de espera na fila exceder t •P(W > t) = probabilidade de o tempo gasto no sistema exceder t Slide 11 Nomenclatura λ— taxa de chegada (n´umero m´edio de clientes que chegam por unidade de tempo). 1 λ— intervalo m´edio entre duas chegadas consecutivas. λn— taxa de chegada dependente do estado, isto ´e, quando existem n clientes no sistema. λ=P∞ n=0λnPn— taxa m´edia de entrada no sistema. µ— taxa de servi¸co (n´umero m´edio de clientes que cada servidor tem capacidade para atender por unidade de tempo). 1 µ— tempo m´edio de servi¸co. µn— taxa de servi¸co dependente do estado, isto ´e, quando existem n clientes no sistema. s— n´umero de servidores. ρ— parˆametro auxiliar, normalmente designado por taxa de ocupa¸c˜ao. Jos´e Fernando Oliveira – FEUP Filas de Espera 6 Slide 12 Caracteriza¸c˜ao das distribui¸c˜oes das chegadas e do atendimento 1. Descrever a informa¸c˜ao recolhida, sobre chegadas de clientes e seu atendimento, atrav´es de histogramas e parˆametros amostrais (m´edia, variˆancia,...). 2. Inferir dos parˆametros amostrais os parˆametros da popula¸c˜ao. 3. “Ajustar” uma distribui¸c˜ao te´orica ao histograma experimental, i.e., escolher uma distribui¸c˜ao estat´ıstica que descreva “adequadamente” o fen´omeno analisado. A maioria dos modelos anal´ıticos de filas de espera sup˜oe chegadas seguindo uma distribui¸c˜ao de Poisson e um tempo de atendimento caracterizado por uma distribui¸c˜ao exponencial negativa – distribui¸c˜oes que mais frequentemente caracterizam as filas de espera reais. Slide 13 Distribui¸c˜ao exponencial negativa Fun¸c˜ao densidade de probabilidade de T: f(t) =    αe−αt se t≥0 0 se t < 0 Distribui¸c˜ao acumulada: F(t) = P(T≤t) = 1 −eαt (t≥0) M´edia: E(T) = 1 α Variˆancia: V ar(T) = 1 α2 Jos´e Fernando Oliveira – FEUP Filas de Espera 7 Slide 14 Distribui¸c˜ao de Poisson Fun¸c˜ao distribui¸c˜ao de probabilidade de X: f(x) = (αt)xe−αt x!x= 0,1,2,... x f(x) 0012345678 0.05 0.1 0.15 0.2 0.25 0.3 Função densidade de probabilidade de uma variável com distribuição de Poisson (αt=2) Parˆametro da distribui¸c˜ao: αt α— n´umero m´edio de acontecimentos por unidade de tempo; t— comprimento do intervalo de tempo em an´alise; x— n´umero de acontecimentos durante o intervalo t. M´edia: E(X) = αt Variˆancia: V ar(X) = αt Slide 15 Propriedades •Se o tempo entre dois acontecimentos consecutivos segue uma distribui¸c˜ao exponencial negativa com parˆametro α, ent˜ao o n´umero de acontecimentos por unidade de tempo tsegue uma distribui¸c˜ao de Poisson com parˆametro αt. •A distribui¸c˜ao exponencial negativa n˜ao tem mem´oria, i.e., a probabilidade de ocorrˆencia de um acontecimento ´e independente do instante de tempo em que ocorreu o acontecimento imediatamente anterior. Jos´e Fernando Oliveira – FEUP Filas de Espera 8 Slide 16 •Sejam T1, T2,...,Tnvari´aveis aleat´orias com distribui¸c˜ao exponencial negativa e parˆametros α1, α2,...,αn. A vari´avel u= min{T1, T2,...,Tn}, que representa o tempo at´e que o primeiro de entre nacontecimentos ocorra, segue uma distribui¸c˜ao exponencial negativa com parˆametro α=Pn i=1 αi. Esta propriedade permite modelizar sistemas com kservidores idˆenticos (mesma distribui¸c˜ao) com parˆametro µ, operando em paralelo, como um ´unico servidor com parˆametro kµ (o pr´oximo cliente ´e atendido quando o primeiro servidor ficar livre). •Desagrega¸c˜ao — se a chegada de clientes seguir uma distribui¸c˜ao de Poisson com parˆametro λ, e esses clientes puderem ser divididos em diferentes tipos de tal forma que a probabilidade pide o cliente ser de um dado tipo iseja fixa e Pipi= 1, ent˜ao a chegada de cada um dos clientes segue ainda uma distribui¸c˜ao de Poisson com parˆametro λi=piλ. Slide 17 Processos de vida e morte Processos estoc´asticos sem mem´oria que, aplicados `as filas de espera, associam vida a uma chegada `a fila e morte `a sa´ıda de um cliente depois de atendido, segundo as seguintes hip´oteses: •Dado que no instante to sistema se encontra no estado n, o tempo que separa t: –do pr´oximo nascimento (chegada) segue uma distribui¸c˜ao exponencial negativa com parˆametro λn; –da pr´oxima morte (servi¸co terminado) segue uma distribui¸c˜ao exponencial negativa com parˆametro µn. •Nunca podem ocorrer simultaneamente mais do que um nascimento ou uma morte (transi¸c˜ao apenas para estados adjacentes). Jos´e Fernando Oliveira – FEUP Filas de Espera 15 Slide 30 Modelo b´asico com Sservidores – M/M/S 0312 λλλ µ2µ3µ nn-1 λ Sµ S-2 S+1S-1 S λλ (S-1)µSµ λ Sµ ... ... •Caso mais geral de uma fila de espera ´unica, baseada num processo de vida e morte, em que existem Sservidores em paralelo. •A taxa de chegada λ´e independente do estado do sistema. •A taxa de servi¸co µ´e igual para todos os servidores, sendo a taxa de atendimento (conjunto dos Sservidores) dada por Sµ. •A taxa de ocupa¸c˜ao ´e igual a λ Sµ , que ter´a que ser <1 para que o sistema esteja em equil´ıbrio. Slide 31 •A taxa de entrada em cada estado ´e sempre igual a λ. •A taxa de sa´ıda varia com o estado: –para estados onde os servidores n˜ao estejam todos ocupados, a distribui¸c˜ao exponencial negativa do intervalo de tempo entre sa´ıdas de clientes atendidos tem parˆametro kµ (com k < S), sendo ko n´umero de servidores ocupados nesse estado — quanto mais servidores estiverem ocupados mais prov´avel ´e sair um cliente atendido do sistema. –para os estados correspondentes a todos os servidores ocupados (estados com Sou mais clientes no sistema), o tempo entre sa´ıdas de clientes atendidos tem parˆametro Sµ e n˜ao depende do n´umero de clientes no sistema. Jos´e Fernando Oliveira – FEUP Filas de Espera 16 Slide 32 Caracter´ısticas do modelo M/M/S Chegada: Poissoniana Tempo atendimento: exponencial negativo Taxa: λclientes / u. tempo Taxa: µclientes / u.tempo e servidor Popula¸c˜ao =∞Noservidores: S Fila m´axima =∞ρ=λ Sµ ,com ρ < 1 Taxa de ocupa¸c˜ao =ρ Taxa de desocupa¸c˜ao = 1 −ρ Lq=∞ X n=S (n−S)Pn= P0³λ µ´Sρ S!(1 −ρ)2Wq=Lq λ L=∞ X n=0 nPn=Lq+λ µW=Wq+1 µ=L λ P0=1 S−1 X n=0 ³λ µ´n n!+³λ µ´S S! 1 1−ρ P(W > t)t≥0=e−µt   1 + P0³λ µ´S S!(1 −ρ) 1−e−µt(S−1−λ/µ) S−1−λ µ    Pn=     ³λ µ´n n!P0,se 0 ≤n≤S ³λ µ´n S!Sn−SP0,se n≥S P(Wq> t)t≥0= [1 −P(Wq= 0)]e−Sµ(1−ρ)t P(Wq= 0) = S−1 X n=0 Pn Slide 33 Exemplo – Esta¸c˜ao de correios Uma moderna esta¸c˜ao de correios pretende dimensionar e reorganizar o seu atendimento ao p´ublico, pretendendo, no entanto, manter o mesmo esquema de atendimento em que todos os funcion´arios atendem todo o tipo de clientes, pedidos de informa¸c˜ao, reclama¸c˜oes, aquisi¸c˜ao de selos, vales postais, etc. Para isso recolheu informa¸c˜ao sobre o n´umero de chegadas de clientes, bem como sobre os tempos de atendimento tendo conclu´ıdo que as chegadas seguiam bastante aproximadamente uma distribui¸c˜ao de Poisson com parˆametro λ= 1.56 chegadas por minuto, enquanto os tempos de servi¸co seguiam uma distribui¸c˜ao negativa com m´edia igual a 66.24 segundos, a que corresponde uma taxa de atendimento µ= 1/66.24 ×60 = 0.906 atendimentos por minuto. O custo hor´ario de cada funcion´ario ´e de 1 500$00. Quanto aos clientes arbitra-se um custo hor´ario independente do tempo de espera e igual ao dos funcion´arios dos correios. Jos´e Fernando Oliveira – FEUP Filas de Espera 17 Slide 34 Resolu¸c˜ao – Esta¸c˜ao de correios Comparando as taxas de chegada e de atendimento conclui-se de imediato que λ > µ pelo que ser´a necess´ario um n´umero de servidores superior a 1. Fazendo c´alculos para 2, 3 e 4 servidores, a partir das express˜oes do quadro relativo ao modelo M/M/S, obt´em-se a seguinte tabela: Noservidores ρ P0Wq S= 2 0.86 0.075 3.17 minutos S= 3 0.57 0.162 0.28 minutos S= 4 0.43 0.175 0.05 minutos Note-se que nas filas M/M/S P0n˜ao representa a taxa de desocupa¸c˜ao mas apenas a probabilidade de todos os servidores estarem desocupados. No entanto, quando a taxa de ocupa¸c˜ao (ρ) diminui, P0aumenta e, inversamente, Wqdiminui. Uma vez que os clientes ter˜ao sempre que ser servidos e o tempo de servi¸co ´e constante (n˜ao depende do n´umero de servidores), o custo depende do tempo gasto na fila de espera Wq. Slide 35 N´umero de clientes chegados num per´ıodo de 8 horas: λ×8×60 = 1.56 ×8×60 = 749 clientes Tempo perdido na fila de espera por dia: S= 2 →3.17 ×749 = 2374 min = 39.57 horas S= 3 →0.28 ×749 = 210 min = 3.50 horas S= 4 →0.05 ×749 = 37 min = 0.62 horas Custos por dia: (custo total = custo de espera dos utentes + custo de servi¸co dos empregados) S= 2 →39.57 ×1500$ + 2 ×8×1500$ = 59355$ + 24000$ = 83355$ S= 3 →3.50 ×1500$ + 3 ×8×1500$ = 5250$ + 36000$ = 41250$ S= 4 →0.62 ×1500$ + 4 ×8×1500$ = 930$ + 48000$ = 48930$ Op¸c˜ao que minimiza os custos globais: 3 servidores. Jos´e Fernando Oliveira – FEUP Filas de Espera 18 Slide 36 Informa¸c˜ao adicional, potencialmente ´util neste processo de tomada de decis˜ao, s˜ao os: Tempos de actividade/inactividade dos empregados: Actividade total = 749 ×1 0.906 = 826min = 13.78h/dia Inactividade: S= 2 →2×8−13.78 = 2.22h (taxa de inactividade = 14%) S= 3 →3×8−13.78 = 10.22h (taxa de inactividade = 43%) S= 4 →4×8−13.78 = 18.22h (taxa de inactividade = 57%) Slide 37 Tabela pr´atica para o c´alculo de P0em filas M/M/S N´umero de servidores (S) λ µ2 3 4 5 0.15 0.8605 0.8607 0.8607 0.8607 0.20 0.8182 0.8187 0.8187 0.8187 0.25 0.7778 0.7788 0.7788 0.7788 0.30 0.7391 0.7407 0.7408 0.7408 0.35 0.7021 0.7046 0.7047 0.7047 0.40 0.6667 0.6701 0.6703 0.6703 0.45 0.6327 0.6373 0.6376 0.6376 0.50 0.6000 0.6061 0.6065 0.6065 0.55 0.5686 0.5763 0.5769 0.5769 0.60 0.5385 0.5479 0.5487 0.5488 0.65 0.5094 0.5209 0.5219 0.5220 0.70 0.4815 0.4952 0.4965 0.4966 0.75 0.4545 0.4706 0.4722 0.4724 0.80 0.4286 0.4472 0.4491 0.4493 0.85 0.4035 0.4248 0.4271 0.4274 0.90 0.3793 0.4035 0.4062 0.4065 0.95 0.3559 0.3831 0.3863 0.3867 Jos´e Fernando Oliveira – FEUP Filas de Espera 19 Slide 38 N´umero de servidores (S) λ µ2 3 4 5 1.00 0.3333 0.3636 0.3673 0.3678 1.20 0.2500 0.2941 0.3002 0.3011 1.40 0.1765 0.2360 0.2449 0.2463 1.60 0.1111 0.1872 0.1993 0.2014 1.80 0.0526 0.1460 0.1616 0.1646 2.00 0.1111 0.1304 0.1343 2.20 0.0815 0.1046 0.1094 2.40 0.0562 0.0831 0.0889 2.60 0.0345 0.0651 0.0721 2.80 0.0160 0.0521 0.0581 3.00 0.0377 0.0466 3.20 0.0273 0.0372 3.40 0.0186 0.0293 3.60 0.0113 0.0228 3.80 0.0051 0.0174 4.00 0.0130 4.20 0.0093 4.40 0.0063 4.60 0.0038 4.80 0.0017 Slide 39 Exemplo – Servi¸co de Veterin´aria da Cooperativa Agr´ıcola de Belos Ares Edmundo Terra ´e um dos cr´ıticos do funcionamento do servi¸co de veterin´aria da Cooperativa Agr´ıcola de Belos Ares – afirma que sempre que chama um veterin´ario ele nunca vem no mesmo dia. Actualmente h´a dois veterin´arios, cada um atendendo em m´edia 5 chamadas por dia – o servi¸co pode ser considerado M/M/2. Quanto aos pedidos de apoio a animais doentes verifica-se que chegam aleatoriamente, seguindo um processo de Poisson, `a raz˜ao de 9 por dia. Sens´ıvel `as cr´ıticas dos membros da Cooperativa, a direc¸c˜ao decidiu discutir o caso, admitindo mesmo contratar um novo veterin´ario. Avalie a situa¸c˜ao, contribuindo com informa¸c˜ao que possa ser ´util para uma tomada de decis˜ao sobre a referida contrata¸c˜ao. Jos´e Fernando Oliveira – FEUP Filas de Espera 20 Slide 40 Exemplo – Servi¸co de fotoc´opias A sec¸c˜ao de fotoc´opias duma empresa, aberta 40 horas por semana, disp˜oe de 2 fotocopiadoras arrendadas pelo valor total de 12.0 contos cada por semana. Os utilizadores chegam `a raz˜ao de 33/hora e o tempo m´edio de servi¸co ´e de 3 minutos. Suponha verificadas as condi¸c˜oes indicadas no estudo das filas de espera. 1. Determine: •o nom´edio de pessoas aguardando a utiliza¸c˜ao duma fotocopiadora; •o tempo m´edio duma pessoa na fila; •o tempo m´edio duma pessoa no sistema. 2. O custo hor´ario m´edio, para a empresa, do pessoal que recorre ao servi¸co de fotocopias ´e de 1.8 contos/hora, incluindo overheads. Ser´a conveniente aumentar ao n´umero de fotocopiadoras arrendadas? E para que n´umero? Slide 41 Exemplo – Manuten¸c˜ao O supervisor operacional duma empresa de m´aquinas el´ectricas reparou que o servi¸co de manuten¸c˜ao corrente de equipamento ´e normalmente atrasado, devido `a espera na sec¸c˜ao de ferramentas. Como qualquer atraso na produ¸c˜ao obriga a uma altera¸c˜ao das ordens de fabrico ou mesmo a trabalho em horas extraordin´arias, o supervisor requereu um estudo sobre a viabilidade de acrescentar mais funcion´arios `a sec¸c˜ao em quest˜ao, para melhorar a resposta `as necessidades do servi¸co de manuten¸c˜ao. O assunto foi estudado, concluindo-se que o tempo m´edio entre-chegadas ´e de 80 segundos e que o tempo m´edio de atendimento, por parte dum funcion´ario, ´e de 60 segundos. O custo total dum funcion´ario na sec¸c˜ao de ferramentas ´e de $8.50 por hora, enquanto que o custo relativo `a espera (m´aquina parada) ´e de $15.00 por hora. Considera-se o dia de 8 horas. A tabela seguinte, parcialmente completa, informa sobre o efeito na fila de espera de acrescentar mais funcion´arios (fila tipo M/M/s, s = 2, 3), `a sec¸c˜ao, incluindo a an´alise dos custos di´arios totais envolvidos nas v´arias op¸c˜oes. Complete a tabela. Na perspectiva dos custos totais tabelados, qual ´e a melhor op¸c˜ao ? Jos´e Fernando Oliveira – FEUP Filas de Espera 21 Slide 42 Node funcion´arios 1 2 3 Nom´edio equipamentos no sistema (L) 3.00 Tempo m´edio no sistema, em min.(W) 4.00 Nom´edio na fila de espera (Lq) 2.25 Tempo m´edio na fila de espera, em min. (Wq) 3.00 Percentagem de tempo de desocupa¸c˜ao 0.25 Custo ($)/dia dos funcion´arios 68.00 Custo ($)/dia de esperas 360.00 Custo total di´ario 428.00 Slide 43 Fila de espera com comprimento limitado – M/M/1/K e M/M/S/K Fila de espera com comprimento limitado — caso em que, por limita¸c˜oes diversas, o n´umero m´aximo de elementos no sistema (atendimento + fila de espera) ´e K. ⇓ Taxa de chegada (λn) depende do estado (n) do sistema: λn=   λpara n= 0,1,2,...,K−1 0 para n≥K Taxa de chegada −→ Taxa m´edia de entrada no sistema λ(m´edia ponderada das taxas λe zero pelas suas probabilidades de ocorrˆencia): λ= K−1 X n=0 λ×Pn=λ× K−1 X n=0 Pn=λ(1 −PK) Note-se que a probabilidade de o sistema estar em estados n≥K+ 1 ´e nula (n˜ao se aceita ningu´em acima de K). Jos´e Fernando Oliveira – FEUP Filas de Espera 22 Slide 44 Consequˆencias •As rela¸c˜oes fundamentais entre Lq,L,WqeWmantˆem-se verdadeiras, substituindo λpor λ. •λ µrepresenta a taxa de ocupa¸c˜ao. •ρ=λ µrepresenta a taxa de press˜ao. •O sistema pode estar em equil´ıbrio para valores de ρsuperiores a 1. No entanto, nesse caso, haver´a um n´umero potencialmente elevado de utentes do sistema que chegam e n˜ao s˜ao servidos. •Pkrepresenta a probabilidade de desistˆencia por falta de capacidade do sistema para atender clientes que chegam quando o sistema est´a cheio. •Para S > 1 servidores a taxa de sa´ıda do sistema continua a depender do estado do sistema. Slide 45 Caracter´ısticas do modelo M/M/1/K Chegada: Poissoniana Tempo atendimento: exponencial negativo Taxa: λclientes / u.tempo Taxa: µclientes / u.tempo e servidor λn=   λpara n= 0,1,2,...,K−1 0 para n≥KNoservidores: 1 λ= K−1 X n=0 λPn=λ(1 −PK)ρ=λ µ Popula¸c˜ao =∞Taxa de ocupa¸c˜ao =λ µ N0m´aximo de elementos no sistema =KTaxa de desocupa¸c˜ao = 1 −λ µ Fila m´axima K−1 Lq=∞ X n=1 (n−1)Pn=L−λ µWq=Lq λ L=∞ X n=0 nPn=ρ 1−ρ−(K+ 1)ρK+1 1−ρK+1 W=Wq+1 µ=L λ P0=1−ρ 1−ρK+1 (Taxa de desocupa¸c˜ao) Pn=   ρnP0,se n= 1,...,K 0,se n > K P(Wq= 0) = P0 Jos´e Fernando Oliveira – FEUP Filas de Espera 23 Slide 46 Caracter´ısticas do modelo M/M/S/K Chegada: Poissoniana Tempo atendimento: exponencial negativo Taxa: λclientes / u.tempo Taxa: µclientes / u.tempo e servidor λn=(λpara n= 0,1,2,...,K−1 0 para n≥KNoservidores: S λ= K−1 X n=0 λPn=λ(1 −PK)ρ=λ Sµ Popula¸c˜ao =∞Taxa de ocupa¸c˜ao =λ Sµ N0m´aximo de elementos no sistema =KTaxa de desocupa¸c˜ao = 1 −λ Sµ Fila m´axima K−S Lq=∞ X n=S (n−S)Pn=Wq=Lq λ =P0³λ µ´Sρ S!(1−ρ)2×[1 −ρK−S−(K−S)ρK−S(1 −ρ)] L=∞ X n=0 nPn=Lq+λ µW=Wq+1 µ=L λ P0=1 S−1 X n=0 ³λ µ´n n!+³λ µ´S S! K X n=S ρn−S Pn=         ³λ µ´n n!P0,se n= 1, . . . , S ³λ µ´n S!Sn−SP0,se n=S,...,K 0,se n > K P(Wq= 0) = S−1 X n=0 Pn Slide 47 Exemplo – Porto de mar Um porto que recebe navios graneleiros tem uma ´unica esta¸c˜ao de descarga (m´ovel) que permite descarregar, em m´edia, 5 navios por dia. O porto tem um cais que permite a acostagem de apenas 2 navios, pelo que, quando o cais est´a ocupado, navios adicionais que pretendam acostar s˜ao desviados para outro porto, acarretando um custo de 20000 contos por navio desviado. A imobiliza¸c˜ao de navios no porto tem um custo de 12000 contos por dia e por navio. As chegadas dos navios podem ser consideradas Poissionianas, com uma taxa de 3 navios por dia, sendo os tempos de descarga exponenciais negativos. Pretende-se avaliar a viabilidade econ´omica de ampliar o cais de modo a poder receber 3 navios, amplia¸c˜ao essa a que corresponderia um encargo adicional de 1000 contos por dia. Jos´e Fernando Oliveira – FEUP Filas de Espera 24 Slide 48 Resolu¸c˜ao – Porto de mar A amplia¸c˜ao do cais justifica-se se a redu¸c˜ao de custos (imobiliza¸c˜ao + desvio) de navios for maior que 1000 contos/dia. •Custo de imobiliza¸c˜ao (CI): CI = 12000Wλ = 12000Lcontos/dia •Custo de desvio (CD): CD = 20000(3 −λ) contos/dia, em que 3 −λ representa o n´umero de navios desviados por dia. Tomando ent˜ao: λ= 3 navios/dia µ= 5 navios/dia S= 1 ρ=3 5= 0.6 e recorrendo `a tabela com as caracter´ısticas do modelo anteriormente apresentada podemos calcular os custos associados a K= 2 e a K= 3. Slide 49 Custo com K= 2 P0= 0.510 P1= 0.306 P2= 0.184 1−P2= 0.816 (Probabilidade de o navio n˜ao ser desviado) λ=λ(1 −P2) = 2.448 Taxa de ocupa¸c˜ao = λ µ= 0.49 L=0.6 1−0.6−3×0.63 1−0.63= 0.673 navios Lq= 0.673 −0.49 = 0.183 navios CI +CD = 12000 ×0.673 + 20000 ×(3 −2.448) = 8076 + 11040 = 19116 contos/dia Jos´e Fernando Oliveira – FEUP