Introdução à Teoria das Filas

Curso Engenharia da Produção Disciplina Modelagem e Simulação Período Semestre 20232 Data 05 10 2023 2 Introdução à Teoria das Filas Teoria das Filas Conceitos Básicos Elementos de uma fila População é de onde surgem os clientes transação ou entidade Fila é onde os clientes aguardam para serem atendidos para algum serviço Atendimento constituem um ou mais servidores atendentes ou canais de serviços Características de uma fila 1 Clientes e tamanho da população Cliente é proveniente de uma população Se a população é muito grande a chegada de um novo cliente não afeta a taxa de chegada de clientes ou seja as chegadas são independentes Ex Pessoas chegando no Metrô Se a população é pequena a chegada de um novo cliente pode afetar a taxa de chegada de clientes Exemplo alunos chegando na sala de aula 2 Processo de chegada Quando clientes chegam ao sistema e aguardam numa fila podemos quantificar o processo de chegada tomando uma taxa média de chegada ou intervalo médio entre chegada Exemplo Num posto de pedágio o processo de chegada de automóveis entre 7 e 8 horas da manhã é em média de 20 automóveis por minuto ou o equivalente de 1 automóvel a cada 3 segundos Estes valores são medias e para caracterizar corretamente o processo de chegada devemos trabalhar com distribuição de freqüências ex Distribuição normal distribuição de Poisson distribuição exponencial etc Em resumo o ritmo das chegadas dos clientes é uma variável aleatória ou randômica Variáveis randômicas do processo de chegada λ ritmo médio de chegada IC Intervalo Médio entre chegadas 3 Processo de Atendimento O processo de atendimento analisa o tempo de atendimento pelos servidores e é quantificado por uma variável randômica Exemplo no exemplo do pedágio anterior podemos supor que atende 6 automóveis por minuto ou leva 10 segundos para atender cada automóvel Prof Oscar K Uehara oscarueharaunisantannabr 1 Curso Engenharia da Produção Disciplina Modelagem e Simulação Período Semestre 20232 Data 05 10 2023 2 Introdução à Teoria das Filas Variáveis randômicas do processo de atendimento μ ritmo médio de atendimento TA Tempo Médio de Atendimento 4 Número de Servidores O sistema mais simples de fila é constituído de um único servidor atendendo um único cliente por vez Podemos aumentar o número de servidores 5 Disciplina da Fila Define uma regra de como será atendido os clientes O mais comum é do tipo FIFO First In First Out Outras regras LIFO Last In First Out por prioridade etc 6 Tamanho médio da Fila É uma característica muito importante para caracterizar o desempenho do sistema Quando maior for o tamanho da fila maior deverá ser o tempo de espera 7 Tamanho máximo da Fila Normalmente os sistemas são dimensionados para uma certa quantidade máxima de clientes em espera Por exemplo o número de cadeiras de uma sala de aula 8 Tempo médio de Espera na Fila O ideal é que não exista tempo de espera mas nem sempre é a melhor situação do ponto de vista econômico O tempo médio de espera depende dos processos de chegada e de atendimento Variáveis Randômicas As variáveis randômicas são caracterizadas por um valor médio e uma distribuição de probabilidade que mostra as chances de ocorrências dos valores Quando afirmamos que a duração média de atendimento é de 10 segundos não quer dizer que todo atendimento será de 10 segundos A distribuição de probabilidades de uma variável randômica como duração de atendimento vai determinar qual a probabilidade de uma certa duração acontecer Por exemplo dado o gráfico de uma distribuição de probabilidade de duração de atendimento de um determinado processo temos a probabilidade de um cliente ser atendido em menos de 5 segundos é zero a probabilidade de atender um cliente em 10 segundos é de 18 a probabilidade de atender um cliente em 25 segundos é de 05 Prof Oscar K Uehara oscarueharaunisantannabr 2 Curso Engenharia da Produção Disciplina Modelagem e Simulação Período Semestre 20232 Data 05 10 2023 2 Introdução à Teoria das Filas Variáveis Randômicas Fundamentais Considere um sistema de filas como da figura abaixo em situação estável onde os clientes chegam e entram numa fila podendo existir mais de um servidor para atendimento Considere também λ ritmo médio de chegada μ ritmo médio de atendimento c capacidade de atendimento ou quantidade de atendentes Consideramos um sistema estável quando λ é menor que μ em todas as estações de trabalho ou seja o ritmo médio de chegada é menor que o ritmo médio de atendimento As variáveis randômicas fundamentais mais utilizadas são Variáveis referentes ao sistema TS tempo médio de permanência no sistema NS número médio de clientes no sistema Variáveis referentes ao processo de chegada λ ritmo médio de chegada IC intervalo médio entre chegadas Relação entre IC e λ IC 1 λ Variáveis referentes à fila TF tempo médio de permanência na fila NF número médio de clientes na fila Variáveis referentes ao processo de atendimento TA tempo médio de atendimento ou de Serviço c capacidade de atendimento ou quantidade de atendentes NA número médio de clientes que estão sendo atendidos μ ritmo médio de atendimento de cada atendente Relação entre TA e μ TA 1 μ Relações Fundamentais NS NF NA TS TF TA NA λ μ TA IC NS NF NA NF λ μ NF TA IC Prof Oscar K Uehara oscarueharaunisantannabr 3 Curso Engenharia da Produção Disciplina Modelagem e Simulação Período Semestre 20232 Data 05 10 2023 2 Introdução à Teoria das Filas Taxa de utilização dos atendentes É representada pela letra grega ρ e representa a fração média do tempo em que cada servidor está ocupado Para o caso de uma filaum atendente a taxa de utilização do atendente é dada pela expressão ρ λ μ Para o caso de uma fila vários atendentes temos ρ λ c μ onde c é o número de atendentes ou servidores Exemplo Num sistema de uma filaum atendente se chegam 4 clientes por hora e se o atendente tem capacidade para atender 10 clientes por hora dizemos que a taxa de utilização é 040 ou seja 40 do tempo o atendente está ocupado e 60 do tempo está livre Obs Em sistema estáveis teremos sempre que ρ 1 ou seja λ c μ os atendentes sempre serão capazes de atender ao fluxo de chegada Fórmula de Little JDC Little demonstrou que para um sistema estável de fila temos NF λ TF NS λ TS Resumo das Fórmulas Nome Fórmula Intervalo entre chegadas IC 1 λ Tempo de Atendimento TA 1 μ Taxa de Utilização dos atendentes ρ λ c μ Relações entre Fila Sistema e Atendimento NS NF NA NA λ μ NS NF λ μ NF TA IC TS TF TA NA ρ λ c μ Fórmula de Little NF λ TF NS λ TS Prof Oscar K Uehara oscarueharaunisantannabr 4 Curso Engenharia da Produção Disciplina Modelagem e Simulação Período Semestre 20232 Data 05 10 2023 2 Introdução à Teoria das Filas Postulados Básicos Os postulados descritos na figura abaixo se aplicam a quaisquer sistemas de filas estáveis Exercícios 1 Dado uma fábrica com os seguintes parâmetros λ 20 clienteshora μ 25 clienteshora e TS 03 hora Qual o tamanho médio da fila Para o mesmo sistema acima calcular NS e NA 2 Em uma pizzaria que faz entregas em casa chegam em média 4 entregadores por minuto para pegar o produto a ser entregue Sabese ainda que o número médio de entregadores dentro da pizzaria é de 6 Qual o tempo médio no sistema 3 Suponha um sistema de atendimento a clientes de uma empresa onde os clientes chegam a uma taxa média de 10 clienteshora O atendimento é feito por um único atendente que gasta em média 10 minutos para solucionar ou encaminhar soluções aos clientes Podemos concluir com base nas informações acima que o sistema não atende adequadamente os clientes porque a o sistema é estável mas há formação de filas b o sistema é instável porque μ λ c o sistema é instável porque a taxa de utilização ρ é maior que 1 d o sistema é instável porque o Número Médio de clientes no sistema é constante e o sistema é estável mas é limitado pelo número máximo de clientes Prof Oscar K Uehara oscarueharaunisantannabr 5 Curso Engenharia da Produção Disciplina Modelagem e Simulação Período Semestre 20232 Data 05 10 2023 2 Introdução à Teoria das Filas Notação para descrição de Tipos de Filas A notação de processos de filas mais utilizada atualmente foi proposta por Kendall em 1953 e é descrita por uma série de símbolos tais como ABmkM onde A indica a distribuição do intervalo entre chegadas dos clientes B o padrão de serviço de acordo com uma distribuição de probabilidade para o tempo de serviço m o número de canais de serviços paralelos servidores k a capacidade do sistema número máximo de clientes no sistema e M a disciplina de filas Em muitas situações só os três primeiros símbolos são utilizados de maneira que é assumido que o sistema tem capacidade ilimitada população infinita e possui fila cuja disciplina é do tipo FIFO First In First Out O Modelo MM1 Neste modelo temos que o tanto as chegadas e atendimento seguem a Distribuição de Poisson ou Exponencial Negativa e que temos apenas um servidor ou atendente Segue abaixo a representação do modelo MM1 Para este sistema são válidos λ ritmo médio de chegada IC intervalo médio entre chegadas IC 1 λ TA tempo médio de atendimento ou de serviço μ ritmo médio de atendimento de cada atendente TA 1 μ Considerase também que a População é Infinita Para ver como essas fórmulas são deduzidas consultem o livro do Prof Paulo José de Freitas Filho No final da apostila encontrarão a referência completa Prof Oscar K Uehara oscarueharaunisantannabr 6 Curso Engenharia da Produção Disciplina Modelagem e Simulação Período Semestre 20232 Data 05 10 2023 2 Introdução à Teoria das Filas Taxa de Utilização É a relação entre o ritmo médio de chegada e o ritmo médio de atendimento μ λ ρ Em sistemas estáveis λ é menor que μ ou ρ 1 Quando ρ tende para 1 a fila tende a aumentar infinitamente NF λ 2 ρ 2 μ μ λ 1 ρ Quando há crescimento do ritmo de chegada causada pelo aumento da demanda NF cresce exponencialmente e em consequência o tempo na Fila TF e o tempo no sistema TS também aumentará Exercícios 1 Suponhamos que as chegadas a uma cabine telefônica obedecem a lei de Poisson com ritmo de 6 chegadas por hora A duração média do telefonema é de 3 minutos e suponhamos que siga a distribuição exponencial Pedese a Qual a probabilidade de uma pessoa chegar à cabine e não ter que esperar b Qual o número médio de pessoas na fila c Qual o número médio de pessoas no sistema d Qual o número médio de clientes usando o telefone e Qual o tempo na fila f Para qual ritmo de chegada teríamos a situação em que o tempo médio de espera na fila seria de 3 minutos g Qual a fração do dia durante a qual o telefone está em uso 2 Uma fábrica possui um depósito de ferramentas onde os operários vão receber as ferramentas especiais para a realização de uma determinada tarefa Verificouse que o ritmo de chegada λ 1 chegadaminuto e o ritmo de atendimento μ 12 atendimento por minuto seguem o modelo marcovianio MM1 A fábrica paga 900 por hora ao atendente e 1800 ao operário Pedese a O custo horário do sistema b A fração do dia em que o atendente não trabalha O Modelo MMc Neste modelo temos que tanto o processo de chegada e atendimento são marcovianos além disso existe uma única fila e tem mais de um servidor A capacidade de atendimento de cada servidor será considerada a mesma μ A figura ao lado representa o diagrama de um modelo de Fila MMc Para este sistema são válidos λ ritmo médio de chegada IC intervalo médio entre chegadas IC 1 λ TA tempo médio de atendimento ou de serviço em cada servidor μ ritmo médio de atendimento de cada servidor TA 1 μ c capacidade de atendimento ou quantidade de servidores Prof Oscar K Uehara oscarueharaunisantannabr 7 Curso Engenharia da Produção Disciplina Modelagem e Simulação Período Semestre 20232 Data 05 10 2023 2 Introdução à Teoria das Filas População Infinita As fórmulas matemáticas utilizadas para o modelo MMc são muito complexas e preferencialmente utilizamos gráficos Em FREITAS FILHO 2008 poderão encontrar as fórmulas em que os gráficos se baseiam O gráfico 1 é utilizado para obter o número médio de clientes na Fila NF em função do fator de utilização e tendo como parâmetro a quantidade de servidores A taxa de utilização é dada por ρ λ c μ O gráfico 2 é utilizado para obter o número médio de clientes no sistema NS Tanto no gráfico 1 e 2 a ordenada tem escala logarítmica e tende para o infinito quando ρ tende para 1 Observações Se dobrarmos a capacidade de atendimento a taxa de utilização ρ cai pela metade Para a mesma taxa de utilização ρ quando aumentamos a quantidade de servidores o tamanho da fila diminui e aumenta a quantidade de clientes no sistema A partir das variáveis NF e NS determinadas pelos gráficos podemos calcular TF e NS pela fórmula de Little TF NF λ TS NS λ Exercícios 1 Fila única x Diversas Filas Um banco deseja modificar a forma de atendimento a seus clientes que hoje funciona com diversas filas pela introdução do sistema de fila única Os dados de hoje são λ 70 clientes por hora que se distribuem em 5 filas c 5 atendentes μ 20 clientes por hora TA 3 minutos 2 Chegada superior a atendimento Uma agência bancária possui 5 atendentes e funciona diariamente das 1000h às 1600h O ritmo de chegada é de 110 clientes por hora e a duração média de cada atendente é de 3 minutos ou μ 20 atendimentoshora Perguntase a O tamanho médio da fila b O tempo médio de espera na fila Referências Bibliográficas PRADO Darcy Teoria das Filas e da Simulação Belo Horizonte INDG 2004 FREITAS FILHO Paulo José de Introdução à Modelagem e Simulação de Sistemas com aplicações em ARENA 2º ed Florianópolis Visual Books 2008 Prof Oscar K Uehara oscarueharaunisantannabr 8 Curso Engenharia da Produção Disciplina Modelagem e Simulação Período Semestre 20232 Data 05 10 2023 2 Introdução à Teoria das Filas Gráfico 1 Gráfico 2 Prof Oscar K Uehara oscarueharaunisantannabr 9