XII. Filas de Espera (Continuação)

Filas de Espera (M/G/1): Características

Nos processos de chegada e atendimento, nem sempre se verificam distribuições Exponenciais Negativas. No caso do atendimento, se as necessidades de serviço dos clientes são muito semelhantes a distribuição dos tempos de atendimento desvia-se muito da forma Exponencial.

O modelo M/G/1 não impõe quaisquer restrições à distribuição dos tempos de serviço. Basta determinar a média, 1 / μ, e a variância, σ², dessa distribuição.

(carregar com o cursor na figura para ver em tamanho grande)
onde:

Fonte de Entrada – modela o processo de chegada dos clientes (M/G/1 = Poisson);
Fila – modela o lugar onde os clientes aguardam pelo serviço;
Disciplina da Fila – critério para escolher a ordem pela qual os clientes na fila são atendidos (M/G/1 = o primeiro a chegar é o primeiro a ser atendido, FIFO);
Mecanismo de Atendimento – ou Serviço, modela o sistema de atendimento dos clientes (M/G/1 = um servidor).

No estado estacionário, um sistema M/G/1 pode ser analisado utilizando as relações matemáticas que se seguem.


Características do Modelo M/G/1
Chegadas com distribuição de Poisson;
Taxa = λ clientes / u. tempo; População = ∞; Fila máxima = ∞.

Tempo de atendimento qualquer variável aleatória;
Média = 1 / μ; Variância = σ²; Servidores = 1.

Condição de equilíbrio λ / μ = ρ < 1
Taxa de ocupação = ρ; Taxa de desocupação = 1 - ρ


L = L_q + (λ / μ) = L_q + ρ

L_q = (λ² σ² + ρ²) / 2 (1 - ρ)

W = L / λ = W_q + (1 / μ)

W_q = L_q / λ


P₀ = 1 - ρ (taxa de desocupação)

P_n = ρⁿ P₀

P (n > k) = ρ^{k + 1}

(Franco, 2006g)

Num hipermercado, a certas horas do dia, os clientes dirigem-se a uma caixa registadora, para pagar as compras, com uma distribuição de Poisson, a uma taxa média de um de dois em dois minutos. A empregada da caixa atende os clientes por ordem de chegada (FIFO). Dado o tempo gasto a fazer as compras, os clientes estão dispostos a esperar para serem atendidos, se for necessário. O tempo de atendimento de cada cliente é, em média, 1,5 minutos, com uma variância de (9 / 4)².

1) Trata-se, portanto, de um sistema M/G/1, com taxa de chegadas λ = 0,5 clientes / minuto e tempo médio de serviço (1 / μ) = 1,5 minutos, com uma variância σ²= (9 / 4)².

2) Verificação da condição de equilíbrio: ρ = λ / μ = 0,5 × 1,5 = 0,75 < 1.
A empregada tem, portanto, capacidade para atender os clientes que se dirigem à caixa para pagar as compras. O sistema poderá atingir o estado estacionário, se as condições dadas se mantiverem por tempo suficiente. A fila de espera não cresce indefinidamente, mas varia de tamanho ao longo do tempo.

Medidas de Desempenho
1) Taxa de ocupação (ρ) =
Taxa média de ocupação do sistema =
Taxa média de ocupação do servidor =
Factor de ocupação do sistema =
Intensidade do tráfego =
Probabilidade de existir algum cliente no sistema (P {n > 0}) =
Probabilidade de ter que esperar na fila (P_w) =
Probabilidade do servidor estar ocupado (P_b) =
ρ = λ / μ = 0,75

2) Taxa de desocupação (P₀) =
Probabilidade de não existir nenhum cliente no sistema =
Probabilidade de não ter que esperar na fila =
Probabilidade do servidor estar desocupado =
P₀ =1 - ρ = 0,25

3) Número médio de clientes no sistema (L) =
L = {(λ² σ² + ρ²) / [2 (1 - ρ)]} + ρ = 4,4 clientes

4) Número médio de clientes na fila (L_q) =
Tamanho médio da fila =
L_q = (λ² σ² + ρ²) / [2 (1 - ρ)] = 3,7 clientes

5) Tempo médio no sistema (W) =
Duração média do período de ocupação do servidor =
W = L / λ = 8,8 minutos

6) Tempo médio na fila (W_q) =
Tempo médio de espera na fila =
W_q = L_q / λ = 7,3 minutos

7) Número médio de clientes na fila, quando o sistema está ocupado (L_b) =
L_b = L_q / P_w = 4,875 clientes

8) Número médio de clientes na fila, quando há pelo menos um (L_q | q > 0) =
Número médio de clientes servidos por período de ocupação do servidor =
L_q | q > 0 = μ W = 5,875 clientes

9) Número médio de clientes a serem servidos (L_S) =
Número médio de servidores ocupados (S_b) =
L_S = L - L_q = ρ = 0,75 clientes
S_b = ρ = P_b = 0,75 servidores

10) Tempo médio na fila, quando o sistema está ocupado (W_b) =
Tempo médio na fila, quando se tem de esperar =
W_b = W_q / P_w = 7,3125 / 0,75 = 9,75 minutos

11) Probabilidade de haver 0, 1, 2, …, n clientes no sistema (P_n)

12) Probabilidade de não haver mais de n (n ou menos) clientes no sistema (P {N ≤ n})

13) Probabilidade de haver mais de n clientes no sistema (P {N > n}) =
1 - Probabilidade de não haver mais de n (n ou menos) clientes no sistema = 1 - (P {N ≤ n})
Probabilidade de haver pelo menos n + 1 (n + 1 ou mais) clientes no sistema (P {N ≥ n + 1}) =
ρ^{n + 1}

14) Probabilidade de haver pelo menos n (n ou mais) clientes no sistema (P {N ≥ n}) =
ρⁿ, para n = 0, 1, 2, …

n	Pn	P {N ≤ n}	P {N ≥ n}	q	Pq	P {Q ≤ q}	P {Q ≥ q}
	(11)	(12)	(14)		(16)	(17)	(18)
0	0,25	0,25	1,00
1	0,19	0,44	0,75	0	0,19	0,44	0,75
2	0,14	0,58	0,56	1	0,14	0,58	0,56
3	0,11	0,68	0,42	2	0,11	0,68	0,42
4	0,08	0,76	0,32	3	0,08	0,76	0,32
5	0,06	0,82	0,24	4	0,06	0,82	0,24
6	0,04	0,87	0,18	5	0,04	0,87	0,18
7	0,03	0,90	0,13	6	0,03	0,90	0,13
8	0,03	0,92	0,10	7	0,03	0,92	0,10
9	0,02	0,94	0,08	8	0,02	0,94	0,08
10	0,01	0,96	0,06	9	0,01	0,96	0,06
11	0,01	0,97	0,04	10	0,01	0,97	0,04
12	0,01	0,98	0,03	11	0,01	0,98	0,03
13	0,01	0,98	0,02	12	0,01	0,98	0,02
14	0,00	0,99	0,02	13	0,00	0,99	0,02
15	0,00	0,99	0,01	14	0,00	0,99	0,01

15) Probabilidade de haver um cliente a ser servido e nenhum na fila =
P₁ = 0,19

16) Probabilidade de haver um cliente a ser servido e q na fila =
Probabilidade de haver 0, 1, 2, …, q clientes na fila (P {Q = q}) =
P₁, para q = 0
P_q + 1, para q = 1, 2, …

17) Probabilidade de não haver mais de q (q ou menos) clientes na fila (P {Q ≤ q}) =
Confiar que há espaço para q clientes esperarem, uma percentagem (probabilidade × 100) do tempo =
P {N ≤ q + 1}

Se quisermos estar confiantes de que há espaço no hipermercado para os clientes de uma caixa, pelo menos 95% do tempo, devemos ser capazes de acolher 10 clientes, incluindo o que está a ser servido, ou seja, haver espaço para uma fila de 9 clientes com os carros das compras.

18) Probabilidade de haver pelo menos q (q ou mais) clientes na fila (P {Q ≥ q}) =
P {N ≥ q + 1} = ρ^{q + 1}

(Franco, 2006j)


Variabilidade do Serviço
A variabilidade do serviço tem um efeito importante nas medidas de desempenho do sistema, para além da velocidade média do servidor. Compare-se o desempenho de três sistemas com variâncias do tempo de serviço crescentes.

Medidas de	σ2 = 0	σ2 = 2,25	σ2 = (2,25)2
desempenho	(M/D/1)	(M/M/1)
ρ	0,75	0,75	0,75
P0	0,25	0,25	0,25
L (clientes)	1,875	3	4,4
Lq (clientes)	1,125	2,25	3,66
W (minutos)	3,75	6	8,8
Wq (minutos)	2,25	4,5	7,3
Lb (clientes)	1,5	3	4,875
Wb (minutos)	3	6	9,75

O número médio de clientes no sistema (L), na fila (L_q), na fila, quando o sistema está ocupado (L_b), o tempo no sistema (W), na fila (W_q) e na fila, quando o sistema está ocupado (W_b), aumentam (linearmente) com a variância, e só dependem da taxa de chegadas, intensidade de tráfego e variância do serviço.

A variabilidade do servidor tem um efeito importante nas medidas de desempenho do sistema, para além da velocidade média do servidor.

Considerando a variância nula (M/D/1), o tamanho médio da fila (L_q), número médio de clientes na fila, quando o sistema está ocupado (L_b), o tempo médio na fila (W_q) e na fila, quando o sistema está ocupado (W_b), são exactamente metade dos valores para M/M/1.

Diminuir a variância pode, portanto, melhorar significativamente as medidas de desempenho do sistema (Franco, 2006k).


Referências

BRONSON, R.; NAADIMUTHU, G. – Investigação Operacional. 2.ª ed., Lisboa, McGraw-Hill, 2001.

HILLIER, Frederick S.; LIEBERMAN, Gerald J. - Introduction to Operations Research, 6.ª ed., Nova Iorque, McGraw-Hill, 1995.

McCLAIN, John O. Queue.XLS: A Teaching Spreadsheet for Queuing Theory. Ithaca, NY, Cornell University, 2003.

SLATER, Tom. M/M/1 Queues. «The Queueing Thery Tutor», University of Edinburgh, 2000.

TAVARES, L. V., et al.,– Investigação Operacional. Lisboa, McGraw-Hill, 1996.