AULA 10 PPT - OTIM DE SISTEMAS DE TRANS GST0311

Prévia do material em texto

OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Aula 10 – Teoria das Filas
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Problema do Fluxo Máximo
Objetivos:
Identificar o que é a Teoria das Filas; 
Verificar como a Teoria das Filas pode ajudar nos transportes;
Compreender como evitar as filas nas Centrais de Distribuição (CD’s).
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
*
Luís Otavio de Marins Ribeiro
*
TEORIA DAS FILAS
Introdução à Teoria das Filas
 Segundo Tanenbaum (2002),
 A teoria de filas é uma das mais interessantes aplicações da teoria da probabilidade, sendo de grande importância para a análise e dimensionamento de sistemas de comunicações e também em sistemas ligados à ciência da computação. 
É possível inclusive se aplicar em um sistema de recebimento e distribuição de produtos, possibilitando a otimização do sistema de transporte. 
*
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Introdução à Teoria das Filas
 Segundo Tanenbaum (2002),
O sistema de filas aparece em diversas situações do nosso cotidiano, tais como:
 Fila de pessoas em supermercados e bancos.
Fila de pessoas para embarcar em um avião.
Fila de carros em um semáforo.
Fila de carros aguardando por conserto em uma oficina.
Fila de containers a serem descarregados em um porto.
Filas de pedidos pendentes a serem recebidos.
Filas de pedidos pendentes a serem distribuídos.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Para Tanenbaum (2002),
Sistemas de fila também são formados em sistemas e redes de comunicações: 
Fila de chamadas telefônicas aguardando por linha em um PABX;
Fila de pacotes aguardando por transmissão;
Fila de pacotes aguardando por roteamento/comutação;
Fila de pacotes recebidos na placa de rede de um terminal;
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Para Tanenbaum (2002),
 Sistemas de fila também são formados em sistemas e redes de comunicações: 
Fila de amostras de voz recebidas em um telefone IP;
Fila de símbolos a serem codificados em um transmissor de TV Digital;
Fila de pedidos a serem separados dentro de uma Central de distribuição;
etc.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
O que é um Sistema de Filas?
Em Tanenbaum (2002) pode ser visto que,
Um sistema de filas (Q – Queuing System) é um sistema composto por:
Uma ou mais filas (W – Waiting Line) onde são armazenados os elementos que aguardam por atendimento;
Um ou mais servidores (S – Servers) que atendem os elementos;
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
O que é um Sistema de Filas?
Em Tanenbaum (2002) pode ser visto que,
Um sistema de filas (Q – Queuing System) é um sistema composto por:
Um processo de chegada, que define como os elementos chegam ao sistema;
Um processo de atendimento, que define como os elementos são atendidos pelo sistema;
O tamanho da população que gera os elementos;
Caminhões aguardando para carregar ou descarregar.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
O que é um Sistema de Filas?
 A Teoria das Filas procura através de análises matemáticas detalhadas, encontrar um ponto de equilíbrio que satisfaça o cliente e seja viável economicamente para o provedor do serviço
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
O que é um Sistema de Filas?
   Exemplo:
 	Seja o caso de uma Central de Distribuição, em que o “conferente da plataforma” leva em média 40 min para carregar ou descarregar um caminhão, e que o número médio de caminhões que chegam a Central é de 20 caminhões/dia e, a Central fica em operação 10 h por dia.
Pergunta:
	Há formação de fila nesta Central?
Solução:
	Utilização da facilidade 
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
   Vamos refletir quanto ao resultado. Se a Central funciona 10 h por dia e, o tempo necessário para atender o funcionamento descrito é de 13,33 h, podemos concluir que teremos a formação de uma fila de espera, sem possibilidade de atendimento de parte dos caminhões. Neste caso deve ser pensado em como poderemos, criar uma janela de horário que permita atender a necessidade dentro do tempo disponível.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
  Na logística do transporte, podemos utilizar as técnicas da teoria das filas para se evitar o congestionamento dentro de uma central de distribuição. Utilizando- se da técnica de janela de horários, que marca determinar horário para chegada e horário para partida dos veículos envolvidos nas tarefas, pode ser ordenado entrada e saída sem que se forme o congestionamento.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
  Podemos exemplificar os tipos de modelos de Centrais em um sistema de filas:
 Também é possível ver em Tanenbaum (2002),
 Sistema de Filas com 1 Central de Distribuição (CD) e várias filiais
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
  Sistema de Filas com mais de 1 Central de Distribuição (CD) e várias filiais.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
   Notação de Kendall e Notação Expandida
 Para Andrade (1998),
A notação de Kendall (David Kendall) foi desenvolvida em 1951 para descrever o comportamento de um sistema de fila em uma única frase:
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Notação de Kendall Expandida
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Notação de Kendall e Notação Expandida
 
Andrade (1998) também diz que,
 
É comum vermos sistemas definidos com a notação simplificada:
 
	 A/B/m.
 
Neste caso assume-se que não há limite para o tamanho da fila, a fonte de clientes é infinita, e a disciplina de tratamento é FIFO (PEPS – Primeiro a Entrar Primeiro a Sair)
 
A/B/m// /FIFO
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Notação de Kendall e Notação Expandida
 Processo de Chegada (A)
Descreve o processo que modela as chegadas de elementos ao sistema.
Também é possível encontrar em Andrade (1998) que o,
Processo de Atendimento (B)
 
Descreve o processo que modela o atendimento de elementos no sistema.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Notação de Kendall e Notação Expandida
 As seguintes opções são utilizadas para ambos:
 
M	Markoviano (Distribuição Exponencial)
D	Determinístico (Constante)
Ek	Erlang (Erlang-k)
Hk	Hiperexponencial
G	Genérico (Intervalo de tempo entre chegadas é tratado de forma 	genérica, independente da distribuição)
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Notação deKendall e Notação Expandida
 
Segundo Andrade (1998),
 
Tamanho da População (S)
Descreve o tamanho da população que gera elementos para o sistema. Tipicamente é considerada como infinito. Ex. ligações chegando, clientes na lanchonete. 
Disciplina de Serviço (X)
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Notação de Kendall e Notação Expandida
Os elementos que aguardam por serviço na fila podem ser selecionados de acordo com uma regra chamada disciplina de serviço. Dentre as principais disciplinas estão:
 
FCFS – First Come First Served (**FIFO)
Primeiro elemento que chega é o primeiro a ser atendido.
LCFS – Last Come First Served
Último elemento que chega é o primeiro a ser atendido.
SIRO – Service In a Random Order
Elementos são atendidos em ordem aleatória. 
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Processo de Nascimento e Morte e Diagrama de Estado
É uma classe especial de processos estocásticos em que são permitidas somente transições aos estados vizinhos.
As probabilidades de transição são determinadas em função do estado atual e das médias das distribuições dos processos de chegada e de atendimento.
Processo de Nascimento e Morte e Diagrama de Estado
Assim, para um sistema em equilíbrio tem-se:
 Onde:
k – Média de chegada de elementos no estado K.
k – Média de saída de elementos no estado K.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Para cada novo elemento que chega se for possível ele será atendido, caso não seja possível, ele entra na fila (é armazenado), acontece o nascimento de um estado. Isso acontecerá enquanto o atendimento estiver sendo feito a outro elemento, quando é finalizado o atendimento de um elemento (ele sai do sistema de filas) nesse momento acontece o que se chama de “morte” de um estado.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
1ª Questão
Pode ser afirmado sobre a teoria das filas:
É uma das mais interessantes aplicações da teoria da probabilidade.
Não é de grande importância para a análise e dimensionamento de sistemas de comunicações e também em sistemas ligados à ciência da computação. 
É uma das mais interessantes aplicações da teoria dos grafos.
Não é uma das mais interessantes aplicações da teoria da probabilidade.
É de grande importância para a análise e dimensionamento de sistemas de comunicações e não em sistemas ligados à ciência da computação.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
1ª Questão
Pode ser afirmado sobre a teoria das filas:
Não é de grande importância para a análise e dimensionamento de sistemas de comunicações e também em sistemas ligados à ciência da computação. 
É uma das mais interessantes aplicações da teoria dos grafos.
É uma das mais interessantes aplicações da teoria da probabilidade.
Não é uma das mais interessantes aplicações da teoria da probabilidade.
É de grande importância para a análise e dimensionamento de sistemas de comunicações e não em sistemas ligados à ciência da computação.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
2ª Questão
O processo de disciplina de serviço na notação de Kendall:
Descreve os elementos que aguardam por serviço na fila podem ser selecionada de acordo com uma regra.
Descreve o processo que modela as chegadas de elementos ao sistema.
Descreve o processo que modela o atendimento de elementos no sistema.
Descreve o tamanho da população que gera elementos para o sistema.
Descreve o tamanho da população que não gera elementos para o sistema.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
2ª Questão
O processo de disciplina de serviço na notação de Kendall:
Descreve o processo que modela as chegadas de elementos ao sistema.
Descreve o processo que modela o atendimento de elementos no sistema.
Descreve o tamanho da população que gera elementos para o sistema.
Descreve os elementos que aguardam por serviço na fila podem ser selecionada de acordo com uma regra.
Descreve o tamanho da população que não gera elementos para o sistema.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
3ª Questão
Sobre a disciplina de serviço FCFS – First Come FirstServed (**FIFO) é correto afirmar que:
O primeiro elemento que chega é o primeiro a ser atendido.
Último elemento que chega é o primeiro a ser atendido.
Elementos são atendidos em ordem aleatória.
Os elementos são atendidos em ordem par, de chegada.
Os elementos são atendidos em ordem impar, de chegada.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
3ª Questão
Sobre a disciplina de serviço FCFS – First Come FirstServed (**FIFO) é correto afirmar que:
O primeiro elemento que chega é o primeiro a ser atendido.
Último elemento que chega é o primeiro a ser atendido.
Elementos são atendidos em ordem aleatória.
Os elementos são atendidos em ordem par, de chegada.
Os elementos são atendidos em ordem impar, de chegada.
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 10 – TEORIA DAS FILAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
BONS ESTUDOS E ATÉ A PRÓXIMA