Curso: Engenharia de Produção Vamos admitir que o tempo de atendimento (tempo de serviço) de clientes diferentes são variáveis aleatórias independentes e que o atendimento de cada consumidor é dado por uma variável S tendo função densidade s(t). Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Curso: Engenharia de Produção Por esse motivo µ será denominada de taxa Vamos denominar 1/µ o tempo médio de de serviço. Por exemplo µ = 5, significa que se atendimento de um cliente. Tem-se, então que: 1 ∞ = ∫ ts( t )dt µ 0 A variável 1/µ será medida em horas por sempre existirem clientes, o atendente poderá atender a 5 clientes por hora, em média, e o tempo médio de serviço (atendimento) para cliente, de modo que µ será medida em cada consumidor será de 1/5 hora. clientes por hora. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Na notação de Kendall, uma fila é descrita por: Curso: Engenharia de Produção David George Kendall (1918 - 2007) estatístico britânico professor das universidades de A/B/C/Z/K/m Ou mais resumidamente por A/B/C, onde é assumido que Z = FIFO, K = ∞, m = ∞. Oxford e Cambridge. Foi um dos maiores especialistas Probabilidade e Análise em de Dados. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 1 Curso: Engenharia de Produção A/B/C/Z/K/m Valores de A mais comuns. Curso: Engenharia de Produção A/B/C/Z/K/m Valores de B mais comuns. Os tempos de serviço: Os tempos entre chegadas: M: são iid tendo uma distribuição exponencial; M: são iid tendo uma distribuição exponencial; G: são iid tendo uma distribuição genérica; G: são iid tendo uma distribuição genérica; D: são iid e determinísticos; D: são iid e determinísticos; Er,k: são iid com distribuição de Erlang de Er,k: são iid com distribuição de Erlang de parâmetros: r e k. parâmetros: r e k. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Curso: Engenharia de Produção A/B/C/Z/K/m A/B/C/Z/K/m Z será omitido quando Número de servidores A terceira característica (C) representa o número de servidores que atuam em paralelo. Disciplina do serviço. FIFO = First In, First Out ou FCFS = First Come, First Served; LIFO = Last In, First Out ou LCFS = Last Come, First Served; SIRO = Service In Random Order; GD = Disciplina Genérica. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Curso: Engenharia de Produção A/B/C/Z/K/m A/B/C/Z/K/m K Número máximo de clientes no sistema. a disciplina for FIFO. é quando for infinito. O número de clientes incluem os que estão na fila e os em atendimento. m é omitido omitido Tamanho da população. quando for infinito. A menos que o número de clientes seja o mesmo que o de servidores a população é considerada infinita. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 2 Curso: Engenharia de Produção A notação utilizada na teoria das filas é variada mas, em geral, as seguintes são comuns: λ = número médio de clientes que entram Curso: Engenharia de Produção Lq = número médio de clientes na fila; Ls = número médio de clientes sendo atendidos; W = tempo médio que o cliente fica no sistema; Wq = tempo médio que o cliente fica na fila; no sistema por unidade de tempo; µ = número médio de clientes atendidos (que saem do sistema) por unidade de tempo; L = número médio de clientes no sistema; Ws = tempo médio que um cliente leva para ser atendido. Nt = Número de clientes no sistema em t. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Wq(t) = FDA do tempo de espera na fila; wq(t) = fdp to tempo de espera na fila; W(t) = FDA do tempo de permanência no sistema; Curso: Engenharia de Produção Um dos objetivos do estudo das filas é determinar o tempo que um cliente fica no sistema. Assim se um sistema de filas está em estado estacionário, tem-se (Leis de Little): T = tempo gasto no sistema. L = λW Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Lq =λ λWq L s = λ Ws Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Curso: Engenharia de Produção David John Dutton Conant Lembrar que L é espresso em termos de Little (1928 - ) graduado em número de clientes, λ é expresso em termos de Física pelo MIT, em 1948, Foi o clientes por hora e W é expresso em horas. primeiro doutor em PO, obtendo Assim λW tem a mesma unidade (clientes) de L. o título em 1955. É professor do MIT desde 1962, tendo trabalhado anteriormente na GE. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística As três equações anteriores são válidas para qualquer sistema de filas. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 3 Curso: Engenharia de Produção Representando por pk a probabilidade de que o sistema contenha k membros (ou esteja no estado Ek ) em um momento t futuro, tem∞ se: ∑ pk = 1 Curso: Engenharia de Produção Fluxo de Entrada: Ek = λk-1pk-1 + µk+1pk+1 Fluxo de Saída: Ek = (λ λk + µk)pk k=0 Para que o sistema esteja em equilíbrio é necessário que em algum momento: Em equilíbrio os dois fluxos devem ser iguais e então: Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Curso: Engenharia de Produção k −1 λk-1pk-1 + µk+1pk+1 = (λ λk + µk)pk pk = p0 ∏ i =0 λi µ i +1 p0 = e p1 = Para Curso: Engenharia de Produção k = 0 i =0 λi µ i +1 e de a existência estados das estacionários (steady-state) pk define-se: Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística ∞ k −1 para k = 0, 1, 2, ... é a estudar probabilidades λ 0 λ 1 ... λ k −1 p µ 1 µ 2 ... µ k 0 S1 = ∑ ∏ A relação pk λi µi + 1 principal equação da teoria das filas. λ0 p µ0 0 Então: pk = 1+ ∑ ∏ k = 1 i =0 A solução dessa equação pode ser obtida considerando inicialmente k = 0, que leva a: 1 ∞ k −1 ∞ k −1 λ i S 2 = ∑ 1 / λ k ∏ k =0 i = 0 µi + 1 Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção É o caso Ergódico (S1 < ∞ e S2 → ∞) que fornece probabilidades de equilíbrio pk e esse é Diz-se, então, que um processo será: o que interessa estudar. Pode-se notar que a Ergódico se: S1 < ∞ e S2 → ∞; condição de Ergodicidade é satisfeita sempre Recorrente Nulo se: S1 → ∞ e S2 → ∞; que a seqüência λk/µ µk é menor do que a unidade Transiente se: S1 → ∞ e S2 < ∞; para algum k em diante, isto é, se existe algum k0 tal que para k ≥ k0 tem-se: λk/µ µk < 1. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 4 Curso: Engenharia de Produção Curso: Engenharia de Produção Lembrar que um sistema M/M/1/GD/∞/∞ tem um tempo de inter chegadas exponencial (a taxa de chegadas por unidade de tempo é λκ = λ para k = 0, 1, 2 …) e um único servidor com tempo de atendimento também exponencial (a taxa de atendimento será assumida como sendo µκ = µ para k = 0, 1, 2, …). Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Assim: Curso: Engenharia de Produção ∞ pk k =0 p0 S1 = ∑ k −1 λ λ λi pk = p0 ∏ = p0 ∏ = p 0 i =0 µ i +1 i =0 µ µ k −1 k para k ≥ 0 A condição para que o sistema seja ergódico (e assim tenha uma solução de equilíbrio pk > 0) é que S1 < ∞ e S2 → ∞. Nesse ∞ λ = ∑ k=0 µ Essa série irá convergir se e somente se (λ λ/µ µ) < 1 ou λ < µ. A segunda condição de Ergodicidade torna-se: ∞ 1 k=0 λ(pk p0 ) S2 = ∑ caso a primeira condição, torna-se: Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística k < ∞ ∞ = ∑ k =0 Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Esta condição será satisfeita se (λ λ/µ µ) < 1, assim a condição necessária e suficiente de ergodicidade do sistema M/M/1 é que λ < µ. Para resolver as equações em relação a p0 partimos de: p0 = 1 ∞ k −1 1+ ∑ ∏ k =1 i=0 λi µi +1 = 1 ∞ λ 1 + ∑ k =1 µ Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 1 µ k =∞ λλ k Curso: Engenharia de Produção Essa soma converge se λ < µ e então: p0 = 1+ 1 λ = 1− λµ µ 1−λ µ Fazendo λ/µ = ρ segue que: pk = (1 – ρ) ρk para k = 0, 1, 2, .... Assim o número de usuários no sistema segue uma distribuição geométrica de parâmetro 1 – ρ. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 5 Curso: Engenharia de Produção Uma medida básica de um sistema de filas é o número esperado de clientes no sistema Curso: Engenharia de Produção De forma similar pode-se determinar a variância σ2N e o desvio padrão σN do número de clientes no sistema que é dado por: que é dado por: ∞ ρ E(N ) = L = ∑ k pk = (1 − ρ) ∑ k ρk = k=0 k =0 1−ρ ∞ ∞ 2 σ2N = ∑ pk ( k − N ) = k =0 ( 1− ρ)2 Assim o desvio padrão é dado por: σN = Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística ρ ρ 1−ρ Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Define-se ρ = λ/µ como a intensidade de trânsito de um sistema de filas ou fator de utilização ou ainda taxa de utilização do Curso: Engenharia de Produção Assim, por exemplo, se λ = 6 clientes por hora e µ = 4 clientes por hora. Se o servidor trabalhar todo o tempo ele só poderá atender sistema. Para o sistema atingir um estado estacionário em média a 4 pessoas por hora. Assim o é necessário que 0 ≤ ρ < 1. Se ρ ≥ 1 é fácil de ver número médio de clientes por hora irá que o estado estacionário não será alcançado. aumentar de 6 – 4 = 2 clientes por hora. Quando ρ = 1, o sistema torna-se instável. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Dessa forma a fila aumentaria sem limites e não existe uma distribuição do estado estacionário. Se ρ = 1, então a não existência de um estado estacionário não é óbvia, mas a uma análise mais aprofundada indica que ele não existe. Curso: Engenharia de Produção Derivação de L De agora em diante será assumido que ρ < 1, assegurando que a distribuição de probabilidade do estado estacionário pk = ρk(1 - ρ) existe. Assumindo que o estado estacionário tenha sido alcançado, o número médio de consumidores no sistema é dado por: Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 6 Curso: Engenharia de Produção Curso: Engenharia de Produção ∞ ∞ ∞ S - ρS = ρ + ρ2 + ρ3 + ... = ρ/(1 – ρ) k =0 k =0 j= 0 Assim: S = ρ/(1 – ρ)2 = V(N) L = ∑ k pk = ∑ k ρk (1 − ρ) = (1 − ρ) ∑ k ρk Definindo: Então L = (1 – ρ)S = (1 – ρ)[ρ ρ/(1 – ρ)2] ∞ S = ∑ k ρk = ρ + 2 ρ2 + 3 ρ3 + ... L = ρ/(1 – ρ) = (λ λ/µ µ)/[1 – (λ λ/µ µ)] = λ/(µ µ – λ) k =0 Portanto: L = λ/(µ µ – λ) = número médio de Tem-se: ρS = ρ2 + 2ρ ρ3 + 3ρ ρ4 + ... clientes no sistema. Subtraindo ρS de S vem: Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Curso: Engenharia de Produção Se k pessoas estiverem no sistema (k ≥ 1), Derivação de Lq Em algumas situações existe interesse em saber o número médio de pessoas esperando então k – 1 estarão esperando na fila. Assim se o sistema estiver em estado estacionário: ∞ ∞ ∞ k =1 k =1 k =1 L q = ∑ ( k − 1) pk = ∑ k pk − ∑ pk na fila. Esse valor será representado por Lq. Note que nenhum ou apenas um cliente estiver Assim Lq = L – (1 – p0) = L – ρ no sistema então ninguém estará esperando na Lq = ρ2/(1 – ρ) = λ2/µ µ(µ µ – λ) fila. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Curso: Engenharia de Produção Então: Lq = λ2/µ µ(µ µ – λ) Utilizando esses resultados O valor de Ls é também de interesse, isto mais o Teorema um podemos determinar outras relações: Tem-se: L = ρ/(1 ρ/(1 – ρ) e L = λW. Assim W = L/λ λ, então W = 1/(µ µ – λ) Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística é, o número médio de clientes sendo atendidos: Ls = 1 – p0 = 1 – ( 1- ρ) = ρ ρ) – ρ = Assim Lq = L – Ls = ρ/(1ρ/( = ρ2/(1 – ρ) Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 7 Curso: Engenharia de Produção Curso: Engenharia de Produção Também Lq = λ2/[µ µ(µ µ – λ)] e Wq = Lq /λ, λ, Outro então: Wq = λ/[µ µ(µ µ – λ)] = ρ/(µ µ − λ) Observe que a medida que ρ se aproxima de 1, tanto W quanto Wq tornam-se muito grandes. Se ρ se aproxima de zero, W se resultado de interesse é a probabilidade de que exista pelo menos k clientes no sistema: ∞ ∞ i =k i =k P( N ≥ k ) = ∑ pi = ∑ (1 − ρ) ρi = ρk aproxima de zero e Wq se aproxima de 1/µ µ que é a taxa média de serviço. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Pode-se ver assim que a probabilidade de existirem mais do que k clientes no sistema é uma função geometricamente decrescente do número k que decresce rapidamente. Curso: Engenharia de Produção Aplicando a lei de Little podemos obter outra expressão para o tempo médio gasto no sistema, isto é: W=T= Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística N ρ 1 1 / µ = = λ 1 − ρ λ 1 − ρ Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Função de distribuição acumulada do Curso: Engenharia de Produção Tem-se Wq(0) = P(Tq ≤ 0) = P(N = 0) = 1 – ρ e para t > 0, tem-se: tempo de espera na fila ∞ Seja Wq(t) a função de distribuição acumulada de Tq = tempo que um usuário espera Wq ( t ) = ∑ P( k usuários no sistema atendidos até o tempo t) k =0 Daí segue que: na fila. Então: Wq(t) = P(Tq ≤ t). Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Wq(t) = 1 – ρe-(µ – λ)t Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 8 Curso: Engenharia de Produção Função densidade do tempo de espera na fila Curso: Engenharia de Produção Função de distribuição acumulada do tempo de permanência no sistema w q (t) = d W q (t) dt d[1 − ρ e −( µ −λ ) t] = = ρ(µ − λ ) e −(µ − λ ) t dt De forma análoga ao caso anterior a função acumulada do tempo T de permanência no sistema W(t) é dada por: Assim wq(t) = ρ(µ – λ)e-(µ – λ)t µ(1 −ρ)t W(t) = P(T ≤ t) = 1 – e-µ(1 Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Assim, pode-se perceber que a VAC T = tempo gasto no sistema, segue uma distribuição exponencial de parâmetro µ(1−ρ). Curso: Engenharia de Produção O valor esperado (média) da variável Tq = tempo que um usuário espera na fila é : ∞ ∞ W q = E( T q ) = ∫0 t w q( t )dt = ∫0 tρ(µ − λ ) e−(µ −λ )t dt = O valor esperado dessa variável é : E(T) = = 1 1 = µ(1 − ρ ) µ − λ Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística λ ρ = µ(µ − λ ) µ − λ Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Probabilidade do tempo de espera na fila ser maior do que t > 0 P(Tq > t) = 1 – Wq(t) = ρe-µ(1− ρ)t Probabilidade de que o tempo no sistema seja maior do que t > 0 µ(1 −ρ)t P(T > t) = 1 – W(t) = e-µ(1 Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção O percentil 0 < p < 1 de clientes que irão esperar no sistema menos do que tp é: µ(1 −ρ)t = p P(T ≤ tp) = W(t) = 1 - e-µ(1 Assim o tempo tp tal que a probabilidade do tempo de espera no sistema seja menor do tp é dado µ(1 µ( 1 −ρ)t = p ou por: tp = W(t) = 1 - e-µ( tp = 1 1 ln( ) µ (1 − ρ) 1 − p Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 9 Curso: Engenharia de Produção Curso: Engenharia de Produção O percentil 0 < p < 1 de clientes que irão tq = esperar na fila menos do que tp é: Esta fórmula só é válida se p que for P(T ≤ tp) = Wq(t) = 1 - ρe-µ(1− ρ)t = p Assim o tempo tp tal que a probabilidade do tempo de espera na fila seja menor do tp é µ(1 −ρ)t = p ou dado por: tp = Wq(t) = 1 - ρe-µ(1 Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 1 ρ ln( ) µ (1 − ρ) 1 − p maior do que “1 – ρ”. Todos os postos percentis abaixo deste valor serão iguais a zero. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Um média de 10 carros por hora chegam a a um drive-thru de um único funcionário. O atendente leva em média 4 minutos para atender cada cliente. Tanto as chegadas quanto o atendimento seguem Curso: Engenharia de Produção 1. Qual é a probabilidade de que o atendente esteja livre? 2. Qual é o número médio de carros esperando para ser atendidos (um carro que está sendo atendido não é contado na fila)? uma distribuição exponencial. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção 3. Qual o tempo médio total que um cliente gasta para ser servido? 4. Na média, quantos consumidores serão atendidos no período de uma hora? Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção Por hipótese estamos lidando com um sistema M/M/1 para o qual λ = 10 carros por hora e µ = 15 carros por hora. Assim ρ = 10/15 = 2/3. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 10 Curso: Engenharia de Produção 1. Tem-se p0 = 1 – ρ = 1 – 2/3 = 1/3. Assim o atendente estará livre 1/3 do tempo. 2. Lq = ρ2/(1 – ρ) = (2/3)2/[1 – (2/3)] = 4/3 = 1,33 carros. Curso: Engenharia de Produção 4. Se o atendente estivesse sempre ocupado ele atenderia uma média de µ = 15 consumidores por hora. Como ele está ocupado apenas 2/3 do tempo então ele 3. W = L/λ. Tem-se L = ρ/(1 – ρ) = atenderá (2/3)15 = 10 consumidores. = (2/3)/[1 – (2/3)] = 2 consumidores. Assim W = 2/10 = 0,2 horas = 12 minutos. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística Curso: Engenharia de Produção GRIMMETT, G. R., SITRZAKER, D. R. Probability and Random Processes. Oxford (London): Oxford University Press, 1991. KLEINROCK, Leonard. Queueing Systems: v. 1: Theory. New York: John Wiley, 1975. WISTON, Wayne L. Operations Research: Applications and Algorithms. 3 ed. Belmont (CA): Duxbury Press, 1994. Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística 11