Estudo Comprobatório da Teoria das Filas pela Simulação de Eventos Discretos - PDF
Download "Estudo Comprobatório da Teoria das Filas pela Simulação de Eventos Discretos"
Talita Sabala Ramires
1 1 Estudo Comprobatório da Teoria das Filas pela Simulação de Eventos Discretos RESUMO O presente artigo tem como proposta comprovar a Teoria das Filas pela Simulação de Eventos Discretos (SED), através do uso do mapeamento de processo e da simulação computacional pelo software Promodel. O trabalho também visa à exploração dos pontos fortes e fracos da SED quando comparada a métodos teóricos em geral. Palavras-Chave: Filas, Simulação, Promodel. 1. INTRODUÇÃO Esse estudo mostra como modelar o tempo médio de espera em função da capacidade do sistema. Para avaliar o desempenho deste modelo, foi realizado um experimento em uma empresa do ramo ferramenteiro. Por fim, o trabalho propõe melhorias ao processo de produção, objetivando eliminar as atividades que não agregam valor ao processo e reduzir o tempo de espera das peças a serem produzidas na fila da linha de produção e consequentemente, redução de Lead Time. 2. METODOLOGIA Na pesquisa em questão, a importância da exploração e descrição dos métodos se sobrepõe à do objeto de pesquisa. A abordagem, no caso, sendo quantitativa, destaca a evidência de relações causais, operacionalização de conceitos e conclusões que, conforme o enfoque, podem ser generalizadas. O conceito de pesquisa descritiva também se aplica ao caso, pois esta tem como objetivo a descrição de características de determinado processo estudado, ou o estabelecimento de relações entre variáveis. Algumas pesquisas descritivas vão além da simples identificação da existência de relações entre variáveis, pretendendo-se determinar a natureza dessa relação, tendo-se, então, uma pesquisa descritiva que se aproxima da explicativa. Há casos de pesquisas, que, embora definidas como descritivas, proporcionam uma nova visão do problema, o que as aproxima das pesquisas exploratórias. Abordagem Tipo de Pesquisa Método de Pesquisa Metodologia Figura 1 Metodologia da Pesquisa Quantitativa Descritiva (Exploratória) Experimentação / Simulação O método de pesquisa adotado é, portanto, a Pesquisa Experimental, pois segundo BRYMAN (1995), de um modo geral, além de se adequar ao caso em questão, o experimento representa o melhor exemplo de pesquisa científica. Consiste em determinar um objeto de estudo, selecionar variáveis que seriam capazes de influenciá-lo, definir as formas de controle e de observação dos efeitos que a variável
2 produz no objeto. Na execução da pesquisa, um sistema MM1 é estudado pela Teoria das Filas e por Simulação de Eventos discretos, sendo então seus resultados comparados. 3. TEORIA DAS FILAS Conforme ANDRADE (1998), um sistema de filas é caracterizado por seis componentes. Os três primeiros são obrigatórios e os três últimos, se não informados, são considerados conhecidos: a) Modelo de chegada dos usuários ao serviço: o modelo de chegada é usualmente especificado pelo tempo entre as chegadas dos usuários/serviços. Pode ser determinístico, isto é, as chegadas ocorrem em intervalos de tempo exatamente iguais (tempo entre as chegadas é constante), ou ser uma variável aleatória, quando o tempo entre as chegadas é variável e segue uma distribuição de probabilidades presumivelmente conhecida. Além de sabermos se o modelo de chegada é determinístico ou é uma variável aleatória, precisamos também saber a taxa de chegada λ. A constante λ é a taxa média de chegadas dos usuários por unidade de tempo. b) Modelo de serviço (atendimento aos usuários): o modelo de serviço é normalmente especificado pelo tempo de serviço, isto é, o tempo requerido pelo atendente para concluir o atendimento. Da mesma forma que o modelo de chegada, pode ser determinístico (constante) ou uma variável aleatória (quando o tempo de atendimento é variável e segue uma distribuição de probabilidades presumivelmente conhecida). Neste último caso, valem as mesmas considerações feitas à distribuição de probabilidades associada ao modelo de chegada dos usuários ao serviço. A constante µ (mi) é a taxa média de atendimentos por unidade de tempo, por atendente. c) Número de servidores: é o número de atendentes disponíveis no sistema. d) Capacidade do sistema: é o número de usuários que o sistema é capaz de atender. Inclui o número de usuários que estão sendo atendidos mais os que esperam na fila. Se este parâmetro não for informado, o sistema é considerado com capacidade ilimitada ( ). e) Tamanha da população: número potencial de clientes que podem chegar a um sistema. Pode ser finito ou infinito. f) Disciplina da fila: é o modo como os usuários são atendidos. A disciplina da fila pode ser: * FIFO (first in, first out): primeiro a chegar é o primeiro a ser atendido; * LIFO (last in, first out): último a chegar é o primeiro a ser atendido; * ALEATÓRIO, isto é, os atendimentos são feitos sem qualquer preocupação com a ordem de chegada; * COM PRIORIDADE, quer dizer, os atendimentos são feitos de acordo com prioridades estabelecidas; Se a disciplina da fila não for informada, é considerada de acordo com o modelo FIFO NOTAÇÃO DE KENDALL É a notação utilizada para descrever os modelos de filas. É necessário conhecer os seis componentes anteriores para especificar um sistema de filas. Esta notação recebe o nome de Notação de Kendall em homenagem ao seu criador David Kendall.
3 Seqüência: v/w/x/y/n/z onde: v indica o modelo de chegada, alguns valores de v mais comuns são M(denota distribuição exponencial equivalente, G(distribuição geral), D(representa um tempo fixo, determinístico); w denota o modelo do serviço, os valores são os mesmos de v; x significa o número de atendentes disponíveis; y representa a capacidade do sistema, é omitido quando for infinito; n representa o tamanho da população, também omitido quando for infinito e z designa a disciplina da fila, quando for modelo FIFO, é omitido. A notação condensada A/B/c é muito usada e se assume que não há limite para o tamanho da fila, a população é infinita e a disciplina da fila é FIFO. Para A e B, quando a distribuição for exponencial negativa, usa-se M. (Marcoviana) O modelo M/M/1 diz respeito ao modelo de filas onde tanto as chegadas quanto o atendimento são marcovianas (o que é o mesmo que dizer que seguem a distribuição de Poisson ou a Exponencial Negativa) e que temos um único atendente. Existem vários outros modelos de fila: O modelo M/M/1/K (População Finita): um caso particular e bastante encontrado na vida prática é aquele onde a população de clientes é finita. O modelo M/M/C (População Infinita): aqui temos o modelo de uma única fila e diversos servidores e tanto chegada como atendimento são marcovianas. Supõe-se aqui que a capacidade de atendimento de cada um dos atendentes é a mesma. O modelo M/M/C/K (População Finita): neste modelo encontramos múltiplos atendentes, mas a população é finita. No artigo será usado especificamente o modelo MM1, com suas devidas equações: p = λ. Ws (taxa de utilização do servidor) wq = p. w (tempo gasto na fila) Ws w = (tempo total no sistema) 1 p 4. SIMULAÇÃO DE EVENTOS DISCRETOS De modo geral, um sistema a eventos discretos (SED) é um sistema dinâmico cujas variações de estado são estritamente condicionadas pela ocorrência de eventos. Em vez de fazer a simulação em tempo real, seu programa usará o conceito de tempo simulado ou tempo da simulação. O que caracteriza a simulação a eventos discretos é o fato do tempo da simulação ser descontínuo. Ele anda aos saltos: suponha que um evento e1 ocorreu no instante t1 do tempo simulado e foi sucedido pelo evento e2, o qual ocorreu no instante t2 do tempo simulado. Se não aconteceu nenhum evento de interesse entre e1 e e2 então o tempo simulado pulou de t1 diretamente para t2.
4 O conceito de evento é fundamental, caracterizado como algo sem duração e única causa possível para as mudanças de estado. Cada evento está associado a um tempo simulado. Os eventos que ainda não foram tratados pelo simulador (ou, em outras palavras, que ainda não aconteceram no tempo simulado) são mantidos numa fila com prioridade (priority queue) denominada fila de eventos. A prioridade de um evento é o tempo simulado associado a ele. Antes da simulação começar, todos os eventos iniciais (aqueles que não são gerados pela própria simulação) são colocados na fila de eventos. Um exemplo de evento inicial: chegada de tarefa com duração 500, no instante t = 35 do tempo simulado''. O evento é a chegada de tarefa com duração 500. Ele está associado ao tempo simulado t = 35. Nessa fase de iniciação da simulação o tempo simulado ainda não começou a correr. O tempo simulado começa a correr quando o simulador entra no seu laço principal, também conhecido como laço de eventos (event loop). Enquanto existirem elementos na fila de eventos, esse laço faz o seguinte: a) Retira o item mais prioritário da fila de eventos. O item mais prioritário é o evento associado ao menor tempo simulado. Esse evento é o evento atual. atual. b) Atribui à variável tempo atual o valor do tempo simulado associado ao evento c) Trata o evento atual. Esse tratamento pode adicionar novos eventos à fila de eventos. Note que o tratamento de um evento depende do tipo desse evento. Exemplos de tipos de eventos: chegada de tarefa com duração x, início da execução de tarefa com duração x, e fim da execução de tarefa. Note também que só o primeiro desses tipos de eventos corresponde a eventos iniciais. Os outros dois tipos são gerados durante a simulação. Exemplo: No esquema FIFO, o tratamento do primeiro evento do tipo chegada de tarefa com duração x gera um evento ``fim da execução de tarefa'' associado ao tempo simulado tempo atual + x. (Isso não é necessariamente verdade no esquema FIFO com preempção, pois a duração da tarefa pode ser maior que a fatia de tempo.) Esses dados determinam o conjunto de eventos iniciais (uma lista de tempos de chegada e durações de tarefas) ou, opcionalmente, permitem a geração aleatória desse conjunto (tempo médio entre chegadas de tarefas e duração média de uma tarefa). A simulação acaba quando a fila de eventos acabar. Ao final da simulação, devem ser impressos os seguintes dados: * duração em tempo simulado (último valor do tempo simulado menos primeiro valor do tempo simulado) * número de tarefas tratadas * duração média de uma tarefa * tempo de espera médio de uma tarefa * tempo total médio de uma tarefa * comprimento médio da fila de espera Portanto, num SED, as mudanças de estado ocorrem estritamente num conjunto enumerável de instantes de tempo. De acordo com HARREL e TUMAY (1994), um bom modelo de simulação de eventos Discretos deve possuir certas características, como ser válido no sentido de
5 representar satisfatoriamente a realidade; e ser mínimo, no sentido de incluir somente elementos que influenciam no problema a ser solucionado. Diz-se também que um SED tem sua dinâmica dirigida pela ocorrência de eventos. Outro aspecto importante a respeito dos SED é o fato de seu espaço de estados ser normalmente discreto (e em muitas aplicações finito). Essas características distinguem os SED dos sistemas que têm sua dinâmica dirigida pelo tempo e seu espaço de estado contínuo, cuja modelagem é tradicionalmente feita através das equações diferenciais e das equações a diferenças. Esses sistemas serão chamados de sistemas contínuos (mesmo no caso em que o tempo for discreto). A simulação de eventos discretos abrange o estudo de modelos de simulação cujas variáveis mudam de estado instantaneamente em pontos específicos de tempo, em contraste aos modelos contínuos, cujas variáveis mudam de estado continuamente no decorrer do tempo. LAW e KELTON (1991) comentam que é comum considerar para fins de simulação o aspecto predominante do sistema, seja discreto ou contínuo. LAW e KELTON (1991) atentam para o fato que poucos sistemas, na prática, são totalmente discretos ou totalmente contínuos. Em um SED os eventos podem ser de vários tipos e programados de maneiras diversas. Podem ocorrer autonomamente ou programados pela ocorrência prévia de algum outro evento e a definição do instante de ocorrência pode ser determinística ou nãodeterminística (inclusive aleatória). Exemplos típicos de SED são os sistemas de manufatura, o hardware de um computador, e em outro nível de abstração, as redes de comunicação. Dois aspectos são de grande importância no estudo da dinâmica de SED: os problemas de conflito e os problemas de sincronização. Os sistemas de manufatura oferecem exemplos desses dois aspectos. Um conflito ocorre num sistema de manufatura quando, por exemplo, duas peças devem ser processadas na mesma máquina, devendo haver uma decisão sobre qual delas será processada em primeiro lugar. O aspecto de sincronização fica evidente, por exemplo, quando a montagem de uma peça depende de duas ou mais partes, cujo processamento por sua vez pode obedecer às mesmas restrições. Nesse caso, obviamente a parte com processamento mais tardio determinará o início da montagem da peça final. Até pouco mais de duas décadas atrás, os SED eram tratados predominantemente através de técnicas de simulação (BANKS, 2000), ou de otimização estática, sendo que os resultados analíticos provinham da Teoria de Filas (KLEINROCK, 1975) e da Teoria de Redes de Petri (MURATA, 1989). Em particular, esta última abordagem teve grande desenvolvimento durante as décadas de 60 e 70, até o início dos anos 80. A partir desse momento, certamente impulsionadas pelos desafios e exigências do mundo da automação industrial, diversas novas abordagens para o problema de análise e síntese de controladores para SED foram iniciadas, envolvendo as áreas de Teoria de Sistemas, Pesquisa Operacional e Teoria da Computação. São exemplos dessas abordagens entre outras, a Teoria de Controle Supervisório (RAMADGE E WONHAM, 1989), a Análise de Perturbações (CASSANDRAS E LAFORTUNE, 1999), as técnicas baseadas em Lógica Temporal (OSTROFF, 1989) e aquelas baseadas na Álgebra Maxplus (BACCELLI, 1992). Além disso, significativos desenvolvimentos ocorreram na já existente Teoria de Redes de Petri e na Teoria de Sistemas Híbridos (ANTSAKLIS, 2000), isto é, sistemas que combinam as características de sistemas contínuos e a eventos discretos.
6 A simulação é um processo de experimentação que utiliza um modelo suficientemente detalhado de um sistema para determinar como este responderá às mudanças em sua estrutura, ambiente ou condições de contorno (CASSANDRAS E LAFORTUNE, 1999). Geralmente o termo simulação refere-se à representação de um processo dinâmico ou sistema de forma a permitir sua análise, por considerar o problema atual muito grande e/ou complexo (HARREL E BATEMAN, 2002). Assim, a utilização de modelos em simulação é, em geral, mais simples e barata que a simulação com o sistema real. Em muitos casos seu propósito é analisar e entender o comportamento do sistema em função de cenários alternativos (LAW E KELTON, 2000). Portanto, uma vantagem importante da simulação é a flexibilidade de avaliar situações, pelo mesmo modelo, pois a avaliação de vários cenários reais levaria muito mais tempo e seria excessivamente dispendiosa. Em simulação por eventos discretos, as variáveis devem ser equacionadas em um modelo, considerando que todos aspectos legais sejam cumpridos. Simulação por eventos discretos quer dizer que uma determinada variável sofre variações discretas em seu valor. Simulação dessa natureza apresenta-se como uma importante ferramenta para o levantamento da contribuição individual de cada parcela no processo, caracterizando estados que descrevem o processo com instâncias observáveis através do modelo. Os fatores inseridos num processo de produção evidenciam um sistema complexo, de difícil tratamento analítico, justificando-se, portanto, a aplicação de simulação computacional para estudar o tamanho de filas, bem como o comportamento característico do sistema face à demanda. A crescente popularidade de uso da simulação como ferramenta de modelagem e análise de problemas resultou em uma vasta e também crescente disponibilidade de softwares de simulação no mercado. Como estes softwares normalmente representam dispêndios consideráveis para as empresas que adquirem uma licença de uso, sua seleção adequada passa a ser um dos fatores chave no sucesso dos projetos de simulação a serem futuramente desenvolvidos. Assim sendo, esta seleção deverá ser feita cada vez mais com base em critérios objetivos, levando em conta não apenas as características dos produtos mas também das aplicações que se pretende desenvolver. (SALIBY, 2002) Nosso interesse principal são os softwares de simulação a eventos discretos. 5. APLICAÇÃO. Foi aplicado a teoria de filas para analisar o problema de congestão. Essa aplicação visa modelar o tempo médio de espera das peças na fila. Dois modelos foram utilizados na aplicação: um através da Teoria das Filas e outro através do software Promodel. Será usado o modelo MM1, serviço único, processo de chegada segue Poisson, tempo de atendimento segue Exponencial, Política FIFO. A grande vantagem desse modelo é a simplicidade de análise, uma vez que o modelo M/M/1 é um modelo Markoviano de fácil análise exata. Diversas medidas de desempenho podem ser facilmente computadas admitindo-se que o sistema esteja em equilíbrio, tais como a utilização média das máquinas, o número médio de peças no sistema, o tamanho médio da fila, o tempo médio de espera em fila, etc. Foi coletada uma amostra. Durante este período, o sistema operou de maneira normal. Para cada máquina, foram coletados os instantes de início e término de serviços.
7 O modelo foi criado no Promodel, com as 2 máquinas, uma soltando peça com distribuição de Poisson (chegada na fila), e outra processando as peças (atendimento) com distribuição exponencial. Esse modelo foi rodado 30 vezes e obtiveram-se 30 dados de tempo de permanência na fila, que foram depois jogados no software Crystal ball para ver qual é a distribuição desses dados de saída. Figura 2 Modelo Simulado no software Promodel. Figura 3 - Dados obtidos.
8 Figura 4 - Analise dos dados obtidos pelo software Crystal Ball: Temos que o tempo de espera na fila segue uma distribuição Lognormal com média 21,17 e desvio padrão de 8,19. A média geral dos intervalos médios entre chegadas nas máquinas é 9 minutos. A média geral dos tempos médios de serviço é 8 minutos. Fazendo os cálculos pela Teoria das Filas, tem-se que: C = 1 (1 servidor) λ = 0,09 (taxa de chegada) Ws = 8 (tempo de serviço) p = λ. Ws (taxa de utilização do servidor) p = 0,09. 8 = 0,72 Ws w = (tempo total no sistema) 1 p w = 28,57 wq = p. w (tempo gasto na fila) wq = 20,57 Então, fazendo os cálculos pela Teoria das Filas, o tempo médio de espera na fila fica em 20,57 minutos. 6. CONCLUSÕES Neste estudo foi aplicado a teoria de filas para modelar o tempo médio de espera das peças num sistema de produção de uma fábrica de ferramentas. O trabalho apresentou uma comparação entre uma Simulação em ProModel e a representação matemática da Teoria de Filas. Geralmente, quando as incertezas são inseridas nos modelos, fica exposta a grande fragilidade de certos métodos determinísticos.
9 A Simulação de Eventos Discretos se apresenta como um método poderoso na análise de incertezas, porém apresenta como limitação, a complexidade dos cálculos e a necessidade de softwares específicos. A maior dificuldade encontrada na aplicação do método está na obtenção de um modelo computacional validado, e não na aplicação dos conceitos estatísticos. As diferenças encontradas na comparação são devidas ao erro de discretização inerente ao processo de amostragem probabilística e ainda às variações de P-value devidas ao condicionamento das distribuições de probabilidade. Para a aplicação do método proposto, deve-se previamente, reduzir ao máximo as dispersões do processo e balancear a linha modelada. Quanto maiores as amostras de tempo coletados, mais exato é o resultado da comparação. Apesar de necessitar de alguns ajustes, o método apresentou-se satisfatório, obtendo valores comparatórios coerentes. 7. REFERÊNCIAS BIBLIOGRÁFICAS BRYMAN, A.; Research Methods and Organization Studies, John Wiley & Sons Ltd ANDRADE, EDUARDO L. DE. Introdução à Pesquisa Operacional: métodos e modelos para a análise de decisão. 2 ed. Rio de Janeiro: LTC, p. HARREL, C.; TUMAY, K. Simulation Made Easy. Engineering & Management press, LAW, AVERILL M.; KELTON, W. DAVID. Simulation Modeling and Analysis. 2nd ed. New York: McGraw-Hill BANKS, J., CARSON, J. S., NELSON, B. L. E NICOL, D. M. Discrete-Event System Simulation. 3rd. ed. Prentice-Hall KLEINROCK, L. Queueing Systems - Theory, Vol. I. Wiley-Interscience MURATA, T. Petri nets : properties, analysis and applications. Proceedings of the IEEE RAMADGE, P. E WONHAM, W. The control of discrete event systems. IEEE CASSANDRAS, C. G. E LAFORTUNE, S. Introduction to Discrete Event Systems. Kluwer Academic Publishers OSTROFF, J. Temporal Logic for Real-Time Systems. John Wiley, New York BACCELLI, F., COHEN, G., OLSDER, G. E QUADRAT, J. Synchronisation and Linearity: An Algebra for Discrete Event System. John Wiley and Sons, New York ANTSAKLIS, A. J. A brief introduction to the theory and applications of hybrid systems. Proceedings of the IEEE: HARREL C.R., MOTT, J.R.A., BATEMAN, R.E., BOWDEN, R.G., GOGG, T.J. Simulação Otimizando os Sistemas. São Paulo: Belge IMAM
10 LAW, A.M., KELTON, W.D. Simulation Modeling and Analysis. Boston: McGraw-Hill, SALIBY, E. Simul 3.1. Software e manual. COPPEAD/UFRJ, 1996.