Baixe Teoria das Filas - Ednário B. de Mendonça e outras Notas de estudo em PDF para Estatística, somente na Docsity! ua ESTADUAL DA PARAÍBA Universidade Estadual da Paraíba Centro de Ciências e Tecnologia Departamento de Estatística Ednário Barbosa de Mendonça Teoria de Filas Markovianas e Aplicações Campina Grande Julho de 2014 Ednário Barbosa de Mendonça Teoria de Filas Markovianas e Aplicações Trabalho de Conclusão de Curso apresentado ao curso de Bacharelado em Estatística do Departamento de Estatística do Centro de Ciências e Tecnologia da Universidade Esta- dual da Paraíba em cumprimento às exigências legais para obtenção do título de bacharel em Estatística. Orientadora: Divanilda Maia Esteves Campina Grande Julho de 2014 Dedicatória Dedico a minha mãe, Ediane Alves Barbosa, por todo o apoio que ela tem me dado ao longo de toda uma vida e por todo o seu esforço em procurar fazer de mim uma pessoa melhor, e ao meu pai, José Nário Martins de Mendonça (in memorian). Agradecimentos A Deus pelas bençãos a mim concedidas e por nunca ter me desamparado ao longo de toda a minha vida. A professora Divanilda Maia Esteves, por me orientar na construção deste trabalho, por me conceder à oportunidade de participar de um Projeto de Iniciação Científica e por stativa no decor) ser sempre pr da minha carreira acadêmica, tirando minhas dúvidas e fazendo com que eu buscasse sempre o aprendizado de forma correta, no intuito de enriquecer meu conhecimento, preparando-me assim para o futuro. A família: minha mãe, que me ensinou o que é realmente importante na vida, que sempre me colocou em primeiro plano, que deixava de se presentear para me presentear em troca de um sorriso e um beijo e é a pessoa que mais amo nesse mundo, minha vó, Maria Odete Alves Barbosa, que está sempre ao meu lado, a minha noiva, Thuanne Barros de Oliveira, que me deu sempre força e apoio nos momentos difíceis, me entendia quando estava estressado e acreditou sempre em min quando ninguém mais acreditava, e aos meus tios, Hélio Alves Barbosa e José Israel Alves Barbosa, os quais também se fazem bastante presentes em minha vida. Aos demais professores da UEPB que passaram por minha graduação e tiveram sua parcela de contribuição na construção da minha carreira acadêmica, em especial, os professor Gustavo Henrique Esteves, Tiago Almeida de Oliveira, Ana Patrícia Barros Peixoto, João Gil de Luna, Ricardo Alves de Olinda, Onildo Freire, Vandik Estevam Barbosa e Francisco Guedes Aos colegas e amigos do “Busão” da cidade de Cubati-PB, os quais passei toda minha graduação viajando até Campina Grande-PB e aos meus colegas de turma. Resumo Um sistema de filas pode ser definido como um sistema onde “usuários” chegam a um posto de atendimento, buscando algum serviço. O tempo entre chegadas é uma variável aleatória e o tempo gasto para realizar o serviço é outra variável aleatória. Devido a esse caráter aleatório é impossível garantir que términos de serviços coincidam exatamente com chegadas de usuários. Consequentemente há vezes que o serviço completa sua tarefa com um usuário e não encontra mais ninguém disponível com quem trabalhar, tornando assim, o sistema ocioso. Outras vezes um usuário chega e já encontra o serviço ocupado com alguma chegada anterior, então ele poderá aguardar a sua vez ou partir. Isso dependerá da estrutura do sistema, pois em uma fila de banco, por exemplo, o cliente pode esperar, mas quando se trata de uma ligação telefônica simples, em geral, não há opção de espera. Esses são aspectos básicos das filas, mas essas estruturas podem ser mais complexas, considerando outras situações como sistemas com uma capacidade finita de espera ou cliente desistindo do serviço quando demora a ser atendido. Atualmente, este tipo de estudo tem se destacado, especialmente devido às leis estabelecendo um tempo máximo de espera por atendimento em bancos, supermercados e call centers. O objetivo do estudo das filas é estimar os parâmetros envolvidos no modelo e calcular algumas medidas de seu desempenho, como por exemplo, tempo médio que o usuário fica na fila ou tamanho médio da fila, considerando as particularidades de cada caso. Uma vez que se conhece tais medidas, é possível buscar sistemas que atendam eficientemente às necessidades de quem procura o serviço sem que o sistema fique ocioso por muito tempo. Neste trabalho, aplicou-se a teoria das filas Markovianas ao fluxo de pessoas em uma casa lotérica da cidade de Cubati-PB, com o objetivo de comparar as medidas de desempenho em dias que há pagamento do benefício Bolsa Família do Governo Federal com os dias normais, ou seja, em que não há pagamento do benefício. Palavras-chave: Filas Markovianas, Medidas de desempenho, Variável aleatória. 26.4 Modelo M/M/c/k/FIFO . ici 3 Metodologia 4 Resultados e Discussões 4.1 Modelagem do Sistema em Situação Normal de Funcionamento . .... 4.2 Modelagem do Sistema em Dias de Pagamento do Bolsa Família .... 4.3 Resumo Geral. ..cccccc 5 Conclusões Referências p.47 p.62 1 Lista de Figuras Representação esquemática de um sistema com fila o Lista de Tabelas Frequências observadas e esperadas do número de chegadas por minuto e cálculo da estatística X? para um dia normal de funcionamento Estimativa dos parâmetros e medidas de desempenho para dias normais de funcionamento Estimativas dos parâmetros e medidas de desempenho para um dia nor- mal de funcionamento, considerando a existência de apenas um posto de serviço Frequências observadas e esperadas do número de chegadas por minuto e cálculo da estatística X? Medidas de desempenho para dias de pagamento do Bolsa Família . Comparação entre as Medidas de Desempenho . o Ss 14 2 Fundamentação Teórica Boa parte deste trabalho consistiu em estudar a teoria envolvida no estudo das filas. Este capítulo contém alguns pontos importantes estudados. Primeiramente, serão apre- sentados os principais conceitos relacionados a Processos Estocásticos, Cadeias de Markov e Processos de Poisson, que são tópicos fundamentais para quem queira estudar Teoria de Filas. Em seguida, serão apresentados, de modo sucinto, algumas definições e resultados relacionados a essa teoria. 2.1 Processos Estocásticos De modo geral, pode-se dizer que um processo estocástico é qualquer processo que evolui de maneira aleatória. Mais formalmente, segundo Fogliatti e Mattos (2007), um processo estocástico (X(t) : t E T) é uma coleção de variáveis aleatórias, isto é, para cadat ET, X(t) é uma variável aleatória. O conjunto T é chamado conjunto de índices. O conjunto de todos os valores que as variáveis X(t) podem assumir é chamado espaço de estados S do processo estocástico. Frequentemente, o índice t é interpretado como tempo t, e por isso, em geral, X(t) é vista como o estado do processo no tempo t. Daí, de uma maneira alternativa, pode-se definir um processo estocástico como uma família de variáveis aleatórias que descreve a evolução de algum processo físico através do tempo. Se LX(t),t E Ty é um processo estocástico com espaço de estados S e conjunto de índices T', então considera-se que: e Se S for enumerável, o processo é dito discreto ou a valores inteiros (do inglês, integer-valued). Se S é um intervalo da reta (ou o próprio R) então dizemos que é um processo a valores reais (do inglês, real-valued) e Seo conjunto de índices T for enumerável, então dizemos que o processo é a tempo 15 discreto e, em geral, consideramos T = (0,1,2,...) e usamos (X,,n > 0) em lugar de (X(t),te TJ. Se T = [0,00), X(t) é dito um processo a tempo contínuo. Um aspecto importante que deve ser considerado é a estrutura de dependência asso- ciada à sequência de variáveis aleatórias. Em Estatística, um caso a se destacar é aquele em que as variáveis são independentes. Neste caso, o processo de inferência sobre os parâmetros envolvidos no modelo fica mais simples, uma vez que a distribuição conjunta das variáveis pode ser escrita como o produto das distribuições unidimensionais. Quando não se observa independência, busca-se descobrir o alcance e a forma de dependência. Um caso de dependência particularmente importante no estudo de processos estocásticos é a dependência de Markov. Definição 2.1 Um processo estocástico (X(t),t > Ok é dito ser markoviano se para to<h << P(X (tas) = tnalX (to) = 20, X (ti) = 21,...,X(tn) = un] = P(X (ta) = tn X (tn) = tn), para qualquer escolha x9,%1,..., ny em S e qualquer n. Isto quer dizer que, uma vez que conhecemos o estado atual da cadeia, os estados passados não influenciam o futuro. E possível generalizar um pouco mais esse caso, dizendo que um processo estocástico EX(t),t > 0) é markoviano de ordem k se paraty< ty <--:<tnm, P(X(t) = an X(to) = 2x0, X (ti) = 21,...,X(tn-1) = tn] é igual a P(X (ta) = en|X (tap) = Uno. X(tam) = nm], para qualquer escolha xo, a1,...,Yny1 em S e qualquer n. Isto quer dizer que o estado atual da cadeia é influenciado pelas k observações mais recentes do processo. Um processo Markoviano que possui o espaço de estados discreto é denominado Cadeia de Markov. O comportamento da Cadeia de Markov (X(t) :t € T) de parâmetro contínuo com espaço de estados discreto, o qual pode ser considerado sem perda de generalidade como S = (0,1,2,...), é caracterizado pela distribuição inicial X(to)=1, 1=0,1,2,..., onde to é o instante inicial de observação, e pelas probabilidades (condicionais) de transição 16 entre os estados i e n, Pin(v, 2), definidas por: Pnlv2)=PlX(2)=n|X(0)=i), 0O<v<z, v,zeT ines, com: 1, sei=n, Polos = (a 0, caso contrário 2.2 Cadeias de Markov Uma Cadeia de Markov é um Processo Estocástico com espaço de estados discreto. Se o conjunto de índices for um conjunto enumerável, então tem-se uma Cadeia de Mar- kov a tempo discreto, caso contrário, tem-se uma Cadeia de Markov a tempo contínuo. Frequentemente, no caso de Cadeias de Markov, usa-se a notação (Xn,n E NJ em lugar de (X(t),t > 0). Definição 2.2 Um processo (X, :n > Oy assumindo valores em um conjunto S é uma Cadeia de Markov se dado o estado presente, o futuro não é influenciado pelo passado, ou seja, PlXim =tnnlXo = 29, X=01,0,Xn=0 = P(Xan = Una])X = Un). Além disso, a Cadeia de Markov será dita homogênea no tempo se PM Xan =X =0)=P(M =yXo=a) (21) para qualquer n > 0. A probabilidade dada pela Equação (2.1) é chamada probabilidade de transição a um passo da cadeia e para facilitar a notação, usa-se P(Xar = 0X =) = PG = yXo= 2) = P(0,9), ao que lê-se: a probabilidade de ir do estado x ao y em um passo. 19 ii) Se o estado x se comunica com o estado y, isso implica que o estado y se comunica com o estado 1. iii) Se o estado «x se comunica com o estado y e o estado y se comunica com o estado z, então o estado x se comunica com o estado 2. Definição 2.7 Uma Cadeia de Markov é dita ser irredutível se existe apenas uma classe, isto é, se todos os estados se comunicam entre si. Definição 2.8 Sea é tal que P(x,x) = 1, então a é um estado absorvente. Para cada estado x E S, seja P, a probabilidade de que, começando no estado x, o processo volte a atingir o estado x em algum tempo, isto é, P,= P(X, = x, para algum n > 1X = 2). Definição 2.9 Um estado « é dito recorrente se P, = 1. Se P, <1, então x é dito transitório. Proposição 2.1 O estado x é recorrente se, e só se, > 14 P"(x,1) = 00. Isto implica que, seS 4 P"(x,x) < 00, então o estado é transitório. Corolário 2.1 Seo estado « é recorrente e o estado y se comunica com o estado x, então o estado y é recorrente. Teorema 2.2 Se C CS é um conjunto finito fechado irredutível de estados, então todo estado de C é recorre Uma consequência dos resultados acima é que um estado transitório é visitado um número finito de vezes (daí o nome transitório). Isso implica que toda cadeia com espaço de estados finito deve ter pelo menos um estado recorrente. Além do mais, se a cadeia tiver espaço de estados finito e for irredutível, então todos os seus estados são recorrentes. 2.2.2 Medida Invariante Definição 2.10 Considere (Xn :n > 0) uma Cadeia de Markov com espaço de estados S e função de transição P. Se n(x), v ES é tal que r(2)>0, ves 20 além disso 3 r(0)P(2,9) = (9) (2.2) zes então 7 é chamada medida invariante da cadeia. A Equação (2.2) pode ser escrita na forma matricial como nP=7, onde P é a matriz de transição da cadeia e 7 = (r(0), 7(1),7(2),...). Como consequência da definição, vemos que erP=7, erP=-7PP=7P=7, e c de maneira geral TP” = 7, para todo n > 1. Além do mais, se 79 = 7, então 7, = 7 para qualquer n > 1. 2.3 Processo de Nascimento e Morte De acordo com Fogliatti e Mattos (2007), uma Cadeia de Markov homogênea, irre- dutível, de parâmetro contínuo, é denominada Processo de Nascimento e Morte (Birth- Death Process) para todo n > 0 se, P(n,n+1)=A, P(mn-1)=1-A.= tn P(n,k) =0, para qualquer k Zn -— ln +1. Em outras palavras, as únicas transições permitidas, em uma unidade de tempo, a partir de um determinado estado n são para seus vizinhos imediatos n — 1 ou n +1. Quando a transição ocorre para estado n + 1 representa um nascimento, e para o estado n — 1, uma morte. Para Processos de Nascimento e Morte, as seguintes hipóteses são válidas: 1. no instante inicial to = 0, o sistema está vazio, isto é, N(0) = 0; 21 2. nascimentos e mortes são eventos estatisticamente independentes; 3. dado que o sistema está no estado n, no intervalo de tempo (t,t + At), At tão pequeno quanto se queira, a probabilidade de ocorrer: (a) um nascimento é igual a À, At + o(At); (b) uma morte é igual a At + o(At); (c) mais de um evento (nascimento(s) e/ou morte(s)) é desprezível, igual a o(At), onde, o(At) =0. dm, At Usando a notação: PP(At) = P(ocorrência de i nascimentos em At) PP(At) = Pfocorrência de j mortes em At), a terceira hipótese pode ser reescrita da forma a seguir: PR(At) = A At + o(At), Yn=0,1,2,. (2.3) PP(At) = unAt+Ho(At), Yn=1,2,... (2.4) PAPAS) = (At), Vijlli+j)> 1 (2.5) De (2.3), (2.4) e (2.5) obtêm-se as probabilidades de não haver nascimentos, Equação (2.6), nem mortes, Equação (2.7), em intervalos pequenos de tempo, At: PIA =1-MAt-o(Ab), Yn=0,1,2.. (2.6) PR(A)=1—unAt—o(At), Yn=1,2,... (2.7) Com essas hipóteses, determinam-se, para todo n, as probabilidades P, dos estados do processo, como mostrado a seguir. Dividindo-se o intervalo de observação (0,t + At) em dois subrintervalos disjuntos (0,t] e (t,t+ At), verifica-se que o sistema está no estado n > 0 no instante (t+ At), para At pequeno, se ocorre um dos seguintes eventos mutuamente excludentes: 1. no instante t, o sistema está no estado n e, no intervalo de tempo (t,t + At), não há nenhum nascimento e nenhuma morte; 24 de onde se conclui que a P= ll mo" >1. (2.17) Como >” P,=1, obtém-se: n>0 1 h=———— (2.18) +51 Hi n>1 i=1 desde que a soma do denominador de (2.18) seja convergente. A partir das Equações (2.17) e (2.18), tem-se a distribuição limite dos estados do sistema (Py, P,, Po, ...), que é também a distribuição do estado do regime estacionário do processo, totalmente determinada pelas taxas de nascimento e morte. As equações (2.14) e (2.15) são denominadas equações de balanço ou de equilíbrio, onde o princípio da conservação de energia é válido, ou seja, para cada estado, “o fluxo de quem entra é igual ao fluxo de quem saí”. Dessa forma, para qualquer estado n > 1, tem-se: Ana Pn-1 + Una Pas = AnPh e para cada estado n = 0, AP = mP. 2.4 Processo de Poisson Um Processo de Poisson ou de Nascimento Puro é uma Cadeia de Markov de parâmetro contínuo onde a única mudança permitida a partir de qualquer estado n é para o estado n-+1 e se processa com uma taxa constante. Então, esse processo pode ser modelado de forma análoga a um Processo de Nascimento e Morte, considerando-se as taxas de nascimento A, = À, Yn e as taxas de morte gn = 0, Yn > 1. Para o Processo de Poisson, as hipóteses consideradas para o Processo de Nascimento e Morte são válidas, a saber: 1. no instante inicial to = 0, o sistema está vazio, isto é, N(0) = 0; 2. dado que o sistema está no estado n, no intervalo de tempo (t,t + At), At tão pequeno quanto se queira, a probabilidade de ocorrer: (a) um nascimento é igual a À, At + o(At); (b) mais de um evento (nascimento(s)) é desprezível, igual a o(At), onde, lim At) Ato At =0. As hipóteses 3a) e 3c) acima podem ser reescritas como, Pi(At) = AAt+ o(At), (2.19) P(A) = (At), Vi>1. (2.20) A partir das hipóteses 1 e 2, de (2.19), de (2.20) e utilizando-se o Teorema da Proba- bilidade Total, têm-se: P(t+ At) = Pit) Po(At) + Pa (t) P(A) + (At) = (1 ABB, (t) + AMP, (t) +o(At), n>1, o que implica que Pt+ AS) = PO) P(A) + o(At) = Pol) — MAL) + (AS). Usando um procedimento análogo àquele usado para Processos de Nascimento e Morte, pode-se escrever: Pilt+ At) — Put) o(At) O = P(D+APa(t Yn>1 Ar n(b) + APama(t) + AE NZ . (t+ 80) - Pi) (1) Pt+ At) - Pt o(At D+ = —APo(t . At d+ a Tomando-se os limites quando At > 0, têm-se: dPlt O e) Pa(b) WMA, dPo(t “O — an, (2.21) que constituem um sistema infinito de equações diferenciais. A solução da Equação (2.21) é dada por: Pilt)= e. (2.22) 26 Resolvendo-se (2.21) recorrentemente, têm-se: Pit) = Me, At 2e-M po = MD, At 3e-M puto = QE, de onde, por indução, (ret nt P()= MO. Observa-se que a variável aleatória discreta que representa o estado do processo em um intervalo de comprimento t segue uma distribuição de Poisson de parâmetro At, com valor esperado dado por: EW(=X* O Processo de Poisson pode ser descrito de forma equivalente pela caracterização do tempo entre mudanças sucessivas como uma variável aleatória exponencial: seja 7 a variável aleatória que representa o tempo entre ocorrências sucessivas em um Processo de Poisson de taxa À, e seja N(t) a variável aleatória que representa o número de ocorrências num intervalo de tempo de comprimento t. O evento (T > t) é equivalente ao evento (N(t) = 0), então: P(T>)=P(N()=0)=Pi(b. (2.23) De (2.22) e (2.23), pode-se determinar a função de distribuição acumulada de 7, F()=1-P(T>)=1-P()=1-€"%, t>0 e a função de densidade de probabilidade, — dF(t) =D =" t> ft) Em Ae t>0 que é a função de densidade de uma variável aleatória com distribuição exponencial de parâmetro À. Reciprocamente, se os tempos 7 entre mudanças sucessivas são variáveis aleatórias independentes, idênticas e exponencialmente distribuídas de parâmetro À, a variável 29 fruíram dessa técnica, destacando-se, entre outros, problemas de congestionamento de tráfego, escoamento de fluxo de carga de terminais, carregamento /descarregamento de veículos, escoamento e fluxo de processamento de informações, formação de estoques, comunicação de computadores. Dentre os trabalhos precursores desenvolvidos em diferentes áreas, podem-se citar, as modelagens apresentadas nas referências: Adams (1936) e Tanner (1951), para o cálculo do tempo médio de espera de pedestres para atravessar uma rua sem sinal; Everett (1953), para o problema de escoamento de fluxo de barcos em terminais portuários; Cobham (1954), para o problema de reparo de maquinárias; Bailey (1954), para o problema de escoamento do fluxo de pacientes na emergência de um hospital; Morse (1962) e Prabhu (1965), para o problema de formação de estoques; Bitran e Morabito (1996), para sistemas de manufaturas. A partir de 1960, a Teoria de Filas foi também utilizada para modelar problemas con- cernentes à Ciência da Computação, Ramamoorthy (1965) e Courtois (1977). Destacam-se a partir de 1980, as aplicações a redes de filas, Gelembe e Pujolle (1987) e Walrand (1988); em comunicação de computadores, Daigle (1991) e em provedores de internet, Fontanella e Morabito (2001). Das publicações em português sobre Teoria de Filas, podem-se mencionar Novaes (1975), que apresenta aplicações direcionadas ao Planejamento de Transportes, e MA- GALHÃES (1996), que trata de modelos de redes de filas frequentemente aplicados à Ciência da Computação. 2.5.1 Estrutura Básica de um Sistema com Fila Um sistema com fila é composto por usuários, por canais ou postos de serviço /atendimento e por um espaço designado para a espera. Os usuários chegam segundo um determinado comportamento que caracteriza o pro- cesso de chegadas, para serem atendidos em canais ou postos de serviço (que funcionam em paralelo) segundo um padrão de atendimento. Enquanto os postos estão ocupados, os usuários aguardam numa única fila em um espaço designado para tal. Assim que um canal de serviço fica livre, um dos usuários da fila é chamado para atendimento segundo um critério estabelecido pela gerência. Uma vez completado o serviço, o usuário é liberado do sistema. A Figura 1 representa esquematicamente um sistema com fila. 30 Sistema de filas Fonte de | Clientes entradas > Fila Mecanismo Clientes de atendimento atendidos Figura 1: Representação esquemática de um sistema com fila O processo de chegadas dos usuários é especificado pelo comportamento do fluxo de chegadas dos mesmos ao sistema. Segundo Fogliatti e Mattos (2007), se são conhecidos o número de chegadas e os instantes de tempo em que elas acontecem, esse processo é denominado determinístico, caso contrário, tem-se um comportamento aleatório consti- tuindo um processo estocástico caracterizado por uma distribuição de probabilidade. O caso mais comum e simples, é quando se considera que os clientes chegam segundo um processo de Poisson. O processo de atendimento é especificado pelo comportamento do fluxo de usuários e a sua caracterização é análoga à do processo de chegadas. Os canais ou postos de serviço são os locais onde são atendidos os usuários. O número de postos de um sistema pode ser finito ou infinito. Como exemplo do primeiro caso, podem-se citar os guichês de um posto de pedágio, para o segundo caso, qualquer aten- dimento do tipo self-service, onde cliente e servidor são a mesma pessoa e onde o serviço está sempre disponível. Segundo Fogliatti e Mattos (2007), a capacidade do sistema é o número máximo de usuários que o mesmo comporta (incluindo fila e atendimento) e pode ser finita ou infinita. Quando a capacidade é finita, os clientes que chegam ao sistema após a capacidade máxima ser atingida são rejeitados. Para o caso de capacidade infinita pode-se citar a espera de navios em ambiente aquaviário para descarregamento em um porto. 31 2.5.2 Disciplina de Atendimento A disciplina de atendimento consiste na maneira pela qual os usuários que estão na fila são selecionados para serem atendidos. Os tipos de disciplinas de atendimento mais utilizados são: FIFO (first in - first out): os usuários são atendidos na ordem das chegadas. Essa disciplina de atendimento é a mais comumente adotada. e LIFO (last in - first out): o primeiro usuário a ser atendido é o que chegou por último. e PRI (priority service): o atendimento aos usuários segue uma ou mais prioridades preestabelecidas pela gerência do sistema. e SIRO (service in random order): o atendimento aos usuários segue uma ordem aleatória. Vale salientar que há outros tipos de disciplinas de atendimento, inclusive conside- rando aspectos como atendimento prioritário e desistências. No entanto, como este é apenas um estudo introdutório, tais modelos não foram vistos. 2.5.3 Notação de um Sistema com Fila A notação utilizada neste trabalho para descrever um sistema com fila é a notação encontrada em boa parte da literatura clássica de estudo de filas e foi proposta por Ken- dall (1953). Considera-se a forma A/B/C/D/E, onde A e B denotam, respectivamente, as distribuições dos tempos entre chegadas sucessivas e de atendimento, C e D deno- tam o número de postos de atendimento em paralelo e a capacidade física do sistema, respectivamente e E, uma das siglas que representam as disciplinas de atendimento. Como exemplos de escolhas para 4 e B, podem-se citar: e D: distribuição determinística ou degenerada; e para comportamento aleatório; M: distribuição exponencial (Memoryless ou Markoviana): e E;: distribuição Erlang do tipo k; G: distribuição geral (não especificada). 34 Da Expressão (2.28), observa-se que o número de usuários no sistema segue uma distribuição geométrica modificada de parâmetro (1 — p) com valor esperado dado por: (2.29) Conforme apresentado na Seção 2.5.4, as medidas de desempenho de um sistema em regime estacionário auxiliam na avaliação da produtividade e no dimensionamento do mesmo. Serão apresentadas a seguir algumas medidas de desempenho correspondentes ao modelo M/M/1. Número médio de usuários no sistema (L) Seja N a variável aleatória discreta que representa o número de usuários no sistema no regime estacionário, com distribuição de probabilidade (P,),n > 0 e valor esperado L. Tem-se, então: L= EN) =Dar, n=0 Usando a Equação (2.28), segue que oo a L=(1-0)5) mp” = (1005 um (1-p p3 E n=0 n=1 n=1 oo Se p<1, então > Pp” converge e então, n=0 Des (5). n=1 n=0 Dessa forma, L=(1-0) e E (50) =( Dea (5) =(1 “oe n=0 De onde se conclui que o que confirma a expressão (2.29) Número médio de usuários na fila (Lg) Seja N, à variável aleatória discreta que representa o número de usuários na fila no regime estacionário e Lg seu valor esperado. Então, N-1, VNBI1, N= 0, N=0, de onde L=EN]=5> (n-1DP,= Soup, - DB=L-1+P) n=1 n=1 n=1 p p=0+P p => —1l+l-p=>>———— — . 1-p (1-0) (1-9) Probabilidade de se ter mais do que k elementos no sistema Apesar de se tratar de um sistema com capacidade infinita, estas probabilidades são úteis para se avaliar a necessidade de incluir certas comodidades no local reservado para a fila, como cadeiras, banheiros ou outras instalações. Para este sistema particular de fila, vale pwz)-De=Drt-9=-0-056" n=k n=k 1=0 k pl =(1-p)p ”M = (1-p)p 1=p' i=0 de onde segue que Função de distribuição acumulada do tempo de espera na fila (Wa(t)) Considerando-se o sistema no regime estacionário, seja T, a variável aleatória contínua que representa o tempo que um usuário qualquer permanece na fila aguardando por aten- dimento. Esse tempo depende do número de unidades que se encontram à sua frente e do tempo que essas unidades levam para ser atendidas. Na chegada de um usuário no sistema, podem ser identificados dois eventos mutua- mente excludentes: 36 1. O sistema está vazio, então, T, = 0; 2. Há n elementos no sistema, n > 0, então, T, > 0. Seja W,(t) a função de distribuição acumulada de T, que expressa a probabilidade de um usuário qualquer aguardar na fila no máximo um tempo t > 0. Então, Walt) = PT, < 0). VWA)=PMT<O)=PN=0=PB=1-p eparat>0, oe Walt) = >” P(n usuários no sistema e os n serviços completados até t). n=0 O evento “n serviços completados até !” é equivalente ao evento “o tempo para com- pletar n serviços é menor do que t”. Seja T(m) à variável aleatória contínua que representa a soma dos tempos de atendi- mento de n usuários consecutivos. Os tempos de serviço são independentes e exponencial- mente distribuídos com taxa |t, consequentemente T(,) segue uma distribuição de Erlang de parâmetros n e |. Então, Vt > 0, Walt) = Wil0) + >” Pl[(n usuários no sistema N (T(n) <t))] n=1 oo = P+ >” PiP(Tm < tn usuários no sistema] n=1 t n—1 5 te n( nua) —uz E-p+ . on(J non" te) n=1 acneêca (030 a er) a n=1 t =(1-p)+p(1- ou f et Nedo, o Sabendo que (ju — À) = u(1 — p), tem-se: Wd) =(1= 9) + 0 — pele =1- pe, (2.30) 39 2.6.2 Modelo M/M/1/k/FIFO O modelo M/M/1/k/FIFO será representado como M/M/1/k para simplificar a notação. Tal modelo é caracterizado por: e tempos entre chegadas sucessivas e os tempos de atendimento seguem distribuições exponenciais de parâmetros À e ju, respectivamente; e existe um único posto de atendimento; e o usuário é atendido conforme sua ordem de chegada; e a capacidade do sistema é limitada a k usuários no sistema. Neste modelo, as chegadas e os atendimentos caracterizam um Processo de Nascimento e Morte. Entretanto, a taxa de ingresso ao sistema, No difere da taxa de chegada para n > k, tendo em vista a existência da limitação na capacidade do sistema (igual a k). Neste caso, as taxas de ingresso e de atendimento são dadas respectivamente por: n x A, 0O<n<k, 0, n>k Un=t, YnDl. Para o estado de regime estacionário do sistema, tem-se: Plt)=Pa 0<n<h. Substituindo, em (2.17), x, e gm pelos seus respectivos valores, tem-se: mn” E) Po, 0O<n<k. u 40 De (2.18), fazendo p = 2, tem-se: nº 1 >” n=0 Po A soma finita do denominador sempre converge, porém para valores distintos, dependendo de p. Dessa forma, 1 — mr SCp= 1, P= (2.36) Str sepfl, de onde, VO< n < k E sep=1, P= (2.37) Qp)p” Tm Sepfl, Conforme apresentado na Seção 2.5.4, as medidas de desempenho de um sistema em regime estacionário auxiliam na avaliação da produtividade e no dimensionamento do mesmo. Serão apresentadas a seguir algumas medidas de desempenho correspondentes ao modelo M/M/1/k. Número médio de usuários no sistema (L) Por definição k L=EIN|=5 np, n=0 Usando (2.36) e (2.37), e supondo que p = 1, LP MRE) Gm (hk+1) (k+1) 2 2 41 Sepfl, k (=) n= 20-95) »no 1 k k | U-0p d n UP do ope) do” = (pop (1) 1 1-» (Lo) [== Mk + 1)98 41 — bt] (1 t+) (1-0)? ol ht! — th + 1)] (= 0) — t+!) Em resumo, tpm , sep=1 L=- (2.38) pll+kpk+ = pé (k+1)] Carga) + Sep fl. Número médio de usuários na fila (Lg) Sabendo que tem-se que k k k LD (n-DR=S nk-SIR=L-1+P, n=1 n=0 n=1 sendo que L é dado por (2.38). Tempo médio de permanência no sistema (W) Para se usar a fórmula de Little (2.33), deve ser feita uma modificação, pois, por existir limitação do espaço reservado para a fila, rejeições acontecem com taxa AP, cada vez que o sistema atinge o estado k. Dessa forma, a taxa de ingressos, À, não coincide com a taxa de chegadas, À. A taxa de efetivos ingressos )', é dada por NX=A-AP,=MI-Pj), que substituída em (2.33) leva a 44 2.6.2.1 Caso particular M/M/1/1/FIFO Neste caso, o sistema não admite fila, ou seja, enquanto o único servidor estiver ocupado, novos usuários são impedidos de entrar no sistema. Então existem apenas dois estados: n=0 en = 1. Tem-se neste caso, para qualquer p, Como Bh +P, =1, tem-se P = pPo. 1 P,> “O (+) p P = “O (1+2) 2.6.3 Modelo M/M/c/co/FIFO No modelo M/M/c/c0/FIFO, de acordo Fogliatti e Mattos (2007), os tempos entre chegadas sucessivas seguem distribuições exponenciais de parâmetro À e há c servidores, cada um dos quais com tempos de atendimento que seguem distribuições exponenciais, de parâmetro js. Como as chegadas e os atendimentos neste caso caracterizam Processos de Nascimento e Morte, logo as taxas de chegadas e de atendimento respectivamente são dadas por: MA Vn>O (2.39) nu, sel<n<c, tu = ( t (2.40) cu, sen >c. Denotando r = à, a taxa de utilização do sistema é dada por: r p=-"=—. c Substituindo (2.39) e (2.40) em (2.17), obtém-se: o ni T» sel<n<c, o que implica que A soma converge se p < 1. Nesse caso, tem-se: oo c1on c Enc) as] 1— n=0 n=0 p -n(Stas)) oe Como ) P,=1,então, n=0 + 1 5) (2.41) Serão apresentadas a seguir algumas medidas de desempenho correspondentes ao mo- delo M/M fc. Número médio de usuários na fila (L,) Para este modelo, tem-se que Port! cle Pr cle Usando a Fórmula de Little (2.33) e as relações (2.34) e (2.35), obtêm-se as demais medidas de desempenho: 46 , 1 eus . Ho e Número médio de usuários no sistema: L=r+ [=E5s] Pa. e Tempo médio de espera na fila: W,= ts Po. e Tempo médio de permanência no sistema: W= + + [ent] Po. Função de distribuição acumulada, W,(t) do tempo de espera na fila Considere T, como sendo o tempo de espera na fila de um usuário qualquer. Como há c postos de atendimento, então T, será zero quando o número de usuários à frente do usuário considerado for menor ou iguala c— 1, ou seja, c-1 con P(M=0=P(N<e-)=5)R=R5 5. n=0 n=0 Neste caso, definindo W,(t) como a função de distribuição acumulada de T, e usando a Equação (2.41), segue que cre WO) =P(L=0)=1-Po-——. dO) = Pl =0)=1- Pis De acordo com Fogliatti e Mattos (2007), o tempo T, que um usuário aguarda na fila é positivo e no máximo t unidades de tempo se esse usuário encontra à sua frente n usuários com n > ce os servidores completam pelo menos (n — c— 1) serviços até t. Desta forma, calcular a probabilidade de que n serviços sejam completados até o tempo t é o mesmo que calcular a probabilidade de que o tempo para completar n serviços seja menor do que t. Assim, definindo a variável aleatória Tn) : soma dos tempos de atendimentos de n usuários consecutivos, então, dado que os tempos de serviço são exponenciais com taxa t, T(n) segue uma dis- tribuição de Erlang de parâmetros n e u. Portanto Wit) = PT, < 0), 49 Caso contrário, se 2 £ 1, então, c Pyet La = cle Pyet cle Poet d de I Pretto (O) = Mk = c+ (ge + (Etr) de 1-0) R nes Número médio de usuários no sistema (L) E possível desenvolver a fórmula do número médio de usuários na fila da seguinte forma. Por definição, k k k => (n-o)P, =S)nP,-c3 SP Como k k Dr=1 e L=Snh, n=0 n=0 segue que e e L= (1-Dun) -c (e) n=0 n=0 e e e-1 =L-— nPa-c+cS PL — (n—-c)P,-—c, n=0 n=0 n=0 de onde se conclui que c- L=L,+c+5 (n-o)P,. n=0 Tempo médio de espera na fila (W,) Utilizando as fórmulas (2.33) e (2.35) e lembrando que existe limitação no espaço físico reservado para a fila, tem-se L m== A com = — Pj). Tempo médio de permanência no sistema (W) Por fim, vê-se que o tempo médio de permanência no sistema é dado por L W=— x com N=X1-Pj). Caso Particular: M/M/c/c/FIFO Este caso considera que a capacidade do sistema é igual ao número de postos de atendimento, ou seja, o cliente chega e só entrará no sistema se algum posto de atendi- mento estiver livre. Como não é permitida a formação de fila, as taxas de ingresso e de atendimento do sistema são dadas respectivamente por: A, 0O<n<c, A = 0, n>c, e Un=nu, 1<n<c. Denotando r = à e substituindo essas taxas em (2.17), tem-se: pr P=P 0O<n<e, n! de onde, ein = n=0 e é conhecida como a fórmula de perda de Erlang (Erlang, 1917) e corresponde à percenta- gem de usuários rejeitados pela limitação física dos sistema. 3 Metodologia Este trabalho dividiu-se em duas partes: na primeira parte foi realizado um estudo teórico do conteúdo proposto e, num segundo momento, foi feita uma aplicação da Teoria das Filas num conjunto de dados real. No que se refere ao estudo teórico, inicialmente, foi preciso fazer uma revisão apro- fundada das distribuições de proabilidade a serem utilizadas: Poisson e Exponencial. Em seguida, foi feito um estudo sobre Processos estocásticos, com ênfase nas Cadeias de Mar- kov e Processos de Poisson. Logo após, o foco foi direcionado em cima dos principais conceitos e dos modelos básicos de filas Markovianas. Toda essa revisão teórica foi feita tomando como base os livros Ross (2007) e Fogliatti e Mattos (2007). A segunda parte é referente a aplicação da Teoria de Filas e cálculo das medidas de desempenho. Várias aplicações foram cogitadas, mas descartadas pela dificuldade de se co- lher os dados. Por fim, decidiu-se modelar os atendimentos em uma casa lotérica localizada na cidade de Cubati-PB. O estabelecimento utilizado foi uma casa lotérica constituída por dois postos de atendimento, a qual se encaixa no modelo de fila M/M/2/00/FIFO. O estabelecimento era motivo de constantes reclamações por parte de seus clientes, devido à demora que os mesmos levavam para serem atendidos em dias de pagamento do benefício Bolsa Família do Governo Federal. Com a definição do problema, foram escolhidos dois dias no mês, considerados pela gerência do estabelecimento representativos do comporta- mento do sistema, para a coleta dos dados. O primeiro dia é referente ao funcionamento do sistema em situação normal, já no segundo dia, havia pagamento do Bolsa Família, o que logicamente causa aumento na fila de espera pelo serviço. Foram observados os tempos entre chegadas sucessivas dos clientes e os tempos que cada um levava em aten- dimento. Após o colhimento dos dados, foram calculadas as taxas de chegadas sucessivas e de atendimento referentes aos dois dias e suas respectivas medidas de desempenho, no intuito de compará-las para se obter conclusões sobre o funcionamento do sistema e consequentemente propor melhorias ao mesmo. Vale salientar que todos os cálculos e gráficos presentes neste trabalho foram feitos utilizando o software R, que pode ser obtido 54 atendimentos ocorrem segundo um processo de Poisson. Para verificar se tal suposição era plausível, propôs-se o uso de um teste Qui-quadrado de aderência, cuja descrição pode ser encontrada em livros de estatística, tais como Bussab e Morettin (2002). Primeiramente as hipóteses formuladas para a execução deste teste foram: Ho: As chegadas do clientes se adequam a uma distribuição de Poisson H,: As chegadas do clientes não se adequam a uma distribuição de Poisson As frequências do número de chegadas por minuto foram calculadas e apresentadas na OO: 2 Tabela 1, no intuito de calcular-se a estatística X2 — é e compará-la com o quantil de uma X2:95%) . Tabela 1: Frequências observadas e esperadas do número de chegadas por minuto e cálculo da estatística X2 para um dia normal de funcionamento Nº de chegadas por minuto | Frequência observada O; | Frequência esperada O. ; 0 305 307,67 0,02317 1 76 69,66 0,57703 2 6 Ts 0,39116 Total 387 385,07 0,99136 Tivemos que x? = 0,99136 < X95%) = 5,991, logo, aceitamos a hipótese nula, portanto, não há evidências significativas para não se levar em consideração que os o número de chegadas por minuto segue uma distribuição de Poisson ao nível de 5% de significância. Uma vez que foi estabelecido o modelo de fila que será utilizado, serão estimados os parâmetros do modelo (A e 4) e calculadas as medidas de desempenho para o mesmo. As medidas de desempenho para dias normais de funcionamento foram calculadas e são mostradas na Tabela 2. Podemos ver, entre outras coisas, que a taxa de chegadas é o menor que a taxa de atendimento e também que a probabilidade de formação de fila baixa. Outro ponto que vale a pena ser destacado é que p < 1, o que é uma condição a considerada no desenvolvimento da teoria apresentada. a = Tabela 2: Estimativa dos parâmetros e medidas de desempenho para dias normais de funcionamento Medidas de desempenho Valores Taxa de chegadas (À) Ha Hz Taxa de atendimento (pt) cu p Fa W, W Probabilidade de haver fila P(N > 2) 0,23 clientes /min 0,55 clientes /min 0,45 clientes /min 0,5 clientes /min 1 cliente /min 0,23 0,63 0,03 clientes 0,49 clientes 0,12 min 2,12 min 0,08 (8%) Tendo em vista a observação das medidas de desempenho apresentadas na Tabela 2, foi feita uma simulação do sistema com apenas um posto de atendimento para o caso de dias normais de funcionamento. As medidas de desempenho para este caso são apresentadas na Tabela 3. Comparando com os resultados apresentados anteriormente na Tabela 2, vemos que há um aumento considerável da probabilidade de se formar uma fila. Além disso, o número esperado de usuários no sistema quase duplicou e o tempo médio de espera aumentou em torno de 73%. Tabela 3: Estimativas dos parâmetros e medidas de desempenho para um dia normal de funcionamento, considerando a existência de apenas um posto de serviço Medidas de desempenho Valores Taxa de chegadas (À) 0,23 clientes /min Taxa de atendimento(p.) 0,5 clientes/min p 0,46 Po 0,54 La 0,39 clientes L 0,85 clientes MW 1,7 min W 3,7 min Probabilidade de haver fila P(N > 1) 0,146=46% 4.2 Modelagem do Sistema em Dias de Pagamento do Bolsa Família Agora as análises feitas na seção anterior serão refeitas para o caso em que os dados foram colhidos em dia de pagamento do benefício concedido pelo Governo Federal a algu- mas famílias de baixa renda, o Bolsa Família. Também aqui será considerado um modelo M/M/2, pelas mesmas razões consideradas anteriormente. Como feito na seção anterior as hipóteses formuladas para a execução deste teste foram: Ho: As chegadas do clientes se adequam a uma distribuição de Poisson H,: As chegadas do clientes não se adequam a uma distribuição de Poisson As frequências do número de chegadas por minuto foram calculadas e apresentadas na O:-0:2 Tabela 4, no intuito de calcular-se a estatística X2 — é e compará-la com o quantil de uma Xe:95%) . Tabela 6: Comparação entre as Medidas de Desempenho M.D S.P.B.F C.P.B.F % de Aumento) A 0,23 clientes/min | 0,67 clientes/min 191,30% u 0,50 clientes /min | 0,62 clientes/min 24% cu 1,00 clientes/min | 1,24 clientes/min 24% p 0,23 0,54 129,17% Ph 0,63=63% 0,30=30% -33% Lg 0,03 clientes 0,45 clientes 1400% L 0,49 clientes 1,53 clientes 212,24% MW 0,12 min 0,68 min 466,67% W 2,12 min 2,29 min 8,02% P(N>2) 0,08=8% 0,624=62,4% 54,40% 60 5 Conclusões No que se refere ao estudo teórico da Teoria das Filas, pode-se dizer que foi bastante importante, visto que foi possível solidificar alguns conceitos vistos superficialmente na graduação, bem como aprender coisas novas. O desenvolvimento deste estudo requeria um bom conhecimento de cálculo (derivadas, integrais e séries), o que resultou num cr cimento da maturidade matemática, que é fundamental para aqueles que queiram fazer uma pós-graduação na área de Estatística. Quanto à aplicação, foi muito gratificante poder aplicar a teoria vista em um problema real, o que justifica horas a fio de estudos. A coleta dos dados teve um nível de dificuldade maior do que o esperado, pois não havia muito tempo disponível. Além disso, como já foi descrito, alguns dos lugares onde buscamos realizar a aplicação não se mostraram disponíveis. Muitos lugares, não gostam de divulgar que o seu sistema de filas não é ideal, no sentido de que tenha a taxa de serviço muito pequena em relação à taxa de chegadas. O que os dados considerados apontaram, como já era de se esperar, é que há uma diferença considerável no comportamento do sistema na situação normal de funcionamento e na situação onde há pagamento do Bolsa Família. Isto é reforçado pelo estudo, pois, temos um aumento no tempo médio que o usuário fica no sistema, no número médio de usuários no sistema e na probabilidade de formação de fila. Apesar da diferença apresentada entre as medidas de desempenho nas duas situações, pode-se concluir que o sistema se comporta muito bem em ambas desde que ele opere efetivamente com os dois caixas, pois, se levarmos em consideração que o estabelecimento só opera com apenas um posto de serviço na maioria das vezes em dias de pagamento do Bolsa Família, que é o que realmente acontece, o sistema fica super lotado e se torna impossível controlar o congestionamento de clientes no estabelecimento, neste caso, por- tanto, os clientes têm razão em reclamar a respeito da espera pelo atendimento. Em dias normais de atendimento, tendo em vista que o número médio de usuários na fila é 0,03 clientes, logo se torna dispensável um posto de atendimento para este caso, já 61 que na simulação feita com o funcionamento de um só caixa de serviço, o sistema também se comporta muito bem, levando em consideração o tempo médio de permanência no sistema para este caso que é de 3,7min, sendo um tempo tolerável de espera. Já em dias de pagamento do Bolsa Família o ideal era que o sistema operasse com sua capacidade máxima, que seria o funcionamento dos dois postos de atendimento, logo, para que isso ocorra, foi sugerido a gerência do sistema a correção do problema da falta de dinheiro nos caixas de serviço, com isso, o sistema atenderia com qualidade as necessidades de seus usuários além de gerar lucros maiores para o estabelecimento, pois quanto mais clientes atendidos, mais movimentações financeiras são feitas. De maneira geral, o problema da casa lotérica não está no atendimento, e sim em questões internas como: falta de dinheiro nos caixas de serviço e a rede de computadores fora de conexão. Com a correção desses problemas é possível controlar o fluxo de usuários que entram e saem do estabelecimento, evitando assim perca de clientes e declínio nos lucros da entidade. Pôde-se concluir também neste trabalho que a Teoria de filas é uma importante ferra- menta tratando-se de controle de fluxos de usuários em sistemas com fila, já que através deste estudo pode-se observar detalhadamente o comportamento desses sistemas e ainda propôr melhorias para um bom funcionamento do mesmo.