ModelagemMat_Aula 9_pdf

Prévia do material em texto

Modelagem Matemática 
Aula 9 
Modelagem Matemática 
Aula 9 
SISTEMAS A EVENTO DISCRETOS 
 
SISTEMAS A EVENTO DISCRETOS 
 
(J.C. Lima Lopez, UFPE) 
 
(J.C. Lima Lopez, UFPE) 
 
1. Sistemas de Filas. 
 A palavra Fila sempre lembra a ideia de espera. 
Elementos básicos em um sistema de filas: 
 Entidades que esperam para utilização dos recursos, ou seja, clientes; 
 Recursos que possibilitam os serviços aos clientes, genericamente 
chamados de servidores; e 
 Espaço onde a espera é realizada, a este elemento dar-se o nome fila. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos. Exemplos de Sistemas a Eventos Discretos. Instituto de Matemática e Estatística 
 Esperar para usar recursos de um caixa de banco ou ônibus; 
 Produtos “esperam” no mercado; 
 Tarefas tb esperam no computador para “usar” os 
recursos da CPU. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
 Servidores 
Processo de chegada 
Fila de espera 
População 
Partida Disc. Serviço 
Modelo simbólico da Teoria das Filas: clientes chegam e se dirigem ao 
servidor. São atendidos ou esperam na fila, e partem depois usar os recursos. 
Exemplos de clientes: pessoas, carros em estradas, mensagens transmitidas, 
tarefas realizadas em sistema computacional, produção em um processo de 
fabricação. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
Exemplos de filas: em banco ou supermercados, redes de comunicação, 
telefonemas, tarefas a serem executadas em áreas de espera. 
Exemplos de servidores: pessoas, canais de comunicação, processadores de 
computador ou dispositivos periféricos, máquinas usadas na fabricação e sinal de 
trânsito. 
Processo de servir clientes consome tempo: servidor 
pode ser visto como um "bloco de atraso“. 
Como sistema de eventos discretos, 
fila tem um conjunto de eventos: 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
Variável de estado - nº de clientes na fila ou o comprimento da fila. 
onde {e} = evento de chegada e 
 {s} = evento de saída. 
E = {e, s} 
Espaço de estados - conjunto de valores não negativos X = {0, 1, 2,...} 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
Coleção de equipamentos e recursos humanos integrados que realiza uma ou mais 
operações de processamento e/ou montagem em matéria-prima, peça ou 
conjunto inicial de peças. 
Características: produção a baixo custo, 
 quantidade certa, 
 mínimo estoque e 
 em acordo com demanda. 
2. Sistemas de Manufatura. 
Normal/, há várias estações automatizadas com roteamentos variáveis entre elas. 
Sistemas Flexíveis de Manufatura  satisfazem às características acima. 
Produção controlada por computador de variedade de produtos em volume 
moderado flexível. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
Sistemas de manufatura podem ser descritos por modelos de filas. 
Geralmente, constituídos por: 
1. Clientes: peças ou itens; 
2. Servidores: máquinas; dispositivos de manuseio e transporte (robôs, 
esteiras...); 
3. Filas: armazéns etc. 
Equipamentos autônomos e cooperação 
interligação via redes industriais + 
Fluxo contínuo de diferentes produtos 
pelas linhas de produção 
dificultam projeto, especificação e 
administração de 
plantas de produção 
Exemplo: 
Peças passam por duas máquinas, sendo a primeira fila infinita de grande 
capacidade, mas a fila da segunda máquina é limitada a dois. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
Armazenamento de peças em uma fila até servidor liberar acesso à próxima 
operação disponível. 
Fila 
 Máquina 
 1 
Entradas 
Fila 
 Máquina 
 2 
Em um sistema industrial normalmente capacidades são finitas e 
Modelos de filas  descrição conveniente para sistemas industriais. 
Conjunto de eventos: 
 E = {e, c1, p2} 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
Serviço da máquina 1 termina, 
máquina 2 está ocupada, fila pode 
estar completa. 
peça permanece na 
máquina 1. 
outras peças esperam 
acesso à máquina 1 – 
fila mantida. 
e = uma chegada à máquina 1. 
c1 = conclusão de serviço da máquina 1. 
p2 = partida para a fila da máquina 2. 
Modelando o bloqueio  introduzir variável adicional B que x2 pode gerar. 
Espaço de estados  conjunto discreto: 
Estado do sistema - vetor x = [x1, x2] correspondendo aos comprimentos de fila 
das duas máquinas. Neste caso, x2 é restrito aos valores {0, 1, 2,3}. 
Se x2 = 3, a máquina 1 é bloqueada. 
X = {(x1, x2): x1 ≥ 0, x2 ∈ {0, 1, 2, 3, B}}. 
Flexibilidade do processo modelado (dependendo do nível de detalhe a ser 
capturado) pode ser representada por um espaço de estado alternativo: 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
X = {(x1, x2): x1 ∈ {I, W, B} e x2 ∈ {I, W}}. 
x1 = estado da máquina 1, inativo (I), trabalhando (W) ou bloqueado (B); 
x2 = estado da máquina 2, I ou W. 
Modelo focaliza estados lógicos de cada máquina e não comprimentos das filas. 
3. Sistemas de Tráfego 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
Há 4 tipos movimentos de veículos: 
1. veículos que vindos de ponto 1 e virando para o ponto 2; 
2. veículos vindos de 1 e virando para o ponto 3; 
3. veículos que vão diretamente do ponto 2 ao 3, 
4. veículos que vão do ponto 3 ao 2. 
Considerando uma simples interseção em uma sistema de tráfico T. 
Funcionamento do Sinal luminoso: 
(a) Vermelho para veículos vindos da posição 1 e Verde para os vindos das posições 2 e 3, 
permitindo assim os movimentos c e d; 
(b) Vermelho para os veículos vindos das posições 2 e 3 e Verde para vindos da posição 1, 
permitindo os movimentos a e b. 
Conjunto de eventos é determinado por: 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplos de Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
Espaço de estados é definido pelos comprimentos de fila formados em chegadas e 
partidas, e estado do sinal luminoso: 
E = {a12, a13, a23, a32, d12, d13, d23, d32, g, r}, 
a12, a13, a23, a32 = chegadas de veículos em cada uma das 4 possibilidades; 
d12, d13, d23, d32 = partidas de veículos quando o sinal luminoso permite o tráfego; 
g, r = estados do sinais luminosos, verde e vermelho, respectivamente. 
x12, x13, x23, x32 = comprimentos de fila, 
 y = estado da luz (gi = verde, ri = vermelho). 
X = {(x12, x13, x23, x32, y)}: x12, x13, x23, x32 ≥ 0, y ∈ {g1, g2, g3, r1, r2, r3}, 
Há 3 formas possíveis para se modelar um sistema a eventos discretos: 
1. Linguagem de programação convencional (C++, Java...) - toda linha 
de código é um detalhe de como o sistema deve efetivamente trabalhar. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Exemplosde Sistemas a Eventos Discretos Exemplos de Sistemas a Eventos Discretos Instituto de Matemática e 
Estatística 
Formas Possíveis para Modelagem 
2. Linguagem informal (linguagem natural) - gera ambiguidade e confusões 
excessivas nas descrições textuais. 
3. Linguagem formal - geradas por Autômatos e Redes de Petri) - evita 
ambiguidade. 
Há diversas abordagens que apresentam métodos, linguagens e padrões para a 
modelagem de aplicações industriais. 
Modelos Existentes. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Instituto de Matemática e 
Estatística 
 Há vários modelos para Sistemas Flexíveis de Manufatura, nenhum universal. 
 Modelos refletem tipos diferentes de Sistemas Flexíveis de Manufatura e 
diferentes objetivos na análise dos sistemas. 
Modelos mais usados para sistemas a eventos discretos são: 
1. Redes de Petri com e sem temporização; 
2. Teoria de Linguagens e Autômatos; 
3. Cadeias de Markov; 
4. Rede de Petri Colorida. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Instituto de Matemática e 
Estatística 
Formas Possíveis para Modelagem 
 Pode ser usada para modelagem, análise e diagnósticos de falha para os Sistemas 
Flexíveis de Manufatura. 
 Modela recursos e planejamento da produção em um sistema flexível de manufatura 
visando redução de custo. 
 Usa um algoritmo genético que tem como regra o menor tempo de operação. 
Linguagem para Modelagens Matemática que define estrutura de um sistema 
distribuído discreto como um grafo direcionado com comentários. 
Rede de Petri (Carl Adam Petri, 1939). 
 Consiste em posições, transições e arcos direcionados, nós de posição, nós de 
transição e arcos direcionados conectando posições com transições. 
 Arco indica posições de entrada de uma transição. 
 Usada para modelar comportamento concorrente em sistemas distribuídos. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Instituto de Matemática e 
Estatística 
Formas Possíveis para Modelagem 
 Estudo das máquinas abstratas ou autômatos e certos 
problemas computacionais. 
 Está relacionada à teoria das linguagens formais. 
Teoria dos Autômatos 
  Objeto de estudo da Ciência da Computação Teórica e Matemática Discreta. 
 Representação finita de uma linguagem formal que pode 
ser um conjunto infinito. 
Variedade de autômatos - máquina de estados finitos. 
Autômato - do grego αὐτόματα = “autuação” - “sem 
influência externa”. 
Círculos = estados; Setas = transições; 
Entrada = estado atual e símbolo recente. 
Quando o autômato recebe um símbolo de entrada, ele faz uma transição (ou 
salto) para outro estado, de acordo com sua função de transição. 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Instituto de Matemática e 
Estatística Formas Possíveis para Modelagem 
 Construção feita de estados para determinar se a entrada pode ser aceita ou rejeitada. 
 Parece com um jogo de tabuleiro básico 
  cada espaço no tabuleiro representa um estado 
  cada estado tem informações sobre o que 
fazer quando máquina recebe uma entrada. 
 Quando a máquina recebe um nova entrada, ela analisa o estado e escolhe um novo 
local baseada na informações sobre o que fazer ao receber essa entrada nesse estado. 
Autômatos 
 Executa (ou roda) uma sequência de entradas em passos de tempo discretos. 
 Processa uma entrada obtida de um conjunto de símbolos ou letras - alfabeto. 
Autômato: 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Instituto de Matemática e 
Estatística Formas Possíveis para Modelagem 
 Símbolos de entrada formam uma sequência de símbolos - palavra. 
 Contém um conjunto finito de estados. 
 Cada instante durante a execução, o autômato está em um de seus estados. 
 Nova entrada leva à transição para outro estado, segundo função de transição. 
 Lê palavra de entrada e faz a transição de estado, até palavra totalmente lida. 
 Estado em que o autômato para é chamado de estado final. 
 Estado final define se autômato pode aceitar ou rejeitar palavra de entrada. 
 Existe subconjunto de estados de aceitação. 
 Conjunto de todas as palavras aceitas por um autômato é linguagem do autômato. 
 Caso particular de processamento estocástico com estados discretos. 
 Mudanças de estado do sistema são chamadas transições. 
 Probabilidades de mudanças de estado chamadas de probabilidades 
de transição. 
Cadeia ou Processo de Markov - Andrei Markov 
Modelagem Matemática 
Sistemas Dinâmicos Discretos 
Instituto de Matemática e 
Estatística 
Formas Possíveis para Modelagem 
 Sequência de variáveis aleatórias com a propriedade de Markov, definindo a 
dependência de série única entre períodos adjacentes. 
 Processo caracterizado por um espaço de estado, uma matriz de 
transição descrevendo as probabilidades de transições de 
particulares e um estado inicial (ou a distribuição inicial) através do 
espaço de estado. 
 Distribuição de probabilidade do próximo estado depende só do estado atual. 
 Estados anteriores são irrelevantes para a predição dos estado. 
Instituto de Matemática e Estatística