Prévia do material em texto
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Teoria das Filas Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Exemplo Protótipo Um pronto socorro atende a casos de emergência, fornecendo cuidados médicos a pacientes. Os pacientes chegam no hospital em ambulâncias ou carros particulares. A qualquer momento há um médico de plantão no pronto socorro. Devido ao crescimento de pacientes chegando no horário de pico (início da noite) com casos de urgência (ao invés de emergência), foi feita uma proposta de se alocar um segundo médico para o pronto socorro neste horário. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Processo de Filas Básico: Clientes que necessitam de atendimento são gerados ao longo do tempo por uma fonte de entradas. Esses clientes entram no sistema de filas e pegam uma fila. Em certos momentos, um integrante da fila é selecionado par o atendimento por alguma regra conhecida como disciplina da fila. O atendimento necessário é então realizado para o cliente pelo mecanismo de atendimento, após o qual o cliente deixa o sistemas de filas. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Fonte de Entradas (população solicitante) Tamanho: número total de clientes que poderiam precisar de atendimento de tempos em tempos, isto é, o número total de possíveis clientes distintos. Pode ser de tamanho finito ou infinito (entradas limitadas ou ilimitadas). Como os cálculos são mais fáceis no caso infinito, caso o tamanho seja grande, por simplificação, considera-se infinito. Padrão estatístico de geração de clientes: Processo de Poisson (distribuição poisson) Distribuição exponencial Em ambos casos observar tempo entre chegadas Outros comportamentos incomuns como recusa. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Fila É o local onde os clientes aguardam antes de serem atendidos. Finita ou infinita. Finito é de maior complexidade, mas o número finito pode ser muito relevante em casos reais Disciplina da Fila Regra pela qual os integrantes da fila são selecionados para atendimento FIFO (PEPS), LIFO (UEPS), por prioridades, aleatório. Normalmente FIFO Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Mecanismo de atendimento Formado por instalações de atendimento, que contém canais de atendimentos paralelos, chamados atendentes. As instalações de atendimento podem ser múltiplas e o cliente pode ser atendida por uma sequência delas (canais de atendimento série) O tempo decorrido entre o início de atendimento até o seu término para um cliente em uma instalação de atendimento é denominado tempo de atendimento (ou tempo de permanência). Este tempo deve ser modelado. Boas aproximações são: Distribuição exponencial, degenerada ou Erlang. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com atendimento μ atendimento μ atendimento μ Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Processo de Filas Elementar A teoria das filas foi aplicada a vários tipos diferentes de situações com filas. O tipo mais freqüente e básico é: uma fila de espera única (que pode ou não estar vazia) se forma na frente de uma única instalação de atendimento na qual se encontram um ou mais atendentes. Cada cliente gerado por uma fonte de entradas é atendido por um dos atendentes, após aguardar um tempo na fila de espera (se for o caso). Um atendente não precisa corresponder a uma única pessoa. Pode ser uma equipe, uma pessoa com maquinário, uma máquina ou um conjunto de máquinas. Os clientes não precisam ser pessoas podem ser trabalhos, processos, equipamentos, materiais, etc. A fila não precisa ser física e concentrada em algum lugar. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Processo de Filas Elementar A maioria dos sistemas de filas pressupõem que: Tempos entre chegadas são independentes e distribuídos de forma idêntica, e Tempos de atendimento são independentes e distribuídos de forma idêntica São identificados como: Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Processo de Filas Elementar: Onde M: distribuição exponencial (markoviana) D: distribuição degenerada (tempos constantes) Ek: distribuição de Erlang (parâmetro de forma = k) G: distribuição geral (distribuição arbitrária) Exemplo, modelo M/M/s, pressupõe que os tempos entre atendimentos e os tempos de atendimento possuem distribuição exponencial e o número de atendentes é s, sendo s um número inteiro positivo. Chegadas Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Terminologia e Notação 𝐿 : Estado do sistema: número de clientes no sistema de filas 𝐿𝑞 :Comprimento da fila: número de clientes que aguardam o início do seu atendimento = estado do sistema menos o número de clientes que estão sendo atendidos. L(t): número de clientes sistema de filas no instante t (t≥0) Pn(t): probabilidade de exatamente n clientes no sistema de filas no instante t, dado o número no instante 0. s: número de atendentes (canais de atendimento paralelos) no sistema de filas. λn: taxa média de chegada (número de chegadas esperado por unidade de tempo) de novos clientes quando n clientes se encontram no sistema. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Terminologia e Notação : taxa média de chegada global de clientes μn: taxa média de atendimento para o sistema global (número de clientes esperado que completa o atendimento por unidade de tempo) quanto n clientes se encontram no sistema. Quando λn for constante para todo n, essa constante é representada por λ. Quando a taxa média de atendimento por atendente ocupado for uma constante para todo n≥1, essa constante é representada por μ. Logo, quando n≥s, μn=s.μ Nestes casos 1/λ: é tempo esperado entre chegadas; e 1/μ: é o tempo de atendiemento esperado. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Estrutura Básica dos Modelos de Fila Terminologia e Notação 𝜌 : Fator de utilização para a instalação de atendimento. 𝑃𝑛 : Probabilidade de haver n clientes no sistema 𝑃0 : Probabilidade de haver 0 clientes no sistema 𝑊 : Tempo de espera no sistema (wait time) 𝑊𝑞 : Tempo de espera na fila (wait time in queue) 𝑃 °𝑤 > 𝑡 : Probabilidade do tempo de espera no sistema ser maior do que t. 𝑃 °𝑤𝑞 > 𝑡 : Probabilidade do tempo na fila no sistema ser maior do que t. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Distribuição Exponencial Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Distribuição Poisson Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Distribuição Erlang Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Distribuição Normal Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Distribuição Uniforme