Slide - Teoria das Filas Pt2 - Modelagem e Simulação de Sistemas de Produção - 2023-2

PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.1 Prof. Dr. Marco A. Mesquita 4. Teoria de Filas – Parte 2 Agenda: - M/M/1 - M/M/c - M/M/c//K/∞ (fila limitada) - M/M/c//∞/K (população finita) - M/G/∞ - M/G/1 - Redes de Filas - Teoria de Scheduling 4 20.4 Fila M/M/1  A fila M/M/1 pode ser modelada como um processo de nascimento e morte com taxa de chegada (l) e taxa de atendimento (m) constantes.  Seja r = l / m o índice de congestionamento:  Se r < 1, então o sistema é ergódico e terá uma distribuição estacionária  Senão, a fila cresce continuamente e não há distribuição estacionária (não ergódico). 0 1 2 n ... l l l l ... l m m m m m PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.2 Prof. Dr. Marco A. Mesquita 5 Distribuição Estacionária 0 1 2 j ... l l l l ... l m m m m m 0 0 r   m l  j j j =      =     1 1 2 0 1  = = = j j l m l m l m 6 Distribuição estacionária (cont.)  Impondo:  Tém-se: 1 0 =   = j j   ,2,1,0 ) 1( =   = j j j r r  PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.3 Prof. Dr. Marco A. Mesquita 7 Cálculo de L  O número médio de clientes no sistema (L), em regime estacionário (r < 1), pode ser calculado por: que se simplifica em:     =   =  =  =  = = 1 1 1 0 ) 1( ) 1( j j j j j j j j j L r r r r r  r r r r r =    = 1 ) 1( 1 ) 1( 2 L 8 Cálculo de Lq  Analogamente, o número médio de clientes na fila, é dado por: ou seja, r r r r r =   =  1 1 2 q L ) 1( )1 ( 0 1 1 1       =  =  =     =  =  = L j j L j j j j j j q PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.4 Prof. Dr. Marco A. Mesquita 9 Cálculo do Ls  O número médio de clientes em atendimento, neste caso (M/M/1), seria:  Verifica-se que: r r     =  =  =     = ) 1( 1 1 ) (1 0 0 2 1 0  sL r r r r r =   =   = 1 1 2 s q L L L 10 Fórmula de Little: L=λW  Sejam: λ = taxa efetiva de entrada no sistema (clientes/min) L = número médio de clientes no sistema Lq = número médio de clientes na fila W = tempo médio total Wq = tempo médio em fila  Para todo sistema ergódico de filas, valem as seguintes igualdades: L = λ∙W Lq = λ∙Wq PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.5 Prof. Dr. Marco A. Mesquita 11 Tempos Médios para Fila M/M/1  Tempo Médio de Fila  Tempo Médio Total  Verifica-se que: l m l  = = 1 L W ) ( l m m l l  = = q q L W m  1 =  = q s q W W W W Para uma fila M/M/1, W também apresenta distribuição exponencial com taxa m – l 12 Exemplo 2 – Posto de Combustível  Considere um posto de combustível com uma única bomba. Suponha que o processo de chegadas seja Poisson, com taxa 7,5 clientes por hora e que os tempos de atendimento sejam v.a.i. com distribuição exponencial e média 4 min. Determine os tempos médios de fila e total dos clientes. PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.6 Prof. Dr. Marco A. Mesquita 13 Solução 1. Tem-se uma fila M/M/1 com λ = 7,5 carros / h e µ = 15 carros / h. Logo, r = 0,50 2. Cálculo dos indicadores L = (0,50)/(1 - 0,50) = 1,0 carros e W = L / λ = 1,0/7,5 = 0,133 h ou 8 min Wq = W - 1/m = 4 min 14 Exemplo 2 (cont.)  Suponha que os clientes passem a abastecer seus carros com maior frequência, tal que: 1. a taxa de chegadas suba para 15 carros/h e 2. o tempo médio de serviço caia para 3 min e 20 s.  Recalcule os tempos médios de fila e total dos clientes. PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.7 Prof. Dr. Marco A. Mesquita 15 Solução 1. Tem-se: l = 2(7,5) = 15 cl. / h µ = 60/3,333 = 18 cl. / h r = 15/18 = 5/6 ou 0,833. 2. Então: L = 0,833/(1 – 0,833) = 5,0 carros e W = L / λ = 5/15 = 0,333 h ou 20 min Wq = W - 1/m = 20 – 3,333 = 16 min e 40 s Nesta situação, o tempo médio de fila é bastante superior (antes: 4 min, agora: 16 min e 40 s) 16 Relação entre ρ e L para a M/M/1 ρ L 0,30 0,40 0,50 0,60 0,70 0,80 0,90 0,95 0,99 0,43 0,67 1,00 1,50 2,33 4,00 9,00 19,0 99,0 0,0 20,0 40,0 60,0 80,0 100,0 120,0 0 0,5 1 r L r r L = 1 PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.8 Prof. Dr. Marco A. Mesquita 17 20.5 Fila Limitada (M/M/1/GD/n/∞)  O modelo M/M/1/GD/n/∞ é semelhante ao M/M/1, exceto pelo fato de que, quando há n clientes, novas chegadas são rejeitadas (não entram).  Processo de Nascimento e Morte com n+1 estados  Os sistemas M/M/1/GD/n/∞ apresentam distribuição estacionária, mesmo que λ ≥ µ, devido à limitação do número máximo de clientes (espaço amostral finito) 0 1 2 n ... l m m l l l m m 18 Distribuição Estacionária  Se l ≠ m, então:  Senão (l = m):  A partir da distribuição estacionária, determinam-se L e Lq, e, a seguir, W e Wq. , ) ,1,0 ( 1 1 n j n j  =  =  , ) ,2,1 ( 1 1 0 1 0 n j j j n  = =   =  r   r r  ) 1( e ) 1( n q q n L W L W  l  l  =  = PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.9 Prof. Dr. Marco A. Mesquita 19 Exemplo 3 - Barbeiro  Uma barbearia tem um único barbeiro e 5 lugares de espera. Quando a barbearia está cheia, novos clientes desistem de entrar. Suponha que o processo de chegadas seja Poisson com taxa 4 clientes por hora e que os tempos de atendimento sejam v.a.i. exponenciais com média 20 min. Determine o tempo médio de fila e a porcentagem de clientes perdidos. 20 Solução  Estado j: qtd de clientes na barbearia 0 1 2 4 4 3 3 4 4 4 3 3 5 3 4 3 1 ... 3 4 3 4 3 4 3 4 3 4 5 1 0 5 4 4 3 3 2 2 1 1 0 =    =   =   =   =   =                j j 0 0,0722 1 0,0962 2 0,1283 3 0,1711 4 0,2281 5 0,3041 1,0   min W min W h cl L L q ef q 51 71 / 78 ,2 ) 1( 37 ,2 30 ,3 5 = = =   = = =  l l PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.10 Prof. Dr. Marco A. Mesquita 21 20.6 Fila M/M/c  Intervalo entre chegadas exponencial (com taxa λ), tempo de atendimento exponencial (com taxa µ), fila única e c servidores idênticos atendendo em paralelo.  Se j ≤ c clientes estão presentes, então todos estão em atendimento; se j > c clientes estão presentes, então todos os c servidores estão ocupados e j – c clientes aguardam em fila.  A fila M/M/c pode ser modelada como um processo de nascimento e morte com: 0 1 2 c ... l l l l ... l m 2m 3m c∙m c∙m n l ... l c∙m c∙m 22 Distribuição Estacionária  Seja r = λ /cµ o índice de congestionamento.  Para r <1, tem-se: ) 1(! ) ( ! ) ( 1 2,...) ,1 , ( ! ) ( 2,1 ,..., ) ( ! ) ( 1 0 0 0 0 r r r   r   r          =   = = = =   =  c c j c c c c j c c c c j j c c c j j c j j j j j PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.11 Prof. Dr. Marco A. Mesquita 23 Distribuição Estacionária (cont.)  Tamanho e tempo médio de fila: l m r l r r  r r L W L L L W c L L W c P j L c c c j P s q s s q q q c =  = = = =   =  =  1 1 ) ( ) 1(! ) ( ) ( 0 0 2) 1(! ) (  r r r  = c c L c q 24 Exemplo 9 – Caixa (p.1089)  M/M/2 com: l=80 e m=50 cl./h (r=0,80), L=?, W=? 1111 ,0 8,0 ) 1(!2 8,0 ) (2 8,0 ) (2 1 1 2 1 0 =      =  ( ,213min) ,0 03556 80 844 ,2 ,2 844 ,01111 8,0 ) 1(!2 8,0 8,0 ) 2 ( 2 2 h W L q q = = =     = ) ( 2,0 1 ,3 33min ,1 20 ,213 ,4 444 6,1 ,2 844 ociosidade W L =  =  = =  = r min) 2,1( ,0 02 50 1 6,1 50 80 h W L s s = = = = PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.12 Prof. Dr. Marco A. Mesquita 25 Planilha – M/M/c 26 20.9 População Finita: Problema de Reparo de Máquinas (M/M/R/GD/∞/K )  No PRM, há K máquinas e R técnicos (𝑅 ≤ 𝐾).  O tempo que uma máquina permanece em operação é uma v.a. exponencial com taxa λ.  Sempre que uma máquina quebra, é mandada para manutenção, onde são reparadas.  O tempo de reparo tem distribuição exponencial com taxa µ.  As máquinas consertadas voltam à operação, quando estarão novamente sujeitas à falha. PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.13 Prof. Dr. Marco A. Mesquita 27  O problema de reparo das máquinas pode ser modelado por processos de nascimento e morte, onde o estado j indica j máquinas quebradas (0,1,...,K).  Cada chegada corresponde a uma quebra de máquina e cada atendimento a um reparo.  No estado j, há K–j máquinas em operação e min (j,R) técnicos trabalhando. 0 1 2 R ... Kl ... m 2m K (K-1)l (K-2)l (K-R+1)l (K-R)l l Rm Rm Rm 3m 28  Dado que cada técnico conserta máquinas à taxa µ, a taxa de atendimento µj é dada por  Definindo r = l / m , a distribuição estacionária será: ) ,..., 2,1,0 ( } , min{ K j R j j = = m m m 2,... ) ,1 ( ! ! 1,0 ,..., ) ( 0 0 K R R j R R j j K R j j K R j j j j j   =       = =       =   r  r   PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.14 Prof. Dr. Marco A. Mesquita 29  Impondo a restrição de soma unitária, obtém-se a distribuição estacionária  A partir da distribuição estacionária, determinam-se:  L = num. médio de máquinas quebradas  Lq = num. médio de máquinas aguardando reparo  W = tempo médio de máquina quebrada (downtime)  Wq = tempo médio aguardando início de reparo l l   q q K R j j q K j j L W L W R j L j L = =  = =   = = ) ( 0 1 0 =  = K j j  Resolver 𝜋𝑗 numericamente (B&D finito) 30 Exemplo 12 – Viaturas Policiais (p.1101)  Frota com K=5 viaturas, uma quebra a cada 30 dias (l=1/30). R=2 técnicos fazem a manutenção, que consome, em média 3 dias (m=1/3). Pede-se: 1. Número médio de viaturas em operação, 2. Tempo médio de espera na fila de cada viatura, 3. Ociosidade de cada um dos mecânicos.  Estado j: viaturas em manutenção 0 1 2 5l m 2m 4l 3 2m 3l 4 2m 2l 5 2m l PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.15 Prof. Dr. Marco A. Mesquita 31 Solução 0 5 0 4 0 3 0 2 0 1 ,0 000075 ,0 0015 ,0 015 1,0 5,0           = = = = = 0 1 2 5/30 1/3 2/3 4/30 3 2/3 3/30 4 2/3 2/30 5 2/3 1/30 ,0 00005 ,0 0009 ,0 009 ,0 062 ,0 309 ,0 618 5 4 3 2 1 0 = = = = = =       maq em operação L K j L j j . ,4 54 ,0 465 5 465 ,0 5 0 =  =  = = =  dias W W W dias L W s q ef j j j ef ,0 07 ,3 07 ,0151 ,0 465 151 ,0 5 0 =  = = = = = = = l l  l ,0 773 5,0 1 . 1 0 =   =    ocios 32 Solução (cont.) j cj j j j lj lj j ocios. ocios. j 0 1 0.6186 0 0.1667 0.1031 1 0.6186 1 0.5 0.3093 0.3093 0.1333 0.0412 0.5 0.1546 2 0.1 0.0619 0.1237 0.1000 0.0062 0 0 3 0.015 0.0093 0.0278 0.0667 0.0006 0 0 4 0.0015 0.0009 0.0037 0.0333 0.0000 0 0 5 0.000075 0.00005 0.0002 0 0 0 0 1.616575 0.4648 0.1512 0.7732 em reparo taxa média ocios. média K - L = 4.54 em oper. W = 3.07 dias Wq = 0.07 dias PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.16 Prof. Dr. Marco A. Mesquita 35 20.7 Fila M/G/∞  Existem muitos exemplos de sistemas nos quais os clientes nunca precisam esperar pelo início do serviço.  Nesses sistemas, há sempre um servidor disponível para cada chegada e podemos considerar um sistema com infinitos servidores.  Usando a notação de Kendall-Lee, tem-se uma fila G/G/∞. Chegada Partida 36 M/G/∞  Se:  Os intervalos entre chegadas A são v.a.i. exponenciais com E(A) = 1 / λ (Poisson, com taxa de chegada λ),  Quando um cliente chega, ele entra imediatamente em serviço e o tempo de serviço S de cada cliente é dado por uma distribuição genérica e independente dos demais, com E(S) = 1 / µ  Então: (j – estado, tem distribuição de Poisson, com média λ / µ) ! ) ( / 1 ) / ( j e L W j j l m  m l m l m  = = =  PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.17 Prof. Dr. Marco A. Mesquita 37 20.8 Fila M/G/1  Processo de Chegada  Os intervalos entre chegadas A são v.a.i. exponenciais com E(A) = 1 / λ (Poisson, com taxa de chegada λ),  Processo de Atendimento  Servidor único, atendimento pela ordem de chegada  Os tempos de serviço S dos clientes é dado por uma distribuição genérica e independente, com E(S) = 1/µ e s2 = V(S)  O modelo M/G/1 não constitui um processo de nascimento e morte, pois os tempos de permanência em cada estado não apresentam distribuição exponencial. 38 M/G/1  A determinação da distribuição estacionária não é simples para a M/G/1.  Fórmulas de Pollaczek–Khinchin para fila M/G/1  Adicionalmente, 0, parcela do tempo durante a qual o servidor fica ocioso, é igual a 1–r. m r l r r s l 1 ) 1( 2 2 2 2  =  = =   = q q q q q W W L L L W L PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.18 Prof. Dr. Marco A. Mesquita 39 Efeito da Variância  Utilizando as fórmulas de P-K, compare o desempenho de duas filas com chegadas Poisson à taxa de λ=5 cl/h e tempos de atendimento exponencial e constante, com taxa de 8 cl/h.  M/M/1: V(S)=(1/8)2 Lq = 25/24 = 1,04 Wq = 5/24 h = 12,5 min  M/D/1: V(S)=0 Lq = 25/48 = 0,52 Wq = 5/48 h = 6,25 min  D/D/1: Lq = 0, Wq = 0 40 20.10 Redes de Filas  Nos modelos de filas isoladas, cada cliente é atendido por um servidor e, ao final do atendimento, deixa o sistema.  Em muitas situações, os clientes necessitam atendimento em diferentes postos (ou estágios) de serviço, que constituem uma rede de filas.  Abaixo, apresenta-se um rede de filas em série com m estágios de atendimento l Fila 1 c1 servidores, Taxa m1 Fila 2 c2 servidores, Taxa m2 Fila m cm servidores, Taxa mm ... l l l l Estágio 1 Estágio 2 Estágio m PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.19 Prof. Dr. Marco A. Mesquita 41 Teorema  Se: 1. o processo de chegadas no estágio 1 é Poisson com taxa l 2. cada estágio tem cj servidores e capacidade ilimitada da fila 3. o tempo de serviço em cada estágio é exponencial com taxa mj 4. em todos os estágios, a capacidade de atendimento é maior que a taxa de chegadas l, ou seja, 𝜌𝑗 = ൗ 𝜆 𝑐𝑗𝜇𝑗 < 1 para todo j  Então: 1. os intervalos entre chegadas em cada estágio também terão distribuição exponencial (chegada Poisson) com taxa l 2. a rede pode ser decomposta e analisada separadamente como se fossem m filas M/M/c independentes 42 Exemplo 13 – Linha de Montagem (p.1105)  M/M/1 -> M/M/3 h W W W h W L h W L h cl q q q q q q q 286 ,0 ,0136 ,7 35 ,0 0249 9,0 ,015 1,8 9,0 / ) ( 20 60 54 2 1 2 2 0 2 1 1 1 2 1 =  = = = = = = = = = = =  r r m m l PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.20 Prof. Dr. Marco A. Mesquita 43 Rede Aberta de Filas  Redes Abertas de Filas são um caso mais geral que as filas em série.  Considere um sistema de filas com m postos ou nós. Suponha que: 1. cada posto i tem ci servidores exponenciais e taxa mi. 2. clientes externos chegam ao posto i conforme um processo de Poisson com taxa gi. 3. terminado o atendimento em i, o cliente segue para o posto j, com probabilidade pij ou deixa o sistema com probabilidade 1 − σ𝑗=1 𝑚 𝑝𝑖𝑗  Problema:  Como dimensionar os m postos de atendimento, equilibrando custos e nível de serviço? 44 Rede Aberta de Filas PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.21 Prof. Dr. Marco A. Mesquita 45  Seja lj a taxa total de chegadas ao posto j.  l1, l2, ..., lm podem ser determinadas pela solução do seguinte sistema linear:  Suponha que cj µj > λj em todos os nós.  Neste caso, o sistema também pode ser decomposto em m sistemas M/M/c, com taxa de chegada λj e de atendimento µj. 2,1 ,..., ) ( 1 m j m i i ij j j p =  =  = l g l 46  Demonstra-se também que as quantidades de agentes em cada um dos postos são v.a. independentes.  Analisando cada posto separadamente, determina-se o número médio de agentes nele. O número médio total de agentes na rede, L, é dado pela soma do número médio de agentes em cada posto.  Para cálculo do W, tempo médio total de permanência dos agentes na rede, basta aplicar a fórmula de Little (L=λW), considerando o sistema como um todo.  Se houver algum posto j com λj ≥ cj µj , então o sistema não terá distribuição estacionária. PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.22 Prof. Dr. Marco A. Mesquita 47 Exemplo  Considere uma rede com m=3 postos de atendimento, uma taxa de chegadas externas de 10 cl/h no posto 1 e zero nos demais. As taxas de serviço e fluxos estão indicados abaixo. Determine o tempo médio de fila em cada posto. 1 2 3.1 50% 50% 3.2 75% 25% 10 cl./h m1 = 20 cl./h m2 = 15 cl./h m3 = 5 cl./h 2 1 3 1 2 1 ,0 25 5,0 5,0 10 l l l l l l    =  = = 25 ,6 0,5 0, 10 3 2 1 = = = l l l 625 ,0 333 ,0 5,0 3 2 1 = = = r r r 48 Solução 1 l1=10 m1=20 2 l2=5 m2=15 3 min ,0 05 10 5,0 5,0 5,0 1 5,0 5,0 2 = = = = =  = h W L q q r 2 min ,0 0333 5 167 ,0 ,0167 ,0 333 1 ,0 333 333 ,0 2 = = = = =  = h W L q q r PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.23 Prof. Dr. Marco A. Mesquita 49 Solução (cont.) 3a 3b l3=6,25 m2=5 ,7 69min ,01282 ,6 25 8013 ,0 ,0 8013 ,0 2308 ,0 625) 1(!2 ,0 625 ,0 625) 2 ( 2308 ,0 ,0 625) 1(!2 ,0 625) (2 ,0 625 2 1 1 ,0 625 5 2 ,6 25 2 2 2 2 0 = = = =     = =      = =  = = h W L c q q  r 50 20.13 Redes Fechadas de Filas  Sistemas onde o número total de agentes permanece constante, sem entradas nem saídas, podem ser analisados como redes fechadas de filas.  Exemplos:  Frota dedicada operando de forma cíclica entre m terminais;  Sistemas de produção com limite de estoque em processo (ConWiP), onde as ordens concluídas no final da linha são substituídas por outras na entrada, mantendo constante os estoques em processo;  Uma rede fechada de computadores, onde o número de usuários é fixo e o tempo inativo dos usuários é modelado por um estágio com infinitos servidores em paralelo. PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.24 Prof. Dr. Marco A. Mesquita 53 Exemplo 17 – FMS (p.1120)  N=10, m=3  m1=0,25 (4 min) m2=0,48 (2,083 min) m3=0,08 (12,5 min)  S = {(0,0,10), (0,1,9), (0,2,8), ... , (10,0,0)} 1 2 3 0,75 0,25 ) ( ) ( 2 1 2 1 N G a a a xm m x x N  x =  i i ia m  =  = = m i ij i j p 1   m1=0,25 m2=0,48 m3=0,08 54 Exemplo 17: solução  Balanço de Fluxo  Número de Estados  Distribuição Estacionária # x1 x2 x3 p(x) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  66 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1  10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5  0 10 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4  0 0,01228143 0,00614071 0,00307036 0,00153518 0,00076759 0,00038379 0,00019190 0,00009595 0,00004797 0,00002399 0,00001199 0,01572023 0,00786011 0,00393006 0,00196503 0,00098251 0,00049126  0,14499350 1 3 1 2 3 2 1 25 ,0 75 ,0         =  =  = ,0 25 ,0 75 0,1 3 2 1 = = =    66 2 12 1 1  =      =          m m N PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.25 Prof. Dr. Marco A. Mesquita 55 Exemplo 17: solução (cont.)  Distribuições marginais  A seguir, as medidas de desempenho de cada estágio podem ser calculadas. x1 p(x1) 0 1 2 3 4 5 6 7 8 9 10 0,02455 0,03141 0,04017 0,05131 0,06542 0,08308 0,10465 0,12963 0,15487 0,16991 0,14499 x2 p(x2) 0 1 2 3 4 5 6 7 8 9 10 0,61897 0,23699 0,09017 0,03402 0,01269 0,00466 0,00167 0,00058 0,00019 0,00005 0,00001 x3 p(x3) 0 1 2 3 4 5 6 7 8 9 10 0,23793 0,18587 0,14520 0,11340 0,08852 0,06900 0,05361 0,04128 0,03105 0,02186 0,01228 56 Exemplo 17: solução (cont.)  As medidas de desempenho de cada posto podem então serem calculadas. Fila Média Utilização Vazão Maq 1 5,72078 0,97545 0,244 Maq 2 0,22860 0,38103 0,183 Maq 3 1,93207 0,76207 0,061 PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.26 Prof. Dr. Marco A. Mesquita 59 Análise do Valor Médio  Método mais simples e recursivo para a análise de Redes de Fechadas de Filas  Dois princípios básicos:  (processo de chegadas) a distribuição do número de agentes em cada posto, vista por um agente no instante de sua chegada em um dado posto, é igual a distribuição estacionária do número agentes em cada posto quando há n-1 agentes na rede  (fórmula de Little) aplica-se a fórmula de Little para a rede como um todo e individualmente para cada posto  https://en.wikipedia.org/wiki/Mean_value_analysis 60 Análise do Valor Médio – Caso 1 m postos com um único servidor cada  Rede Fechada de Filas com n clientes e m nós  Em cada nó, há um único servidor e o tempo de atendimento é exponencial com taxa mj  P=[pij] – probabilidade de um cliente ir de “i” para “j”  Caso particular: Rede Circular  pij = 1 para j=i+1 e pm1 =1; caso contrário, pij=0  =P – taxa relativa de chegadas aos nós  Para o caso de Rede Circular: j=1 para todo j  Lj(n) – número médio de clientes em j quando há n clientes na rede  Wj(n) – tempo médio de permanência dos clientes em j quando há n clientes na rede  l(n) – fluxo médio quando há n clientes na rede PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.27 Prof. Dr. Marco A. Mesquita 61 Análise do Valor Médio - Caso 1  Inicialização  Para n=1 até N, faça:  Caso particular: rede circular onde j=1 para todo j m j Lj 2,1 ,..., ,0 (0) = = m j W n n n L n W n n m j L n n W j j j j m j j j j j 2,1 ,..., ( ), ( ) ) ( ) ( ) ( 2,1 ,..., 1, )1 ( ) ( 1 =   =  = =   =  =  l  l m 62 Exemplo 1 – Linha ConWip  n jobs, m=3 estágios, rede circular (j=1 para todo j)  Em cada estágio, tempos exponenciais com médias: 2, 5 e 3 min, respectivamente  Determine a vazão e o tempo médio de ciclo em função do número de jobs no sistema m1=1/2 1 2 3 m2=1/5 m3=1/3 PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.28 Prof. Dr. Marco A. Mesquita 63 Solução 1/μ1 1/μ2 1/μ3 2 5 3 n W1 W2 W3 Wt lbd L1 L2 L3 0 0 0 0 1 2.000 5.000 3.000 10.000 0.100 0.200 0.500 0.300 2 2.400 7.500 3.900 13.800 0.145 0.348 1.087 0.565 3 2.696 10.435 4.696 17.826 0.168 0.454 1.756 0.790 4 2.907 13.780 5.371 22.059 0.181 0.527 2.499 0.974 5 3.054 17.494 5.922 26.471 0.189 0.577 3.305 1.119 6 3.154 21.523 6.356 31.032 0.193 0.610 4.161 1.229 7 3.220 25.807 6.687 35.713 0.196 0.631 5.058 1.311 8 3.262 30.292 6.932 40.486 0.198 0.645 5.986 1.370 9 3.289 34.928 7.109 45.327 0.199 0.653 6.935 1.412 10 3.306 39.677 7.235 50.218 0.199 0.658 7.901 1.441 11 3.317 44.505 7.322 55.143 0.199 0.662 8.878 1.461 12 3.323 49.389 7.382 60.094 0.200 0.664 9.862 1.474 13 3.327 54.312 7.422 65.061 0.200 0.665 10.852 1.483 14 3.330 59.261 7.449 70.039 0.200 0.666 11.845 1.489 15 3.331 64.227 7.467 75.025 0.200 0.666 12.841 1.493 16 3.332 69.206 7.479 80.016 0.200 0.666 13.838 1.495 17 3.333 74.192 7.486 85.010 0.200 0.666 14.837 1.497 18 3.333 79.183 7.491 90.007 0.200 0.667 15.835 1.498 19 3.333 84.177 7.494 95.004 0.200 0.667 16.835 1.499 20 3.333 89.173 7.496 100.003 0.200 0.667 17.834 1.499 ( ) ( ) ) ( ) ( ) ( 1 )1 ( ) ( 3 1 n W n n L n W n n L n n W j j j j j j j  = =   =  = l l m 64 Solução (cont.) PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.29 Prof. Dr. Marco A. Mesquita 65 Análise do Valor Médio - Caso 2 Servidor único ou infinitos servidores  Cada nó pode ter um único ou infinitos servidores  Nos nós com infinitos servidores, não há espera pelo atendimento (não há fila)  O tempo de permanência em cada nó será:  Os demais passos permanecem iguais  É possível generalizar para outros valores de cj (Caso 3)        = =   = j j j j j j c se se c n L n W , 1 1 1, )1 ( ) ( m m 66 Exemplo 2 – Frota Circular  n jobs, m=4 estágios, rede circular (j=1 para todo j)  Estágios ímpares com servidor único e os pares com n servidores  Cada estágio, tempo exponencial com taxa m=1 job/h  Determine a vazão e o tempo médio de ciclo em função do número de jobs no sistema m1=1 1 2.2 3 m2=1 m3=1 2.1 2.n ⋮ 4.2 m4=1 4.1 4.n ⋮ PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.30 Prof. Dr. Marco A. Mesquita 67 Solução 1 2 3 4 cj 1 ∞ 1 ∞ 1/μj 1 1 1 1 n W1 W2 W3 W4 Wt lbd L1 L2 L3 L4 0 0 0 0 0 1 1.000 1.000 1.000 1.000 4.000 0.250 0.250 0.250 0.250 0.250 2 1.250 1.000 1.250 1.000 4.500 0.444 0.556 0.444 0.556 0.444 3 1.556 1.000 1.556 1.000 5.111 0.587 0.913 0.587 0.913 0.587 4 1.913 1.000 1.913 1.000 5.826 0.687 1.313 0.687 1.313 0.687 5 2.313 1.000 2.313 1.000 6.627 0.755 1.745 0.755 1.745 0.755 6 2.745 1.000 2.745 1.000 7.491 0.801 2.199 0.801 2.199 0.801 7 3.199 1.000 3.199 1.000 8.398 0.834 2.666 0.834 2.666 0.834 8 3.666 1.000 3.666 1.000 9.333 0.857 3.143 0.857 3.143 0.857 9 4.143 1.000 4.143 1.000 10.286 0.875 3.625 0.875 3.625 0.875 10 4.625 1.000 4.625 1.000 11.250 0.889 4.111 0.889 4.111 0.889 11 5.111 1.000 5.111 1.000 12.222 0.900 4.600 0.900 4.600 0.900 12 5.600 1.000 5.600 1.000 13.200 0.909 5.091 0.909 5.091 0.909 13 6.091 1.000 6.091 1.000 14.182 0.917 5.583 0.917 5.583 0.917 14 6.583 1.000 6.583 1.000 15.167 0.923 6.077 0.923 6.077 0.923 15 7.077 1.000 7.077 1.000 16.154 0.929 6.571 0.929 6.571 0.929 16 7.571 1.000 7.571 1.000 17.143 0.933 7.067 0.933 7.067 0.933 17 8.067 1.000 8.067 1.000 18.133 0.938 7.562 0.938 7.562 0.938 18 8.562 1.000 8.562 1.000 19.125 0.941 8.059 0.941 8.059 0.941 19 9.059 1.000 9.059 1.000 20.118 0.944 8.556 0.944 8.556 0.944 20 9.556 1.000 9.556 1.000 21.111 0.947 9.053 0.947 9.053 0.947 ( ) ( ) ) ( ) ( ) ( 2,1 1 ) ( 1 )1 ( ) ( 4 1 2 2 1 2 1 2 1 2 n W n n L n W n n j n W n L n W j j j j j j j j j  = = = =   =  =    l l m m 68 Solução (cont.) PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.31 Prof. Dr. Marco A. Mesquita 69 Exemplo 3 – Frota Circular  Frota com n veículos, operando entre dois terminais  Terminal 1: tempo de carga exponencial com média 2h e capacidade para atender 2 veículos por vez  Terminal 2: tempo de descarga exponencial com média 1h e capacidade para atender 1 veículos por vez  Viagens: tempos exponenciais com média de 4h m1=0,5 1.1 2.2 3 m2=0,25 m3=1 2.1 2.n ⋮ 4.2 m4=0,25 4.1 4.n ⋮ 1.2 Implementar (qquer cj) Programação de Operações (Scheduling) PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.32 Prof. Dr. Marco A. Mesquita 73 Problemas de Programação de Máquinas Máquina Única Máquinas em Série (flow shop) Máquinas Paralelas Oficina de Máquinas (job shop) 74 Filas determinadas  Na teoria de filas, os modelos pressupõem processos de chegadas dinâmicos e tempos de atendimento aleatórios  Um processo de chegadas dinâmico é aquele em que os jobs chegam ao longo do tempo, normalmente de forma aleatória  As análises são feitas principalmente em regime estacionário, com alguns indicadores de desempenho calculados  A seguir, consideraremos um problema em que os jobs são todos conhecidos e disponíveis no tempo zero, com os tempos de processamento predefinidos  Assim, a fila pode ser predeterminada, ou seja, a ordem de processamento dos jobs podem ser escolhida, visando otimizar algum indicador de desempenho  Problemas deste tipo são tratados na Teoria de Scheduling, onde a variável de decisão é exatamente definir a ordem de processamento dos jobs nas máquinas PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.33 Prof. Dr. Marco A. Mesquita 75 Exemplo: Permutation Flow Shop Problem (PFSP)  Considere uma linha com m=2 máquinas e n=5 jobs que devem ser processados sequencialmente nas máquinas com os tempos de processamento dados na tabela abaixo. Suponha que todos os jobs estejam disponíveis no instante zero e que a sequência de processamento deva ser a mesma em todas as máquinas. Determine uma sequência dos jobs para minimizar o tempo total de processamento dos n jobs nas m máquinas. Jobs Tempo Maq. 1 Tempo Maq. 2 A 6 3 B 1 3 C 8 6 D 4 6 E 2 5 ? ? ? ? ? 1 2 3 4 5 Sequência: 76 Solução inicial Jobs Tempo Maq. 1 Tempo Maq. 2 A 6 3 B 1 3 C 8 6 D 4 6 E 2 5 A A B B C C D D E E 0 5 10 15 20 25 30 35 M1 M2 PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.34 Prof. Dr. Marco A. Mesquita 77 Solução pela regra SPT – Shortest Processing Time First Jobs Tempo Maq. 1 Tempo Maq. 2 A 6 3 B 1 3 C 8 6 D 4 6 E 2 5 B B E E D D A A C C 0 5 10 15 20 25 30 M1 M2 78 Solução ótima Jobs Tempo Maq. 1 Tempo Maq. 2 A 6 3 B 1 3 C 8 6 D 4 6 E 2 5 B B E E D D C C A A 0 5 10 15 20 25 30 35 M1 M2 PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.35 Prof. Dr. Marco A. Mesquita 79 Formulação Matemática do PFSP Cmax  Índices  𝑖 – job  j – posição  k – máquina  Parâmetros  𝑚 – número de máquinas  n – número de jobs  [𝑝𝑖𝑘] – tempos de processamento dos n jobs nas m máquinas  Variáveis de Decisão  𝑥𝑖𝑗 – 1, se o job i está na posição j e 0, caso contrário  𝑠𝑗𝑘 – start time do job da posição j na máquina k  𝑐𝑗𝑘 – completion time do job da posição j na máquina k  𝑐𝑛𝑚 = 𝐶𝑚𝑎𝑥 – completion time do último job na última na máquina k 80 Formulação Matemática do PFSP Cmax 0/1 ,0 , 1,..., 1 1,..., 1 2,..., ,..., 1 1,..., ,..., 2 1,..., ,..., 1 . . min 1 1 1 , ,1 1 =  = = = = = =  = =  = =      = =   = ij jk jk n j ij n i ij j k jk k j jk n i ik ij jk jk nm x c s n i x n j x m k n j c s m k n j c s m k n j x p s c a s c PRO 3342 – Teoria de Filas – Parte 2 USP – Poli – PRO 4.36 Prof. Dr. Marco A. Mesquita 81 Próxima aula  Controle de Estoques  Winston (2004, cap.15 e 16)  15.1, 15.2, 16.3 e 16.6