Teoria das Filas

Prévia do material em texto

Portos e Vias Navegáveis
Rodrigo Marques Beneveli
Sistema Operacional Portuário –
Teoria das Filas
Introdução
Qualquer pessoa sabe exatamente o que são filas em decorrência das
experiências que o dia-a-dia nos coloca. Nós entramos em uma fila para
utilizar um banco, para pagar pelas compras em um supermercado, para
comprar ingresso em um cinema, para pagar o pedágio em uma estrada e
tantas outras situações.
Certamente não é agradável entrar em uma fila e esperar pelo serviço (o
ideal é chegar ao local de serviço e ser imediatamente atendido) e,
quando a espera é longa, ficamos aborrecidos (algumas pessoas ficam
profundamente irritadas).
Como consequência de nossas amargas experiências tomamos algumas
atitudes, tais como não mais comprar em um determinado supermercado,
mudar a conta bancária para outra agência (ou banco), etc. Visto pelo
ângulo das empresas, estas atitudes significam perda de negócio.
Introdução
As filas são dispendiosas, isto é válido em qualquer ambiente, indo de
fábricas a um supermercado e não de forma diferente nos sistemas de
transporte. A espera em filas nada mais é que o aumento nos custos e
atrasos no atendimento as embarcações.
Há muito tempo tem se falado no Brasil em exportação, equilíbrio da balança
comercial dentre outros assuntos do gênero e é sabido, que o
desenvolvimento do comércio internacional está ligado diretamente à
questão portuária, uma vez que a maioria das mercadorias
comercializadas no mundo transporta-se em navios e são movimentadas
em portos.
Os portos são os lugares centrais dessa conexão com a troca internacional,
permitindo que cada país introduza, não apenas mercadorias, mas
também as mais-valias resultantes da passagem das mesmas por essa
conexão, portanto, sendo visto como uma porta de entrada, uma abertura
para a constituição de negócios, criando um amplo campo de
oportunidades industriais e comerciais para um país.
Modelagem do Sistema – Teoria das Filas
A modelagem de sistemas pode ser feita por duas abordagens inteiramente
diferentes entre si: Teoria das Filas e Simulação. A Teoria das Filas é um
método analítico que aborda o assunto através de fórmulas matemáticas.
Já a simulação é uma técnica que, usando o computador digital, procura
montar um modelo que melhor represente o sistema em estudo.
A modelagem de filas tem sido usada no transporte ferroviário, rodoviário,
aeroviário e marítimo. Especificamente no transporte marítimo, as
aplicações se referem à confecção da tabela de horários em função do
dimensionamento de portos.
A Teoria das Filas surgiu no início do século XX (1908), em Copenhague,
Dinamarca, pelo matemático Agner Krarup Erlang, quando desenvolveu
fórmulas de matemática para estudar o problema de redimensionamento
de uma companhia telefônica de Copenhague devido ao
congestionamento nas centrais telefônicas. A teoria das filas cuida dos
pontos de estrangulamentos (congestionamentos) e dos tempos de
espera, ou seja, das demoras verificadas em algum ponto do serviço
prestado.
Modelagem do Sistema – Teoria das Filas
Os componentes de um sistema de fila de espera são a população ou fonte
de potenciais embarcações e o sistema de fila de espera.
O sistema é constituído pela fila de espera propriamente dita e pelo
mecanismo de serviços que serve os elementos na fila de espera. O
mecanismo de serviço, que pode compreender um ou mais servidores,
posiciona as embarcações numa ordem determinada pela disciplina de
serviços.
Uma embarcação é uma unidade contável originária de determinada
população, que espera pela sua vez para ser servido na fila de espera,
considerando que já entrou no sistema, ocupa um servidor durante um
certo tempo e por fim sai do sistema.
O exemplo tradicional de fila compõe-se de dois elementos, como mostra a
figura a seguir. As embarcações que chegam ao sistema de fila esperam
em linha até serem atendidas, ou se o sistema estiver vazio, o recém-
chegado poderá ser atendido imediatamente. Uma vez completado o
atendimento, a embarcação deixa o sistema.
Modelagem do Sistema – Teoria das Filas
Características de um Sistema de Filas
No geral, são seis características básicas do processo de filas,
designadamente:
 Processo de chegada;
 Distribuição do tempo de serviço;
 Número de servidores;
 Capacidade do sistema;
 População de utilizadores;
 Disciplina da fila.
Características de um Sistema de Filas
Processo de Chegada
O processo de chegada indica qual o padrão de chegada das embarcações
no sistema. Apresenta comportamento estocástico, ou seja, as chegadas
ocorrem no tempo e no espaço de acordo com as leis da probabilidade.
Assim sendo, é preciso conhecer qual a distribuição de probabilidade que
descreve os tempos entre as chegadas das embarcações.
A distribuição mais comum é a de Poisson, esta teoria foi descoberta por
Siméon Denis Poisson (1781-1840) e publicada, conjuntamente com a
sua teoria da probabilidade, em 1838. Na teoria da probabilidade e na
estatística a distribuição de Poisson é uma distribuição de probabilidade
de variável aleatória discreta, que expressa a probabilidade de uma série
de eventos ocorrer num certo período de tempo se estes eventos ocorrem
independentemente de quando ocorreu o último evento, ou seja, os
tempos entre as chegadas das embarcações são exponencialmente
distribuídos.
Características de um Sistema de Filas
Processo de Chegada
O padrão de chegada de embarcações em função do tempo pode ser
permanente; nesse caso o padrão não muda no tempo, ou seja, a
distribuição de probabilidade que descreve as chegadas é independente
do tempo. Também pode ser não permanente, isto é, o padrão de
chegada muda com o tempo.
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 e 𝟏/𝝀 é o tempo médio entre chegada.
Características de um Sistema de Filas
Distribuição do Tempo de Serviço
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 μ é a taxa média de atendimentos por unidade de tempo e 𝟏/𝛍
e o tempo médio de serviço a uma embarcação.
Características de um Sistema de Filas
Número de Servidores
Esse componente é também conhecido como número de canais de serviço.
Indica a quantidade de "pontos de atendimento" do sistema, de forma a
servir as embarcações paralelamente. Quando um sistema possui mais
de um servidor (multiservidor ou multicanal), ele pode apresentar duas
variações. Em um sistema de fila única, existe uma única fila para todos
os servidores, como em um caixa de banco. Em um sistema de múltiplas
filas, existe uma fila para cada servidor, como em um caixa de
supermercado.
Quando existirem infinitos servidores, ou seja, toda embarcação que chega é
atendida imediatamente, temos um caso especial conhecido como
"Centro de atraso".
Características de um Sistema de Filas
Capacidade do Sistema
Representa o número máximo de embarcações que o sistema suporta,
incluindo os que estão em espera e os que estão sendo atendidos. A
capacidade pode ser infinita ou finita. Se a capacidade for finita, quando o
sistema estiver lotado nenhuma embarcação pode entrar até que uma
embarcação saia do sistema, liberando espaço.
Características de um Sistema de Filas
População de Utilizadores
A população em que dá origem, ou gera as embarcações do sistema. Essa
população pode ser finita ou infinita. Considera-se população infinita
quando a probabilidadede ocorrer uma nova chegada, num dado
intervalo de tempo, não for influenciada pelo número de embarcações que
já se encontram no sistema. A população diz-se finita quando o número de
embarcações no sistema (fila mais atendimento) é, ou pode ser, uma
parte significativa da população.
Características de um Sistema de Filas
Disciplina da Fila
A disciplina de filas refere-se a maneira como as embarcações são
escolhidas para entrar em serviço após uma fila ser formada. A maioria
das disciplinas comuns que podem ser observadas na vida diária é FIFO
(First In First Out), ou seja, o primeiro a chegar é o primeiro a ser
atendido. Entretanto, existem outras disciplinas, tais como, LIFO (Last In
First Out), ou seja, último a chegar é o primeiro a ser atendido; os casos
ALEATÓRIOS, isto é, os atendimentos são feitos sem qualquer
preocupação com a ordem de chegada; e os casos COM PRIORIDADE,
quer dizer, os atendimentos são feitos de acordo com prioridades
estabelecidas.
Características de um Sistema de Filas
Medidas de Desempenho
Tendo em conta que o tempo perdido em filas de espera pode constituir um
custo para as organizações, entende-se a preocupação dos gestores em
melhorar as características dos sistemas de fila de espera considerando
diversas alternativas. Para isso é útil quantificar o desempenho de cada
sistema através de medidas de desempenho que constituirão uma valiosa
informação para quem decide.
Em uma situação estável, na qual embarcações chegam e entram em fila,
existindo X servidores para atendê-los, sendo λ o ritmo médio de chegada
e μ o ritmo médio de atendimento de cada atendente. Dentre as medidas
de todo este sistema, estudaremos, algumas que serão frequentemente
citadas e as chamaremos de “variáveis randômicas fundamentais”.
Características de um Sistema de Filas
Medidas de Desempenho
Para as variáveis randômicas fundamentais, existe um valor médio e uma
distribuição de probabilidades, que mostra as chances de ocorrências dos
valores. Quando se afirma que o tamanho médio de uma fila é de 5
embarcações, não está dizendo que o tamanho da fila é sempre de 5
embarcações. Em diferentes momentos de observação você pode, por
exemplo, constatar que o tamanho é de 10, 7, 3 ou que não existe fila. O
valor médio 5 significa uma média aritmética ponderada dos tamanhos da
fila durante consecutivos intervalos de tempo. Estas variáveis
fundamentais são as seguintes:
Características de um Sistema de Filas
Medidas de Desempenho
 Número médio de Embarcações na Fila (Lq)
Número médio de embarcações que aguardam o atendimento, ou seja, é o
que determina o tamanho da fila. É a característica mais relevante ao se
defrontar com a opção de escolher uma fila. A meta é não ter fila, chegar e
ser atendido. Supondo que os ritmos médios de chegada e atendimento
sejam constantes, o tamanho da fila irá oscilar em torno de um valor
médio, representado pela seguinte formulação:
sendo:
Lq = número médio de embarcações na fila (navios);
𝜆 = taxa de chegada;
𝜇 = taxa média de atendimentos por unidade de tempo.
Características de um Sistema de Filas
Medidas de Desempenho
 Número Médio de Embarcações no Sistema (L)
Número de embarcações aguardando na fila mais os que estão sendo
atendidos. Pode ser entendido também como sendo o tamanho médio na
fila mais o número médio de embarcações no atendimento, representado
pela seguinte formulação:
sendo:
L = número médio de embarcações no sistema;
𝜆 = taxa de chegada;
𝜇 = taxa média de atendimentos por unidade de tempo.
Características de um Sistema de Filas
Medidas de Desempenho
 Tempo Médio que a Embarcação Espera na Fila (Wq)
Tempo médio de espera pela embarcação na fila esperando para ser
atendido, representado pela seguinte formulação:
sendo:
Wq = tempo médio que a embarcação espera na fila (horas);
𝜆 = taxa de chegada;
𝜇 = taxa média de atendimentos por unidade de tempo;
24 = horas de um dia.
Características de um Sistema de Filas
Medidas de Desempenho
 Tempo Médio que o Embarcação Fica no Sistema (W)
Tempo médio de espera pela embarcação na fila esperando para ser
atendido mais o tempo de atendimento. A partir do número médio de
embarcações no sistema ou na fila, é possível calcular o tempo médio de
permanência da embarcação no sistema (TS) e na fila (TF), representado
pela seguinte equação:
sendo:
W = tempo médio que a embarcação fica no sistema;
𝜆 = taxa de chegada;
𝜇 = taxa média de atendimentos por unidade de tempo;
24 = horas de um dia.
Características de um Sistema de Filas
Medidas de Desempenho
 Probabilidade de que o Sistema Esteja Ocupado (ρ)
A razão ρ é chamada de “Fator de Utilização do Servidor”, o qual representa
a fração média do tempo em que o servidor (sistema) esteja ocupado.
Este fator é a base de cálculo da probabilidade de haver um número K de
embarcações no sistema, o qual definirá o tamanho da fila e o tempo
médio que as embarcações permanecem nela e no sistema, este fator é
obtido pela seguinte formulação:
sendo:
ρ = probabilidade de que o sistema esteja ocupado;
𝜆 = taxa de chegada;
𝜇 = taxa média de atendimentos por unidade de tempo.
Características de um Sistema de Filas
Medidas de Desempenho
 Probabilidade de que o Sistema esteja Desocupado (P0)
Refere-se a probabilidade de logo após a chegada da embarcação, o mesmo
seja atendido, situação ideal, representada pela seguinte formulação:
sendo:
P0 = probabilidade que o sistema esteja desocupado;
ρ = probabilidade de que o sistema esteja ocupado.
Características de um Sistema de Filas
Medidas de Desempenho
 Probabilidade de Existirem n Embarcações no Sistema (Pn)
Refere-se a probabilidade de existência de embarcações no sistema, quando
a chegada de uma nova embarcação na fila, representada pela seguinte
formulação:
sendo:
Pn = probabilidade de existirem n embarcações no sistema;
ρ = probabilidade de que o sistema esteja ocupado.
Características de um Sistema de Filas
Medidas de Desempenho
Outras medidas que os gestores podem utilizar para tomar decisões que são
mais pormenorizadas mas igualmente úteis:
 Probabilidade de existirem no sistema k ou mais embarcações →
P(n ≥ k) = 𝑛=𝑘
∞ 𝑃𝑛
 Probabilidade de o tempo de espera na fila seja zero → P (Wq = 0);
 Probabilidade de o tempo de espera na fila exceder t → P (Wq > t);
 Probabilidade de o tempo gasto no sistema exceder t → P (W > t).
Modelos de Fila de Espera
Modelos de Fila de Espera
A notação de processos de filas mais utilizada atualmente foi proposta pelo
matemático inglês David George Kendall, em 1953, e é descrita por um
série de símbolos, A/B/c/K/m/Z, conforme mostrada no quadro a seguir,
em que: A descreve a distribuição dos intervalos entre chegadas; B
descreve a distribuição do tempo de serviço; c é o número de canais de
serviços ou capacidade de atendimento; K é o número máximo de clientes
permitidos no sistema; m é o tamanho da população que fornece clientes
e Z é a disciplina da fila.
Modelos de Fila de Espera
Modelos de Fila de Espera
Modelos de Fila de Espera
Modelos de Fila de Espera
 Modelo M/M/1
Este modelo é baseado em processos sem memória na distribuição negativa
que, aplicados às filas de espera associam “vida” a uma chegada à fila e
“morte” à saída de uma embarcação depois de atendido”. M/M/1
corresponde ao modelo básico onde o sistema tem uma distribuição das
chegadas de Poisson e dos tempos de atendimento exponencial e contém
um só servidor, a capacidade do sistema e da população são infinitas e a
disciplina é FIFO (mais comum), correspondendo a quem entra primeiro
no sistema é o primeiro a ser atendido.
Modelos de Fila de Espera
Modelos de Fila de Espera
 Modelo M/M/S
Este modelo difere do anterior apenas no número de servidores disponíveis:
S. Temos assim um modelo em que o número de servidores é S, o
sistema tem uma distribuição das chegadas de Poisson e dos tempos de
atendimento exponencial, a capacidade do sistema eda população são
infinitas e a disciplina corresponde a quem entra primeiro no sistema ser o
primeiro a ser atendido e a sair.
Gerenciando Filas
Estudam-se filas para poder modificar sistemas nos quais existem problemas
no atendimento, com o objetivo de prestar um melhor atendimento ou uma
redução de custos. O conhecimento do comportamento de uma fila,
quando alteramos algumas de suas características, pode ser fundamental
para atingirmos os objetivos citados de qualidade de atendimento e
custos. Em situações nas quais o tempo de atendimento pode variar
dentro de uma larga faixa de valores não recomenda o uso de diversas
filas. É o caso, por exemplos, de centros de distribuição de produtos, em
que existem diversos tipos de caminhões, desde os menores até os
maiores, sendo que alguns apresentam uma carga de serviço muito
grande em relação a outros, portanto, o tempo de atendimento para estes
casos será exageradamente maior que a média. Neste caso uma fila
única com diversos atendentes é a melhor solução.
Gerenciando Filas
Em outras situações, é conveniente modificar dinamicamente a quantidade
de atendentes conforme aumente ou diminua o fluxo de chegada de
clientes, como por exemplo, tornar disponíveis atendentes extras no
horário de pico de chegada de caminhões em um centro de distribuição.
Às vezes a fila é impraticável, como no caso de praças de pedágio. Aqui a
existência de “passagens expressas” representa uma maneira de se
prestar um bom serviço, se levar em consideração inclusive que alguns
usuários desistem da viagem em dias e horários de pico.
Exercício Proposto
Supondo-se que a chegada de um navio ao cais portuário siga a distribuição
de Poisson, com uma taxa de 6 navios por dia. As durações médias de
atendimento por navio são de 3 horas, seguindo-se a distribuição
exponencial. Calcule os seguintes valores:
a. Qual a probabilidade de um navio chegar ao porto e não esperar para
atracar?
b. Qual é a quantidade média de navios na fila do porto?
c. Qual é a quantidade média de navios no sistema portuário?
d. Qual é a quantidade média de navios utilizando o porto?
e. Qual é o tempo médio de um navio na fila?
f. Qual deve ser a taxa de chegada de um navio para que o tempo médio
na fila seja de 3 horas?
g. Qual a probabilidade de já existirem navios no sistema?