Teoria das Filas - Modelos MMc MM1N e MMcN - Análise e Distribuições

Teoria de Filas Modelos MMc MM1N e MMcN Distribuição de Probabilidade dos Tempos Ormeu Coelho da Silva Júnior DSc Departamento de Engenharia de Produção Revisão Breno dos Santos de Assis 062024 MODELO M M c GD Este modelo considera 𝑐 servidores paralelos idênticos que operam com a mesma taxa de serviço 𝜇 A taxa de chegada ao sistema é 𝜆 e a taxa efetiva é 𝜆𝑒 𝜆 porque não há limite ao número de usuários no sistema O efeito do uso de servidores paralelos idênticos é um aumento proporcional na taxa de serviço da instalação Em termos do modelo generalizado de Poisson têmse 𝜆𝑛 𝜆 𝑛 0 21 𝜇𝑛 ቊ𝑛𝜇 𝑛 𝑐 𝑐𝜇 𝑛 𝑐 22 Assim sendo a probabilidade de haver 𝑛 usuários no sistema é calculada pelo par de expressões em 23 MODELO M M c GD 𝑃𝑛 𝜆𝑛 𝜇 2𝜇 3𝜇 𝑛𝜇 𝑃0 𝜆𝑛 𝑛 𝜇𝑛 𝑃0 𝑛 𝑐 𝜆𝑛 𝜇 2𝜇 3𝜇 𝑐𝜇𝑐𝜇𝑛𝑐 𝑃0 𝜆𝑛 𝑐 𝑐𝑛𝑐𝜇𝑛 𝑃0 𝑛 𝑐 23 Para calcular a probabilidade de que o sistema esteja vazio quando em regime estacionário assumese que a razão da taxa média de chegadas pela taxa média de atendimento do sistema é menor que 1 Ou seja 𝜌 Τ 𝜆 𝑐𝜇 1 Substituindose as expressões em 23 em σ𝑛0 𝑃𝑛 1 obtémse após as simplificações necessárias 𝑃0 𝑖0 𝑐1 𝜆𝑖 𝑖 𝜇𝑖 𝜆𝑐 𝑐 𝜇𝑐 1 1 𝜌 1 24 MODELO M M c GD O tamanho médio da fila pode então ser calculado como 𝐿𝑞 𝑛𝑐 𝑛 𝑐 𝑃𝑛 𝑛0 𝑛𝑃𝑛𝑐 𝑛0 𝑛 𝜆𝑛𝑐 𝑐 𝑐𝑛𝜇𝑛𝑐 𝑃0 𝜆𝑐1 𝑐 𝑐 𝜇𝑐1 𝑃0 𝑛0 𝑛 𝜆 𝑐𝜇 𝑛1 𝜆𝑐1 𝑐 𝑐 𝜇𝑐1 𝑃0 𝑛0 𝑛𝜌𝑛1 𝜆𝑐1 𝑐 𝑐 𝜇𝑐1 𝑃0 𝑛0 𝑛𝜌𝑛1 𝜆𝑐1 𝑐 𝑐 𝜇𝑐1 𝑃0 𝑑 𝑑𝜌 𝑛0 𝜌𝑛 𝜆𝑐1 𝑐 𝑐 𝜇𝑐1 𝑃0 𝑑 𝑑𝜌 1 1 𝜌 Após simplificações 𝐿𝑞 𝜌 λμ 𝑐 𝑐 1 𝜌2 𝑃0 25 MODELO M M c GD Dado que 𝜆 𝜆 pois não há desistência por parte dos clientes o número médio de usuários no sistema é 𝐿 𝜆 𝑊𝑞 𝜆 𝜇 𝐿𝑞 𝜆 𝜇 26 Assim como no modelo MM1 as medidas de desempenho 𝑊𝑞 e 𝑊 também podem ser obtidas a partir 𝐿𝑞 e 𝐿 pela fórmula de Little Exercício 3 Uma comunidade é atendida por duas empresas de táxi Cada empresa possui dois táxis e dividem o mercado igualmente com chamadas chegando ao escritório de despacho de cada empresa a uma taxa média de oito por hora O tempo médio por viagem é de 12 minutos As chamadas chegam de acordo com uma distribuição de Poisson e o tempo de viagem segue uma distribuição exponencial As duas empresas foram compradas por um investidor e serão consolidadas em uma única central de despacho Analise o desempenho da nova empresa que será formada MODELO M M c GD central de despacho Analise o desempenho da nova empresa que será formada Resolução Um bom parâmetro de desempenho da qualidade dos serviços prestados é o tempo médio de espera em fila A avaliação da operação em separado consiste na modelagem das ambas empresas como um sistema MM2 no qual 𝜆 8 chamadoshora e 𝜇 5 chamadoshora Logo 𝜌 𝜆 𝑐𝜇 8 2 5 08 𝑃0 𝑛0 𝑐1 𝜆𝑛 𝑛 𝜇𝑛 𝜆𝑐 𝑐 𝜇𝑐 1 1 𝜌 1 80 0 50 81 1 51 82 2 52 1 1 08 1 1 9 𝐿𝑞 𝜆 𝜇 𝑐 𝜌 𝑐 1 𝜌2 𝑃0 8 5 2 08 2 1 082 1 9 284 MODELO M M c GD 𝑊𝑞 𝐿𝑞 𝜆 284 8 0355 h 213 min Agora é preciso analisar a nova configuração ou seja operando como um sistema MM4 com 𝜆 16 chamadoshora e 𝜇 5 chamadoshora Note que 𝜌 não muda 𝑃0 160 0 50 161 1 51 162 2 52 163 3 53 164 4 54 1 1 08 1 00273 𝐿𝑞 16 5 4 08 4 1 082 00273 239 𝑊𝑞 239 16 0149 h 896 min MODELO M M c GD Portanto a fusão das duas empresas torna mais eficiente o sistema de atendimento resultante Este exercício ilustra um resultado importante a operação de serviços em um pool é sempre mais eficiente do que as operações em separado MODELO M M 1 GD N Este modelo por vezes chamado apenas de MM1N considera a existência de um limite para o número de usuários dentro do sistema O efeito desta premissa é que uma vez atingido este limite novos clientes são impedidos de entrar o que afeta a taxa efetiva de chegada Aplicandose o modelo generalizado de Poisson têmse 𝜆𝑛 ቊ𝜆 𝑛 𝑁 0 𝑛 𝑁 27 𝜇𝑛 𝜇 28 A probabilidade de haver 𝑛 usuários no sistema fica então calculada como 𝑃𝑛 ቊ𝜌𝑛𝑃0 𝑛 𝑁 0 𝑛 𝑁 29 MODELO M M 1 GD N Portanto a probabilidade de o sistema estar vazio é calculada como 1 𝜌 𝜌2 𝜌𝑁 𝑃0 1 30 A soma dos termos da progressão geométrica no lado esquerdo de 30 para 𝜌 1 é 1 𝜌 𝜌2 𝜌𝑁 1 𝜌𝑁1 1 𝜌 Chegase então a 𝑃0 1 𝜌 1 𝜌𝑁1 𝜌 1 1 𝑁 1 𝜌 1 31 MODELO M M 1 GD N Por conseguinte 𝑃𝑛 1 𝜌𝜌𝑛 1 𝜌𝑁1 𝜌 1 1 𝑁 1 𝜌 1 32 Devido ao limite de capacidade para o número de usuários no sistema a taxa efetiva de chegada é 𝜆 𝜆 𝜆𝑃𝑛 𝜆 1 𝑃𝑛 33 Com isso o número médio de usuários no sistema pode ser calculado como MODELO M M 1 GD N 𝐿 𝑛0 𝑁 𝑛𝑃𝑛 𝑛0 𝑁 𝑛 𝜌𝑛𝑃0 1 𝜌 1 𝜌𝑁1 𝑛0 𝑁 𝑛 𝜌𝑛 1 𝜌 1 𝜌𝑁1 𝜌 𝑑 𝑑𝜌 𝑛0 𝑁 𝜌𝑛 1 𝜌 1 𝜌𝑁1 𝜌 𝑑 𝑑𝜌 1 𝜌𝑁1 1 𝜌 1 𝜌𝜌 1 𝜌𝑁1 𝑁 1 𝜌𝑁 1 𝜌 1 𝜌𝑁1 1 1 𝜌2 Após as simplificações 𝐿 𝜌 1 𝑁 1 𝜌𝑁 𝑁𝜌𝑁1 1 𝜌1 𝜌𝑁1 𝜌 1 33 MODELO M M 1 GD N Note que ao derivar as equações de estado estacionário não foi necessário assumir que 𝜌 1 pois a existência de uma capacidade máxima impede a entrada de novos usuários evitando assim que a fila cresça indefinidamente Logo neste modelo é considerase que 𝜌 1 Como exercício verifique que se 𝜌 1 então o número médio de usuários no sistema será 𝐿 Τ 𝑁 2 Observe ainda que quando 𝑁 a expressão para 𝐿 em 33 converge para o valor que calcula este mesmo parâmetro no modelo MM1 Ou seja 𝐿 𝜌 1𝜌 se 𝑁 Como no modelo MM1 o número médio de usuários em fila pode ser obtido pela expressão 17 E as medidas de desempenho relativas aos tempos médios 𝑊𝑞 e 𝑊 através da fórmula de Little devese lembrar porém que neste modelo 𝜆 𝜆 acabamento da limpeza de um carro segue uma distribuição exponencial com média 𝜇 75 min Há um espaço para até três carros aguardarem por atendimento dentro do esedo est MODELO M M 1 GD N Exercício 4 A taxa de chegada de clientes ao lavajato BrilhoRápido segue uma distribuição de Poisson com média 𝜆 7 carroshora O tempo para lavagem e acabamento da limpeza de um carro segue uma distribuição exponencial com média 𝜇 75 min Há um espaço para até três carros aguardarem por atendimento dentro do estabelecimento Se um novo cliente chega quando já há três clientes aguardando ele é obrigado a ir embora uma vez que a rua de acesso não permite estacionamento Perguntase a Quantos clientes o lavajato deixa de atender em um dia devido às restrições de espaço Considere que o estabelecimento opera dez horas por dia b Qual o tamanho médio da fila de espera c Qual o tempo médio de espera MODELO M M 1 GD N Resolução Inicialmente observe que 𝜌 Τ 𝜆 𝜇 Τ 7 8 0875 e 𝑁 4 a Para responder esta pergunta deve calcular a probabilidade de haver exatamente quatro carros dentro do lavajato ou seja 𝑃 𝑛 4 𝑃𝑛4 1 𝜌𝜌𝑛 1 𝜌𝑁1 1 0875 08754 1 08755 1504 Esse resultado mostra que aproximadamente um a cada sete clientes que procuram o serviço deixam de ser atendidos por conta da limitação de espaço Essa é uma informação importante que pode ser usada por exemplo para analisar a viabilidade econômica de se aumentar o espaço de espera ou mesmo de mudar o local da operação MODELO M M 1 GD N b O número médio de usuários em espera pode ser obtido como 𝐿𝑞 𝐿 𝜌 𝐿 𝜌 1 𝑁 1 𝜌𝑁 𝑁𝜌𝑁1 1 𝜌1 𝜌𝑁1 0875 1 5 08754 4 08755 1 08751 08755 2 Logo 𝐿𝑞 𝐿 𝜌 2 0875 1125 clientes em espera c O tempo médio de espera pode então ser obtido pela fórmula de Little 𝑊𝑞 𝐿𝑞 𝜆 1125 7 60 964 min MODELO M M c GD N Neste modelo de múltiplos servidores por vezes chamado apenas de MMcN assume se implicitamente que 𝑐 𝑁 Logo o número máximo de usuários em fila é 𝑁 𝑐 Logo partir do modelo generalizado de Poisson se chega às seguintes expressões 𝜆𝑛 ቊ𝜆 𝑛 𝑁 0 𝑛 𝑁 32 𝜇𝑛 ቊ𝑛𝜇 𝑛 𝑐 𝑐𝜇 𝑐 𝑛 𝑁 33 A partir das taxas de chegada e atendimento definidas em 32 e 33 chegase a 𝑃𝑛 𝜆 𝜇 𝑛 𝑛 𝑃0 𝑛 𝑐 𝜆 𝜇 𝑛 𝑐 𝑐𝑛𝑐 𝑃0 𝑛 𝑐 34 MODELO M M c GD N Dado que σ𝑛0 𝑁 𝑃𝑛 1 a probabilidade de o sistema estar vazio é calculada como 𝑃0 𝑛0 𝑐1 𝜆 𝜇 𝑛 𝑛 𝜆 𝜇 𝑐 1 𝜌𝑁𝑐1 𝑐 1 𝜌 1 𝜌 1 𝑛0 𝑐1 𝜆 𝜇 𝑛 𝑛 𝜆 𝜇 𝑐 𝑁 𝑐 1 𝑐 1 𝜌 1 35 A partir destas expressões o número médio de usuários em espera quando 𝜌 1 é 𝐿𝑞 𝑛𝑐 𝑁 𝑛 𝑐𝑃𝑛 𝑛0 𝑁𝑐 𝑛𝑃𝑛𝑐 𝑛0 𝑁𝑐 𝑛 𝜆 𝜇 𝑛𝑐 𝑐 𝑐𝑛 𝑃0 MODELO M M c GD N 𝜆 𝜇 𝑐1 𝑐 𝑐 𝑃0 𝑛0 𝑁𝑐 𝑛 𝜆 𝜇 𝑛1 𝑐𝑛1 𝜆 𝜇 𝑐 𝑐 𝜌𝑃0 𝑛0 𝑁𝑐 𝑛𝜌𝑛1 𝜆 𝜇 𝑐 𝑐 𝜌𝑃0 𝑑 𝑑𝜌 𝑛0 𝑁𝑐 𝜌𝑛 𝜆 𝜇 𝑐 𝑐 𝜌𝑃0 𝑑 𝑑𝜌 𝜌𝑁𝑐1 1 𝜌 1 Desenvolvendo a derivada anterior obtémse 𝐿𝑞 𝜆 𝜇 𝑐 𝑐 𝜌 1 𝜌2 1 𝑁 𝑐 1 𝜌𝑁𝑐 𝑁 𝑐 𝜌𝑁𝑐1 𝑃0 36 MODELO M M c GD N Quando 𝜌 1 não é difícil verificar que o número médio de usuários em fila será 𝐿𝑞 𝜆 𝜇 𝑐 2𝑐 𝑁 𝑐 𝑁 𝑐 1 𝑃0 36 Já o número esperado de usuários no sistema é 𝐿 𝑛0 𝑐 𝑛𝑃𝑛 𝐿𝑞 36 E assim como no modelo MM1N para calcular as medidas de desempenho 𝑊𝑞 e 𝑊 basta dividir 𝐿𝑞 e 𝐿 respectivamente por 𝜆 MODELO M M c GD N Exercício 5 De volta ao enunciado do Exercício 1 veja agora como os mesmos resultados podem ser obtidos pelo modelo MMcN Antes de iniciar lembrese que 𝜆 24 chamadoshora 𝜇 6 chamadoshora 𝑐 6 e 𝑁 10 Resolução a Inicialmente calcule 𝜌 𝜆 𝑐𝜇 24 66 2 3 e 𝜆 𝜇 4 𝑃0 𝑛0 𝑐1 𝜆 𝜇 𝑛 𝑛 𝜆 𝜇 𝑐 1 𝜌𝑁𝑐1 𝑐 1 𝜌 1 4 0 0 4 1 1 4 2 2 4 5 5 46 1 2 3 5 6 1 2 3 1 00173 MODELO M M c GD N Resolução 𝐿𝑞 𝜆 𝜇 𝑐 𝑐 𝜌 1 𝜌2 1 𝑁 𝑐 1 𝜌𝑁𝑐 𝑁 𝑐 𝜌𝑁𝑐1 𝑃0 𝐿𝑞 4 6 6 2 3 1 2 3 2 1 5 2 3 4 4 2 3 5 00173 0319 chamados b ҧ𝑐 𝜌𝑐 4 atendentes c 𝑃𝑛10 𝜆 𝜇 𝑛 𝑐 𝑐𝑛𝑐 𝑃0 2 3 10 6 64 00173 00194 𝜆 𝜆 1 𝑃10 24 1 00194 23534 clientesh MODELO M M c GD N Resolução c 𝑊𝑞 𝐿𝑞 𝜆 0319 23534 4880 segundos d 𝑊 𝑊𝑞 1 𝜇 64880 segundos DISTRIBUIÇÃO DO TEMPO DE ESPERA Ao desenvolver as expressões que calculam as medidas de desempenho dos sistemas de filas estudados até aqui nenhuma consideração específica foi feita a respeito da disciplina de filas Isso quer dizer que os resultados são válidos qualquer que seja a disciplina adotada Todavia não se pode afirmar que a distribuição de probabilidades destes parâmetros independa da disciplina adotada Nos desenvolvimentos a seguir você verá que a distribuição do tempo de espera depende da disciplina sob a qual a fila opera Para tal considerarseá o modelo MM1 FIFO Seja 𝜏 a variável aleatória que representa o tempo que uma cliente recém chegado isto é que acaba de entrar no sistema permanecerá até a conclusão do serviço e sua partida Considere ainda 𝑡𝑖 para 𝑖 12 𝑛 1 tal que 𝑡1 é o tempo para conclusão do ndimento DISTRIBUIÇÃO DO TEMPO DE ESPERA atendimento que está ocorrendo 𝑡2 𝑡3 𝑡𝑛 são os tempos de atendimento dos 𝑛 1 clientes que estão na fila de espera e 𝑡𝑛1 é o tempo de atendimento que será experimentado por este cliente recémchegado Definese então 𝑆𝑛1 𝑡1 𝑡2 𝑡𝑛1 37 como sendo o tempo de permanência condicional quando 𝑛 clientes já se encontram no sistema no momento da chegada do cliente 𝑛 1 Uma vez que os tempos de atendimento 𝑡𝑖 seguem uma distribuição exponencial note que isso é válido até mesmo para 𝑡1 devido à propriedade da falta de memória então 𝑆𝑛1resulta da soma de 𝑛 1 variáveis aleatórias independentes e identicamente distribuídas De acordo com a Teoria das Probabilidades podese afirmar que 𝑆𝑛1tem distribuição gamma com parâmetros 𝜇 e 𝑛 1 DISTRIBUIÇÃO DO TEMPO DE ESPERA Portanto 𝑃 𝜏 𝑇 𝑛0 𝑃𝑛𝑃𝑆𝑛1 𝑇 38 Após algumas manipulações trabalhosas aqui omitidas chegase aatendimento 𝑃 𝜏 𝑇 𝑒𝜇𝜆𝑇 𝑇 0 39 Vêse assim que o tempo de permanência no sistema para um cliente recém chegado segue uma distribuição exponencial de média igual 𝐸 𝜏 1 𝜇𝜆 Em algumas situações o parâmetro de desempenho de maior relevância é tempo de espera É o caso por exemplo dos serviços de atendimento emergencial onde o que importa é o tempo decorrido até o início do serviço Considere então o tempo de espera e DISTRIBUIÇÃO DO TEMPO DE ESPERA em fila 𝜏𝑞 Se ao chegar um dado cliente encontra o sistema vazio então ele é servido imediatamente Neste caso 𝑃 𝜏𝑞 0 𝑃0 1 𝜌 40 Por outro lado se já houver 𝑛 clientes no sistema o cliente que acaba de chegar terá que esperar pela conclusão de 𝑛 serviços cujo duração é exponencial 𝑃 𝜏 𝑇 𝑛1 𝑃𝑛𝑃𝑆𝑛 𝑇 41 Após simplificações a expressão se reduz a 𝑃 𝜏 𝑇 𝜌𝑒𝜇𝜆𝑇 𝑇 0 42 DISTRIBUIÇÃO DO TEMPO DE ESPERA Vêse pelas expressões em 4042 que o 𝜏𝑞 não possui uma distribuição exponencial Contudo a distribuição condicional de 𝜏𝑞 dado 𝜏𝑞 0 é exponencial Veja 𝑃 𝜏 𝑇 𝜏 0 𝑃 𝜏 𝑇 𝑃 𝜏 0 𝑒𝜇𝜆𝑇 𝑇 0 42 Exercício 6 Considere um lavajato com apenas uma baia de serviço ao qual os carros chegam segundo uma distribuição de Poisson com média de 4 por hora O tempo de lavagem segue uma distribuição exponencial de média 10 minutos Não há limite para o número de carros em espera uma vez que aqueles que não puderem entrar no estabelecimento podem esperar estacionados do lado de fora Qual a probabilidade de um cliente que acaba de chegar permanecer no sistema por um tempo superior ao tempo médio estimado DISTRIBUIÇÃO DO TEMPO DE ESPERA Resolução Temse aqui um modelo MM1 não capacitado Assim sendo o tempo médio de espera é 𝑊 1 𝜇 𝜆 1 6 4 1 2 hora Logo a probabilidade de um cliente recém chegado esperar até ao menos 30 minutos até a conclusão de seu atendimento é 𝑃 𝜏 𝑊 𝑒 𝜇𝜆 1 𝜇𝜆 𝑒1 03679 Note que a probabilidade de que a espera seja superior ao tempo médio esperado independe dos valores de 𝜆 e 𝜇 O seu seja quaisquer que sejam as taxas de chegada e atendimento sempre se terá aproximadamente 37 dos clientes permanecendo no mais DISTRIBUIÇÃO DO TEMPO DE ESPERA sistema por um tempo superior a 𝑊 Como 30 minutos já é um tempo consideravelmente alto para a média do tempo no sistema a solução para melhorar o desempenho seria reduzir o tempo de atendimento Τ 1 𝜇 até que 𝑊 tenha um valor aceitável ou selecionar Τ 1 𝜇 tal que a probabilidade de exceder um dado tempo de permanência 𝑇 seja menor ou igual a uma porcentagem 𝛼 considerada razoável CONSIDERAÇÕES FINAIS A presente texto é uma breve introdução à Teoria de Filas que se concentrou nos modelos de filas de Poisson Contudo há diversos outros modelos que não foram discutidos aqui e que consideram por exemplo filas com prioridade para serviço redes de filas e filas nas quais as taxas de chegada e serviço não seguem uma distribuição de Poisson Um aspecto que justifica o grande interesse nos modelos de Poisson é que na maior parte dos casos as fórmulas derivadas para calcular os parâmetros de desempenho em regime estacionário são computacionalmente tratáveis Todavia nem todo modelo de filas é Poisson tendo em vista a variedade de problemas do mundo real em que as premissa de uma fila Poisson não são aderentes Os modelos DM1 e DMc de Erlang com tempo entre chegadas constante e o modelo PollaczekKhintchine MG1 com distribuição geral para o tempo de serviço são algumas das poucas exceções de modelos qual qualquer distribuição de probabilidade pode ser usada a matemática de alto nível associada a esses modelos resultou em informações manchadas ou CONSIDERAÇÕES FINAIS distribuição geral para o tempo de serviço são algumas das poucas exceções de modelos nãoPoisson tratáveis O modelo geral GGc no qual qualquer distribuição de probabilidade pode ser considerada para os processos de chegada e serviço requer o desenvolvimento de expressões demasiadamente complexas inviabilizando seu uso Nestes casos o emprego de simulação é uma alternativa dada a facilidade de representar computacionalmente o comportamento do sistema de filas Em uma simulação as medidas de desempenho são obtidas através de estatísticas calculadas a partir da observação do comportamento do sistema simulado ao longo do tempo Embora seja uma ferramenta flexível e de fácil implementação ela também tem desvantagens Como por exemplo um custo computacional mais elevado e resultados aproximados em contraposição à solução analítica obtida por modelos de filas tratáveis BIBLIOGRAFIA HILLIER FS LIEBERMAN GJ Introduction to Operations Research MacGrawHill 2001 TAHA HA Pesquisa Operacional 8 ed Pearson Prentice Hall 2008 WINSTON W Operations Reseach Applications and Algorithms Duxbury Press 2003 PINTO LR Notas de aula da disciplina Simulação Programa de PósGraduação em Engenharia de Produção Departamento de Engenharia de Produção UFMG 2005