Teoria das Filas

Apresentação descritiva da disciplina Pesquisa Operacional sobre o Tema : Teoria das Filas.

1. Teoria das Filas Pesquisa operacional II 1

2. Equipe: -> André Quadros -> Viviane Basílio -> Juliana Lorenzo -> Robson Pereira -> Juliete Soares 2

3. Introdução A teoria das filas é um ramo da probabilidade que estuda a formação de filas , através de análises matemáticas precisas e propriedades mensuráveis das filas. Ela provê modelos para demonstrar previamente o comportamento de um sistema que ofereça serviços cuja demanda cresce aleatoriamente , tornando possível dimensioná-lo de forma a satisfazer os clientes e ser viável economicamente para o provedor do serviço, evitando desperdícios e gargalos. 3

4. O sistema de filas pode ser: Rede de filas - Conjunto de entidades interligadas que oferecem serviços (centros de serviço) e de usuários (clientes). Rede com vários nós de comutação. 4

5. Centro de serviço - Representa os recursos do sistema , compreendendo um ou mais servidores e um conjunto de clientes que esperam pelo serviço. O sistema de filas pode ser: 5

6. Fila - Representa os clientes que estão esperando pelo serviço, juntamente com os que estão sendo atendidos pelos servidores. O sistema de filas pode ser: 6

7. Fila de espera - Somente os clientes que estão aguardando pelo serviço. O sistema de filas pode ser: 7

8. Estrutura Básica de um Modelo de Fila Fila ⇒ onde os clientes aguardam antes de serem atendidos . 1)Número máximo de clientes que a fila pode conter ( buffer): finito ou infinito. Disciplina da Fila ⇒ ordem que os clientes em fila são selecionados para atendimento . (FIFO), ( FCFS), ( LIFO ), (LCFS) ou filas com prioridades . Mecanismos de Atendimento (Serviço) ⇒ onde o cliente é atendido . 1)Número de instalações para atendimento. 2)Número de canais para atendimento (servidores) em paralelo para cada instante de atendimento. 3)Distribuição de Probabilidade para cada servidor (Exponencial). Fonte de Entrada ⇒ onde gera-se os clientes. 1)Tamanho da População: finita ou infinita. 2)Distribuição de Probabilidade que os clientes são gerados sobre o tempo (Poisson). 3)Distribuição de Probabilidade do tempo entre chegadas (Exponencial). 8

9. Sistema de filas Uma fila ocorre sempre que a procura por um determinado serviço é maior que a capacidade do sistema de prover este serviço. Um sistema de filas pode ser definido como: Clientes chegando; Cliente esperando pelo serviço; Cliente saindo do sistema após terem sido atendidos; Em teoria das filas "Cliente” é um termo genérico, aplicando-se não somente a seres humanos . O conceito pode abranger, por exemplo: Processos esperando para receber a CPU ; Pacotes que chegam a um roteador para serem encaminhados; Pessoas esperando no caixa do supermercado , etc. 9

10. Aplicações Existem diversas aplicações da teoria das filas, entre elas destacam-se: Prestação de serviços ( bancos , correios , lanchonetes ); Escalonamento ( pacientes em hospitais , programas em computadores ); Fluxo de tráfego ( aviões , carros , pessoas , comunicações ); 10

11. Componentes de um sistema de filas Processo de chegada O processo de chegada indica qual o padrão de chegada dos clientes no sistema. Apresenta comportamento estocástico , ou seja, as chegadas ocorrem no tempo e no espaço de acordo com as leis da probabilidade ; assim, é preciso conhecer qual a distribuição de probabilidade que descreve os tempos entre as chegadas dos clientes. A distribuição mais comum é a de Poisson , ou seja, os tempos entre as chegadas são exponencialmente distribuídos. Entre outras distribuições, estão a de Erlang , hiperexponencial e arbitrária . 11

12. Distribuição do tempo de serviço Assim como no processo de chegada, também é necessário conhecer a distribuição de probabilidade do tempo de serviço, sendo válidas as mesmas distribuições apresentadas. Da mesma forma que no processo de chegada, o padrão de serviço pode variar de acordo com o tempo. Por exemplo, a experiência adquirida com o serviço pode aumentar a produtividade ; o cansaço, por outro lado, pode diminuí-la. Caso não haja variação o padrão é estacionário. Componentes de um sistema de filas 12

13. Número de servidores Um centro de atraso ou Servidor infinito: É também conhecido como número de canais de serviço. Indica a quantidade de "pontos de atendimento" do sistema, de forma a servir aos clientes paralelamente. 13

14. Número de servidores Quando um sistema possui mais de um servidor podemos chama-lo de ( multiservidor ou multicanal ). Onde temos uma única fila para todos os servidores 14

15. Número de servidores Em um sistema de múltiplas filas, existe uma fila para cada servidor, como em um caixa de supermercado. 15

16. Pontos importantes num sistema de fila: Capacidade do sistema: 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. A capacidade pode ser infinita ou finita: População de usuários: Esse componente indica o número potencial de clientes que podem chegar a um sistema. Podendo ser finita ou infinita. 16 INFINITA: Não há restrinções quanto ao crescimento da fila; FINITA: Existe limitações físicas da quantidade de espaço na fila;

17. Pontos importantes num sistema de fila: Disciplina de atendimento: Descreve a forma como os clientes saem da fila de espera para serem atendidos. Algumas disciplinas são: FCFS ( First Come, First Served ): Primeiro a Chegar, Primeiro a ser Atendido. FIFO ( First In, First Out ): Primeiro a Entrar, Primeiro a Sair. LCFS ( Last Come, First Served ): Último a chegar, Primeiro a ser Atendido. LIFO ( Last In, First Out ): Último a Chegar, Primeiro a Sair. Fila com prioridade : A cada cliente é atribuída uma prioridade; clientes com maior prioridade têm preferência no atendimento e pode ser de dois tipos: Preemptivo : O cliente com maior prioridade é atendido imediatamente, interrompendo o atendimento ao cliente com menor prioridade. Ao terminar, o cliente de menor prioridade volta a ser atendido, podendo continuar o processo de onde parou ou então reiniciá-lo. Não-preemptivo : O cliente com maior prioridade é colocado no início da fila, recebendo o serviço somente quando o cliente em atendimento sai do sistema, mesmo se este for de prioridade mais baixa. 17

18. Distribuição de Poisson Normalmente usada para representar chegadas de clientes ao sistema e tempos de atendimento. Distribuição DISCRETA Distribuições Existe duas distribuições teóricas validas para aplicação em teoria das filas: 18 Distribuição Exponencial Normalmente usada para representar tempos de atendimento. Distribuição CONTINUA

19. Chegada de clientes ao sistema Segundo a distribuição de Poisson as chegadas se processam com a média de chegadas por tempo, os seus parâmetros são: 19 é o ritmo média de chegada IC é o intervalo médio entre chegadas

20. Padrão de serviço no atendimento O tempo de atendimento segue uma distribuição Exponencial Negativa, ou seja o número de atendimento segue uma distribuição de Poisson com média , seus parâmetros são: 20 é o ritmo média de atendimento TA é o tempo de duração médio dos serviços por atendimento

21. Notação Utiliza-se a notação de Kendall, proposta em 1953 , composta por uma série de símbolos da seguinte forma: 21 A/S/m/K/N/Q A : Distribuição dos tempos entre as chegadas (Processo de chegada) S : Distribuição dos tempos de serviço m : Número de servidores K : Capacidade do sistema N : Tamanho da população Q : Disciplina de atendimento Onde:

22. Calculo 22 Denota a taxa média de clientes chegando no serviço de filas È a taxa média de serviço (C Service) È a média de congestionamento do sistema Sendo assim:

23. Quando 23 O nº médio de chegada no sistema excede a taxa média de serviço do sistema e quando o tempo avança a fila se torna cada vez maior, impedindo qualquer situação de equilibrio. Sendo assim, para obter uma situação de equilibrio deve ser estritamente. As chegadas e serviços devem ser deterministicos e bem escalonada, assim a aleatoriedade impedirá que a fila se esvazie ou cresça sem limites. Observação: Quando a taxa média de serviço e a taxa média de chegada for conhecido, o nº médio de servidores paralelos requeridos para equilíbrio pode ser imediatamente calculado encontrando o menor C Service que satisfaça a equação.

24. 24 Com base em tudo que vimos, podemos avaliar o comportamento de um sistema de filas e seus parametros, como por exemplo: A probabilidade de haver clientes no sistema A probabilidade de que nº de cliente no sistema seja superior a um certo valor A probabilidade de que o sistema esteja ocioso A probabilidade de que o sistema esteja ocupado O nº médio de cliente no sistema O nº médio de cliente na fila O tempo médio de espera na fila por cliente O tempo médio gasto no sistema por cliente

25. Em um sistema de filas simples podemos ter 3 alternativas de tratamento Conclusão Achometria : Tratamento empregado de bom senso e um pouco de adivinhação. Tratamento analítico: Empregado a teoria das fila. Modelagem e Simulação. Que é uma ferramento poderosa devido a uma grande área de atuação e se fosse seguida conforme a teoria não teriamos no Brasil um sistema de servidores tão precario .

26. ¨Obrigado a todos pela atenção¨ 26