Baixe o app para aproveitar ainda mais
Prévia do material em texto
. SIMULAÇÃO DE SISTEMAS Noções Sobre Teoria de Filas Jon Cambra Guinea e Pedro Matos da Silva 22/09/2016 Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas SIMULAÇÃO DE SISTEMAS Objetivo Geral da Aula Desenvolver conceitos (Noções) sobre Teoria de Filas de forma a contribuir com o estudo de “Simulação de Sistemas”. Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas SIMULAÇÃO DE SISTEMAS Objetivos Específicos da Aula ● Analisar definições de Teoria de Filas; Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas SIMULAÇÃO DE SISTEMAS Objetivos Específicos da Aula ● Analisar definições de Teoria de Filas; ● Relatar o início da História da Teoria de Filas; Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas SIMULAÇÃO DE SISTEMAS Objetivos Específicos da Aula ● Analisar definições de Teoria de Filas; ● Relatar o início da História da Teoria de Filas; ● Compreender a importância da Teoria de Filas na Simulação de Sistemas; Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas SIMULAÇÃO DE SISTEMAS Objetivos Específicos da Aula ● Analisar definições de Teoria de Filas; ● Relatar o início da História da Teoria de Filas; ● Compreender a importância da Teoria de Filas na Simulação de Sistemas; ● Classificar Sistemas de Filas distintos; Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas SIMULAÇÃO DE SISTEMAS Objetivos Específicos da Aula ● Analisar definições de Teoria de Filas; ● Relatar o início da História da Teoria de Filas; ● Compreender a importância da Teoria de Filas na Simulação de Sistemas; ● Classificar Sistemas de Filas distintos; ● Compreender a notação Kendal-Lee; Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas SIMULAÇÃO DE SISTEMAS Objetivos Específicos da Aula ● Analisar definições de Teoria de Filas; ● Relatar o início da História da Teoria de Filas; ● Compreender a importância da Teoria de Filas na Simulação de Sistemas; ● Classificar Sistemas de Filas distintos; ● Compreender a notação Kendal-Lee; ● Compreender as medidas de desempenho de um sistema de filas; Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas SIMULAÇÃO DE SISTEMAS Objetivos Específicos da Aula ● Analisar definições de Teoria de Filas; ● Relatar o início da História da Teoria de Filas; ● Compreender a importância da Teoria de Filas na Simulação de Sistemas; ● Classificar Sistemas de Filas distintos; ● Compreender a notação Kendal-Lee; ● Compreender as medidas de desempenho de um sistema de filas; ● Calcular medidas de desempenho para sistemas distintos usando Arena e “manualmente”. Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas . Definições 1. A Teoria de Filas é um ramo da Pesquisa Operacional que estuda as relações entre as demandas em um sistema e os atrasos sofridos pelo usuário desse sistema1. 2. A Teoria de 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 filas2. 1Arenales et al. 2007; 2 Wikipédia TEORIA DE FILAS Teoria de Filas. ● A Teoria des Filas tenta nos ajuda a encontrar um ponto de equilíbrio entre a satisfação do “cliente” e a “viabilidade econômica”. Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Benefícios da Teoria de Filas Teoria de Filas. ● A Teoria des Filas tenta nos ajuda a encontrar um ponto de equilíbrio entre a satisfação do “cliente” e a “viabilidade econômica”. ● A Teoria de Filas auxilia no projeto e na operação dos sistemas para encontrar um balanceamento adequado entre os custos de oferecer serviços no sistema e o custo dos atrasos sofridos pelos usuários; Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Benefícios da Teoria de Filas Exemplo da aula anterior Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Exemplo da aula anterior Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Exemplo da aula anterior Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Exemplo da aula anterior Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas . ● Pai da Teoria das Filas ● Nasceu e faleceu em Lonborg, Jutland na Dinamarca. Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Agner Krarup Erlang(1878 - 1929) . ● Primeiro trabalho publicado em 1909 “The Theory of Probabilities and Telephone Conversations”, provando que ligações telefônicas distribuídas aleatoreamente seguiam a distribuição de Poisson. Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Agner Krarup Erlang(1878 - 1929) . ● Vários de seus documentos foram traduzidos para o inglês, francês e alemão; ● Em 1917, “Solution of some Problems in the Theory of Probabilities of Significance in Automatic Telephone Exchanges”, continha fórmulas para perda e tempo de espera que são bem conhecidas na teoria de tráfego de telefonia. Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Agner Krarup Erlang(1878 - 1929) Filas em Simulação de Sistemas. Simulação Arena- Fabrica de Boxers e Meias (1:35 a 1:50) Miegsi Simulação 3 ano Hipermercado - Arena (0:30 a 0:50) Simulação de Um Aeroporto em Arena (2:40 a 3:00) Simulação: Projecto 2: Arena (Fabrica Textil - Boxers) (1:10 – 1:40) Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Teoria de Filas Principais elementos de uma fila3: ● Clientes: Que chegam ao sistema procurando um serviço; (solicitar exemplos) ● Servidores: Que prestam os serviços; (solicitar exemplos) 3 C. Perin Filho Definições Básicas e Classificação de um Sistema de Filas Teoria de Filas Diferentes tipos de sistema de filas Figura extraída de Arenales et al. 2007; Solicitar exemplos (i) fila única e um servidor Teoria de Filas Diferentes tipos de sistema de filas Figura extraída de Arenales et al. 2007; Solicitar exemplos (ii) fila única e múltiplos servidores em paralelo Teoria de Filas Diferentes tipos de sistema de filas Figura extraída de Arenales et al. 2007; Solicitar exemplos (iii) múltiplas filas e múltiplos servidores em paralelo Teoria de Filas Diferentes tipos de sistema de filas Figura extraída de Arenales et al. 2007; Solicitar exemplos (iv) fila única e múltiplos servidores em série Teoria de Filas Redes de Filas Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Simulação de um Hipermercado ● Genericamente, podemos ter redes de filas combinando sistemas de filas diversos em série e em paralelo Teoria de Filas Classificação de um Sistema de Filas Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Para descrever um sistema de filas, precisamos ESPECIALMENTE de informações sobre três elementos: Teoria de Filas Classificação de um Sistema de Filas Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Para descrever um sistema de filas, precisamos ESPECIALMENTE de informações sobre três elementos: ● Fonte de usuários: Processo de chegada com intervalos de chegadas modelados por uma distribuição de probabilidade;Teoria de Filas Classificação de um Sistema de Filas Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Para descrever um sistema de filas, precisamos ESPECIALMENTE de informações sobre três elementos: ● Fonte de usuários: Processo de chegada com intervalos de chegadas modelados por uma distribuição de probabilidade; ● Fila: A disciplina da fila (Ordem em que os usuários são atendidos). FIFO = FCFS, LIFO = LCFS, SIRO(Select In Random Order), etc... Teoria de Filas Classificação de um Sistema de Filas Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Para descrever um sistema de filas, precisamos ESPECIALMENTE de informações sobre três elementos: ● Fonte de usuários: Processo de chegada com intervalos de chegadas modelados por uma distribuição de probabilidade; ● Fila: A disciplina da fila (Ordem em que os usuários são atendidos). FIFO = FCFS, LIFO = LCFS, SIRO(Select In Random Order), etc... ● Dispositivo de Serviços(Atendimento): Processo de serviço descrito pelo tempo de serviço modelados por uma distribuição de probabilidade. Notação Kendall-Lee A / B / m / C / K / N Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Para simplificar a análise dos sistemas de filas, os mais simples foram classificados conforme a notação de Kendall-Lee, que considera sistemas de fila única com um ou mais servidores idênticos em paralelo (Arenales et al. 2007) Notação Kendall-Lee A / B / m / C / K / N Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Para simplificar a análise dos sistemas de filas, os mais simples foram classificados conforme a notação de Kendall-Lee, que considera sistemas de fila única com um ou mais servidores idênticos em paralelo (Arenales et al. 2007) ● As três primeiras características foram definidas em 1953 por D. Kendall; ● As três últimas foram definidas em 1968 por A. Lee Teoria de Filas Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Classificação do sistema de fila por suas características: Notação Kendall-Lee A / B / m / C* / K* / N* (A) : Distribuição de probabilidade do processo de chegada; (B) : Distribuição de probabilidade do processo de serviço; (m) : Número de servidores em paralelo; (C) : Disciplina da fila; (K) : Número máximo de usuários no sistema; (N) : Tamanho da população; * A ordem aqui apresentada está segundo Arenales et al. 2007 Teoria de Filas Exemplos de códigos para distribuições Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas M : Markoviana U : Uniforme Ek : Erlang Hk : Hiperexponencial A / B / m / C / K / N Teoria de Filas A / B / m / C / K / N Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas CÓDIGO DISCIPLINA DA FILA FCFS/FIFO First Come First to be Served LIFS/LIFO Last In First to be Served SIRO Select In Random Order RD Atendimento baseado em prioridade PRP Preemptive Priority NPRP Nonpreemptive Priority Teoria de Filas Exemplo 1 Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas M / M / 4 / LCFS / 30 / 500 ● Processo de chegada Markoviana ● Distribuição dos tempos de serviço Markoviano ● Quatro servidores ● "Último a Chegar, Primeiro a ser Servido" ● Capacidade para 30 clientes ● População de 500 clientes Teoria de Filas Exemplo 2 Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas M / M / 1 ● Processo de chegada Markoviana ● Distribuição dos tempos de serviço Markoviana ● 1 servidor ● "Primeiro a Chegar, Primeiro a ser Servido" ● Capacidade ilimitada ● População infinita M / M / 1 / FCFS / ∞ / ∞ Teoria de Filas Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Exemplo MM1 usando Arena Medida de desempenho Medida de desempenho de um sistema de filas Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas ● Taxa de Chegada dos Clientes ( λ ) ● Taxa de Atendimento dos Clientes ( μ ) ● Número médio de clientes na fila ( NF ) ● Número médio de clientes no sistema ( NS ) ● Tempo médio que o cliente fica na fila ( TF ) ● Tempo médio que o cliente fica no sistema ( TS ) ● Fator de utilização do servidor ρ = λ/(mμ ) Medidas para o modelo M / M / 1 Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Número médio de clientes na fila: NF = λ 2 μ(μ– λ ) Número médio de clientes no sistema: NS= λ μ – λ Tempo médio que o cliente fica na fila: TF = λ μ(μ– λ) Tempo médio que o clientes fica no sistema: TS= 1 μ – λ Para o modelo M / M / 1, dadas as taxas: Taxa de Chegada dos Clientes: λ Taxa de Atendimento dos Clientes: μ Teremos: Probabilide de o sistema estar com n clientesPn = ρ n(1−ρ) Medidas e Modelos Diversos Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Apresentaremos agora Pn e E(L) = NS para alguns modelos. Pn : probabilidade de haver n usários no sistema. E (L): Número médio de usuários no sistema. ● ● Medidas e Modelos Diversos Figura extraída de Arenales et al. 2007 Medidas e Modelos Diversos Figura extraída de Arenales et al. 2007 Medidas e Modelos Diversos Figura extraída de Arenales et al. 2007 Medidas e Modelos Diversos Figura extraída de Arenales et al. 2007 Medidas e Modelos Diversos Figura extraída de Arenales et al. 2007 Medidas e Modelos Diversos Figura extraída de Arenales et al. 2007 Medidas e Modelos Diversos Figura extraída de Arenales et al. 2007 Medidas e Modelos Diversos Figura extraída de Arenales et al. 2007 Teoria de Filas Exemplo da Aula de 08/09/2016 Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Votaremos agora ao exemplo de fila M/M/1 apresentado no material do Prof. Paulo Freitas – UFSC/CTC/INE. Relatório Arena - Simulação Teoria de Filas Exemplo do Cinema Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas . C. Perin Filho, Introdução à Simulação de Sistemas, Campinas (SP): Editora da Unicamp, 1995. M. Arenales, V. Armentano, R. Morabito & H. Yanasse, Pesquisa Operacional, Rio de Janeiro:Elsevier, 2007 Prado, Darci; Teoria das filas e simulação; INDG, 2009 “The Theory of Probabilities and Telephone Conversations”, Nyt Tidsskrift for Matematik B, vol 20, 1909 Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Referências . https://pt.wikipedia.org/wiki/Teoria_das_filas Acesso em 21 de setembro de 2016. http://www.erlang.com.br/brhistor.asp Acesso em 21 de setembro de 2016. https://dialnet.unirioja.es/descarga/articulo/5578365.pdf Acesso em 21 de setembro de 2016 http://www.inf.ufsc.br/~freitas.filho/cursos/Aula15-03-2005.pdf Acesso em 21 de setembro Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Referências . Simulação de Sistemas(MS614/MT702) Aula 3 – Noções sobre Teoria de Filas Referências Vídeos Simulação de Um Aeroporto em Arena https://www.youtube.com/watch?v=t7UaVydLg1s Simulação Arena- Fabrica de Boxers e Meias https://www.youtube.com/watch?v=FNa_XYGUTYk Simulação: Projecto 2: Arena (Fabrica Textil - Boxers) https://www.youtube.com/watch?v=ztsTrBMqeek Miegsi Simulação 3 ano Hipermercado - Arena https://www.youtube.com/watch?v=-i-MZETzMfM Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36 Slide 37 Slide 38 Slide 39 Slide 40 Slide 41 Slide 42 Slide 43 Slide 44 Slide 45 Slide 46 Slide 47 Slide 48 Slide 49 Slide 50 Slide 51 Slide 52 Slide 53 Slide 54 Slide 55
Compartilhar