Sistemas de Filas e Simulação - Análise e Modelagem com Pesquisa Operacional

Sistemas de Filas e Simulação Ref TAHA H Operations Research An Introduction Eight Edition Pearson Prentice Hall 2007 Disciplina Pesquisa Operacional II Prof José Arica LEPRODCCTUENF AVALIAÇÔES P1 P2 P3 PF Sistemas de Filas Filas ou Fenômenos de Espera aparecem em diferentes contextos nos caixas de bancos produtos esperando para serem processados em diferentes estágios de um processo produtivo aviões voando em círculos para pousar num aeroporto etc ESPERA X CUSTOS OBJETIVO Diminuir impactos negativos a metas estabelecidas O estudo das filas determina medidas de desempenho do sistema de espera como tempo médio de espera e comprimento médio da fila Estas medidas se usam para decidir sobre o nível apropriado dos serviços Sistemas de Filas Exemplo 1 Os clientes de um restaurante de comida a quilo se queixam do serviço lento nos caixas O restaurante atualmente tem três caixas e contrata uma consultoria para estudar o problema O estudo indica a seguinte relação entre o tempo de espera e o número de caixas N de caixas 1 2 3 4 5 6 7 Tempo médio de espera min 162 103 69 48 29 19 13 Os dados indicam um tempo médio de espera atual de aproximadamente 7 minutos Note que se o gerente quiser reduzir esse tempo para menos de 3 minutos só conseguirá esse objetivo com 5 ou mais caixas menos de 3 minutos Tempo atual Sistemas de Filas Os resultados da análise de filas também podem usarse num modelo de otimização de custos onde o custo total soma dos custos de operação do serviço e o tempo de espera se minimiza Quando se trabalham modelos de custos o problema principal é estimar os custos unitários de espera em particular quando o comportamento humano influência a operação do modelo custo n nível do serviço X Nível ótimo do serviço Custo total 𝐶0 𝑛 Custo de Operação do serviço 𝐶𝑤 𝑛 Custo de espera dos clientes Sistemas de Filas Exemplo 2 Suponha que estudos adicionais em relação ao restaurante do Exemplo 1 indicam os seguintes resultados Sistemas de Filas N de caixas 1 2 3 4 5 6 7 Tempo médio de espera min 162 103 69 48 29 19 13 Ociosidade 0 8 12 18 29 36 42 a Qual a eficiência do serviço dos caixas medida pelo percentual de tempo no que estes estão ocupados quando o número de caixas é 5 b Pretendese manter o tempo médio de espera não maior do que 3 minutos e ao mesmo tempo manter a eficiência das instalações em aproximadamente 90 Poderseá atingir esse objetivo Solução a 71 b O tempo médio de espera menor igual a 3 minutos precisa 5 caixas ou mais já a eficiência maior o igual a 90 precisa de 3 caixas ou menos Portanto não é possível atingir a meta proposta Sistemas de Filas Exemplo 3 Uma empresa metalmecânica pretende alugar uma fresadora multipropósito Dois modelos A e B estão disponíveis com custos de operação horário de R 18 e 25 respectivamente O modelo A é mais lento que o B e análises de filas de modelos similares indicam que usando A o número médio de tarefas na fila é 4 e que usando B é 3 Uma tarefa atrasada representa perda de oportunidade de lucro estimada em 10 por hora de tarefa em espera Qual o modelo a ser alugado Solução Custohora R Número médio de tarefas na fila Lq Perda de lucrohora A 18 4 10 B 25 3 10 BA 7 1 Assim escolhendo B ao invés de A temse o seguinte balanço 7 R adicionais de custo e 10 R de oportunidade de lucro obtido ie essa escolha representa lucro de 3 R escolher A representaria perder 3 R cada hora Sistemas de Filas Elementos de um Modelo de Filas Cliente Fonte Fila Tempo entre Chegadas Serviço Tempo de Serviço Clientes chegando INSTALAÇÔES Servidor Servidor Servidor Servidor Clientes partindo Clientes partindo Clientes partindo Fonte Tempo entre chegadas Tempo de serviço Sistemas de Filas A DISCIPLINA DA FILA representa a ordem na que os clientes se selecionam da fila As mais comuns são FIFO first in first out O primeiro a chegar é o primeiro a ser atendido LIFO last in first out O último a chegar é o primeiro a ser atendido SIRO service in random order serviço em ordem aleatório GD General distribution Distribuição genérica Prioridade algum tipo de prioridade A FONTE onde se geram os clientes pode ser FINITA limitando a chegada de clientes ao serviço solicitações de manutenção numa empresa ou INFINITA sempre abundante exemplo ligações para uma central telefônica O projeto das instalações do serviço pode incluir um ÚNICO SERVIDOR ou MÚLTIPLOS SERVIDORES em PARALELO ou em SÉRIE A variação dos elementos do ambiente de filas origina vários modelos Ainda O comportamento dos clientes influência a análise de espera nas filas Pessoas por exemplo podem EVITAR entrar na fila podem MUDAR de fila e podem RENUNCIAR à fila Sistemas de Filas Associadas ao tempo aleatório entre chegadas dos clientes e ao tempo aleatório de serviço num ambiente de filas têmse as distribuições de POISSON e EXPONENCIAL Dirseá que os clientes chegam a um serviço aleatoriamente segundo a distribuição de Poisson se 𝑃 𝑥𝑘 𝜆 𝑘𝑒 𝜆 𝑘 onde x número de clientes que chegam ao serviço por unidade de tempo número médio de chegadas taxa de chegada por unidade de tempo Por outro lado o tempo entre chegadas ou o tempo de serviço dizse distribuído segundo uma distribuição Exponencial se 𝑓 𝑡𝜆𝑒 𝜆𝑡𝑡 0 onde taxa de ocorrência dos eventos OBS se o número de chegadas é Poisson os intervalos entre chegadas se distribuem exponencialmente e viceversa t 𝜆 𝑓 𝑡 𝜆𝑒 𝜆𝑡 Sistemas de Filas Propriedade de falta de memória ou esquecimento da exponencial Considere t distribuída exponencialmente se S é o intervalo no que ocorreu o último evento então a propriedade de FALTA DE MEMÓRIA se descreve da seguinte forma 𝑃 𝑡 𝑇 𝑆𝑡𝑆𝑃 𝑡𝑇 Prova Desde que 𝑃 𝑡 𝑌 𝑌 𝑓 𝑡𝑑𝑡 0 𝑌 𝜆𝑒 𝜆 𝑡𝑑𝑡𝑒 𝜆𝑡0 𝑌1𝑒 𝜆 𝑌 𝑃 𝑡𝑌 1𝑃 𝑡 𝑌 𝑒 𝜆𝑌 Portanto 𝑃 𝑡 𝑇 𝑆𝑡𝑆 𝑃 𝑡𝑇 𝑆𝑡𝑆 𝑃 𝑡𝑆 𝑃 𝑡 𝑇 𝑆 𝑃 𝑡𝑆 𝑒 𝜆𝑇 𝑆 𝑒 𝜆 𝑆 𝑃 𝑡 𝑇 𝑆𝑡𝑆𝑃𝑡 𝑇 Assim se neste momento são as 1030h e a última chegada ao sistema ocorreu às 1025h a probabilidade da próxima chegada ocorrer às 1040h é função só do intervalo 1030 1040 e independe do tempo transcorrido entre as 1025 e as 1030 Sistemas de Filas Exemplo 4 Uma máquina de serviço tem uma de reserva para substituição imediata em caso de falha O tempo de falha é exponencial e ocorre a cada 40 minutos em média O operador da máquina afirma que a máquina tem o hábito de quebrar cada noite ao redor das 0830h Analisar a afirmação do operador Solução A taxa média de falha das máquinas é Assim o tempo de falha se distribui exponencialmente como 𝑓 𝑡15𝑒 15𝑡 𝑡 0 Desde que o tempo de falha é aleatório a afirmação do operador não é verdadeira Note que a probabilidade de falha às 0830h depende da hora do dia relativa às 0830h na que esta se calcula Por exemplo se neste momento são as 0820h a probabilidade de falha às 0830h será 𝑃𝑡 10 601 𝑒 15 10 60 022 Já se a hora atual for 0700h 𝑃 𝑡151𝑒 1 515090 Sistemas de Filas Exemplo 5 O tempo entre chegadas numa agência dos correios é exponencial com valor médio de 005h A agência abre às 0800h a Encontre a probabilidade de nenhum cliente chegar até as 0815h b Se agora são as 0835h e o último cliente chegou às 0826h qual a probabilidade de que o próximo cliente chegue antes das 0838h Qual a probabilidade de chegar depois das 0840h c Quantos clientes se esperam entre as 0810 e as 0845 Solução Assim distribuição do tempo entre chegadas dos clientes 𝑓 𝑡20𝑒 20𝑡𝑡0 a 𝑃 𝑛𝑒𝑛ℎ𝑢𝑚𝑎𝑐ℎ𝑒𝑔𝑎𝑑𝑎𝑎𝑡é0815𝑃𝑡15 601𝑃𝑡15 6011𝑒 20 15 60𝑒 5000674 b 𝑃𝑡 3 601𝑒 20 3 60 1𝑒 10632 𝑃𝑡 5 60𝑒 20 5 60 𝑒 5 3 019 Sistemas de Filas c Lembrar que se os tempos de chegada são exponenciais então x número de chegadas por unidade de tempo é Poisson 𝑃 𝑥𝑘 𝜆 𝑘𝑒 𝜆 𝑘 𝑘0 12 Portanto desde que temse que a média do número de chegadas entre 0810 e 0845 é 𝐸 𝑥 𝜆𝐸 Sistemas de Filas A Distribuição Exponencial Os axiomas sobre os quais se formula a distribuição exponencial para o comportamento em filas de espera são os seguintes Teorema 1 A distribuição exponencial baseiase em três axiomas Ax 1 Dado Nt o número de eventos durante o intervalo 0t o processo aleatório que descreve Nt tem incrementos estacionários independentes no sentido de que a ocorrência de um evento T TS depende só do incremento S Ax 2 A probabilidade de um evento ocorrer num intervalo de tempo arbitrariamente pequeno h 0 é positiva mas menor do que 1 Ax3 Num intervalo de tempo arbitrariamente pequeno ocorre no máximo um evento ie 𝑃 𝑁 ℎ1 0 Sistemas de Filas Prova Seja Ax 1 P0 eventos no intervalo 0t e 0 eventos no intervalo t th eventos independentes Assim a solução da equação anterior usando os Ax 2 e Ax 3 resulta 𝑝0 𝑡𝑒 𝜆 𝑡𝑡 0com 𝜆0 Considere agora ft função de densidade de probabilidade do tempo t entre eventos sucessivos t0 Ptempo entre eventos T Pnenhum evento até o tempo T 𝑇 𝑓 𝑡 𝑑𝑡𝑝0 𝑇 𝑇0 0 𝑇 𝑓 𝑡 𝑑𝑡1 𝑇 𝑓 𝑡 𝑑𝑡1 𝑝0𝑇 1 𝑒 𝜆𝑡 𝑓 𝑡𝜆𝑒 𝜆𝑡𝑡 0 Sistemas de Filas Modelo de Nascimento Puro Seja a taxa de chegada de clientes por unidade de tempo Assim para um tempo h 0 arbitrariamente pequeno temse que o Ax 3 máximo uma chegada para 𝑝1ℎ 1𝑝0 ℎ h0 𝑝1ℎ 𝜆ℎ Considere agora 𝑝𝑛 𝑡𝑝𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒 𝑑𝑒𝑜𝑐𝑜𝑟𝑟𝑒𝑟 𝑛𝑐ℎ𝑒𝑔𝑎𝑑𝑎𝑠 𝑑𝑢𝑟𝑎𝑛𝑡𝑒𝑜𝑡𝑒𝑚𝑝𝑜𝑡 Tentaremos encontrar qual a forma desta expressão Modelos de Nascimento e Morte Puros Relação entre as distribuições exponencial e Poisson Apresentamse aqui dois modelos de filas Admitindo só chegadas nascimento puro e Admitindo só partidas morte pura Ambos os modelos baseados nos Axiomas do Teorema 1 ie tempo entre chegadas exponencial 𝑓 𝑡𝜆𝑒 𝜆𝑡𝑡 0 Sistemas de Filas Assim para um tempo h 0 arbitrariamente pequeno temse que 𝑝𝑛 𝑡ℎ 𝑝𝑛 𝑡 𝑝0ℎ 𝑝𝑛1 𝑡 𝑝1ℎ 𝑛0 ou 𝑝0 𝑡 𝑝0 ℎ 𝑛0 𝑝𝑛 𝑡ℎ 𝑝𝑛 𝑡 1 𝜆ℎ𝑝𝑛 1𝑡 𝜆ℎ 𝑛0 ou 𝑝0 𝑡 1 𝜆ℎ 𝑛0 Portanto para n 0 h0 𝑝𝑛 𝑡 𝜆𝑝𝑛 𝑡 𝜆𝑝𝑛 1𝑡 1 n 0 h0 𝑝0 𝑡 𝜆𝑝0 𝑡 2 Assim a solução da equação 1 2 está dada por n012 POISSON com média de chegadas no tempo t Conclusão Se o tempo entre chegadas é exponencial com média o número de chegadas num tempo t é Poisson com média o recíproco também é verdadeiro Sistemas de Filas Exemplo 6 Numa certa região crianças nascem segundo a taxa de um nascimento a cada 12 minutos O tempo entre nascimentos segue distribuição exponencial Encontrar a O número médio de nascimentos por ano b A probabilidade de não ter nascimentos num dia c A probabilidade de ter 50 nascimentos em 3 horas dado que 40 nascimentos ocorreram nas 2 primeiras horas Solução A taxa de nascimentos por dia é Portanto a 𝐸 𝑛𝑡365 𝑑𝑖𝑎𝑠 12036543800nasc b 𝑝0 𝑡1𝑑𝑖𝑎12010𝑒120 1 0 0 c com 𝜆 1 12 𝑛𝑎𝑠𝑐 𝑚𝑖𝑛 60𝑚𝑖𝑛 ℎ𝑜𝑟𝑎 5 𝑛𝑎𝑠𝑐 ℎ𝑜𝑟𝑎 Sistemas de Filas Exemplo 7 Suponha que no Exemplo 6 o funcionário que registra os nascimentos no sistema espera pelo menos um lote de 5 nascimentos para iniciar os registros Encontrar a probabilidade de que o funcionário entre com um lote numa hora Solução 𝑝𝑛 511 𝑛0 4 𝑝𝑛 1com onde Poisson com Assim Sistemas de Filas Exemplo 8 A universidade X tem duas linhas de ônibus circulares no campus Cada linha faz um percurso diferente com uma estação de integração entre elas A linha verde G chega aleatoriamente de acordo a uma Poisson à estação de integração a cada 10 minutos em média e a vermelha R a cada 7 minutos em média também segundo uma Poisson i Qual é a probabilidade de que dois ônibus estejam na estação de integração num intervalo de 5 minutos ii Um estudante que tem uma aula em 10 minutos chega na estação de integração Qualquer uma das linhas o levará a sua sala de aulas A viagem demora 5 minutos depois dos quais deverá andar mais 3 minutos Qual a probabilidade do estudante chegar à aula a tempo Solução𝜆𝐺 1 10 𝑏𝑢𝑠 𝑚𝑖𝑛 𝜆𝑅1 7 𝑏𝑢𝑠 𝑚𝑖𝑛 Poisson com Poisson com i P2 ônibus na estação em 5 minutos p Sistemas de Filas ii Pestudante chegar a tempo Pao menos um ônibus na estação em dois minutos Sistemas de Filas Modelo de Morte Pura Neste modelo o sistema começa com N clientes no tempo 0 e não se permitem chegadas Ocorrem saídas na taxa de clientesunidade de tempo Para calcular probabilidade de n clientes ficar no sistema depois de t unidades de tempo usamse os mesmos argumentos que para o Modelo de Nascimento Puro resultando 𝑝0 𝑡𝜇 𝑝1 𝑡 Sendo a solução destas equações 𝑝𝑛 𝑡𝜇𝑡 𝑁 𝑛𝑒 𝜇𝑡 𝑁𝑛 𝑛12𝑁 𝑝0 𝑡1 𝑛1 𝑁 𝑝𝑛𝑡 Exemplo 9 Uma floraria armazena 18 dúzias de rosas no início de cada semana Vendemse Em média 3 dúziasdia a venda é por dúzias mas a demanda é Poisson Sempre que o estoque diminui para 5 dúzias ou menos colocase um novo pedido de 18 dúzias que se entrega no início da semana seguinte Devido à natureza do artigo todas as rosas que ficam no fim de semana se descartam Determinar o seguinte i A probabilidade de colocar um pedido durante cada dia da semana ii O número médio de dúzias de rosas descartadas no fim de semana Sistemas de Filas Solução Desde que 𝑝𝑛 𝑡3𝑡 18𝑛𝑒 3𝑡 18𝑛 𝑛1218tnú merode dias temse que i Assim t dias 1 2 3 4 5 6 7 3 6 9 12 15 18 21 00000 00088 01242 04240 07324 09083 09755 𝐸 ii Considere n número de clientes no sistema fila serviço taxa de chegada de clientes dados n clientes no sistema taxa de saída de clientes dados n clientes no sistema probabilidade do estado estável de n clientes no sistema Sistemas de Filas Modelo de Filas de Poisson Generalizado Este modelo combina chegadas e partidas baseadas nas hipóteses de Poisson ie os tempos entre chegadas e tempos de serviço seguem distribuição exponencial Assumese que o comportamento corresponde ao estado do longo prazo estado contínuo ou estado estável atingido pelo sistema depois de funcionar por um longo período O curto prazo corresponde ao estado transiente ou de aquecimento que prevalece durante a operação inicial do sistema Supõese que as taxas de chegada e saída dependem do estado ie que dependem do número de clientes nas instalações do serviço Objetivo Exprimir como função de e de essa expressão para determinar as medidas de desempenho do sistema comprimento médio da fila tempo médio de espera média de utilização dos servidores etc Sistemas de Filas Usaremos para tanto o diagrama de taxa de transição Diremos que o sistema está no estado n quando o número de clientes no sistema é n Assim das hipóteses do processo de Poisson Teorema 1 a probabilidade de mais de um evento entrada ou saída acontecer num tempo tende a 0 quando Assim quando n 0 o estado n pode mudar unicamente para dois casos possíveis n1 n n1 𝜇𝑛 𝜆𝑛 É claro que o estado n 0 só pode mudar para n 1 quando uma chegada acontece com taxa Portanto temse o diagrama de taxa de transição 𝜆𝑛1 𝜇𝑛1 n1 n n1 𝜇𝑛 𝜆𝑛 0 1 2 𝜇1 𝜆1 𝜆0 𝜇2 Sistemas de Filas Sob as condições de estado estável para n 0 as taxas esperadas de entrada e saída ao estado n devem ser iguais balanceadas Assim desde que o estado n só pode mudar para os estados n1 ou n1 temse que Taxa esperada de entrada ao estado n Taxa esperada de saída do estado n 𝜆0𝑝0𝜇1 𝑝1 𝑛0 Portanto para n0 𝑝1 𝜆0 𝜇1𝑝 0 𝜆0𝑝0𝜇2 𝑝2 n1 𝑝2 𝜆1 𝜆0 𝜇2𝜇1𝑝 0 n geral 𝑝𝑛 𝜆𝑛1 𝜆𝑛 2 𝜆0 𝜇𝑛𝜇𝑛 1𝜇1 𝑝 0 𝑛12 onde o valor de 𝑛0 𝑝𝑛1 Equações de balanço Sistemas de Filas Exemplo 10 O minimercado AB opera até com 3 caixas da seguinte forma abre um caixa adicional cada vez que a fila em qualquer caixa passar de 3 clientes ie para menos de 4 clientes funciona só um caixa para mais de 6 funcionam os 3 Os clientes chegam aos caixas segundo uma distribuição de Poisson com média de 10 clienteshora O tempo médio de atendimento nos caixas é exponencial com média de 12 minutoscliente Determinar a probabilidade de estado estável de n clientes no sistema de caixas Solução Sabese que Então 𝑝1 10 5 𝑝 0 2𝑝0 𝑝2 10 5 2 𝑝 0 4 𝑝0 𝑝3 10 5 3 𝑝 0 8𝑝0 𝑝4 10 5 3 10 10𝑝 0 8 𝑝0 𝑝5 10 5 3 10 10 2 𝑝 0 8𝑝0 𝑝6 10 5 3 10 10 3 𝑝 0 8𝑝0 𝑝𝑛 10 5 3 10 10 3 10 15 𝑛 6 𝑝 0 8 2 3 𝑛6 𝑝 0 𝑛7 8 Assim de temse 𝑝0𝑝0311 2 3 2 3 2 2 3 3 1 1 Sistemas de Filas A partir dessas probabilidades podem estabelecerse algumas medidas relativas ao sistema Por exemplo a probabilidade de que só um caixa esteja operativo equivalente à probabilidade de ter no máximo 3 clientes 𝑝0𝑝1𝑝2𝑝31248 1 550 273 Note que se supõe que mesmo sem clientes no sistema mantémse um caixa operativo Outras medidas de desempenho podem calcularse Por exemplo o número médio de caixas ociosos fora de operação Média de caixas ociosos m 𝑚3𝑝02 𝑝1𝑝2𝑝31𝑝4𝑝5𝑝6 𝑚3𝑝02 2𝑝04𝑝08𝑝08 𝑝08𝑝08𝑝055𝑝0 𝑚1 Sistemas de Filas Exemplo 11 considere um sistema de filas com um único servidor com as seguintes taxas de chegadas e saídas 3 𝜇𝑛 𝑛 2 5𝑛1234 i Estabelecer o diagrama de transição e determinar as equações de balanço para o sistema ii Determinar as probabilidades de estado estável Note que a taxa de chegada diminui e a de saída aumenta na medida que o número de usuário aumenta no sistema Solução i 𝜆2 𝜇4 3 4 𝜇3 𝜆3 0 1 2 𝜇1 𝜆1 𝜆0 𝜇2 𝜆0𝑝0𝜇1𝑝110 𝑝055𝑝1 Desde que Por outro lado 𝒏𝟏10𝑝06 𝑝2145𝑝1 𝒏𝟐9𝑝16 5𝑝314𝑝2 𝒏𝟑8 𝑝27 𝑝413 5𝑝3 ii 𝑝0𝑝1𝑝2𝑝3𝑝41 𝑝000816𝑝10 1484 𝑝202225𝑝3𝑝402739 𝒏𝟒 𝑝3𝑝4 Sistemas de Filas Filas Especializadas de Poisson A seguinte figura ilustra um sistema de filas especializado O sistema consta de c servidores idênticos em paralelo onde um cliente se seleciona da fila pelo primeiro servidor livre O número de clientes no sistema corresponde a todos aqueles que esperam na fila mais os que estão sendo servidos num certo momento Servidor 1 Servidor 2 Servidor c Sistema Fila Serviço Taxa de chegada Taxa de saída Taxa de saída Taxa de saída Sistemas de Filas A notação de KENDALL a seguir usase para resumir as características de um sistema de filas como o da figura 𝑎𝑏𝑐 𝑑𝑒 𝑓 onde a Descreve a distribuição de chegada b Descreve a distribuição de saída c Número de servidores em paralelo d Disciplina da fila e Capacidade do sistema fila serviço finita ou infinita f Tamanho da fonte finito ou infinito A notação padrão para representar as distribuições de chegada e saída a e b é M Chegadas ou saídas Markovianas Poisson Equivalentemente distribuições do tempo entre chegadas e de serviço exponenciais D tempo constante determinístico Distribuição Erlang ou Gama do tempo GI Distribuição genérica geral do tempo entre chegadas G Distribuição genérica geral do tempo de serviço Sistemas de Filas Exemplo 12 denota um sistema com chegadas Poisson M tempo de serviço constante D 10 servidores em paralelo sem disciplina específica GD com capacidade para N usuários e tamanho da fonte infinita 𝑀 𝐷10 𝐺𝐷𝑁 Medidas de Desempenho o Estado Estável As mais comuns são Número médio de clientes no sistema Número médio de clientes na fila Tempo médio de espera no sistema Tempo médio de espera na fila Número médio de servidores ocupados É claro que 𝐿𝑠 𝑛1 𝑛𝑝𝑛 𝐿𝑞 𝑛𝑐1 𝑛𝑐𝑝𝑛 As relações entre e e conhecemse como FÓRMULAS DE LITTLE 𝐿𝑠𝜆𝑒𝑓 𝑊 𝑠 𝐿𝑞𝜆𝑒𝑓 𝑊 𝑞 onde é a taxa de chegada efetiva ao sistema será calculado mais tarde em geral Sistemas de Filas Desde que Tempo médio de espera no serviço Tempo médio de espera no sistema Tempo médio de espera na fila 𝑊 𝑠𝑊 𝑞 1 𝜇 𝜆𝑒𝑓𝐿𝑠𝐿𝑞 𝜆𝑒𝑓 𝜇 Agora por definição 𝑐𝐿𝑠 𝐿𝑞 𝜆𝑒𝑓 𝜇 Daqui que o PERCENTUAL DE UTILIZAÇÃO dos servidores se define como 𝑐 𝑐 100 Sistemas de Filas Exemplo 13 O estacionamento para visitantes numa empresa está limitado a 5 vagas Os visitantes chegam segundo uma distribuição Poisson com taxa de 6 carroshora O tempo de estacionamento é exponencial com média de 30 minutos Os visitantes que não encontram vaga podem esperar temporariamente dentro do estacionamento até uma vaga se liberar Este espaço de espera só tem 3 vagas Todos os outros carros que não podem estacionar ou esperar devem sair do estacionamento Determinar i A probabilidade de ter n carros no estacionamento ii A taxa de chegada efetiva ao estacionamento iii O número médio de carros no estacionamento iv O tempo médio de espera de um carro no estacionamento v O número médio de vagas do estacionamento ocupadas vi O número médio de carros que não podem entrar ao estacionamento num período de 8 horas vii O número médio de vagas livres Solução O número de servidores em paralelo é c 5 e o sistema tem capacidade N 8 Assim 𝜆𝑛6 carros hora 𝑛012 8 Sistemas de Filas 𝑝𝑛 𝜆𝑛1 𝜆𝑛 2 𝜆0 𝜇𝑛𝜇𝑛 1𝜇1 𝑝 0 𝑝𝑛 62𝑛 𝑛 𝑝0𝑛15 62 𝑛 55𝑛 5 𝑝0𝑛6 7 8 i n 1 2 3 4 5 6 7 8 014436 021654 021654 016240 009744 005847 003508 002105 ii Para calcular taxa de chegada efetiva note que Fonte 𝜆6 𝜆𝑒𝑓 𝜆𝑝𝑒𝑟𝑑𝑎𝑛8 Sistema 𝜆𝜆𝑒𝑓 𝜆𝑝𝑒𝑟𝑑𝑎𝜆𝑝𝑒𝑟𝑑𝑎λ𝑝801263 𝑐𝑎𝑟𝑟𝑜𝑠 ℎ𝑜𝑟𝑎 𝜆𝑒𝑓 𝜆 𝜆𝑝𝑒𝑟𝑑𝑎𝜆1𝑝858737 𝑐𝑎𝑟𝑟𝑜𝑠 ℎ𝑜𝑟𝑎 iii Assim 𝐿𝑠 𝑛1 8 𝑛𝑝𝑛31286𝑐𝑎𝑟𝑟𝑜𝑠 Sistemas de Filas iv 003625 horas v 29368 carros vagas vi Número médio de carros que não poderá estacionar num período de 8 horas 8 𝜆𝑝𝑒𝑟𝑑𝑎10104𝑐𝑎𝑟𝑟𝑜𝑠 vii Desde que Número médio de vagas livres Sistemas de Filas Modelos de um único servidor Consideramse aqui dois modelos com um único servidor c 1 onde os clientes chegam segundo uma taxa fixa e saem a uma taxa fixa Primeiro se considera um modelo com capacidade infinita para logo considerar outro modelo com capacidade finita N Ambos os modelos supõem fonte infinita Desde que os resultados anteriores não dependem da disciplina da fila assumese disciplina da fila genérica GD Assim o primeiro modelo a tratar é com e Desde que a capacidade é infinita Considerando da equação de balanço temse 𝑝𝑛𝜌 𝑛𝑝0𝑛12 𝑛0 𝑛 𝑝𝑛1 𝑝0 1𝜌𝜌 21 𝑛0 𝜌𝑛 1 1 𝜌 se 𝜌1 𝑝01 𝜌 𝑝𝑛𝜌 𝑛 1 𝜌𝑛0 12𝜌1 Note que para obter as probabilidades de estado estável precisase da hipótese ie Para a série não converge e o sistema não atinge o estado estável Neste caso o sistema opera sempre em estado transiente e a fila cresce indefinidamente com o tempo Sistemas de Filas Desde que 𝐿𝑠 𝑛1 𝑛𝑝𝑛 𝑛1 𝑛 𝜌 𝑛 1𝜌 𝐿𝑠 𝜌 1 𝜌 𝜆𝑒𝑓 𝜆 𝑊 𝑠 𝐿𝑠 𝜆 1 𝜇1 𝜌 𝑊 𝑞𝑊 𝑠 1 𝜇 𝜌 𝜇1 𝜌 𝐿𝑞 𝜆𝑊 𝑞 𝜌2 1𝜌 𝑐 𝐿𝑠 𝐿𝑞𝜌 Sistemas de Filas Exemplo 14 As instalações de um lavajato operam com uma única ducha Os carros chegam segundo uma distribuição de Poisson com média de 4 carroshora e podem esperar no estacionamento se a ducha estiver ocupada O tempo de lavagem é exponencial com média de 10 minutoscarro Os carros que no encontram lugar no estacionamento podem esperar na rua mas o gerente das instalações quer determinar o tamanho do estacionamento Solução 𝜆4 𝑐𝑎𝑟𝑟𝑜𝑠 ℎ𝑜𝑟𝑎 𝜇6 𝑐𝑎𝑟𝑟𝑜𝑠 ℎ𝑜𝑟𝑎 𝜌 4 6 0667 Assim Note que mesmo que carros este parâmetro não pode ser usado para dimensionar o estacionamento pois este é um número médio O tamanho de estacionamento deve estar relacionado com o tamanho máximo da fila que frequentemente se define como por exemplo que um carro que chegar encontre estacionamento 90 das vezes Assim se s é o tamanho da fila a ser determinado terseá s1 como capacidade do sistema sob a condição de que um cliente que chegar encontre ao menos uma vaga 90 das vezes ie encontre no máximo s clientes no sistema Sistemas de Filas s Exemplo 15 Para o caso do exemplo anterior determinar i O percentual de utilização da ducha ii A probabilidade de que um carro ao chegar deva esperar no estacionamento antes do serviço Solução i 𝑐 𝑐 100 𝜌 𝑐 10046 1 1006667 ii Distribuição de tempo de espera para As fórmulas de para o modelo não dependem da disciplina da fila Portanto as medidas de desempenho encontradas se aplicam para qualquer disciplina Sistemas de Filas Entretanto embora o tempo médio de espera não dependa da disciplina da fila sua função de densidade de probabilidade é dependente Estabelecese aqui o caso da distribuição do tempo de espera na fila para o modelo com disciplina FIFO Considere 𝜏 𝑡𝑒𝑚𝑝𝑜𝑑𝑒𝑒𝑠𝑝𝑒𝑟𝑎𝑑𝑒𝑢𝑚𝑐𝑙𝑖𝑒𝑛𝑡𝑒𝑞𝑢𝑒𝑎𝑐𝑎𝑏𝑜𝑢 𝑑𝑒𝑐ℎ𝑒𝑔𝑎𝑟𝑎𝑡 é 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑎𝑟 𝑜𝑠𝑒𝑟𝑣𝑖ç 𝑜 Desde que a disciplina é FIFO se ao chegar existem n usuários no sistema o cliente deverá esperar 𝜏𝑡1 𝑡2𝑡𝑛𝑡𝑛1 tempo para completar o serviço do cliente em atendimento tempos de serviço para clientes na fila tempo de serviço para o cliente que acabou de chegar Sistemas de Filas Seja Desde que a distribuição de tempos de serviço é exponencial sem memória também se distribui exponencialmente Portanto é a soma de n1 variáveis aleatórias independentes igualmente distribuídas exponencialmente Sabese da Teoria de Probabilidades que segue uma distribuição Gama Erlang com parâmetros e n1 𝑤 𝜏𝑛1𝜇𝜇𝜏 𝑛𝑒 𝜇𝜏 𝑛 Assim 𝜌 𝜆 𝜇 𝑤 𝜏 𝑛0 𝑤 𝜏 𝑛1𝑝𝑛 𝑛0 𝜇𝜇𝜏 𝑛𝑒 𝜇𝜏 𝑛 1 𝜌 𝜌 𝑛1𝜌𝜇𝑒 𝜇𝜏 𝑛0 𝜆𝜏 𝑛 𝑒 𝜆𝜏 𝑤 𝜏 𝜇1𝜌𝑒 𝜇1 𝜌 𝜏 𝜏0 ie é exponencial com média Exemplo 16 Para o caso do exemplo do lavajato é razoável supor que a disciplina da fila seja FIFO Avaliar a confiabilidade de usar como estimativa do tempo de espera no sistema Sistemas de Filas Solução Uma possível forma de responder a questão é calcular a proporção de usuários cujo tempo de espera excederá Assim 𝑃𝜏𝑊 𝑠1 0 𝑊 𝑠 𝑤 𝜏 𝑑𝜏𝑒 𝜇1 𝜌 𝑊 𝑠𝑒 10 368 ie cerca de 37 dos usuários deverá esperar mais do que Proporção que parece grande sobretudo quando é grande Note quenão depende denem depara nenhum modelo o que significa que esse valor não pode ser reduzido ie sempre haverá cerca de 37 dos usuários que esperará mais do que Sistemas de Filas Entretanto duas opções são possíveis i Aumentar a taxa de serviço de forma a reduzir o valor de ou ii Selecionar tal que a probabilidade de tempo de espera que exceder um tempo pré estabelecido digase 10 minutos seja razoavelmente pequeno digase 10 Note que i Encontrar tal que ii Encontrar tal que 10 minutos 01 Sistemas de Filas O modelo A diferença do modelo anterior neste modelo a capacidade do sistema está limitada a N clientes Assim o número máximo de clientes na fila é N1 Uma vez que o número de usuários atinge a capacidade não são aceitas mais chegadas Portanto 𝜌𝜆𝜇 𝑝𝑛 𝜆𝑛1 𝜆𝑛 2 𝜆0 𝜇𝑛𝜇𝑛1𝜇1 𝑝 0 𝑝𝑛 𝜌 𝑛𝑝0𝑛01𝑁 1 0𝑛𝑁 𝑁1 𝜆𝑛 𝜆𝑛01 𝑁 1 0𝑛𝑁 𝑁1 𝜇𝑛𝜇𝑛12 onde é tal que 𝑝0 1 𝜌 1 𝜌 𝑁 1 𝜌 1 1 𝑁1 𝜌1 𝑝𝑛 𝜌𝑛1 𝜌 1 𝜌 𝑁 1 𝜌 1 1 𝑁1 𝜌1 𝑛 Note que neste caso não precisa ser menor do que 1 pois as chegadas neste modelo estão controladas pela capacidade do sistema Sistemas de Filas Por outro lado desde que cliente serão rejeitados quando o sistema tiver N usuários temse 𝜆𝑝𝑒𝑟𝑑𝑎𝜆𝑝𝑁 𝜆𝑒𝑓 𝜆 𝜆𝑝𝑒𝑟𝑑𝑎𝜆1𝑝 𝑁 Assim 𝐿𝑠 𝑛1 𝑁 𝑛𝑝𝑛 𝜌 1 1 𝜌 1𝜌 𝑁 1 𝑛1 𝑁 𝑛 𝜌 𝑛 𝐿 𝑠 𝜌 1 𝑁1 𝜌 𝑁𝑁 𝜌 𝑁 1 1𝜌1𝜌 𝑁 1 𝜌 1 Quando 𝜌1 𝐿𝑠 𝑛0 𝑁 𝑛 1 𝑁1 1 𝑁 1 𝑛0 𝑁 𝑛 𝐿 𝑠 𝑁 2 𝜌1 𝑊 𝑠 𝐿𝑠 𝜆𝑒𝑓 𝜌 1 𝑁1 𝜌 𝑁 𝑁 𝜌 𝑁1 λ1 𝜌1 𝜌 𝑁 𝜌 1 𝑁1 2 𝜆 𝜌1 Encontrar e Sistemas de Filas Exemplo 17 Para o caso do exemplo do lavajato suponha que se conta com 4 vagas de estacionamento para espera Se o estacionamento estiver lotado não se aceitam novos clientes O proprietário deseja estimar o impacto das 4 vagas de estacionamento na perda de clientes Solução É claro que o modelo de filas corresponde a com e e Portanto desde que temse que 𝑝𝑛 𝜌𝑛1 𝜌 1𝜌 6 𝑛0125 0𝑛6 Assim Sendo N5 a capacidade do sistema a proporção de clientes perdidos é ie cerca de 5 dos clientes se perdem a cada hora Portanto num dia de 16 horas de serviço se perdem Por outro lado desde outro ponto de vista note que o tempo médio de espera no sistema aprox 22 minutos é menor que os 30 minutos correspondentes a Essa redução se consegue ao custo de perder 5 dos clientes Sistemas de Filas Modelos com múltiplos servidores Tratamse aqui os seguintes modelos markovianos Modelo Neste modelo se tem c servidores em paralelo A taxa de chegada é e a de serviço Desde que a capacidade do sistema é ilimitada O efeito de contar com c servidores é um aumento proporcional na taxa de serviço das instalações Portanto em termos do modelo geral temse 𝜆𝑛𝜆𝑛0 𝑝𝑛 𝜆𝑛 𝜇2𝜇 3𝜇 𝑛𝜇 𝑝0 𝜆𝑛 𝑛𝜇𝑛 𝑝0𝑛𝑐 𝜆𝑛 𝜇2𝜇 𝑐 1𝜇𝑐𝜇𝑛𝑐 1 𝑝0 𝜆𝑛 𝑐𝑐𝑛 𝑐𝜇𝑛 𝑝0𝑛𝑐 Considerando e temse de 𝑝0 𝑛0 𝑐 1 𝜌 𝑛 𝑛 𝜌 𝑐 𝑐 𝑛𝑐 𝜌 𝑐 𝑛 𝑐 1 Sistemas de Filas Note que podese calcular como 𝐿𝑞 𝑛𝑐 𝑛𝑐𝑝𝑛 𝐿𝑞 𝜌 𝑐 1 𝑐1 𝑐𝜌 2 𝑝0 Desde que 𝑊 𝑠 𝐿𝑠 𝜆 𝑊 𝑞 𝐿𝑞 𝜆 Sistemas de Filas Exemplo 18 Numa casa lotérica o atendimento nos caixas está organizado em duas filas com dois guichês para cada uma Os clientes entram nas filas com uma taxa de 8 clienteshora A média de tempo de atendimento em cada guichê é de 12 minutos e a chegada é Poisson sendo o tempo de atendimento exponencial O gerente da casa está interessado em modificar o atendimento nos caixas colocando fila única para os 4 caixas Analisar a proposta Solução Visto como modelos de filas os sistemas são os seguintes ATUAL PROPOSTO Uma medida adequada para o desempenho dos sistemas pode ser Sist Atual 4444 0556 2844 0356 Sist Proposto 5586 0349 2386 0149 Obs Em geral fila única é uma operação mais eficiente Sistemas de Filas Modelo Neste modelo só se permitem N clientes no sistema ie Nc na fila As taxas de chegada e de serviço são é e respectivamente É claro que dada a capacidade limitada do sistema N Portanto em termos do modelo geral temse 𝜆𝑛 𝜆0 𝑛 𝑁 1 0 𝑛 𝑁 𝑝𝑛 𝜌𝑛 𝑛 𝑝0 0𝑛 𝑐 𝜌𝑛 𝑐𝑐𝑛 𝑐 𝑝0𝑐 𝑛 𝑁 Assim de e temse que 𝑛0 𝑝𝑛1 𝑝0 𝑛0 𝑐 1 𝜌𝑛 𝑛 𝜌𝑐1 𝝆 𝑐 𝑁 𝑐1 𝑐 1 𝝆 𝑐 1 𝜌 𝑐 1 𝑛 0 𝑐 1 𝜌 𝑛 𝑛 𝜌𝑐 𝑐 𝑁 𝑐1 1 𝜌 𝑐 1 Sistemas de Filas Para obter e precisase calcular Desde que se rejeitam clientes quando se tem N usuários no sistema temse que 𝜆𝑝𝑒𝑟𝑑𝑎𝜆𝑝𝑁 𝜆𝑒𝑓 𝜆 𝜆𝑝𝑒𝑟𝑑𝑎𝜆1𝑝 𝑁 Assim a partir de e se obtêm e Sistemas de Filas Exemplo 19 Para o caso do exemplo anterior da casa lotérica suponha que não se tem condições de abrir um novo guichê O proprietário é aconselhado a reduzir o tempo de espera informando aos clientes que quando a fila atingir tamanho 6 o tempo de espera é potencialmente longo Analisar a proposta Solução Limitar a 6 os clientes na fila estabelece a capacidade do sistema em N 6410 Assim o modelo proposto é com clienteshora e clienteshora Portanto 𝜆𝑒𝑓 𝜆 𝜆𝑝𝑒𝑟𝑑𝑎𝜆 1𝑝10161 165 10 4 410 4 𝑝015428 𝐿𝑞1154 𝑊 𝑞 𝐿𝑞 𝜆𝑒𝑓 0074 𝑊 𝑠𝑊 𝑞 1 𝜇 0274 𝐿𝑠𝐿𝑞 𝜆𝑒𝑓 𝜇 4239 n 0 1 2 3 4 5 6 7 8 9 10 00312 00998 01597 01704 01363 01097 00872 00698 00558 00446 00357 Note que Portanto se reduz à metade ao custo de perder cerca de 36 dos clientes Sistemas de Filas Modelo autoserviço Neste modelo tanto o número de clientes como o de servidores é ilimitado pois o próprio cliente é servidor É o caso por exemplo de tickets preenchidos e depositados numa urna pelo cliente num supermercado Assumese que a taxa de chegada é e a de serviço constantes Dos resultados do modelo generalizado temse Então de e temse 𝜆𝑛𝜆𝑛0 12 𝜇𝑛𝑛𝜇 𝑛12 𝑝𝑛 𝜌 𝑛𝑒 𝜌 𝑛 𝑛012 ie se distribui segundo uma Poisson 𝐿𝑠𝜌 𝜆𝑒𝑓 𝜆𝐿𝑠𝐿𝑞 𝜆𝑒𝑓 𝜇 𝐿𝑞0𝑊 𝑞0 Sistemas de Filas Exemplo 20 Um investidor investe R 100000 mensais num tipo de ações Dado que deve esperar por boas oportunidades de compra o momento desta é aleatório O investidor normalmente mantém as ações por 3 anos em média mas vende em tempo aleatório quando se apresenta um bom momento de venda Embora saibase que o investidor é um jogador experto sabese que ao redor de 25 das ações declina cerca de 20 anualmente O restante 75 se valoriza a uma taxa de 12 anual Estimar o rendimento médio de longo prazo do investidor Solução Desde que o investidor não precisa esperar para comprar ou vender seu comportamento pode ser descrito pelo modelo Sendo o tempo médio entre compras 1 mês temos comprasano e as vendas podem ser consideradas como 13 comprasano Assim ações Por tanto os rendimentos anuais de longo prazo são 025 𝐿𝑠1000 10 2075 𝐿𝑠1000 1012 𝐿𝑠1000639003600027 990 Sistemas de Filas Modelo de Manutenção de Máquinas Neste modelo a proposta é de um serviço de manutenção que considera K máquinas sempre que uma máquina quebra demandase o serviço de manutenção e um dos R técnicos disponíveis atende o pedido A taxa de defeitos é de máquinasunidade de tempo e os técnicos reparam as máquinas defeituosas a razão de máquinasunidade de tempo Defeitos e serviços técnicos se supõem distribuídos segundo Poisson Note que a fonte dos usuários máquinas é finita se todas as máquinas quebrarem a demanda termina ie unicamente máquinas em serviço podem gerar demanda Assim a taxa de defeito do conjunto de máquinas é proporcional ao número de máquinas em funcionamento Em termos da linguagem de filas ter n máquinas no sistema de filas significará que n máquinas estão com defeito e 𝜆𝑛 𝐾 𝑛 𝜆0 𝑛 𝐾 0 𝑛 𝐾 Sistemas de Filas Assim do modelo generalizado onde temse 𝑝𝑛 𝐾 𝑛 𝜌 𝑝0 1 𝑛 𝑅 𝐾 𝑛 𝑛 𝜌𝑛 𝑅 𝑅𝑛 𝑅 𝑝0 𝑅 𝑛 𝐾 0𝑛𝐾 𝑛0 𝑝𝑛1 𝑝0 Neste modelo é difícil obter uma fórmula para e que devem ser calculados como 𝐿𝑠 𝑛1 𝐾 𝑛𝑝𝑛 O valor de se calcula como 𝜆𝑒𝑓 𝐸 𝜆 𝐾 𝑛𝜆𝐾 𝐿𝑠 Sistemas de Filas Exemplo 21 Uma empresa opera um serviço com 22 máquinas Sabese que cada máquina quebra em média uma vez a cada 2 horas e toma uma média de 12 minutos para ser reparada Os tempos entre defeitos e de reparação seguem distribuição exponencial A empresa está interessada em determinar o número de técnicos necessários para manter um serviço adequado Solução O problema pode ser analisado estabelecendo a produtividade das máquinas como função do número de técnicos onde a produtividade se mede como 𝑃𝑟𝑜𝑑𝑢𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒 𝑀 é 𝑑𝑖𝑎 𝑑𝑒𝑚á𝑞𝑢𝑖𝑛𝑎𝑠 𝑠𝑒𝑚𝑑𝑒𝑓𝑒𝑖𝑡𝑜 𝑇𝑜𝑡𝑎𝑙 𝑑𝑒𝑚á𝑞𝑢𝑖𝑛𝑎𝑠 100 22 𝐿𝑠 22 100 A seguir se mostram os resultados do modelo para R variando de 1 a 4 K 22 com e R 1 2 3 4 Produtividade 4544 8015 8879 9045 Aumento marginal 100 3471 864 166 Sistemas de Filas Os resultados anteriores foram obtidos da seguinte tabela R 1 05 5 4998 12004 2402 11004 2202 2 05 5 8816 4368 0495 2604 0295 3 05 5 9767 2466 0252 0513 0052 4 05 5 9950 2100 0211 0110 0011 Note que de acordo à tabela de produtividade a proposta mais forte parece ser a de R 2 pois a produtividade aumenta 3471 de R 1 para R 2 Entanto que só aumento 864 de R 2 para R 3 A proposta R 4 é muito pobre Uma comparação entre a receita gerada pelo 864 de produtividade marginal de ir de R 2 para R 3 e o custo de contratar um técnico adicional pode definir qual das duas propostas é mais conveniente Sistemas de Filas Modelo de Fórmula de PollaczekKintchine Modelos de filas nos que as chegadas ou saídas não seguem a distribuição Poisson são complexos Nesses casos se recomenda usar técnicas de simulação para a análise correspondente Apresentase aqui um caso de modelo não Poisson nos que os resultados analíticos estão disponíveis chegada Poisson taxa mas tempo de serviço aleatório genérico com média Et e variância vart Este modelo não proporciona uma fórmula fechada para por causa da intratabilidade analítica mas assumindo que provase que 𝐿𝑠𝜆 𝐸 𝑡 𝜆2 𝐸 2 𝑡𝑣𝑎𝑟𝑡 2 1 𝜆𝐸 𝑡 Desde que e a partir de Sistemas de Filas No que segue considerarseá complementarmente a o exposto alguns assuntos de interesse ver para os detalhes o arquivo Múltiplas fontes exponenciais e outrosdoc Problema 1 A distribuição conjunta do intervalo entre chegadas correspondente a um sistema de filas alimentado por r fontes que fornecem clientes independentemente cujos intervalos entre chegadas é exponencial com taxa de chegada para Problema 2 Considere um sistema de filas constituído por uma única fonte que fornece clientes exponencialmente a uma taxa para um serviço que está constituído por k estágios em série cada um com tempo de serviço exponencial e taxa de serviço Discuta o cálculo das medidas de desempenho e e Para efeitos de análise considere inicialmente k2 depois generalize Problema 3 Modelos de filas com múltiplas classes de usuários e prioridade Considere um modelo com r usuários de diferentes fontes onde cada fonte tem seu processo de chegada e seu processo de serviço no sistema mas os usuários têm prioridade no serviço o usuário da Fonte k tem prioridade sobre o da Fonte k1 k Assim se um servidor ficar livre deverá atender um usuário da fila de maior prioridade de acordo à disciplina da correspondente fila Neste caso pode ser considerado ainda que a prioridade é com interrupção preemptive priority PRP ou sem interrupção nonpreemptive priority NPRP ie se interrompe ou não o serviço que está sendo prestado se chegar um cliente com prioridade Sistemas de Filas Problema 1 Adistribuição conjunta do intervalo entre chegadas correspondente a um sistema de filas alimentado por n fontes que fornecem clientes independentemente cujos intervalos entre chegadas é exponencial com taxa de chegada para Sistema de Filas Fonte r Fonte 2 Fonte 1 𝜆1 𝜆2 𝜆𝑟 𝑖1 𝑟 𝜆𝑖 Se ft é a função de distribuição de probabilidade conjunta do intervalo entre chegadas então 𝑓 𝑡 𝑖1 𝑟 𝜆𝑖𝑒 𝑖 1 𝑟 𝜆𝑖𝑡 𝑡0 Sistemas de Filas Problema 2 Considere um sistema de filas constituído por uma única fonte que fornece clientes exponencialmente a uma taxa para um serviço que está constituído por k estágios em série cada um com tempo de serviço exponencial e taxa de serviço Discuta o cálculo das medidas de desempenho e e Para efeitos de análise considere inicialmente k2 depois generalize 𝜆 Servidores 1 Servidores 2 c servidores Taxa de serviço para todo servidor Intervalo entre chegadas Para o caso k2 temse Sistemas de Filas Problema 3 Modelos de filas com múltiplas classes de usuários e prioridade Considere um modelo com usuários de diferentes fontes onde cada fonte tem seu processo de chegada e seu processo de serviço no sistema mas os usuários têm prioridade no serviço o usuário da Fonte k tem prioridade sobre o da Fonte k1 k Assim se um servidor ficar livre deverá atender um usuário da fila de maior prioridade de acordo à disciplina da correspondente fila Neste caso pode ser considerado ainda que a prioridade é com interrupção preemptive priority PRP ou sem interrupção nonpreemptive priority NPRP ie se interrompe ou não o serviço que está sendo prestado se chegar um cliente com prioridade 1 Modelo um servidor e prioridade sem interrupção Aqui as fontes fornecem clientes exponencialmente com taxa e o serviço é genérico segundo a fonte do usuário com taxa e variância onde é o tempo médio do serviço note que o sistema pode ser visto como um sistema de filas múltiplas com um único servidor Considerando com podese provar que r k S E S V W k i i k i i i i i k Q 1 1 1 2 1 1 1 2 Tempo médio de espera na fila onde se Caso para algum k para pois o sistema não atinge o equilíbrio As outras medidas de desempenho podem ser encontradas das Fórmulas de Little 2 Modelo um servidor e prioridade com interrupção Como no modelo anterior r fontes fornecem clientes exponencialmente com taxa mas o serviço é único para todas as fontes com taxa Considerando para cada cliente e podese provar que Sistemas de Filas 𝑊 𝑄 𝑘 1 𝜇 1 𝑖1 𝑘 1 𝜌𝑖1 𝑖1 𝑘 𝜌 𝑖 𝑘1 𝑟 Tempo médio de espera no sistema Devido à falta de memória da exponencial o resultado é válido tanto para quando o serviço interrompido se reinicia a partir do ponto de interrupção como quando é recomeçado desde o início interrupção com perda Sistemas de Filas 3 Modelo c servidores e prioridade sem interrupção Considere neste caso e podese provar que 𝑊 𝑄 𝑘 𝑐 𝜌 𝑐 𝑐 𝜇 1 𝜌 𝑐 1 𝑖1 𝑘 1 𝜌𝑖1 𝑖1 𝑘 𝜌 𝑖 𝑝0 𝑘1 𝑟 onde é a probabilidade de um sistema com fator estra vazio Caso para algum para pois o sistema não atinge o equilíbrio Sistemas de Filas Modelos de decisão para Filas O nível de serviço em um sistema de filas é função da taxa de serviço ou do número de servidores em paralelo c Discutemse aqui dois modelos de decisão para determinar níveis de serviço convenientes para sistemas de filas 1 Modelo e custos 2 Modelo de metas Em ambos os modelos se assume que um maior nível de serviços reduz o tempo de espera no sistema Os modelos fazem uso das medidas de desempenho estabelecidas para encontrar um balanço entre os fatores conflitantes nível de serviço e tempo de espera MODELO DE CUSTOS Pretende encontrar um balanço entre dois custos conflitantes o custo de oferecer os serviço e o custo de retardar o oferecimento do serviço custo do tempo de espera Estes custos são conflitantes na medida que aumentar um significa diminuir o outro Considere ou onde Custo total médio esperado por unidade de tempo Custo de operação médio esperado da instalação por unidade de tempo Custo de espera médio esperado por unidade de tempo Sistemas de Filas As formas mais simples para COE e CWE são lineares onde custo marginal por unidade de por unidade de tempo custo de espera do cliente por unidade de tempo Os seguintes exemplos ilustram o modelo de custos para e para Exemplo 22 Uma gráfica está no processo de compra de uma copiadora de alta velocidade Quatro tipos de copiadora cujas especificações se apresentam a seguir foram propostos Tipo Custo Operacional Rhora Velocidade Folhasminuto 1 15 30 2 20 36 3 24 50 4 27 66 Sistemas de Filas Os pedidos chegam à gráfica segundo uma distribuição de Poisson com média de 4 trabalhosdia 24 horas O tamanho do pedido é aleatório mas tem média de 10000 folhas Os contratos com os clientes especificam uma penalidade por atraso na entrega de R 80 trabalhodia Qual a copiadora a ser recomendada Solução O custo total esperado diário para cada copiadora é onde corresponde ao custo operacional horário do respectivo modelo e ao tamanho médio dos pedidos no sistema para o qual a copiadora deverá ser tratada como um modelo de filas MM1GD com e determinado para cada tipo de copiadora da seguinte forma i1 Tempo médio por trabalho Assim temse Tipo i 1 2 3 4 pedidosdia 432 518 720 950 Sistemas de Filas Usando a relação temse Tipo 1 4 432 1250 2 4 518 339 3 4 720 125 4 4 950 073 Portanto Tipo COE R 1 36000 100000 136000 2 48000 27120 75120 3 57600 10000 67600 4 64800 5840 70640 Sistemas de Filas Exemplo 23 Em uma oficina de manutenção mecânica de uma empresa com vários balconistas os pedidos para troca de ferramentas ocorrem segundo uma Poisson com média de 175 pedidoshora Cada balconista pode atender uma média de 10 pedidoshora O custo de contratar um balconista é de R 12 hora e o custo de perda de produção por pedido em espera é aproximadamente R 50 Determinar o número de balconistas mais adequado Solução O problema corresponde a um sistema MMc no qual se deseja determinar c de forma a minimizar o custo total esperado Assim considerando o modelo de custos pode ser formulado como onde c é o número de balconistas Usando o modelo MMc GD com e temse de 𝑝0 𝑛0 𝑐 1 𝜌 𝑛 𝑛 𝜌 𝑐 𝑐 𝑛𝑐 𝜌 𝑐 𝑛 𝑐 1 para 𝜌 𝜆 𝜇 𝑐 e 𝐿𝑠𝐿𝑞𝜌 que e Sistemas de Filas c balconistas pedidos em espera R 2 7467 39735 3 2217 14235 4 1842 14010 5 1769 14845 6 1754 15970 MODELO DE METAS O Modelo de Custos depende da apuração dos parâmetros de custo com frequência difíceis de estimar em particular se associados tempos de espera de pessoas O Modelo de metas pretende evitar essa dificuldade trabalhando diretamente com as medidas de desempenho dos sistemas de filas A ideia é determinar uma variação aceitável para o nível do serviço ou c especificando limites razoáveis sobre as medidas de desempenho conflitantes Tais limites se denominam METAS que o tomador de decisão deseja atingir Sistemas de Filas Ilustrase o procedimento aplicandoo ao modelo de múltiplos servidores onde se deseja determinar um número aceitável de servidores Considere as seguintes duas medidas de desempenho conflitantes 1 Tempo médio de espera no sistema 2 Percentual de servidores ociosos Desde que para o modelo MMc temse e onde o problema se reduz a determinar tal que e onde e são as metas determinadas pelo tomador de decisão Por exemplo 3 e 10 Ver a figura seguinte para uma interpretação gráfica das metas Sistemas de Filas c 𝛼 𝛽 𝑋 𝑊 𝑠 Variação aceitável de c e Sistemas de Filas Exemplo 24 No exemplo anterior balconistas de uma oficina de apoio mecânico suponha que se queira determinar o número de balconistas de forma que o tempo de espera para troca de ferramentas não ultrapasse 5 minutos Simultaneamente requerse que o percentual de ociosidade seja no máximo de 20 Solução Note antes de iniciar os cálculos que desde que o tempo de espera médio só para a recepção é de 6 minutos Assim ás metas estabelecidas não são atingíveis Na tabela abaixo mostramse os e como função de c c 2 3 4 5 6 7 8 min 256 76 63 60 60 60 60 125 417 563 650 708 750 780 ie aumentar c não diminui para a meta proposta Portanto o problema deveria ser atacado diminuindo ou Sem tempo de espera na fila min Sistemas de Filas Modelos de Simulação Simulação Técnica que permite levantamento de informação sobre o comportamento de um sistema por meio de execução de um modelo computarizado O objetivo é verificar o comportamento do sistema quando os parâmetros mudam de forma a melhorar o desempenho do mesmo A Simulação se usa em todas as áreas do conhecimento e seus resultados estão baseados na amostragem aleatória como quando se observa um sistema real Portanto técnicas estatísticas estão por trás das técnicas de Simulação Simulação de Monte Carlo Esta técnica é a mais usada em Simulação e faz uso da amostragem aleatória para estimar o desempenho de um sistema por um experimento computacional Exemplo 25 Estimar a área do círculo de raio 5 com centro no ponto 12 usando o Monte Carlo Solução A equação do círculo é A técnica consiste em colocar o círculo dentro duma figura conhecida por exemplo inscrevêlo num quadrado e aleatoriamente tomar escolher pontos da figura de forma que determinado a proporção desses pontos no círculo possa estimarse a área deste Sistemas de Filas A estimativa da área do círculo se baseia na hipótese de que todos os pontos do quadrado tem a mesma probabilidade de ser escolhidos Assim se numa amostra aleatória de tamanho n m pontos estão no círculo então 𝐴𝐶 𝐴𝑄 𝑚 𝑛 𝐴𝐶 𝑚 𝑛 𝐴𝑄 Lembrar que a função de densidade de probabilidade para a escolha aleatória de um ponto no intervalo está dada pela Distribuição Uniforme 𝑓 𝑥 1 𝑏 𝑎 𝑎 𝑥 𝑏 0 𝑐𝑐 a b 1ba fx Q 12 5 43 63 47 67 C Sistemas de Filas Assim representando um ponto do quadrado pelo par e definindo a distribuição uniforme 𝑓 𝑅 1 0 𝑅1 0 𝑐𝑐 poderemos gerar dois pontos para gerar o ponto 410 y310 Logo gerando um conjunto de pontos aleatórios temse o correspondente conjunto de pontos aleatórios no quadrado Q onde cada par de pontos estará no círculo C se 𝑥12 𝑦 22 25 Sistemas de Filas Assim por exemplo usando a tabela de números aleatórios abaixo podemos gerar um ponto usando os números os dois primeiros números aleatórios da primeira coluna e 6733 410 y310 Portanto o ponto está no círculo pois 3 4111 23 7332 222 4625 TABELA Uma lista de números aleatórios O procedimento será repetido n vezes considerando o número m de vezes no que o ponto pertence ao círculo e a área do círculo será estimada por Sistemas de Filas Observação Para aumentar a confiabilidade da estimativa da área do círculo usamse procedimentos usuais dos experimentos estatísticos i aumentar n o tamanho da amostra e ii considerar como valor estimado da área do círculo o correspondente à média de N repetições com o tamanho n da amostra usada Surgem assim duas questões i Qual o tamanho n da amostra a usar ii Quantas repetições serão necessárias O tamanho de n e N depende da natureza do experimento Em geral quanto maiores melhores mas estão associados à confiabilidade e precisão desejadas É claro por outro lado que estes parâmetros dependem dos custos associados De forma geral entretanto podese dizer que esses tamanhos são adequados se produzem um desvio padrão relativamente pequeno Se considerarmos como e a média da área do círculo e o desvio padrão respectivamente para N repetições de amostras de tamanho n um intervalo de de confiança para a área é 𝐴 𝑠 𝑁 𝑡𝛼 2 𝑁 1 𝐴 𝐴 𝑠 𝑁 𝑡𝛼 2 𝑁 1 onde corresponde à uma t de Student com N1 graus de liberdade e nível de confiança Sistemas de Filas Exemplo 26 Considere um jogo com dois jogadores A e B no que uma moeda é lançada Se resultar cara A recebe R 1000 de B Caso resultar coroa B recebe R 1000 e A i Simular o jogo como experimento de Monte Carlo ii Realizar o experimento com 5 repetições de 10 lançamentos Usar as primeiras cinco colunas da tabela com a lista de números aleatórios fornecida anteriormente considerando cada coluna uma repetição iii Estabeleça um intervalo de 95 de confiança para o número de vitórias de A sobre B iv Compare o intervalo de confiança em iii com o número esperado de vitórias de A Solução Vitória Vitória Vitória Vitória Vitória A B A B B B B A A B A A B B A B B B B B B A A B B A B A A A A A B B A A B B A B B B A B A B A A A B Xnúmero de vitórias de A sobre B 2 4 2 0 0 Na tabela ao lado gerado um número aleatório considerase que a vitória é de A se for menor o igual a 05 caso contrário considerase vitória de B Assim 𝑁51𝛼095𝑡𝛼2 𝑁 1𝑡 0025 42775 𝑥𝑡 𝛼 2 𝑁 1𝜇 𝑥𝑡 𝛼 2 𝑁 1 4 398 𝜇 2798 Número esperado de vitórias de A sobre B Sistemas de Filas Tipos de Simulação Em geral a simulação se baseia na amostragem de Monte Carlo e se relaciona com o comportamento de sistemas reais como função do tempo Existem dois tipos de Simulação Contínua e Discreta Modelos Contínuos Tratam com sistemas cujo comportamento muda continuamente com o tempo ie o tempo é variável contínua Este tipo de modelos em geral representase por meio de sistemas de equações diferenciais em diferença relacionado as variáveis do sistema Modelos Discretos Tratam com sistemas cujo comportamento muda só em certos instantes ie o tempo é variável discreta Por exemplo no caso dos sistemas de filas onde o comportamento muda quando entra ou sai um cliente o resto do tempo o sistema não muda No caso dos Modelos discretos os instantes nos que ocorrem mudanças no sistema determinam os EVENTOS DO MODELO eg chegada e saída de clientes Desde que estes eventos ocorrem em tempos discretos temse o nome de SIMULAÇÃO DE EVENTOS DISCRETOS Aqui nos ocupamos deste tipo de Simulação Sistemas de Filas Elementos da Simulação de Eventos Discretos Em geral toda simulação de eventos discretos descreve de alguma forma um sistema de filas no que os clientes chegam esperam numa fila recebem o serviço e saem Os modelos de ventos discretos estão compostos por uma rede de filas relacionadas Assim os dados necessários para simular esses modelos estão relacionados com os tempos que correspondem às chegadas e às saídas dos clientes do sistema simulado pois nos outros instantes os sistema não sofre mudanças Exemplo 27 Uma empresa metalmecânica recebe dois tipos de encomendas regulares e urgentes Os trabalhos se processam em dois estágios consecutivos com amplo espaço de processamento Encomendas urgentes sempre têm prioridade sobre as regulares Identificar os eventos do sistema Solução O sistema consiste de duas filas uma após a outra correspondentes aos dois estágios em série A primeira vista podese pensar nos seguintes eventos REGULAR URGENTE chega saí chega saí C11 S11 C12 S12 C21 S21 C22 S22 Estagio 1 Estagio 2 Note entretanto que as saídas do estagio 1 coincidem com as entradas ao estagio 2 Portanto as chegadas ao estágio 2 podem ser eliminadas como eventos Assim os eventos se reduzem a chegadas à empresa e saídas de cada estágio Sistemas de Filas Definidos os eventos básicos do modelo de simulação a figura abaixo dá uma representação esquemática das ocorrências típicas dos eventos na escala do tempo simulado tempo Evento 1 Evento 2 Evento 3 Evento 4 Depois que as ações associadas à ocorrência dum evento se realizam a simulação avança pulando ao seguinte evento cronológico Note que a execução da simulação ocorre no instante no que ocorre o evento Como a simulação determina o tempo no que os eventos ocorrem Os eventos de chegada estão separados pelos tempos entre chegadas e os de saída pelos tempos de serviço Esses tempos podem ser determinísticos como as chegadas do metrô numa estação ou aleatórios como achegada de clientes a uma agência bancária Se o tempo for determinístico os momentos de ocorrência são facilmente calculados Já se for aleatório os momentos de ocorrência devem ser simulados usando um procedimento de amostragem com a correspondente distribuição de probabilidade Sistemas de Filas Amostragem usando distribuições de probabilidade A aleatoriedade em simulação surge quando o intervalo t entre eventos sucessivos é probabilístico Em continuação se discutem métodos para simular amostras aleatórias sucessivas usando uma distribuição de probabilidade ft Estes métodos se baseiam na geração de números aleatórios em 01 uniformemente distribuídos e independentes Método Inverso Suponha que se deseja obter uma amostra aleatória de uma variável aleatória x contínua ou discreta cuja função de densidade de probabilidade fx é conhecida O Método inverso determina primeiro uma expressão fechada da função de densidade acumulada onde para todo x Logo assumindo que R seja um número aleatório obtido da distribuição uniforme em 01 denotando por a inversa de F os passos do método são como segue Passo1 Gerar um número aleatório Passo2 Calcular Sistemas de Filas Graficamente terseia a seguinte figura 𝐹 𝑥 1 R 0 𝑥 1 𝐹 𝑥 R 0 𝑥 Caso contínuo Caso discreto Observação A validade do procedimento anterior está baseado no fato de que a variável está uniformemente distribuída no intervalo 01 ver Teorema 1631 TAHA Sistemas de Filas Exemplo 28Distribuição Exponencial O tempo t entre chegadas de clientes numa barbearia está dado por uma distribuição exponencial com média unidades de tempo ie 𝑓 𝑡𝜆𝑒 𝜆𝑡𝑡0 Determinar uma amostra aleatória t a partir de ft Solução 𝐹 𝑡 𝑡 𝑓 𝑡 𝑑𝑡 0 𝑡 𝜆𝑒 𝜆𝑡 𝑑𝑡1𝑒 𝜆𝑡𝑡0 Logo fazendo 𝑅𝐹 𝑡 1𝑒 𝜆𝑡 𝑡 1 𝜆ln 1 𝑅 Desde que e é aleatório podese substituir por Assim temse 𝑡 1 𝜆 ln 𝑅 Evento Evento tempo simulado Observação para simular o tempo t aleatório o valor deve ser gerado aleatoriamente Sistemas de Filas Exemplo 29 Para o caso do exemplo anterior onde o tempo t entre chegadas de clientes numa barbearia está dado por uma distribuição exponencial considere o tempo médio entre chegadas clienteshora Use os valores R 00589 06733 e 04799 para simular os valores dos próximos três clientes e esboce um desenho na escala do tempo simulado Solução Desde que temse que 𝑡11 4ln 005890708 0 𝑡 21 4 ln0673300989 𝑡 3 14 ln 04799 0 1815 𝑡 00 𝑡107080 0989 1815 𝑡 𝑡1 𝑡1𝑡 2 𝑡1𝑡 2𝑡3 Sistemas de Filas O Método Inverso podese aplicar quando Fx é analiticamente tratável mas uma grande quantidade de funções não é desse tipo Poisson Normal etc Os métodos a seguir tratam alguns desses casos Método de Convolução A ideia deste método é expressar a amostra desejada como a soma estatística de outras variáveis aleatórias fáceis de amostrar Casos típicos são os da distribuição de Erlang Gama e Poisson que podem ser expressas em função da exponencial Exemplo 30 Distribuição de Erlang A variável aleatória Erlangm ou Erlang de m estágios definese como a soma estatística convolução de m variáveis aleatórias exponenciais independentes e idênticas Assim 𝑦 𝑦1 𝑦2 𝑦𝑚 Erlangm Portanto desde que cada pode ser amostrada como então 𝑦 1 𝜆 ln 𝑅1 1 𝜆 ln 𝑅2 1 𝜆 ln 𝑅𝑚𝑦 1 𝜆 ln 𝑅1𝑅2𝑅𝑚 Amostragem para Erlang Sistemas de Filas Assim se m3 e clienteshora considerando R 00589 06733 e 04799 temse que o valor gerado é 𝑦 1 𝜆 ln 𝑅1𝑅2𝑅3 1 4ln 0019 0 991horas Exemplo 31 Distribuição de Poisson Sabese que a distribuição de tempos entre chegadas é exponencial se e somente se o número de chegadas por unidade de tempo é Poisson Usase esta relação para amostrar uma Poisson Seja uma Poisson com média de chegadas por unidade de tempo Então o tempo entre eventos é exponencial com média unidades de tempo Assim uma amostra Poisson de tamanho n ocorrerá durante t unidades de tempo quando Período até ocorrer o evento nt Período até ocorrer o evento n1 𝑡 1𝑡 2𝑡𝑛 𝑡𝑡 1𝑡2𝑡𝑛𝑡 𝑛1 𝑛0 0 𝑡𝑡1 𝑛0 onde é uma amostra da distribuição exponencial com média Sistemas de Filas Assim do caso da Erlang temse que 1 𝜆l n 𝑅1 𝑅𝑛 𝑡1𝑡2𝑡 𝑛 𝑡 1 𝜆l n 𝑅1 𝑅𝑛 𝑅𝑛1 𝑡 1𝑡 2 𝑡𝑛 𝑡𝑛1 𝑛0 0 𝑡 1 𝜆ln 𝑅1 𝑡 1 𝑛0 𝑅1 𝑅𝑛 𝑒 𝜆𝑡 𝑅1 𝑅𝑛 𝑅𝑛 1 𝑛0 1 𝑒 𝜆𝑡𝑅1 𝑛0 Para ilustrar suponha que clienteshora e que se deseja obter uma amostra para um período de t 05 horas Portanto e usando 0 0589𝑹𝟏 𝒆 𝝀𝒕01353𝟏 𝑛0 Note que alternativamente poderseia usar a primeira das relações apresentados 𝒕𝟏 1 𝜆l n 𝑅1 1 4l n 00589070805𝒕 𝟎 𝑛0 Sistemas de Filas Se considerarmos uma amostra Poisson para um período de duas horas dado clienteshora usando os números aleatórios da tabela fornecida no slide 81 temos 𝑡1 1 𝜆l n 𝑅1 02 l n 00589 60339830 𝑡1𝑡 2 1 𝜆l n 𝑅1𝑅202l n 0058906733 60387279 𝑡1𝑡 2𝑡3 1 𝜆l n 𝑅1𝑅2𝑅302l n 00589067330 47996047 5399 𝑡1𝑡 11 1 𝜆l n 𝑅1 𝑅1102l n 005890352960113 8611 𝑡1𝑡 12 1 𝜆l n 𝑅1 𝑅1202l n 0 05890 3646 601259685120 Portanto os eventos amostrados a o longo de 120 minutos são 𝑡 0𝟎 𝑡1𝑡 2𝟑𝟖 𝟕𝟐 3398 𝑡1𝑡 11𝟏𝟏𝟑𝟖𝟔 5 120 Sistemas de Filas Exemplo 32 Distribuição Normal O Teorema do Limite Central estabelece que a soma convolução de n variáveis aleatórias independentes igualmente distribuídas tende a ser normalmente distribuída na medida que n é suficientemente grande Usase esse resultado para gerar uma amostra de uma Normal com média e desvio padrão Seja 𝑥 𝑅1𝑅2𝑅𝑛 𝑛 𝑥𝑅1 𝑅2𝑅𝑛 𝑁 𝑛 2 𝑛 12 Distribuição uniforme em 01 𝑧 𝑥 𝑛 2 𝑛 12 𝑁 01 𝑦𝜎 𝑧 𝜇 𝑁𝜇𝜎 Assim usando 𝑦𝜎 𝑥 𝑛 2 𝑛 12 𝜇 𝑁 𝜇 𝜎 podese gerar uma amostra aleatória para uma Para simplificar por conveniência toma se Assim 𝒚 𝝈 𝒙𝟔𝝁 𝑵𝝁𝝈 12 n n N 2 112 n N média populacional dos R desvio padrão populacional dos R Sistemas de Filas A maneira de ilustração suponha que quer uma amostra para uma distribuição N1012 ie e Assim tomando a soma dos n12 primeiros números aleatórios das colunas 1 e 2 da tabela de números aleatórios fornecida temse x61094 Então 𝑦12 61094610102188 Observação Note que este tipo de amostragem é ineficiente pois precisa de 12 números aleatórios para gerar uma amostra de uma Alternativamente provase que 𝑥2ln 𝑅1cos2 𝜋 𝑅2 𝑁 01𝒚 𝝁𝝈 𝒙 𝑵 𝝁𝝈 ie também produz uma amostra para gerado só por pois números aleatórios Adicionalmente 𝑥2ln 𝑅1cos2 𝜋 𝑅2 𝑁 01𝒚 𝝁𝝈𝒙 𝑵 𝝁𝝈 ie com só dois números aleatórios produzemse duas amostras para Sistemas de Filas Método de AceitaçãoRejeição Este método está pensado para manipular funções de densidade de probabilidade complexas para as quais os métodos anteriores não se aplicam A ideia consiste em substituir a distribuição original fx por outra equivalente hx tratável analiticamente Assim amostras de hx podem ser usadas para gerar amostra de fx Dada a função de densidade de probabilidade fx definese uma função majorante gx para fx como uma função que domina fx em todo seu domínio ie 𝑓 𝑥 𝑔𝑥 𝑥 Logo em termos de gx definese uma função de densidade de probabilidade equivalente a fx hx como ℎ 𝑥 𝑔𝑥 𝑔 𝑥 𝑑𝑥 𝑥 𝑔 𝑥 ℎ 𝑥 𝑔 𝑥 𝑑𝑥 0 𝑥1 gera ponto aleatório em f Aceitar Sistemas de Filas Os passos do método de aceitaçãorejeição são PASS0 1 Obter uma amostra de hx usando um dos métodos anteriores PASSO 2 Obter um número aleatório PASSO 3 Se aceitar como amostra apropriada de fx Caso contrário descartar e voltar ao Passo1 𝐹ℎ𝑥 1 0 𝑥1 𝑅1 ℎ𝑥 0 𝑥1 𝑦 1 𝑓 𝑥 não gera ponto aleatório em f Não Aceitar 𝑥1𝑔𝑥1 Note que gerar um ponto aleatório para fx é associar um número aleatório ao gráfico desta função Assim a ideia é associar ao gráfico de hx para logo associálo por meio de gx ao gráfico de fx desde que sendo constante gerar um ponto aleatório no gráfico de h é equivalente a gerar um ponto aleatório no gráfico de g Assim estando g associada a f gerado um ponto aleatório em g permite decidir se se aceita ou não esse ponto como ponto aleatório de f Sistemas de Filas Exemplo 33 Aplicar o Método de AceitaçãoRejeição a 𝑓 𝑥 6 𝑥 1 𝑥 0 𝑥 1 0 𝑐 𝑐 Solução 𝑔𝑥 𝑓 𝑥 15 0 05 1 g Assim 𝐹 ℎ 𝑥 𝑥 ℎ 𝑦 𝑑𝑦𝑥 𝑅 𝐹ℎ 1𝑥 𝑥 Sistemas de Filas Aplicando agora o Método de AceitaçãoRejeição usando a primeira coluna da tabela de números aleatórios temse PASS0 1 então é uma amostra de hx PASSO 2 PASSO 3 Desde que rejeitase como amostra apropriada de fx Voltar ao Passo1 Repetindo os passos do algoritmo temse 4799 Passo 1 e Passo 2 então aceitase como amostra de Sistemas de Filas Geração de Números Aleatórios A geração de números aleatórios uniformemente distribuídos em 01 joga um papel central em Simulação Entretanto números aleatórios só podem ser gerados por meio de processos aleatórios experimentos físicos aparelhos mecânicos elétricos ou eletrônicos que resultam lentos e eventualmente caros Além disso sendo aleatórios não poderiam ser repetidos como parte de um processo de simulação verificação e validação de um modelo Assim o processo a ser apresentado que gera números não verdadeiramente aleatórios está baseado num procedimento aritmético no qual a priori os números gerados podem ser conhecidos Estes números se denominam NÚMEROS PSEUDOALEATÓRIOS Lembrar que dados os números inteiros onde com dizse que é o resíduo de dividir por Isso se denota por 𝑟 𝑎𝑚𝑜𝑑𝑚 𝑎 𝑚𝑞 𝑟 𝑚 0 𝑟 𝑚1 0 𝑟 𝑚 1 congruente Baseados na definição anterior formulase o Método de Congruência para geração de números aleatórios Sistemas de Filas Dados os parâmetros um número pseudoaleatório se gera como 𝑢𝑛 𝑏𝑢𝑛1𝑐 𝑚𝑜𝑑𝑚𝑛12 𝑅𝑛 𝑢𝑛 𝑚 𝑛1 2 é chamado de semente do gerador Exemplo 34 Considere Então 𝑢1 9 115 𝑚𝑜𝑑128 𝑅1 8 120 6666 𝑢2 9 85 𝑚𝑜𝑑 125 𝑅2 5 12 0 4167 𝑢3 9 55 𝑚𝑜𝑑122 𝑅3 2 120 1666 Observação A escolha os parâmetros é fundamental para a boa qualidade do método assim como para o comprimento do ciclo Implementações pouco cuidadosas produzem resultados errados Sistemas de Filas A Mecânica da Simulação Discreta Todos os modelos de simulação discreta podem ser aproximados por sistemas de filas com dois eventos básicos chegadas e saídas que definem os momentos de mudanças nas estatísticas do sistema Exemplo 35 O tempo entre chegadas num cabeleireiro é exponencial com média de 10 minutos A loja é atendida por um único cabeleireiro que executa dois tipos de corte maquina zero que toma uma média de 10 minutos e corte com tesoura que toma 15 minutos em média Sabese que um de cada quatro clientes em média solicita máquina zero mas o processo é aleatório Simular o seguinte i A média de ocupação do cabeleireiro ii O número médio de clientes na espera iii O tempo médio de espera na fila Solução O mecanismo de funcionamento do sistema pode ser descrito em termos de chegadas e saídas Evento de chegada 1 Gerar e armazenar cronologicamente o tempo de ocorrência da próxima chegada 2 Se a instalação estiver ociosa a Começar o serviço declarar a instalação ocupada e atualizar as estatísticas de utilização b Gerar e armazenar cronologicamente o tempo de saída do cliente 3 Se a instalação estiver ocupada colocar o cliente na fila e atualizar as estatísticas da fila Sistemas de Filas Evento de saída 1 Se a fila estiver vazia declarar a instalação ociosa e atualizar as estatísticas de utilização 2 Se a fila não estiver vazia a selecionar um cliente da fila FIFO e colocálo no serviço Atualizar as estíticas da fila e de utilização do serviço b Gerar e armazenar cronologicamente o tempo de saída do cliente Dos dados do problema o tempo entre chegadas é exponencial com média de 10 minutos e o tempo de serviço é discreto 10 minutos com probabilidade 025 e 15 minutos com probabilidade 075 Denotando por p e q respectivamente as amostras aleatórias para o tempo entre chegadas e o tempo de serviço temse 𝑝10ln 𝑅 𝑞 10 0 𝑅 025 15 025𝑅 1 Usamse aqui os números aleatórios fornecidos anteriormente começando pela primeira coluna O tempo horário simulado se denota por T e se assume que o primeiro cliente chega no tempo com a instalação vazia Sistemas de Filas Tempo Cliente 1 O cliente 2 chegará quando onde minutos Desde que em o serviço está vazio declarase o serviço ocupado o cliente 1 inicia o serviço imediatamente sendo seu tempo de serviço simulado por ie minutos Assim o cliente 1 sairá no instante 𝑝1 𝑞1 Tempo Cliente 1 Fila vazia declarar o serviço ocioso registrar que esteve ocupada entre 1 2 1 𝑇 0 𝑇15𝑇28 3 1 2 1 𝑇 0 𝑇15𝑇28 3 Tempo Cliente 2 O cliente 3 chegará quando onde Sistemas de Filas minutos Desde que em o serviço está vazio declarase o serviço ocupado o cliente 2 inicia o serviço imediatamente sendo seu tempo de serviço simulado por ie minutos Assim o cliente 2 sairá no instante 1 2 1 𝑇 0 𝑇15𝑇28 3𝑇35 64𝑇433 𝑞2 𝑝2 3 2 4 𝑇4574 4 3 1 2 1 𝑇 0 𝑇15𝑇28 3𝑇35 64 𝑇433 𝑝3 3 2 𝑇4052 4 𝑝4 5 3 4 𝑞3 𝑇583𝑇6299 5 𝑝5 3 6 Os cálculos anteriores mostram todas as possibilidades de simulação do modelo formulado Portanto a partir deste ponto se passa a os cálculos mostrando as estatísticas do modelo Sistemas de Filas Suponha que a simulação se executou por 50 minutos As figuras a seguir mostram as mudanças no comprimento da fila e a utilização das instalações como função do tempo simulado T 1 2 0 5000 T 𝐴1𝐴2𝐴3𝐴4 3564 4052 4330 4574 278 24 4 426 488 Comprimento da fila 𝐴1488 𝐴25 56 𝐴3244 𝐴48 52 𝐴𝑇2140 1 0 5000 T 𝐴115 2170 1000 1500 2830 4000 Utilização das instalações 𝐴𝑇3670 Tanto o Comprimento da Fila como a Utilização das Instalações se denominam VARIÁVEIS BASEADAS NO TEMPO devido a sua variação em função do tempo Seus valores médios se calculam como 𝑀 é 𝑑𝑖𝑎𝑑𝑎𝑣𝑎𝑟𝑖á𝑣𝑒𝑙 𝑏𝑎𝑠𝑒𝑎𝑑𝑎𝑛𝑜𝑡𝑒𝑚𝑝𝑜 Á𝑟𝑒𝑎𝑠𝑜𝑏𝑎𝑐𝑢𝑟𝑣𝑎 𝑃𝑒𝑟 í 𝑜𝑑𝑜𝑑𝑒 𝑠𝑖𝑚𝑢𝑙𝑎çã𝑜 Sistemas de Filas Assim para o caso deste exemplo temse 𝐶𝑜𝑚𝑝𝑟𝑖𝑚𝑒𝑛𝑡𝑜𝑚é 𝑑𝑖𝑜 𝑑𝑎𝐹𝑖𝑙𝑎 21 4 50 0428𝑐𝑙𝑖𝑒𝑛𝑡𝑒𝑠 𝑈𝑡𝑖𝑙𝑖𝑧𝑎çã 𝑜𝑚 é 𝑑𝑖𝑎 𝑑𝑎𝑠 𝐼𝑛𝑠𝑡𝑎𝑙𝑎 çõ𝑒𝑠 36 7 50 0 734 𝑐𝑎𝑏𝑒𝑙𝑒𝑟𝑒𝑖𝑟𝑜𝑠 O Tempo de Espera na Fila se denomina VARIÁVEL BASEADA EM OBSERVAÇÃO e sua média se calcula como 𝑀 é 𝑑𝑖𝑎𝑑𝑎𝑣𝑎𝑟𝑖á 𝑣𝑒𝑙 𝑏𝑎𝑠𝑒𝑎𝑑𝑎𝑒𝑚𝑜𝑏𝑠𝑒𝑟𝑣𝑎çã 𝑜 𝑆𝑜𝑚𝑎 𝑑𝑒𝑜𝑏𝑠𝑒𝑟𝑣𝑎çõ𝑒𝑠 𝑁 ú𝑚𝑒𝑟𝑜𝑑𝑒𝑜𝑏𝑠𝑒𝑟𝑣𝑎çõ 𝑒𝑠 Para o caso deste exemplo note que a área sob a curva Comprimento da Fila corresponde à soma dos tempos de espera dos três clientes que entraram nas filas Portanto para os clientes que efetivamente esperaram o Tempo Média de Espera na Fila foi de 2143 713 minutos Note que para obter o Tempo Médio de Espera na Fila de Todos os Clientes deverá calcular se como 2145428 minutos