Teoria de Filas: Sistemas em Série e Sistemas Abertos - Roteiro da Aula 1

FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 1 Teoria de Filas Sistemas em série e Sistemas abertos Roteiro da aula 1 Contextualização e conceitos 2 Exemplos resolvidos 1 Contextualização e conceitos 11 Sistemas em série Em diversas situações o atendimento de uma pessoa ou o processamento de uma peça é realizado em mais de um servidor Ocorre que ao completar um estágio o item é encaminhado para um estágio seguinte e o processo é continuado até que o cliente ou a peça tenha percorrido os kestágios necessários Esse caso é descrito como um sistema com servidores em série A Figura 1 apresenta o exemplo de um sistema com estágios em série com destaque para o fato de que a saída de um estágio corresponde a entrada de um estágio seguinte Dessa forma sendo atingido o estado estacionário em todos os estágios a taxa de chegada é constante e equivalente a 𝜆 Figura 1 Exemplo de sistema de filas em série Fonte Winston 2004 A consistência dessa configuração é dependente da condição de que cada estágio possua capacidade suficiente para processar ou atender todas as chegadas com taxa 𝜆 caso contrário a fila intermediária S1B S2A Taxa de entrada λ S1A S1C S2B Fila 1 Fila 2 S3 S k1 SkA SkB Fila 3 Fila K1 Fila k Saída 1 Entrada 2 Saída 2 Entrada 3 Saída k1 Entrada k Estágio 1 Servidores s1 Taxa μ1 Estágio 2 Servidores s2 Taxa μ2 Estágio 3 Servidores s3 Taxa μ3 Estágio k1 Servidores sk1 Taxa μk1 Estágio k Servidores sk Taxa μk FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 2 irá crescer desenfreadamente ou no termo específico irá explodir Observase ainda que poderá haver conexões entre sistemas de diferentes tipos isto é um sistema MM1 pode estar conectado a um sistema MMs e viceversa Além disso as conexões são estabelecidas entre as máquinas de um estágio e a fila do estágio seguinte 12 Sistemas abertos Sistemas abertas é um caso específico de filas em série no qual um estágio 𝑗 possui um conjunto de servidores operando com uma taxa de processamentoatendimento 𝜇𝑗 As entidades sejam peças ou pessoas podem chegar de uma fonte externa com taxa 𝑟𝑗 seguindo uma distribuição exponencial Após ser completado o processamento a entidade sai do estágio 𝑗 com probabilidade 𝑝𝑖𝑗 e é considerada concluída com probabilidade 1 𝑝𝑖𝑗 𝑗𝑘 𝑗1 Seja 𝜆𝑗 a taxa de chegada de entidades em um estágio 𝑗 deverão ser incluídas as entradas vindas de fora do sistema bem como de outros estágios anteriores e subsequentes Dessa forma a taxa de chegada para cada estágio deve ser obtida a partir do seguinte sistema de equações lineares 𝜆𝑗 𝑟𝑗 𝑃𝑖𝑗 𝜆𝑖 𝑘 𝑖1 𝑖𝑗 𝑝𝑎𝑟𝑎 𝑗 1 2 𝑘 É importante salientar também que o número de chegadas no sistema é dado pela soma das chegadas vindas de fontes externas conforme segue 𝜆 𝑟1 𝑟2 𝑟3 𝑟𝑛 A Figura 2 exibe o exemplo de um sistema aberto FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 3 Figura 2 Exemplo de sistema aberto Esse tipo de abordagem pode representar um sistema em que peças são retrabalhadas podendo ser considerado também que parte das peças tem o processamento iniciado em um estágio que não seja o estágio inicial do fluxo padrão 2 Exemplos resolvidos 21 Em uma unidade de pronto atendimento o atendimento dos pacientes é realizado em dois estágios exames preliminares e consulta Em média é registrada a chegada de um paciente a cada 100 segundos Após o preenchimento da ficha de entrada os pacientes são encaminhados para a sala de espera para aferição de pressão e medição de temperatura processo que leva em média 75 segundos sem considerar o tempo de espera Em seguida os pacientes aguardam para a consulta com um dos quatro médicos que estão de plantão Nesse segundo estágio a duração média de um atendimento é de 250 segundos Assumindo que as chegadas e tempos de atendimento ocorram de acordo com distribuições exponenciais calcule a O número médio de pacientes na fila anterior a cada estágio b O tempo médio que cada paciente permanece na fila em cada estágio p12 1p12 Servidor 1 μ1 Servidor 2 μ2 p21 p23 r1 Servidor 3 μ3 1p31p32 p32 r3 p31 FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 4 Resolução A partir da descrição apresentada é possível constatar que se trata de um sistema formado por dois estágios em série ou seja que ocorrem de forma sequencial e são aplicáveis a todos os pacientes Dessa forma cada estágio será tratado individualmente como um subsistema integrante do sistema completo De início é sempre recomendada a elaboração de uma representação ilustrativa da situação conforme exibido na figura a seguir Antes de dar início aos cálculos o intervalo entre chegadas será transformado em taxa de chegadas 100 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠 1 𝑝𝑎𝑐𝑖𝑒𝑛𝑡𝑒 60 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠 𝜆 𝜆 60 100 060 𝑝𝑎𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑝𝑜𝑟 𝑚𝑖𝑛𝑢𝑡𝑜 Da mesma forma o tempo de processamento será transformado em taxa de processamento para cada estágio 75 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠 1 𝑝𝑎𝑐𝑖𝑒𝑛𝑡𝑒 60 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠 𝜇1 𝜇1 60 75 08 𝑝𝑎𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑝𝑜𝑟 𝑚𝑖𝑛𝑢𝑡𝑜 250 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠 1 𝑝𝑎𝑐𝑖𝑒𝑛𝑡𝑒 60 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠 𝜇2 𝜇2 60 250 024 𝑝𝑎𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑝𝑜𝑟 𝑚𝑖𝑛𝑢𝑡𝑜 Em seguida deve ser avaliado se os dois estágios atingirão a condição de estado estacionário Atendimento 2B μ2 024 pacmin λ 060 pacientes por minuto Atendimento 2A μ2 024 pacmin Atendimento 2D μ2 024 pacmin Fila 2 Fila 1 Exames de entrada μ1 08 pacmin Exames preliminares Consulta Atendimento 2C μ2 024 pacmin FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 5 𝜌1 λ 𝑠1 𝜇1 1 𝜌1 060 108 075 1 𝜌2 λ 𝑠2 𝜇2 1 𝜌2 060 4024 0625 1 Dado que a taxa de fluxo é menor do que 1 para os dois estágios concluise que o sistema está dimensionado com número suficiente de recursos a O número médio de pacientes na fila anterior a cada estágio Para o estágio de exames temse um sistema MM1 𝐿𝑞1 𝜌2 1 𝜌 0752 1 075 225 𝑝𝑎𝑐𝑖𝑒𝑛𝑡𝑒𝑠 Para o estágio de atendimento temse um sistema MMs 𝐿𝑞 𝑃𝑗 𝑠𝜌 1 𝜌 Para tanto é necessário obter dois valores previamente A fração de tempo em que o sistema está ocioso 1 0 0 1 1 s i s i s s i s 𝜋0 1 40625𝒊 𝒊 3 0 406254 4 1 0625 𝜋0 1 1 25 3125 26 434 00737 E a probabilidade de que todos os médicos estejam ocupados 𝑃𝑗 𝑠 𝑠𝜌𝑠𝜋0 𝑠 1 𝜌 𝑃𝑗 𝑠 40625400737 4 1 0625 03198 FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 6 E então 𝐿𝑞 𝑃𝑗 𝑠𝜌 1 𝜌 𝐿𝑞 031980625 1 0625 05325 𝑝𝑎𝑐𝑖𝑒𝑛𝑡𝑒𝑠 b O tempo médio que cada paciente permanece na fila em cada estágio Novamente em uma abordagem por partes cada estágio é analisado individualmente 𝑊𝑞1 𝐿𝑞1 𝜆 𝑊𝑞1 225 060 𝑊𝑞1 375 𝑚𝑖𝑛𝑢𝑡𝑜𝑠 𝑊𝑞2 𝐿𝑞2 𝜆 𝑊𝑞2 05325 060 𝑊𝑞2 08875 𝑚𝑖𝑛𝑢𝑡𝑜𝑠 Observação Devido às transformações realizadas inicialmente todos os cálculos tiveram minutos como unidade de tempo 22 Uma fábrica possui um fluxo produtivo composto por três máquinas Em média 15 peças por hora chegam do estoque para a máquina 1 e em média 22 peças por hora são recebidas do estoque para processamento na máquina 2 Por sua vez a máquina 3 não recebe nenhum material que ainda não tenha sido processado na máquina 2 A taxa de processamento das máquinas 1 2 e 3 é de 40 50 e 60 peças por hora respectivamente Após serem processadas na máquina 1 70 das peças são encaminhadas para o estoque de produtos acabados e 30 são encaminhadas para a máquina 2 Por ora após concluído o processamento na máquina 2 75 das peças são enviadas para máquina 3 e os outros 25 são direcionadas a máquina 1 Por último na máquina 3 95 das peças são finalizadas e 5 retornam a máquina 2 para acabamento Por serem contrários a trajetória principal os fluxos das máquinas 2 para 1 e das máquinas 3 para 2 são denominados refluxos Com base nas informações e dados apresentados calcule FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 7 a Qual a fração de tempo em que a máquina 2 está ociosa b Qual o número esperado de peças no sistema c Qual o tempo médio que uma peça permanece no sistema d O que aconteceria se a máquina 3 tivesse a sua capacidade de processamento reduzida para 25 peçashora Resolução De início é fundamental elaborar uma representação ilustrativa do problema apresentado tal qual a figura a seguir Em seguida devem ser obtido os valores correspondentes as taxas de chagadas para cada estágio considerando tanto as entradas vindas de fontes externas nesse caso 𝑟1 e 𝑟2 como também os refluxos provenientes dos demais estágios do sistema considerado Portanto tratase de um sistema aberto Para tanto deve ser formado um sistema linear no qual cada equação é associada a um dos estágios e estabelecidas a partir da seguinte relação 𝜆𝑗 𝑟𝑗 𝑃𝑖𝑗 𝜆𝑖 𝑘 𝑖1 𝑖𝑗 𝑝𝑎𝑟𝑎 𝑗 1 2 𝑘 De forma simplificada a taxa de chegada de uma máquina 𝑗 é igual a soma das entradas vindas de fontes externas com os múltiplos da probabilidade de ocorrência do refluxo pela taxa de chegada da 30 70 Máquina 1 μ1 40 peçash Máquina 2 μ2 50 peçash 25 75 r2 22 pçh r1 15 pçh Máquina 3 μ3 60 peçash 95 5 FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 8 máquina de origem do refluxo Nesse sentido deve haver um componente de multiplicação para cada entrada desse segundo tipo A seguir são mostradas as equações correspondentes ao problema apresentado 𝜆1 15 025𝜆2 𝐸𝑞 𝐼 𝑀á𝑞𝑢𝑖𝑛𝑎 1 𝜆2 22 030𝜆1 005𝜆3 𝐸𝑞 𝐼𝐼 𝑀á𝑞𝑢𝑖𝑛𝑎 2 𝜆3 075𝜆2 𝐸𝑞 𝐼𝐼𝐼 𝑀á𝑞𝑢𝑖𝑛𝑎 3 A solução do sistema pode ser obtida por meio do método de substituição Passo 1 Substituir a Eq I e a Eq III na Eq II 𝜆2 22 030𝜆1 005𝜆3 𝐸𝑞 𝐼𝐼 𝑀á𝑞𝑢𝑖𝑛𝑎 2 𝜆2 22 03015 025𝜆2 005075𝜆2 Dessa forma temse 𝜆2 como única incógnita Então é aplicada a propriedade distributiva 𝜆2 22 45 0075𝜆2 00375𝜆2 1𝜆2 0075𝜆2 00375𝜆2 265 𝜆2 265 08875 2986 𝑝𝑒ç𝑎𝑠ℎ𝑜𝑟𝑎 Passo 2 Substituir o resultado de 𝜆2 na Eq I e na Eq III 𝜆1 15 025𝜆2 𝜆1 15 0252986 𝜆1 22465 𝑝𝑒ç𝑎𝑠 𝑝𝑜𝑟 ℎ𝑜𝑟𝑎 𝜆3 075𝜆2 𝜆3 0752986 𝜆3 22395 𝑝𝑒ç𝑎𝑠 𝑝𝑜𝑟 ℎ𝑜𝑟𝑎 De posse dos valores das taxas de chegada relacionadas a cada estágio é necessário calcular as respectivas taxas de fluxo 𝜌1 λ1 𝑠1 𝜇1 𝜌2 λ2 𝑠2𝜇2 𝜌3 λ3 𝑠3𝜇3 𝜌1 22465 1 40 056 1 𝜌2 2986 1 50 060 1 𝜌3 22395 1 60 037 1 FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 9 Como o valor é menor do que 1 para os três estágios concluise que não é necessário acrescentar servidores em paralelo para nenhum deles visto que as filas intermediárias não irão explodir Logo todos os estágios são sistemas do tipo MM1 a Qual a fração de tempo em que a máquina 2 está ociosa Esta informação é representada pelo valor de 𝜋0𝐼𝐼 conforme segue 𝜋0𝐼𝐼 1 𝜌2 𝜋0𝐼𝐼 1 060 𝜋0𝐼𝐼 04 40 b Qual o número esperado de peças no sistema Primeiramente é preciso calcular o número de peças em cada estágio 𝐿1 𝜌1 1 𝜌1 𝐿1 056 1 056 𝐿1 127 𝑝𝑒ç𝑎𝑠 𝐿2 𝜌2 1 𝜌2 𝐿2 060 1 060 𝐿2 15 𝑝𝑒ç𝑎𝑠 𝐿3 𝜌3 1 𝜌3 𝐿3 037 1 037 𝐿3 059 𝑝𝑒ç𝑎𝑠 Em seguida é obtida a soma que corresponde ao número de peças no sistema como um todo 𝐿𝑇𝑂𝑇𝐴𝐿 𝐿1 𝐿2 𝐿3 𝐿𝑇𝑂𝑇𝐴𝐿 127 15 059 336 𝑝𝑒ç𝑎𝑠 c Qual o tempo médio que uma peça permanece no sistema 𝑊 𝐿 𝜆 𝐿 𝑟1 𝑟2 336 15 22 009 ℎ Observação ao considerar o sistema completo o valor da taxa de chegada 𝜆 corresponde apenas as entradas vindas de fora do sistema isto é desconsiderando os refluxos É assim determinado para que os refluxos não sejam contabilizados repetidamente o que seria redundante e inconsistente com a situação representada FUNDAÇÃO HERMÍNIO OMETTO Engenharia de Produção EGP053 Pesquisa Operacional II 10 d O que aconteceria se a máquina 3 tivesse a sua capacidade de processamento reduzida para 25 peçashora Para avaliar o impacto da alteração sugerida é necessário recalcular o valor de 𝜌3 𝜌 22395 1 25 090 1 Como o resultado continua sendo menor do que 1 concluise que o sistema continuará atingindo o estado estacionário e que não há necessidade de acrescentar uma máquina em paralelo Em contrapartida se o resultado fosse maior do que 1 seria indispensável adicionar uma máquina em paralelo a fim de evitar que a fila de peças para serem processadas viesse a explodir Referência WINSTON Wayne L GOLDBERG Jeffrey B Operations research applications and algorithms 4 ed Belmont Thomson BrooksCole 2004