Baixe o app para aproveitar ainda mais
Prévia do material em texto
Disciplina: Sistemas de Transportes Aula 8: Otimização em sistemas de transportes – Organização de filas Apresentação Uma fila é caracterizada por um processo de chegadas (pessoas, veículos, trens, etc.) a um sistema de atendimento formado por uma ou mais unidades de serviço. As unidades podem ser atendidas individualmente (pedágio, porto etc.), ou em grupos (pessoas num elevador, veículos num semáforo etc.). Nesta aula, vamos compreender a determinar a melhor maneira de usar uma equipe e outros recursos, ao mesmo tempo em que reduz os tempos de espera dos clientes. O modelo também pressupõe que as filas seguem a regra FIFO (primeiro a entrar, primeiro a sair). Outras regras de fila incluem LIFO (última entrada, primeiro a sair), primeiro o trabalho mais curto, seleção aleatória e ordem de prioridade. Objetivos Compreender princípios e fundamentos do Modelo de Otimização — Organização de filas; Reconhecer os métodos e as técnicas do Modelo de Otimização — Organização de filas; Identificar os procedimentos de obtenção das soluções Ótimas por meio das etapas do Modelo de Otimização — Organização de filas. Teoria de Filas A Teoria de Filas é de extrema importância no ato de estudar as características do processo, pois possibilitará a redução dos problemas causados aos clientes, como por exemplo, atrasos, fazendo com que aconteça a fidelização dos clientes e que a empresa forneça um serviço de qualidade. O estudo baseado na Teoria das Filas é realizado por meio de fórmulas matemáticas que facilitam a verificação do comportamento de sistemas reais em situação aleatória. Desta forma, é possível mencionar a capacidade de atendimento, garantindo um nível de satisfação aos seus clientes, ao se combinar custo do serviço, qualidade oferecida e investimentos nos gargalos. O que são filas na prática? Qualquer pessoa sabe exatamente o que são filas em decorrência das experiências que o dia a dia nos coloca. Nós entramos em uma fila para descontar um cheque em um banco, para pagar pelas compras em um supermercado, para comprar ingresso em um cinema, para pagar o pedágio em uma estrada e tantas outras situações, tais como: sequência de cargas e descargas de caminhões. As filas são muito utilizadas em transportes A modelagem de filas tem sido usada no transporte ferroviário, rodoviário, marítimo e por elevadores. No transporte ferroviário, o pátio de consertos e serviços apresenta problemas interessantes, que incluem o número e a localização dos desvios e alocação de máquinas de serviço (com base em uma tabela de trens e carros a serem removidos ou adicionados), além da tabela de horários de trens diretos que passam pelo local. O sistema ferroviário pode ser analisado como um todo, com o objetivo de minimizar o movimento de carros vazios. No transporte marítimo e aéreo as aplicações se referem à confecção da tabela de horários e ao dimensionamento de portos e aeroportos. No modelo rodoviário é possível dimensionar um pedágio ou estabelecer o melhor esquema do fluxo de veículos pelas ruas de uma cidade, com as durações dos semáforos, de modo a melhorar o serviço, agilizando o sistema e, consequentemente, diminuindo os gastos com combustível. Quais são os clientes e o tamanho da população? Um cliente é proveniente de uma população. Quando a população é muito grande (dizemos infinita para efeitos práticos), a chegada de um novo cliente a uma fila não afeta a taxa de chegada de clientes subsequentes e concluímos dizendo que as chegadas são independentes. Exemplo O funcionamento de um metrô. Quando a população é pequena o efeito existe e pode ser considerável. Uma mineração, na qual uma carregadeira carrega minério em caminhões que chegam. Se existem 3 caminhões e, se ocorrer que todos eles estejam na fila da carregadeira, então não chegará nenhum outro caminhão. Como é o processo de chegada? Consideremos, como exemplo, um posto de pedágio com 5 atendentes. Pode-se constatar que o processo de chegada entre 7 e 8 horas da manhã é definido por 20 automóveis por minuto ou 1 automóvel a cada 3 segundos. Trata-se de um valor médio, pois não significa que em todo intervalo de 1 minuto chegarão 20 automóveis. Em alguns intervalos de 1 minuto podem chegar 10, 15, 25 ou até 30 automóveis. Consequentemente, o intervalo de 3 segundos entre chegadas não é rígido e os valores, por exemplo, desde zero segundos (2 veículos chegando juntos) até 20 segundos. O número fornecido, 3 segundos, representa, assim, o intervalo médio entre chegadas no período da 7 às 8 horas da manhã. Resumindo as afirmações acima quantificamos o processo de chegada dizendo que a taxa média é de 20 veículos por minuto ou que o intervalo médio entre chegadas é de 3 segundos. Fonte: Shutterstock Poderia ser encontrado outro sistema de filas com exatamente os mesmos valores médios acima citados, mas com diferentes variações no entorno da média (por exemplo, uma situação em que os intervalos entre chegadas estão entre 0 e 10 segundos). Este sistema, conforme veremos, terá um comportamento diferente do primeiro e conclui-se dizendo que não basta apenas fornecer os valores médios, é necessário também mostrar como os valores se distribuem em torno da média. Um tipo raro de processo de chegada é o regular, ou seja, aquele no qual não existe nenhuma variação entre valores para os intervalos entre chegadas. I 20 clientes por minuto IC 3 segundos Como é o processo de atendimento? Vamos continuar no exemplo do pedágio e observar um atendente em serviço, por exemplo, que ele atende a 6 veículos por minuto ou que gasta 10 segundos para atender a um veículo. Fonte: Shutterstock Estes valores são médios e, para descrevê-los corretamente, deve-se também lançar mão da distribuição de probabilidades. Aqui também é rara a existência prática de atendimento regular, ou seja, existe um único valor (sem variação) para a duração do atendimento. O processo de atendimento é também quantificado por uma importante variável randômica. A letra grega μ é usada para significar ritmo de atendimento e se usa TA para tempo ou duração do serviço ou atendimento. Assim, no exemplo acima tem-se que: μ 6 clientes por minuto TAC 10 segundos por cliente Qual é o número de servidores? O mais simples sistema de filas é aquele de um único servidor que pode atender a um único cliente de cada vez. Conforme aumente o ritmo de chegada, pode-se manter a qualidade do serviço aumentando convenientemente o número de servidores. Esta é, portanto, uma das características para modelar um sistema de filas. Qual é o regime de disciplina da fila? Trata-se de regras que definem qual o próximo a ser atendido: FIFO Primeiro a chegar é o primeiro a sair LIFO Último a chegar é o primeiro a sair SIRO Atendimento aleatório PRI Atendimento por prioridade GD Outra ordem Qual é o tamanho médio da fila? Esta é a característica da fila mais considerada ao se defrontar com a opção a escolher. O ideal é a situação de ser atendido (fila zero). Quando a fila é de um tamanho razoável (por exemplo, 10 elementos) intuitivamente sabe- se que o tempo de espera na fila será longo. O tamanho da fila não é constante e, posteriormente, veremos que, quando os ritmos médios de chegada e de atendimento são constantes, o tamanho da fila oscila em torno de um valor médio. Qual é o tamanho máximo da fila? Quando os clientes devem aguardar, alguma área de espera deve existir (por exemplo: as cadeiras de uma barbearia). Observa-se, na prática, que os sistemas existentes são dimensionados para certa quantidade máxima de clientes em espera, sendo este dimensionamento geralmente feito com base em experiência real. Quando existe um crescimento na demanda, se faz uma ampliação também baseada na experiência com o manuseio do referido sistema. Qual é o tempo médio de espera na fila? Esta é a característica capaz decausar irritação quando se está em uma fila de espera. O ideal é que não exista espera, mas esta nem sempre é a melhor situação do ponto de vista econômico. Se entrarmos em uma fila com 10 pessoas à nossa frente, o tempo de espera será igual ao somatório dos tempos de atendimento de cada um dos clientes da nossa frente ou, possivelmente, será igual a 10 vezes a duração média de atendimento. Tal como o tamanho médio da fila, o tempo médio de espera depende dos processos de chegada e de atendimento. Fonte: Shutterstock Como observamos a dinâmica de uma fila? Imagine agora, o observador comodamente instalado em uma poltrona dentro de um banco, com a finalidade de observar o funcionamento da fila formada por pessoas que desejam um novo talão de cheques. No período de meia hora verificou-se que chegaram ao sistema 12 pessoas. Os intervalos (valores em minutos) entre chegadas foram: Cliente 1 2 3 4 5 6 7 8 9 10 11 12 Intervalo 2 3 3 3 5 0 1 5 1 4 1 2 Momento 2 5 8 11 16 16 17 22 23 27 28 30 O valor zero acima significa que o sexto cliente chegou junto com o quinto. O valor médio dos dados acima é 2,5 minutos e, portanto, o sistema funcionou com um ritmo médio de 24 chegadas por hora. Os dados anotados para cada atendimento são os seguintes (valores em minutos): Cliente 1 2 3 4 5 6 7 8 9 10 11 12 Duração 1 2 1 1 3 2 1 4 2 3 1 3 O valor médio dos dados acima é 2,0 minutos e, portanto, pode-se dizer que o servidor tem uma capacidade de atender 30 clientes por hora. Finalmente, o sistema trabalhou conforme abaixo e por ela verifica-se que os clientes de números 6, 7, 9, 10, 11 e 12 tiveram que esperar em fila. Cliente 1 2 3 4 5 6 7 8 9 10 11 12 Tempo em fila 0 0 0 0 0 3 4 0 3 1 3 2 Qual é o tamanho de amostra? Um sistema estável em estudo mostrará sempre os mesmos resultados desde que adequadamente analisado. Para isto, a escolha de um correto tamanho de amostra é fundamental. A não observância deste item pode confundir, por produzir diferentes valores para a mesma variável. Exemplo Em um sistema estável podemos ter um tempo médio de espera na fila de 5 minutos. Para se chegar a esta conclusão foi necessário observar o funcionamento do sistema durante um longo período, no qual inúmeros clientes foram atendidos. Quais as opções de dimensionamento: o tipo da fila — gerenciando filas? Estudam-se filas para poder modificar sistemas nos quais existem gargalos, com o objetivo de prestar um melhor atendimento ou uma redução de custos. O conhecimento do comportamento de uma fila, quando alteramos algumas de suas características, pode ser fundamental para atingirmos os objetivos citados de qualidade de atendimento e custos. Em situações nas quais o tempo de atendimento pode variar dentro de uma larga faixa de valores não recomenda o uso de diversas filas. É o caso de bancos, correios etc., nos quais pode ocorrer que alguns clientes apresentem uma carga de serviço muito grande e, portanto, o tempo de atendimento para eles será exageradamente maior que a média. Aqui, uma fila única com diversos atendentes é a melhor solução. Canal único, atendimento único. Canal único, atendimento múltiplo. Canal múltiplo, atendimento único. Canal múltiplo, atendimento múltiplo. Vamos conhecer as definições na prática e em exercícios resolvidos. 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 Por definição: 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 M = Quantidade de atendentes NA = Número médio de clientes sendo atendidos μ = Ritmo médio de atendimento de cada atendente Por definição: TA = 1 / μ Relações básicas Existem duas relações importantes: NS NF + NA TS TF + TA Pode-se demonstrar também que NA = λ / μ = TA / IC. Portanto: NS = NF + NA = NF + λ / μ = NF + TA / IC Qual é a taxa de utilização dos atendentes? Para o caso de “uma fila / um atendente”, chama-se de taxa de utilização do atendente a expressão: 𝜌=𝜆/𝜇 Na qual: λ = ritmo médio de chegada μ = ritmo médio de atendimento No caso de uma fila / vários atendentes, a expressão se torna: 𝜌 = 𝜆 / ( M .𝜇 ) Onde: M é o número de atendentes. Assim, ρ representa a fração média do tempo em que cada servidor está ocupado. Exemplo Com um atendente, caso cheguem 4 clientes por hora e ele tenha capacidade para atender a 10 clientes por hora, logo a taxa de utilização é 0,40 e pode-se também afirmar que o atendente fica 40% do tempo ocupado e 60% do tempo livre (esta afirmação é intuitiva mas pode ser matematicamente demonstrada). Visto que o estudo é com sistemas estáveis (os atendentes sempre serão capazes de atender ao fluxo de chegada) tem- se sempre que ρ < 1. Quando ρ = 1 o atendente trabalhará 100% do tempo (e estranhos fatos ocorrerão ...). Qual é a intensidade de tráfego ou o número mínimo de atendentes? Chama-se de intensidade de tráfego a expressão: 𝑖=|𝜆/𝜇 | = | 𝑇𝐴/𝐼𝐶 em que i é o próximo valor inteiro que se obtém (ou seja, o valor absoluto) e é medido em “erlangs” em homenagem a A. K. Erlang . Na prática, i representa o número mínimo de atendentes necessários para atender a um dado fluxo de tráfego. Exemplo Se λ = 10 clientes / hora e TA = 3 minutos (ou μ = 20 clientes / hora) tem-se que λ / μ = 0,5, ou i = 1, e conclui-se dizendo que 1 atendente é suficiente para o caso. Se o fluxo de chegada aumentar para λ = 50 clientes / hora, tem- se que λ / μ = 2,5, ou i = 3, isto é, necessita-se de no mínimo 3 atendentes. Na indústria telefônica esta variável é bastante utilizada ao se referir a tráfego em troncos telefônicos. Tabela resumo das fórmulas Nome Fórmula Intervalo entre chegadas IC = 1 / λ Tempo de Atendimento TA = 1 / μ 1 Taxa de Utilização dos Atendentes 𝜌 = λ / ( M . μ ) Intensidade de Tráfego i = | λ / μ | = | TA / IC | Relação entre Fila, Sistema e Atendimento NS = NF + NA NA = λ / μ NS = NF + l / m = NF + TA / IC TS = TF + TA NA = 𝜌 = λ / ( M μ ) Fórmulas de Little NF = λ . TF NS = λ . TS Duração do Ciclo Ciclo = Qtdd / λ Ciclo = TFS + TS Vejamos alguns exemplos: Em uma fábrica observou-se o funcionamento de um setor, em que o ritmo médio de chegadas (λ) é de 20 clientes/hora, o ritmo médio de atendimento (μ) é de 25 clientes/hora e o tempo médio de permanência no sistema (TS) é de 0,3 hora. Pede-se o tamanho médio da fila (NF). Solução: TA = 1 / μ = 1 / 25 = 0,04 TF = TS – TA = 0,3 – 0,04 = 0,26 NF = l x TF = 20 x 0,26 = 5,2 clientes Em uma mineração verificou-se que o tempo médio de permanência no sistema (TS) dos caminhões junto às carregadeiras é de 3 minutos e que, em média, existem 6 caminhões (NS) no setor. Qual a taxa de chegada de caminhões? Solução: NS = l x TS ou l = NS / TS Pela Lei de Little: l = 6 / 3 = 2 chegadas por minuto Atividade 1 - Considere um sistema no qual navios chegam a um porto para carregar algum produto. Abaixo estão anotados os valores de intervalos entre chegadas (em horas) para 20 navios: Cliente 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Intervalo 10 2 13 7 2 8 8 8 10 9 1 14 14 1 10 9 9 9 8 A duração da carga (em horas) de cada navio são as seguintes: Cliente 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Duração 5 5 3 3 6 7 6 8 2 5 8 8 8 3 4 3 3 4 5 5 Pede-se: a) O intervalo médio entre chegadas; b) A duração média da carga. Modelos Básicos Existem alguns modelos básicos que compõe um sistema de filas, com ênfase nos processos probabilísticos descritos em Fogliatti (2007). Nestes modelos é comum que os tempos entrechegadas e os tempos de atendimento sigam distribuições exponenciais e as nuances descritas a seguir. O Modelo M/M/1 Tem um único atendente. Definições: λ Ritmo médio de chegada IC Intervalo médio entre chegadas = 1/ λ TA Tempo médio de atendimento ou de serviço em cada atendente. Por definição TA =1/ μ μ Ritmo médio de atendimento de cada atendente População Infinita (quando a população é muito grande). Principais variáveis randômicas: Nome Descrição Fórmula NF Número médio de clientes na fila. NS Número médio de clientes no sistema. TF Tempo médio que o cliente espera na fila. TS Tempo médio que o cliente fica nosistema. P Probabilidade de existirem n clientes nosistema. Taxa de utilização Relação entre o ritmo de chegada e o ritmo médio de atendimento: NF = λ 2 μ(μ−λ) NS = λ μ−λ TF = λ μ(μ−λ) TS = 1 μ−λ n = (1 − ) (Pn λ μ λ μ ) n ρ = λ μ Comentário Sistemas estáveis exigem λ < μ ou ρ < 1. Quando ρ tende para 1 a fila tende a aumentar infinitamente, pois: Modelo M/M/c • Tem uma única fila e diversos servidores; • Chegada e atendimento seguem a Distribuição de Poisson ou a Distribuição Exponencial Negativa; • Supõe-se que a capacidade de atendimento de cada um dos servidores é a mesma (μ). Definições: λ Ritmo médio de chegada IC Intervalo médio entre chegadas = 1/ λ TA Tempo médio de atendimento ou de serviço. TA = 1/ μ μ Ritmo médio de atendimento de cada atendente c Capacidade de atendimento ou quantidade de atendentes Taxa de utilização Relação entre o ritmo de chegada e o ritmo médio de atendimento: População Infinita O uso de gráficos facilita o estudo do modelo M/M/c. O gráfico seguinte permite 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 c. NF = = λ 2 μ(μ−λ) ρ 2 (1−ρ) ρ = λ cμ Atividade 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 determinada tarefa. Verificou-se que o ritmo de chegada (λ) é de uma chegada por minuto e o ritmo de atendimento (μ) é de 1,2 atendimentos por minuto (seguem o modelo marcoviano M/M/1). A fábrica paga $9,00 por hora ao atendente e $18,00 por hora ao operário. Determine: a) O custo horário do sistema; b) A fração do dia em que o atendente não trabalha. 3 - Uma cooperativa agrícola prevê um crescimento na chegada de caminhões a seu terminal de descarga. O pátio de estacionamento, onde os caminhões permanecem, comporta seis veículos. A cooperativa acha aceitável que um caminhão aguarde na fila sua vez de descarregar por no máximo 0h75. Como a equipe de descarga tem condições de descarregar quatro caminhões por hora em média, deseja-se saber: Qual a taxa média de chegada que faz com que o tempo médio de espera seja igual ao máximo admissível? b) Para essa taxa de chegada, qual a probabilidade de que o pátio não seja suficiente? 4 - Em uma mineração verificou-se que o tempo médio de permanência no sistema (TS) dos caminhões junto às carregadeiras é de 3 minutos e que, em média, existem 6 caminhões (NS) no setor. No mesmo sistema, existindo um total de 30 caminhões em serviço, qual a duração de um ciclo? a) 20 minutos b) 15 minutos c) 30 minutos d) 10 minutos e) 25 minutos 5 - Em uma mineração verificou-se que o tempo médio de permanência no sistema (TS) dos caminhões junto às carregadeiras é de 3 minutos e que, em média, existem 6 caminhões (NS) no setor. Qual o tempo médio para o processo completo de descarregamento (ou TFS: Tempo Fora do Sistema)? a) 12 caminhões b) 10 caminhões c) 15 caminhões d) 20 caminhões e) 525 caminhões 6 - Abaixo estão citadas algumas classificações de filas. Qual é aquela que segue o canal único e atendimento único? a) Máquina para lavagem automática de carros. b) Travessia de rio por balsas. c) Elevadores. d) Bancos. e) Supermercados. 7 - Qual dos textos a seguir apresenta a definição de filas? a) Um sistema de filas consiste no processo de chegada, da distribuição do tempo de serviço, do número de servidores, da capacidade do sistema, da população de usuários e da disciplina de atendimento. b) Este fenômeno ocorre no tempo e no espaço de acordo com as leis da probabilidade; assim, é preciso conhecer quais os tempos entre as chegadas dos clientes. c) Representa o número máximo de clientes que o sistema suporta, incluindo os que estão em espera e os que estão sendo atendidos. d) Ocorre sempre que a procura por determinado serviço é maior que a capacidade do sistema de prover este serviço. e) Existem diversas aplicações da teoria das filas que podem ser encontradas, entre elas destacam-se: Fluxo de tráfego (aviões, carros, pessoas, comunicações), Escalonamento (pacientes em hospitais, programas em computadores), Prestação de serviços (bancos, correios, lanchonetes). Notas A. K. Erlang Matemática dinamarquês (1878-1929). Referências FOGLIATTI, Maria Cristina Mattos. Teoria das filas. Rio de Janeiro: Interciência, 2007. MOREIRA, D. A. Pesquisa operacional: curso introdutório. São Paulo: Thomson Learning, 2007. MOREIRA, D. A. Pesquisa operacional: curso introdutório. São Paulo: Thomson Learning, 2007. PARREIRA JUNIOR, Walteno Martins. Apostila de modelagem e avaliação de desempenho. Universidade do Estado de Minas Gerais. Fundação Educacional de Ituiutaba. Curso de Sistemas de Informações, 2010. Disponível em: <http://www.waltenomartins.com.br/ap_mad_cap1.pdf <http://www.waltenomartins.com.br/ap_mad_cap1.pdf> >. Acesso em: 08 ago. 2018. Próximos Passos Os benefícios reais que a implantação da lógica de Roteirização e Programação de Veículos pode trazer num sistema de transportes; Métodos e técnicas que tem por objetivo a redução do tempo, da distância percorrida e dos custos operacionais logísticos; 1 A programação das entregas baseada na quantidade e capacidade dos veículos, na quantidade de pedidos e nos locais de entrega. Explore mais BRUNS, Rafael de et al. Pesquisa operacional – Uma aplicação da teoria das filas a um sistema de atendimento. Disponível em: <http://www.abepro.org.br/biblioteca/ENEGEP2001_TR60_0158.pdf <http://www.abepro.org.br/biblioteca/ENEGEP2001_TR60_0158.pdf> >. Acesso em: 08 ago. 2018. DUARTE, Karia Pires e LIMA, Milton Luiz Paiva de. Análise operacional do terminal público do porto do Rio Grande usando teoria de filas. Disponível em: <http://www.semengo.furg.br/2006/08.pdf <http://www.semengo.furg.br/2006/08.pdf> >. Acesso em: 08 ago. 2018. LIMA, Vitor Costa de et al. Aplicação da teoria das filas em serviços bancários. Disponível em: <https://www.researchgate.net/profile/Osvaldo_Quelhas/publication/298429375_Aplicacao_da_teoria_das_filas _em_servicos_bancarios/links/574c1e0108ae538af6a50c8a/Aplicacao-da-teoria-das-filas-em-servicos- bancarios.pdf <https://www.researchgate.net/profile/Osvaldo_Quelhas/publication/298429375_Aplicacao_da_teoria_das_filas _em_servicos_bancarios/links/574c1e0108ae538af6a50c8a/Aplicacao-da-teoria-das-filas-em-servicos- bancarios.pdf> >. Acesso em: 08 ago. 2018.
Compartilhar