Teoria das Filas - Ednário B. de Mendonça

Teoria das Filas - Ednário B. de Mendonça

(Parte 1 de 3)

Universidade Estadual da Paraıba

Centro de Ciencias e Tecnologia Departamento de Estatıstica

Ednario Barbosa de Mendonca Teoria de Filas Markovianas e Aplicacoes

Campina Grande Julho de 2014

Ednario Barbosa de Mendonca

Teoria de Filas Markovianas e Aplicacoes

Trabalho de Conclusao de Curso apresentado ao curso de Bacharelado em Estatıstica do Departamento de Estatıstica do Centro de Ciencias e Tecnologia da Universidade Estadual da Paraıba em cumprimento as exigencias legais para obtencao do tıtulo de bacharel em Estatıstica.

Orientadora: Divanilda Maia Esteves

Campina Grande Julho de 2014

Dedicatoria

Dedico a minha mae, Ediane Alves Barbosa, por todo o apoio que ela tem me dado ao longo de toda uma vida e por todo o seu esforco em procurar fazer de mim uma pessoa melhor, e ao meu pai, Jose Nario Martins de Mendonca (in memorian).

Agradecimentos

A Deus pelas bencaos 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 construcao deste trabalho, por me conceder a oportunidade de participar de um Projeto de Iniciacao Cientıfica e por ser sempre prestativa no decorrer da minha carreira academica, tirando minhas duvidas 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 mae, que me ensinou o que e 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 e a pessoa que mais amo nesse mundo, minha vo, Maria Odete Alves Barbosa, que esta sempre ao meu lado, a minha noiva, Thuanne Barros de Oliveira, que me deu sempre forca e apoio nos momentos difıceis, me entendia quando estava estressado e acreditou sempre em min quando ninguem mais acreditava, e aos meus tios, Helio Alves Barbosa e Jose Israel Alves Barbosa, os quais tambem se fazem bastante presentes em minha vida.

Aos demais professores da UEPB que passaram por minha graduacao e tiveram sua parcela de contribuicao na construcao da minha carreira academica, em especial, os professores: Gustavo Henrique Esteves, Tiago Almeida de Oliveira, Ana Patrıcia Barros Peixoto, Joao Gil de Luna, Ricardo Alves de Olinda, Onildo Freire, Vandik Estevam Barbosa e Francisco Guedes

Aos colegas e amigos do “Busao” da cidade de Cubati-PB, os quais passei toda minha graduacao viajando ate Campina Grande-PB e aos meus colegas de turma.

Resumo

Um sistema de filas pode ser definido como um sistema onde “usuarios” chegam a um posto de atendimento, buscando algum servico. O tempo entre chegadas e uma variavel aleatoria e o tempo gasto para realizar o servico e outra variavel aleatoria. Devido a esse carater aleatorio e impossıvel garantir que terminos de servicos coincidam exatamente com chegadas de usuarios. Consequentemente ha vezes que o servico completa sua tarefa com um usuario e nao encontra mais ninguem disponıvel com quem trabalhar, tornando assim, o sistema ocioso. Outras vezes um usuario chega e ja encontra o servico ocupado com alguma chegada anterior, entao ele podera aguardar a sua vez ou partir. Isso dependera da estrutura do sistema, pois em uma fila de banco, por exemplo, o cliente pode esperar, mas quando se trata de uma ligacao telefonica simples, em geral, nao ha opcao de espera. Esses sao aspectos basicos das filas, mas essas estruturas podem ser mais complexas, considerando outras situacoes como sistemas com uma capacidade finita de espera ou cliente desistindo do servico quando demora a ser atendido. Atualmente, este tipo de estudo tem se destacado, especialmente devido as leis estabelecendo um tempo maximo de espera por atendimento em bancos, supermercados e call centers. O objetivo do estudo das filas e estimar os parametros envolvidos no modelo e calcular algumas medidas de seu desempenho, como por exemplo, tempo medio que o usuario fica na fila ou tamanho medio da fila, considerando as particularidades de cada caso. Uma vez que se conhece tais medidas, e possıvel buscar sistemas que atendam eficientemente as necessidades de quem procura o servico 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 loterica da cidade de Cubati-PB, com o objetivo de comparar as medidas de desempenho em dias que ha pagamento do benefıcio Bolsa Famılia do Governo Federal com os dias normais, ou seja, em que nao ha pagamento do benefıcio.

Palavras-chave: Filas Markovianas, Medidas de desempenho, Variavel aleatoria.

Abstract

A queuing system can be defined as a system where users get to a service station, looking for some service. The time between arrivals is a random variable and the time taken to perform the service is another random variable. Because of this randomness is impossible to guarantee that services endings coincide exactly with arrivals of users. Consequently there are times when the service completes its task with a user and can not find anyone else available to work with, thus making the system idle. Sometimes a user arrives and longer service busy with some earlier arrival then he can wait your turn or go. This depends on the structure of the system, as in a line at the bank, for example, the client can expect, but when it comes to a simple phone call, in general, no waiting option. These are basic aspects of the queues, but these structures may be more complex, considering other situations as systems with a finite capacity to hold or giving customer service takes when being serviced. Currently, this type of study has been outstanding, especially due to the laws establishing a maximum waiting time for service in banks, supermarkets and call centers. The objective of the study is to estimate the rows of the parameters involved in the model and calculate some measures of performance, such as average time that a user is in the queue or average queue size, considering the particularities of each case. Once you know these measures, it is possible to search efficiently systems that meet the needs of those looking for the service until the system is idle for long. This study applied the theory of Markovian flow of people queuing in a lottery town house Cubati-PB, with the aim of comparing the performance measures in days there Bolsa Famılia benefit payment from the Federal Government to normal days , meaning that no benefit payment.

Keywords: Markovian queues, performance measures, random variable.

Sumario

Lista de Figuras

Lista de Tabelas

1 Introducao p.12

2.1 Processos Estocasticosp. 14
2.2 Cadeias de Markovp. 16
2.2.1 Classificacao dos Estadosp. 18
2.2.2 Medida Invariantep. 19
2.3 Processo de Nascimento e Mortep. 20
2.4 Processo de Poissonp. 24
2.5 Conceitos Basicos da Teoria de Filasp. 28
2.5.1 Estrutura Basica de um Sistema com Filap.29
2.5.2 Disciplina de Atendimentop. 31
2.5.3 Notacao de um Sistema com Filap.31
2.5.4 Medidas de Desempenhop. 32
2.6 Modelos de Filas Basicosp. 32
2.6.1 Modelo M/M/1/∞/FIFOp.32
2.6.2 Modelo M/M/1/k/FIFOp.39
2.6.2.1 Caso particular M/M/1/1/FIFOp.4

3 Metodologia p.51

4.1 Modelagem do Sistema em Situacao Normal de Funcionamentop.53
4.2 Modelagem do Sistema em Dias de Pagamento do Bolsa Famıliap.56
4.3 Resumo Geralp. 58

4 Resultados e Discussoes p.53

5 Conclusoes p.60 Referencias p.62

Lista de Figuras 1 Representacao esquematica de um sistema com fila . . . . . . . . . . . p.30

Lista de Tabelas

e calculo da estatıstica X2 para um dia normal de funcionamentop.54

1 Frequencias observadas e esperadas do numero de chegadas por minuto

de funcionamentop. 5

2 Estimativa dos parametros e medidas de desempenho para dias normais

servicop. 56

3 Estimativas dos parametros e medidas de desempenho para um dia normal de funcionamento, considerando a existencia de apenas um posto de

e calculo da estatıstica X2p. 57
5 Medidas de desempenho para dias de pagamento do Bolsa Famıliap.57

4 Frequencias observadas e esperadas do numero de chegadas por minuto 6 Comparacao entre as Medidas de Desempenho . . . . . . . . . . . . . . p.59

12 1 Introducao

As filas de espera por servicos fazem parte do dia-a-dia das pessoas na sociedade e, como nao podem ser evitadas, tendem a ser toleradas, apesar dos atrasos e das inconveniencias que causam. Entretanto, os processos geradores de filas podem ser estudados e dimensionados de forma a aliviar os prejuızos em tempo e produtividade, assim como as perdas financeiras que elas acarretam. Entre as medidas que auxiliam no estudo de sistemas com fila, podem-se citar: numero medio de elementos na fila, tempo de espera pelo atendimento e tempo ocioso dos prestadores de servico.

Segundo Fogliatti e Mattos (2007), a Teoria de Filas consiste na modelagem analıtica de processos ou sistemas que resultam em espera e tem como objetivo determinar e avaliar quantidades, denominadas medidas de desempenho, que expressam a produtividade e/ou operacionalidade desses processos. O estudo dessas quantidades e importante na tomada de decisao quanto a modificacao ou manutencao da operacao do sistema no seu estado atual, facilita tambem o dimensionamento racional da infraestrutura, de recursos humanos e financeiros, de equipamentos e instalacoes, visando um melhor desempenho no geral. Dessa forma, os conceitos e a teoria basica de Filas sao fundamentais para a gerencia e a administracao de sistemas produtivos.

Em processos com determinadas caracterısticas, apos seu funcionamento durante um certo perıodo de tempo, as medidas de desempenho tendem a se estabilizar. Neste caso, o intervalo de tempo de funcionamento do sistema, [t0,t), pode ser dividido em dois subintervalos: [t0,t∗) e [t∗,t), onde t0 e o instante de entrada em operacao e t∗ e o instante a partir do qual as medidas de desempenho se mantem estaveis. Diz-se que em [t0,t∗) o sistema se encontra no regime transitorio, enquanto que em [t∗,t) o sistema se encontra no regime estacionario, os quais falaremos mais adiante.

No regime transitorio, a variabilidade das medidas de desempenho dificulta as representacoes analıticas das mesmas, sendo necessarios para tal, conhecimentos matematicos avancados. No regime estacionario, a estabilidade dessas medidas permite o uso dos respectivos valores esperados para a avaliacao do sistema.

Neste trabalho, foi feito um estudo da Teoria das Filas Markovianas, bem como alguns conceitos previos para a construcao desta teoria. Alguns aspectos principais deste estudo serao apresentados na Fundamentacao Teorica. Depois, aplicou-se tal teoria em um conjunto de dados referente ao fluxo de clientes em uma casa loterica na cidade de Cubati-PB. O intuito foi comparar as medidas de desempenho para aqueles dias em que ha pagamento do benefıcio Bolsa Famılia com aqueles dias em que nao ha.

14 2 Fundamentacao Teorica

Boa parte deste trabalho consistiu em estudar a teoria envolvida no estudo das filas.

Este capıtulo contem alguns pontos importantes estudados. Primeiramente, serao apresentados os principais conceitos relacionados a Processos Estocasticos, Cadeias de Markov e Processos de Poisson, que sao topicos fundamentais para quem queira estudar Teoria de Filas. Em seguida, serao apresentados, de modo sucinto, algumas definicoes e resultados relacionados a essa teoria.

2.1 Processos Estocasticos

De modo geral, pode-se dizer que um processo estocastico e qualquer processo que evolui de maneira aleatoria. Mais formalmente, segundo Fogliatti e Mattos (2007), um processo estocastico {X(t) : t ∈ T} e uma colecao de variaveis aleatorias, isto e, para cada t ∈ T, X(t) e uma variavel aleatoria. O conjunto T e chamado conjunto de ındices. O conjunto de todos os valores que as variaveis X(t) podem assumir e chamado espaco de estados S do processo estocastico.

Frequentemente, o ındice t e interpretado como tempo t, e por isso, em geral, X(t) e vista como o estado do processo no tempo t. Daı, de uma maneira alternativa, pode-se definir um processo estocastico como uma famılia de variaveis aleatorias que descreve a evolucao de algum processo fısico atraves do tempo.

Se {X(t),t ∈ T} e um processo estocastico com espaco de estados S e conjunto de ındices T, entao considera-se que:

Se S for enumeravel, o processo e dito discreto ou a valores inteiros (do ingles, integer-valued). Se S e um intervalo da reta (ou o proprio R) entao dizemos que e um processo a valores reais (do ingles, real-valued)

Se o conjunto de ındices T for enumeravel, entao dizemos que o processo e a tempo

Um aspecto importante que deve ser considerado e a estrutura de dependencia associada a sequencia de variaveis aleatorias. Em Estatıstica, um caso a se destacar e aquele em que as variaveis sao independentes. Neste caso, o processo de inferencia sobre os parametros envolvidos no modelo fica mais simples, uma vez que a distribuicao conjunta das variaveis pode ser escrita como o produto das distribuicoes unidimensionais. Quando nao se observa independencia, busca-se descobrir o alcance e a forma de dependencia. Um caso de dependencia particularmente importante no estudo de processos estocasticos e a dependencia de Markov.

para qualquer escolha x0,x1,...,xn+1 em S e qualquer n. Isto quer dizer que, uma vez que conhecemos o estado atual da cadeia, os estados passados nao influenciam o futuro.

para qualquer escolha x0,x1,...,xn+1 em S e qualquer n. Isto quer dizer que o estado atual da cadeia e influenciado pelas k observacoes mais recentes do processo.

Um processo Markoviano que possui o espaco de estados discreto e denominado Cadeia de Markov. O comportamento da Cadeia de Markov {X(t) : t ∈ T} de parametro contınuo com espaco de estados discreto, o qual pode ser considerado sem perda de generalidade como S = {0,1,2,...}, e caracterizado pela distribuicao inicial

X(t0) = l, l = 0, 1, 2,,

onde t0 e o instante inicial de observacao, e pelas probabilidades (condicionais) de transicao entre os estados i e n, Pin(v,z), definidas por:

com:

0, caso contrario

2.2 Cadeias de Markov

Uma Cadeia de Markov e um Processo Estocastico com espaco de estados discreto.

Se o conjunto de ındices for um conjunto enumeravel, entao tem-se uma Cadeia de Markov a tempo discreto, caso contrario, tem-se uma Cadeia de Markov a tempo contınuo.

Frequentemente, no caso de Cadeias de Markov, usa-se a notacao {Xn,n ∈ N} em lugar de {X(t),t > 0}.

Definicao 2.2 Um processo {Xn : n > 0} assumindo valores em um conjunto S e uma Cadeia de Markov se dado o estado presente, o futuro nao e influenciado pelo passado, ou seja,

A probabilidade dada pela Equacao (2.1) e chamada probabilidade de transicao a um passo da cadeia e para facilitar a notacao, usa-se

Quando temos uma cadeia quee homogenea no tempo, suas probabilidades de transicao podem ser representadas matricialmente na forma

Neste caso, P e a matriz de transicao a um passo da cadeia, ou simplesmente matriz de transicao da cadeia. Observe que os elementos da matriz sao nao negativos e que a soma dos elementos de cada linha deve ser igual a 1.

Basicamente, para que se possa modelar a evolucao de uma Cadeia de Markov, e necessario conhecer como se comporta a cadeia inicialmente e como sao feitas as transicoes a partir daı. As transicoes passo a passo sao modeladas segundo a matriz de transicoes a um passo. No entanto, seria tambem interessante modelar as transicoes em um numero maior de passos.

pi0 = [pi0(0), pi0(1), pi0(2),].

Frequentemente, a funcao de distribuicao inicial e apresentada na forma de um vetor:

Teorema 2.1 A distribuicao conjunta de X0,X1,...,Xn pode ser expressa em termos da funcao de transicao e da distribuicao inicial da seguinte maneira:

A ideia da demonstracao do Teorema 2.1 e usar o Teorema da Multiplicacao que pode ser encontrado na literatura classica de probabilidade, que neste caso, seria

×× P(X1 = x1|X0 = x0)P(X0 = x0).

Definicao 2.4 A funcao de transicao a m passos da cadeia e definida como Pm(x,y) = P(Xm = y|X0 = x), x,y ∈ S.

A funcao de transicao a m passos da cadeia e a probabilidade de que uma cadeia, que esta em um determinado estado x e em m “unidades de tempo”, passe ao estado y em m passos, sem se importar com o que aconteceu “no meio do caminho”. A funcao de transicao a m passos tambem sera representada na forma de uma matriz como

(Parte 1 de 3)

Comentários