Slide - Teoria das Filas Pt1 - Modelagem e Simulação de Sistemas de Produção - 2023-2

PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.1 Prof. Dr. Marco A. Mesquita 3. Teoria de Filas – Parte 1 Agenda: - Teoria de Filas - Exponencial e Poisson - Birth & Death Process 6 3.1 Teoria de Filas  Estrutura Básica  Processo de Chegada  Intervalos entre chegadas  Processo de Atendimento  Tempos de atendimento  Disciplina de Filas Chegada de clientes Clientes atendidos Fila Servidores PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.2 Prof. Dr. Marco A. Mesquita 7 Processo de Chegada  Clientes (“jobs”) chegam procedentes de uma população de origem (“fonte”).  Se a população é grande (infinita), a taxa de chegadas é independente do número de clientes no sistema, caso contrário (finita), a taxa varia conforme o estado do sistema.  As chegadas podem ser “individuais” ou em “ grupo”.  O processo de chegada é caracterizado por uma distribuição de probabilidade que determina os intervalos entre chegadas.  Para chegada em grupo, tem-se ainda a distribuição do número de clientes por chegada.  Em alguns modelos, os clientes podem, dependendo do estado da fila, desistir no instante de chegada (balking) ou abandonar a fila após um dado tempo de espera (reneging).  Em alguns casos, a taxa de chegada pode variar com o tempo. 8 Processo de Atendimento  Os clientes podem ser atendidos em um único estágio de serviço (fila simples) ou terem que passar por múltiplos estágios (rede de filas).  Em cada estágio, pode haver um ou mais servidores “idênticos”, atendendo em paralelo.  Os atendimentos podem ser “individuais” ou “em grupo”.  Os tempos de atendimento são definidos por uma distribuição de probabilidade independente do servidor e do número de clientes na fila.  Em redes de filas é necessário definir o padrão de fluxo dos clientes (jobs) na rede.  Para efeito de atendimento, os clientes podem ser divididos em classes, com diferentes prioridades. PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.3 Prof. Dr. Marco A. Mesquita 9 Disciplina da Fila  A disciplina determina a ordem de atendimento dos clientes: FCFS (first come, first served): ordem de chegada, LCFS (last come, first served): ordem inversa, SPT (shortest processing time): menor tempo de serviço, EDD (earliest due time): mais urgente primeiro etc, SIRO (service in random order): ordem aleatória, ou ainda, filas com múltiplas classes, cada classe com sua prioridade de atendimento diferente. 10 Fila simples em AnyLogic Inputs: • Taxa de chegadas • Tempo médio de atendimento • Número de servidores • ... Outputs: • Tamanho médio da fila • Tempo médio de espera • Taxa de atendimentos • Utilização do servidor • ... PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.4 Prof. Dr. Marco A. Mesquita 11 Dinâmica da Fila Cliente Intervalo Chegadas Chegada Tempo de Serviço Servidor 1 Servidor 2 Tempo Tempo Início Fim Início Fim de Fila Total 1 2,1 21,2 2 4,7 12,4 3 1,9 16,2 4 7,9 12,6 5 9,6 16,6 6 11,7 22,1 7 3,9 5,1 8 5,3 5,4 9 7,3 30,8 10 1,6 7,6 12 Dinâmica da Fila (cont.) Cliente Intervalo Chegadas Chegada Tempo de Serviço Servidor 1 Servidor 2 Tempo Tempo Início Fim Início Fim de Fila Total 1 2,1 2,1 21,2 2,1 23,3 2 4,7 6,8 12,4 6,8 19,2 3 1,9 8,7 16,2 19,2 35,4 4 7,9 16,6 12,6 23,3 35,9 5 9,6 26,2 16,6 35,4 52,0 6 11,7 37,9 22,1 37,9 60,0 7 3,9 41,8 5,1 52,0 57,1 8 5,3 47,1 5,4 57,1 62,5 9 7,3 54,4 30,8 60,0 90,8 10 1,6 56,0 7,6 62,5 70,1 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.5 Prof. Dr. Marco A. Mesquita 13 Dinâmica da Fila (cont.) Cliente Intervalo Chegadas Chegada Tempo de Serviço Servidor 1 Servidor 2 Tempo Tempo Início Fim Início Fim de Fila Total 1 2,1 2,1 21,2 2,1 23,3 0,0 21,2 2 4,7 6,8 12,4 6,8 19,2 0,0 12,4 3 1,9 8,7 16,2 19,2 35,4 10,5 26,7 4 7,9 16,6 12,6 23,3 35,9 6,7 19,3 5 9,6 26,2 16,6 35,4 52,0 9,2 25,8 6 11,7 37,9 22,1 37,9 60,0 0,0 22,1 7 3,9 41,8 5,1 52,0 57,1 10,2 15,3 8 5,3 47,1 5,4 57,1 62,5 10,0 15,4 9 7,3 54,4 30,8 60,0 90,8 5,6 36,4 10 1,6 56,0 7,6 62,5 70,1 6,5 14,1 𝑊 = 21,2 + 12,4 + ⋯ + 14,1 10 = 20,87 𝑊𝑞 = 0 + 0 + 10,5 + ⋯ + 6,5 10 = 5,87 14 Dinâmica da Fila (cont.) Cliente Intervalo Chegadas Chegada Tempo de Serviço Servidor 1 Servidor 2 Tempo Tempo Início Fim Início Fim de Fila Total 1 00:02:06 08:02:06 00:21:12 08:02:06 08:23:18 00:00:00 00:21:12 2 00:04:42 08:06:48 00:12:24 08:06:48 08:19:12 00:00:00 00:12:24 3 00:01:54 08:08:42 00:16:12 08:19:12 08:35:24 00:10:30 00:26:42 4 00:07:54 08:16:36 00:12:36 08:23:18 08:35:54 00:06:42 00:19:18 5 00:09:36 08:26:12 00:16:36 08:35:24 08:52:00 00:09:12 00:25:48 6 00:11:42 08:37:54 00:22:06 08:37:54 09:00:00 00:00:00 00:22:06 7 00:03:54 08:41:48 00:05:06 08:52:00 08:57:06 00:10:12 00:15:18 8 00:05:18 08:47:06 00:05:24 08:57:06 09:02:30 00:10:00 00:15:24 9 00:07:18 08:54:24 00:30:48 09:00:00 09:30:48 00:05:36 00:36:24 10 00:01:36 08:56:00 00:07:36 09:02:30 09:10:06 00:06:30 00:14:06 𝑊 = 00: 20: 52 𝑊𝑞 = 00: 05: 52 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.6 Prof. Dr. Marco A. Mesquita 15 Clientes 0 20 40 60 80 100 1 2 3 4 5 6 7 8 9 10 Fila Atendimento 16 Servidores 0 20 40 60 80 100 Servidor 1 Servidor 2 Espera Atendimento PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.7 Prof. Dr. Marco A. Mesquita 17 Clientes no Sistema 0 1 2 3 4 5 6 0 20 40 60 80 100 N(t) Como calcular o número médio de clientes no sistema? 18 Estimativa do Número Médio de Clientes no Sistema Tempo Evento Cliente N(t) Delta 0 Início 0 2,1 2,1 Chegada 1 1 4,7 6,8 Chegada 2 2 1,9 8,7 Chegada 3 3 7,9 16,6 Chegada 4 4 2,6 19,2 Partida 2 3 4,1 23,3 Partida 1 2 2,9 26,2 Chegada 5 3 9,2 35,4 Partida 3 2 0,5 35,9 Partida 4 1 2,0 37,9 Chegada 6 2 3,9 41,8 Chegada 7 3 5,3 47,1 Chegada 8 4 4,9 52,0 Partida 5 3 2,4 54,4 Chegada 9 4 1,6 56,0 Chegada 10 5 1,1 57,1 Partida 7 4 2,9 60,0 Partida 6 3 2,5 62,5 Partida 8 2 7,6 70,1 Partida 10 1 20,7 90,8 Partida 9 0 9,2 100 Fim 0 𝐿 = 0 ∙ 2,1 + 1 ∙ 4,7 + ⋯ + 0 ∙ 9,2 100 𝐿 = 2,087 𝐿𝑞 = 0,587 Analogamente, calcula-se o número médio na fila. PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.8 Prof. Dr. Marco A. Mesquita 19 Clientes no Sistema 0 1 2 3 4 5 6 0 20 40 60 80 100 N(t) 𝐿 = 2,087 20 Notação de Kendall-Lee para Filas  Padrão de representação de sistemas de fila isolada em que os clientes aguardam em uma fila única antes do atendimento em um dos servidores em paralelo.  Cada modelo é representado por 6 códigos: 1/2/3/4/5/6 1. processo de chegada (M, D, Ek e G) 2. processo de atendimento (M, D, Ek e G) 3. quantidade de servidores 4. disciplina da fila (default FCFS) 5. capacidade do sistema (default ) 6. tamanho da população (default ) Exemplos: • M/M/1 • M/M/c • M/G/1 ... PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.9 Prof. Dr. Marco A. Mesquita 21 Definições  X(t) = quantidade de clientes no sistema em t (t  0)  Pk(t) = probabilidade de haver exatamente k clientes no sistema no instante t  c = número de servidores em paralelo  n = taxa média de chegada quando há n clientes (chegadas por unidade de tempo)  n = taxa média de serviço quando há n clientes (atendimentos por unidade de tempo)  A = distribuição dos intervalos entre chegadas  S = distribuição dos tempos de atendimento (serviço) 22 Medidas de Desempenho em Regime  pj = prob. de haver exatamente j clientes no sistema  L = número médio de clientes no sistema Lq = número médio de clientes na fila Ls = número médio de clientes em atendimento  W = tempo médio de permanência no sistema Wq = tempo médio de espera na fila Ws = tempo médio de atendimento PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.10 Prof. Dr. Marco A. Mesquita 23 Cálculo dos Indicadores  A partir dos pj’s, determinam-se: = num. médio de clientes no sistema = num. médio de clientes na fila (queue) = num. médio de clientes em serviço = taxa média (efetiva) de chegadas = utilização do sistema     0 j j j L p       1 ) ( c j j q c j L p q s L L L       0 j j j ef  p  c  Ls  24 Fórmula de Little Onde: L = número médio de clientes no sistema  = taxa média de chegadas W = tempo médio de permanência no sistema  Exemplo (slide 13):  Fórmula para Tempo de Fila 𝐿 = 𝜆 ∙ 𝑊 𝐿𝑞 = 𝜆 ∙ 𝑊𝑞 𝜆 = 10 100 = 0,1 𝑐𝑙/𝑚𝑖𝑛 𝑊 = 20,87 𝑚𝑖𝑛 𝐿 = 2,087 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.11 Prof. Dr. Marco A. Mesquita 25 Exemplo: M/M/1/FCFS/5/∞ j pj j pj vazão vj pj utilização uj pj fila qj pj 0 0,2711 1 0,2168 2 0,1735 3 0,1388 4 0,1110 5 0,0888 ? ? ? ? L médio Vazão média (cl./min) Utilização média Fila média Tempo médio total (min) Tempo médio de fila (min) Taxa efetiva (cl./min) W = L / ef = ? Wq=Lq/ef = ? ef = ? Prob. atend. sem fila Prob. desistência Prob. atend. com fila ? ? ? Dados: 𝜆 = 2,0 𝑐𝑙/𝑚𝑖𝑛 1/μ = 24 𝑠 (𝜇 = 2,5 𝑐𝑙/𝑚𝑖𝑛) 26 Exemplo: M/M/1/FCFS/5/∞ j pj j pj vazão vj pj utilização uj pj fila qj pj 0 0,2711 0 0 0 0 0 0 0 1 0,2168 0,2168 2,5 0,5421 1 0,2168 0 0 2 0,1735 0,3470 2,5 0,4337 1 0,1735 1 0,1735 3 0,1388 0,4163 2,5 0,3470 1 0,1388 2 0,2776 4 0,1110 0,4441 2,5 0,2776 1 0,1110 3 0,3331 5 0,0888 0,4441 2,5 0,2221 1 0,0888 4 0,3553 1,8683 1,8224 0,7289 1,1394 L médio Vazão média (cl./min) Utilização média Fila média Tempo médio total (min) Tempo médio de fila (min) Taxa efetiva (cl./min) W = L / ef = 1,0252 Wq=Lq/ef = 0,6252 ef = 1,8224 Prob. atend. sem fila Prob. desistência Prob. atend. com fila 0,2711 0,0888 0,6401 Como calcular os 𝜋𝑗? PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.12 Prof. Dr. Marco A. Mesquita 27 3.2 Distribuição Exponencial  fdp  FDA  Média  Variância       . . 0 0 ) ( c c t e t f t         . . 0 0 1 ) ( c c t e t F t     T  1 E   2 1 T   V https://en.wikipedia.org/wiki/Exponential_distribution 28 Exemplo 1  Suponha que o tempo entre chegadas de clientes em um posto de serviço seja uma v.a. exponencial com média de 5 min. Pede-se: a) qual é a probabilidade de não chegar ninguém nos próximos 3 min? b) qual é a probabilidade de chegar pelo menos um cliente nos próximos 10 min? c) qual é a probabilidade de demorar mais de 5 min até a próxima chegada? d) qual é o desvio padrão do tempo até a próxima chegada? PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.13 Prof. Dr. Marco A. Mesquita 29 Solução ,0 865 (10) 10) (    F X P 5min 1/       ,0 368 (5) 1 5) (     F X P a) b) c) d) Estes resultados independem do tempo decorrido desde a última chegada! (propriedade da falta de memória) ) ( 1 ( ) 1/5 /5 x em minutos e x F   x   ,0 549 (3) 1 3) (     F X P 30 Propriedades da Distribuição Exponencial  Propriedade da Falta de Memória  Exemplos:  Confiabilidade: o tempo de uso não altera a distribuição do tempo de falha do componente.  Intervalo entre Chegadas: o tempo até a próxima chegada é independente do tempo desde a última chegada.  Tempo de Atendimento: o tempo de serviço restante é independente do tempo já decorrido. 0 , ) ( ) (       u t t P X u X t u P X PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.14 Prof. Dr. Marco A. Mesquita 31 Exemplo 2  Suponha que o tempo de reparo de uma máquina tenha distribuição exponencial com média igual a 30 min. Pergunta-se: a) qual a probabilidade do tempo de reparo ultrapassar 30 min? 60 min? 90 min? b) dado que o reparo iniciou-se há mais de 30 min, qual a probabilidade do tempo total ultrapassar uma hora? Solução: a) ത𝐹 30 = 𝑒 Τ −30 30 = 36,8% ത𝐹 60 = 𝑒 Τ −60 30 = 13,5% ത𝐹 90 = 𝑒 Τ −90 30 = 5,0% b) 𝑃 𝑋 > 60|𝑋 > 30 = 𝑃 𝑋 > 30 = 36,8% 32 Exemplo 3  Um cliente C chega a um posto de atendimento com dois servidores, cada servidor atendendo um cliente (A e B). O cliente C, irá ser atendido pelo primeiro servidor livre. Admitindo-se que os tempos de atendimento sejam v.a.i. com distribuição exponencial e taxa igual a m, qual seria a probabilidade de que o cliente C seja o próximo a deixar o posto de atendimento. Pela falta de memória da exponencial e pelo fato da taxa ser a mesma para todos os atendimentos, o cliente que permanece em atendimento (A ou B) terá a mesma chance de concluir antes ou depois do cliente C. Portanto, há 50% de chance de C ser o próximo a deixar o posto. Qual seria esta probabilidade se os tempos fossem constantes? PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.15 Prof. Dr. Marco A. Mesquita 33 Propriedades da Exponencial (cont.)  Mínimo de Exponenciais: Sejam 𝑋1, 𝑋2, … , 𝑋𝑛 v.a.i. exponenciais com taxa 𝜆𝑖 (i=1,2,...,n). Então, também será uma v.a. exponencial com taxa: ou seja 𝑌~𝐸𝑥𝑝(𝜆1 + 𝜆2 + ⋯ + 𝜆𝑛) 𝜆1 + 𝜆2 + ⋯ + 𝜆𝑛 𝑌 = 𝑚𝑖𝑛(𝑋1, 𝑋2, … , 𝑋𝑛) 34 Propriedades da Exponencial (cont.)  Exponenciais Concorrentes: Sejam 𝑋1, 𝑋2, … , 𝑋𝑛 v.a.i. exponenciais com taxas 𝜆𝑖 (i=1,2,...,n), então: Para n=2: 𝑃 𝑋𝑖 < 𝑋𝑗, ∀𝑗 ≠ 𝑖 = Τ 𝜆𝑖 (𝜆1+𝜆2 + ⋯ + 𝜆𝑛) 𝑃 𝑋1 < 𝑋2 = Τ 𝜆1 (𝜆1+𝜆2) PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.16 Prof. Dr. Marco A. Mesquita 35 Exemplo 4  Suponha: (1) que os tempos entre chegadas em um posto de serviço com um único servidor sejam exponenciais com média de 5 min, e (2) que os tempos de atendimento também sejam exponenciais com média 3 min. Considerando que, em dado momento, há clientes aguardando na fila, pergunta-se: a) qual é a probabilidade de ocorrer uma chegada antes da próxima partida? b) qual é a probabilidade da fila permanecer inalterada nos próximos 5 minutos? Solução: a) P 𝑋𝐴 < 𝑋𝑆 = 𝜆 𝜆+𝜇 = 1 5 /[1 5 + 1 3] = 37,5% b) Y = min 𝑋𝐴, 𝑋𝑆 𝑌~𝐸𝑥𝑝(𝜈 = 1 5 + 1 3) P 𝑌 > 5 = 𝑒− 8 15 ∙ 5 = 6,95% 36 Propriedades da Exponencial (cont.)  Soma de Exponenciais: Seja X1, X2 , …, Xk uma amostra aleatória de variáveis exponenciais com taxa k, então Y = X1 + X2 + …+ Xk terá distribuição Erlang (caso particular da distribuição Gama), com parâmetros k e . A função densidade de probabilidade será dada por:     2 1 1 1 0 ,0 0 , 1)! ( ) ( ( )      k V Y Y E y y k k y e k y f k y k            k 1 k ... k k 2 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.17 Prof. Dr. Marco A. Mesquita 37 Distribuição Erlang Erl 1 Erl 2 Erl 4 Erl 8 Erl 16  Distribuições Erlang com mesma média e diferentes “k”. 38 Exemplo 5  Suponha que um cliente acaba de chegar em um caixa automático e encontra cinco outros clientes, um em atendimento e quatro na fila. Considere que os tempos de atendimento de cada cliente sejam v.a.i. exponenciais com média 4 minutos (15 clientes/h). a) Determine a média e a variância do tempo de espera na fila deste cliente que acaba de chegar? b) Qual é a probabilidade deste cliente ter que esperar mais de 30 min na fila? PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.18 Prof. Dr. Marco A. Mesquita 39 Solução  Seja W o tempo de espera na fila do cliente em questão:  W=X0+X1+X2+X3+X4 onde X0 é o tempo do cliente em atendimento, X1 será o tempo do primeiro da fila, X2 será o tempo do segundo etc.  Então:  E[W]: 5*4min = 20 min  V[W]: 5*(16)=90 (DP[W]: 9,5 min)  Como Y é a soma de 5 v.a.i. exponenciais, terá distribuição Erlang de ordem 5 (caso particular da Gama). Usando o Excel ou uma biblioteca de probabilidades, calcula-se:  P(W>30) = 1 – F(30) = 13,2%  Excel: DISTGAMA(30;5;4;1)  from scipy.stats import gamma: 1-gamma.cdf(30,5,0,4) 40 Outra forma de solução... Outra forma de forma seria usar a Poisson. A probabilidade do tempo de espera na fila ser maior que 30 min é igual a probabilidade de serem atendidos no máximo 4 clientes durante estes 30 min. ,0132 ... ! 5,7 4) ( 30) ( 4 0 5, 7           k k k e P Y W P Sabendo-se que o número de clientes atendidos em 30 min (Y) é uma v.a. Poisson com média 7,5 (15*0,5), tem-se: PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.19 Prof. Dr. Marco A. Mesquita 41 3.3 Processo de Poisson  Definição: um processo de contagem {N(t), t  0} é um processo de Poisson com taxa  (>0) se: a) N(0) = 0 b) tem incrementos estacionários e independentes c) P[N(h) = 1] = h + o(h) d) P[N(h)  2] = o(h) Obs: uma função f é da ordem de grandeza de h, o(h), se 0 ( ) lim 0   h h f h 42 Distribuição de Probabilidades  Seja Pn(t) = P(N(t) = n)  Para n>0  Para n=0  Expectativa e Variância:   e t P t P t t P o h h P t h t P               ( ) ( ) ) ( ( ) ( ) 1 ) ( 0 0 ' 0 0 0 ! ) ( ) ( ( ) ( ) ) ( ( ) ( ) ) 1( ( ) ) ( 1 ' 1 n t e t P P t t P t P o h P t h t h P h t P n t n n n n n n n                      𝐸 𝑁(𝑡) = 𝑉 𝑁(𝑡) = 𝜆𝑡 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.20 Prof. Dr. Marco A. Mesquita 43 Exemplo 6  Suponha que as chegadas de clientes em um posto de serviço seja um Processo de Poisson com taxa de 12 chegadas por hora. Pede-se: a) qual a probabilidade de não chegar ninguém nos próximos 3 min? b) qual a probabilidade de chegar pelo menos um cliente nos próximos 10 min? c) qual a probabilidade de chegarem 5 ou mais clientes nos próximos 15 min? d) calcule a média e o desvio padrão do número de chegadas em 1 h. 44 Exemplo 6 (solução) ,0 865 0! ( ,2 0) 1 (1/ 6) 1 2,0 0 0     e P ,3 46 )1( 12 )1(     ,0185 ] ! 4 3 !3 3 ! 2 3 3 [ 1 3 4 3 3 3 2 3 3                e e e e e a) b) c) d) ) ( ! (12 ) ( ) /. 12 12 t em h k e t P t h cl t k k     ,0 549 0! ( ,0 6) ,0 05) ( 0,6 0 0   e P PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.21 Prof. Dr. Marco A. Mesquita 45 Propriedades do Processo de Poisson  Em um processo de Poisson com taxa , os intervalos entre chegadas são v.a.i. exponenciais com taxa . t N(t) A2 A1 A3 A4 t1 t2 t3t4 t5 A5 (exponencia )l ) ( 1 ) ( 0) ( ) ( 0) ) ( ) ( ( ) ( 0) ( ) ( ) ( 1 1 1 t A t A u n n n u e t f e t F e N u P N t u N t P u A P e P N u u A P                            46 Propriedades do Processo de Poisson  União de Poisson: Sejam N1(t) e N2(t) dois Processos de Poisson, com taxas 1 e 2, respectivamente. Então N(t) = N1(t) + N2(t) também será um Processo de Poisson com taxa 1 + 2. 1 2 1 + 2 Vale para n>2 também PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.22 Prof. Dr. Marco A. Mesquita 47 Propriedades do Processo de Poisson (cont)  Divisão de Poisson: Seja {N(t), t  0} um Processo de Poisson com taxa  . Suponha que cada chegada seja direcionada para dois destinos, com probabilidades p (destino 1) e 1-p (destino 2). Seja Ni(t) o número de partidas para o destino i (i=1 e 2) até o instante t. Então, N1(t) e N2(t) serão Processos de Poisson independentes com taxas p e (1-p), respectivamente.  p   (1–p) Vale para n>2: 𝑝1, 𝑝2, … , 𝑝𝑛 ∑𝑝𝑗 = 1 48 Poisson Arrivals See Time Averages – PASTA  Em uma fila isolada com processo de chegada Poisson, a probabilidade de um cliente que chega encontrar o sistema com j clientes, em regime estacionário, é igual a probabilidade estacionária de haver j clientes no sistema.  Interpretação: a visão do cliente que chega é a mesma de um observador externo. 𝑎𝑗 = 𝜋𝑗 𝑗 = 0,1,2, … PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.23 Prof. Dr. Marco A. Mesquita 49 Processo de Poisson Composto  Um processo de contagem {Y(t), t  0} constitui um Processo de Poisson Composto se: onde {N(t), t  0} é um Processo de Poisson e {Xi, i = 1, 2, …} são v.a. inteiras, independentes e com mesma distribuição de probabilidades (v.a.i.i.d.)  Demonstra-se que: 0 ) ( ) ( 1     t X t Y t N i i 𝐸 𝑌(𝑡) = 𝜆𝑡 ∙ 𝐸 𝑋 𝑉 𝑌(𝑡) = 𝜆𝑡 ∙ 𝐸 𝑋2 Exemplo: chegada de passageiros em um aeroporto 50 3.4 Processos de Nascimento e Morte (Birth-and-Death)  Estado: X(t) = qtd de clientes no sistema em t (x=0,1,2,...)  Transições apenas entre estados adjacentes: “nascimento” = transição de i para i+1 (chegada), “morte” = transição de i para i-1 (partida).  Eventos: 1) dado X(t) = n, o tempo até a próxima chegada (nascimento) tem distribuição exponencial com taxa n (n = 0, 1, 2, ...) 2) dado X(t) = n, o tempo até a próxima partida (morte) tem distribuição exponencial com taxa n (n = 1, 2, ...) PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.24 Prof. Dr. Marco A. Mesquita 51 Processos de Nascimento e Morte são Cadeias de Markov em Tempo Contínuo  O tempo médio de permanência em cada estado é uma v.a. exponencial com taxas 𝜐𝑗 dadas por:  As probabilidades de transição entre estados são: ,2  ,1 0 0     j j j j      0 1 2 j ... 0 1 2 j-1 ... j 1 2 3 j j+1 ,2  ,1 1 1 , 1 , 01         j p p p j j j j j j j j j j       52 Diagrama e Matriz das Taxas de Transição entre Estados Matriz Q:                                  ) ( 0 0 ) ( 0 0 ) ( 0 0 3 3 3 2 2 2 2 1 1 1 1 0 0              Q 0 1 2 j ... 0 1 2 j-1 ... j 1 2 3 j j+1 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.25 Prof. Dr. Marco A. Mesquita 53 Casos Particulares de Processos de Nascimento e Morte  Processo de Poisson (nascimento puro)  Fila M/M/3 0 1 2 3     ... 0 1 2    ...  2 3 4   3 3 3 54 Distribuição Estacionária  Análise em regime estacionário para os processos de nascimento e morte.  Equações de Balanço: Fluxo de entrada = Fluxo de saída  Seja pj = prob. em regime estacionário do estado j. 0 1 2 j ... 0 1 2 j-1 ... j 1 2 3 j j+1 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.26 Prof. Dr. Marco A. Mesquita 55 Saída de 0   Entrada em 0 Saída de 1   Entrada em 1 Saída de j   Entrada em j Equivalente a: Equações de Balanço 1 1 0 0  p  p  2 2 0 0 1 1 1 ) (  p  p  p     1 1 1 1 ) (        j j j j j j j p  p   p  Q  0 p 0 1 2 j ... 0 1 2 j-1 ... j 1 2 3 j j+1   56 Equação 0  Equação 1  Equação 2  • • • Equação j  • • • Equações de Balanço (cont.) 0 1 1 0 2 1 p       p               j j j j j Solução: 0 0 1 1  p  p  1 1 2 2  p  p  2 2 3 3  p  p  j j j j  p p     1 1 𝜋𝑗+1 = 𝜆𝑗 𝜇𝑗+1 𝜋𝑗 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.27 Prof. Dr. Marco A. Mesquita 57 Seja Cj = para j = 1, 2, … Como Sjpj = 1, determina-se p0 pela expressão p0 = 1 / (1 + Sj Cj) e, a seguir, os demais pj’s. Solução Assim, tem-se: pj = Cjp0 (j = 1, 2, . . . ) 1 1 0 2 1            j j j j 58 Exemplo 7 – Reparo de Máquinas  2 máquinas, 1 técnico  Tempo entre quebras de uma máquina  V.A. Exponencial com taxa  (média 1/)  Tempo de Reparo  V.A. Exponencial com taxa  (média 1/)  Determine a distribuição estacionária do processo PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.28 Prof. Dr. Marco A. Mesquita 59 Exemplo 7 – Reparo de Máquinas (cont.)  X(t)= quantidade de máquinas em manutenção (t≥0)  Pij(t) = P(X(t) = j | X(0) = i )  Distribuição Estacionária: Matriz das Taxas de Transição Diagrama de Transição ( ) lim t Pij t j   p                        0 ) ( 0 2 2 Q 0 1 2 2    60 2 p0   p1  p1   p2 Exemplo 7 – Reparo de Máquinas (cont.) Então: p1  (2/) p0 p2  (/) p1  (22/2) p0 0 1 2 2    Impondo que a soma dos pj´s seja unitária, obtém-se: p0  1 / 1  (2/)  (22/2) PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.29 Prof. Dr. Marco A. Mesquita 61 Exemplo 7 – Reparo de Máquinas (cont.)  Supondo que os tempos de reparo e falha tenham média 1 e 8h, respectivamente, tem-se:  = 0,125  = 1,0 p0 = 0,780 p1 = 0,195 p2 = 0,025  Número médio de máquinas em reparo: L = 0 p0 + 1 p1 + 2 p2 = 0,244  Fração do tempo do técnico ocupado = 1 - p0 = 0,220  Fração do tempo da máquina operando = p0 + 0,5 p1 = 0,780 + 0,5 (0,195) = 0,878 62 Exemplo 8: ATM (Fila M/M/1//5) Clientes são atendidos, um por vez, em um ATM localizado dentro de um posto bancário. Se houver mais de um cliente presente, forma-se uma fila em frente ao ATM. Suponha que a fila comporte no máximo quatro clientes, isto é, se houver cinco clientes no ATM, o próximo a chegar desiste de entrar e parte. Dados estatísticos apontam que a taxa de chegadas é de 2 clientes por minuto (intervalos médios de 30 segundos entre chegadas), enquanto o tempo médio de atendimento é 24 segundos, ambos com distribuição exponencial. Responda às seguintes questões: PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.30 Prof. Dr. Marco A. Mesquita 63 Exemplo 8 (cont.)  Recurso a) Quanto tempo o ATM estará vazio? (27%) b) Qual é o nível de utilização do ATM? (73%) c) Quantos clientes são atendidos por minuto? (1,822) d) Qual é o número médio de clientes no sistema? (1,868)  Usuários e) Quantos clientes são atendidos sem esperar na fila? (27%) f) Quantos clientes desistem por encontrar o sistema cheio? (9%) g) Qual é o tempo médio de espera no ATM? (1,03 min) 64 Distribuição Estacionária – 𝜋  N(t) = Número de clientes no sistema no instante t  Espaço amostral: S={ 0, 1, 2, 3, 4, 5 }  Diagrama de transição entre estados  Dados:  = 2,0 cl./min (intervalo entre chegadas = 0,5 min)  = 2,5 cl./min (tempo médio de atend. = 24/60 min) 0 1 2 3  4 5          PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.31 Prof. Dr. Marco A. Mesquita 65 Equações de Balanço 0 1 2 3  4 5          Saída de 0  Saída de 1  Saída de 2  Saída de 3  Saída de 4  Saída de 5  1 0 p p  2 0 ) 1 ( p p  p     3 1 ) 2 ( p p  p     4 5 p p   Entrada em 0  Entrada em 1  Entrada em 2  Entrada em 3  Entrada em 4  Entrada em 5 4 2 ) 3 ( p p  p     5 3 ) 4 ( p p  p     66 Equação 1  Equação 2  Equação 3  Equação 4  Equação 5  Equações de Balanço (cont.) ,2 ..., 5 ,1 0         j j j p   p Solução: 1 0 p p  2 1 p p  3 2 p p  4 3 p p  5 4 p  p PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.32 Prof. Dr. Marco A. Mesquita 67 Solução  Impondo que a soma dos pj seja unitária, tem-se: p0 [1+(/)+(/)2 + ... + (/)5 ] = 1 p0 = 1 / { [1-(/)6 ] /[1-(/) ] }  Substituindo =2,0 e =2,5, obtém-se: p0 = 0,2711 e os demais pj’s: p1 = 0,2168 p2 = 0,1735 p3 = 0,1388 p4 = 0,1110 p5 = 0,0888 68 Matriz Q e Solução para M/M/1//5  Matriz Q – taxas de transição  Solução (pQ=0, Σp=1): 0 1 2 3 4 5 0 -2 2 0 0 0 0 1 2,5 -4,5 2 0 0 0 2 0 2,5 -4,5 2 0 0 3 0 0 2,5 -4,5 2 0 4 0 0 0 2,5 -4,5 2 5 0 0 0 0 2,5 -2,5 j 0 1 2 3 4 5 πj 0,271 0,217 0,173 0,139 0,111 0,089 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.33 Prof. Dr. Marco A. Mesquita 69 Equações de Balanço – 𝜋 ∙ 𝑄 = 0 0 1 2 3 2,0 4 5 2,0 2,0 2,0 2,0 2,5 2,5 2,5 2,5 2,5 0 5,2 0,2 1 0      p p 0 5,2 5,4 0,2 2 1 0       p p p 0 5,2 5,4 0,2 3 2 1       p p p 0 5,2 0,2 5 4     p p 0 5,2 5,4 0,2 4 3 2       p p p 0 5,2 5,4 0,2 5 4 3       p p p Mesmas equações do slide 65 70 Exemplo 8 (cont.)  Recursos a) Quanto tempo o ATM estará vazio? b) Qual é o nível de utilização do ATM? c) Quantos clientes são atendidos por min? d) Qual é o número médio de clientes no sistema?  Usuários e) Quantos clientes são atendidos sem esperar na fila? f) Quantos clientes desistem por encontrar o sistema cheio? g) Qual é o tempo médio de espera no ATM? PASTA – Poisson Arrivals See Time Averages 𝑎𝑗 = 𝜋𝑗 𝜋0 = 27% 𝜌 = 1 − 𝜋0 = 73% 𝜆𝑒𝑓 = 𝜆 ∙ (1 − 𝜋5) = 1,822 𝐿 = 0 ∙ 𝜋0 + 1 ∙ 𝜋1 + 2 ∙ 𝜋2 + 3 ∙ 𝜋3 + 4 ∙ 𝜋4 + 5 ∙ 𝜋5 = 1,868 𝑎0 = 27% 𝑎5 = 9% 𝐿 = 𝜆𝑒𝑓 ∙ 𝑊 ⇒ 𝑊 = Τ 𝐿 𝜆𝑒𝑓 = Τ 1,868 1,822 = 1,03 𝑚𝑖𝑛 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.34 Prof. Dr. Marco A. Mesquita 71 Análise de Sensibilidade  Um dos objetivos da teoria de filas é auxiliar no dimensionamento de sistemas de atendimento, analisando o efeito do aumento dos recursos no desempenho e custos do atendimento ao cliente.  No exemplo em questão, avalie o resultado do aumento de um para dois terminais de atendimento no ATM no nível de atendimento ao cliente. (M/M/2//5)  Qual é o impacto da inclusão de um terceiro posto de auto atendimento ? (M/M/3//5) 72 Comparação das alternativas Indicador 1 ATM 2 ATM 3 ATM Utilização Vazão (Throughput) Fila Média Tempo Médio de Fila (min) % de clientes que pegam fila (espera) Porcentagem de clientes desistentes PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.35 Prof. Dr. Marco A. Mesquita 73 M/M/1//5  1 terminal de atendimento 0 1 0,2 5,2 p p    1 2 0,2 5,2 p p    2 3 0,2 5,2 p p    3 4 0,2 5,2 p p    4 5 0,2 5,2 p p    j pj 0 0,2711 1 0,2168 2 0,1735 3 0,1388 4 0,1110 5 0,0888  0 1 2 3 2,0 4 5 2,0 2,0 2,0 2,0 2,5 2,5 2,5 2,5 2,5 74 M/M/1//5 j pj j pj vazão vj pj utilização uj pj fila qj pj 0 0,2711 0 0 0 0 0 0 0 1 0,2168 0,2168 2,5 0,5421 1 0,2168 0 0 2 0,1735 0,3470 2,5 0,4337 1 0,1735 1 0,1735 3 0,1388 0,4163 2,5 0,3470 1 0,1388 2 0,2776 4 0,1110 0,4441 2,5 0,2776 1 0,1110 3 0,3331 5 0,0888 0,4441 2,5 0,2221 1 0,0888 4 0,3553 1,8683 1,8224 0,7289 1,1394 L médio Vazão média (cl./min) Utilização média Fila média Tempo médio total (min) Tempo médio de fila (min) Taxa efetiva (cl./min) W = L / ef = 1,0252 Wq=Lq/ef = 0,6252 ef = 1,8224 Prob. atend. sem fila Prob. desistência Prob. atend. com fila 0,2711 0,0888 0,6401 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.36 Prof. Dr. Marco A. Mesquita 75 M/M/2//5  2 terminais de atendimento 0 1 0,2 5,2 p p    1 2 0,2 0,5 p p    2 3 0,2 0,5 p p    3 4 0,2 0,5 p p    4 5 0,2 0,5 p p    j pj 0 0,4311 1 0,3449 2 0,1380 3 0,0552 4 0,0221 5 0,0088  0 1 2 3 2,0 4 5 2,0 2,0 2,0 2,0 2,5 5,0 5,0 5,0 5,0 76 M/M/2//5 j pj j pj vazão vj pj utilização uj pj fila qj pj 0 0,4311 0 0 0 0 0 0 0 1 0,3449 0,3449 2,5 0,8622 0,5 0,1724 0 0 2 0,1380 0,2759 5 0,6898 1 0,1380 0 0 3 0,0552 0,1655 5 0,2759 1 0,0552 1 0,0552 4 0,0221 0,0883 5 0,1104 1 0,0221 2 0,0441 5 0,0088 0,0441 5 0,0441 1 0,0088 3 0,0265 0,9187 1,9823 0,3965 0,1258 L médio Vazão média (cl./min) Utilização média Fila média Tempo médio total (min) Tempo médio de fila (min) Taxa efetiva (cl./min) W = L / ef = 0,4635 Wq=Lq/ef = 0,0635 ef = 1,9823 Prob. atend. sem fila Prob. desistência Prob. atend. com fila 0,7760 0,0088 0,2152 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.37 Prof. Dr. Marco A. Mesquita 77 M/M/3//5  3 terminais de atendimento 0 1 0,2 5,2 p p    1 2 0,2 0,5 p p    2 3 0,2 5,7 p p    3 4 0,2 5,7 p p    4 5 0,2 5,7 p p    j pj 0 0,4476 1 0,3581 2 0,1432 3 0,0382 4 0,0102 5 0,0027  0 1 2 3 2,0 4 5 2,0 2,0 2,0 2,0 2,5 5,0 7,5 7,5 7,5 78 M/M/3//5 j pj j pj vazão vj pj utilização uj pj fila qj pj 0 0,4476 0 0 0 0 0 0 0 1 0,3581 0,3581 2,5 0,8952 0,333 0,1194 0 0 2 0,1432 0,2865 5 0,7162 0,667 0,0955 0 0 3 0,0382 0,1146 7,5 0,2865 1 0,0382 0 0 4 0,0102 0,0407 7,5 0,0764 1 0,0102 1 0,0102 5 0,0027 0,0136 7,5 0,0204 1 0,0027 2 0,0054 1,0 0,8134 1,9946 0,2659 0,0156 L médio Vazão média (cl./min) Utilização média Fila média Tempo médio total (min) Tempo médio de fila (min) Taxa efetiva (cl./min) W = L / ef = 0,4078 Wq= Lq/ef = 0,0078 ef = 1,9946 Prob. atend. sem fila Prob. desistência Prob. atend. com fila 0,9489 0,0027 0,0484 PRO 3342 – Teoria de Filas – Parte 1 USP – Poli – PRO 3.38 Prof. Dr. Marco A. Mesquita 79 Comparação das alternativas Indicador 1 ATM 2 ATM 3 ATM Utilização 0,729 0,396 0,266 Vazão (Throughput) 1,822 1,982 1,995 Fila Média 1,139 0,126 0,016 Tempo Médio de Fila (min) 0,625 0,064 0,008 % de clientes que pegam fila (espera) 0,640 0,215 0,048 Porcentagem de clientes desistentes 0,0888 0,0088 0,0027 80 Próxima aula  Winston (2004, cap.20)  20.4 a 20.10 e 20.13