Filas de espera: transparências de apoio á leccionação de aulas teóricas

Slide 1 Filas de Espe a T anspa ˆencias de apoio `a lecciona¸c˜ao de aulas e´o icas Ve s˜ao 1 c °1998 Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 1 Slide 2 In odu¸c˜ao •Fen´omeno co en e no dia-a-dia –clien es – pessoas, e´ıculos ou ou as en idades ´ısicas ou concep uais – que necessi am de um –se i¸co, pelo qual podem e que espe a numa ila ´ısica ou concep ual (a ila pode s´o exis i concep ualmen e, p.ex. senhas com n´ume o de a endimen o). •T abalho pionei o de A. K. E lang (in´ıcio do s´ec. XX), cien is a dinama quˆes, sob e chamadas ele ´onicas agua dando linha pa a se em encaminhadas. Slide 3 Es u u a de um sis ema de ila de espe a •Fon e ou popula¸c˜ao, que ge a os clien es que ˜ao chega ao sis ema. •Fila, cons i u´ıda pelos clien es `a espe a de se a endidos (n˜ao inclui o(s) clien e(s) em a endimen o). •Se i¸co ou a endimen o, que pode se cons i u´ıdo po um ou mais pos os de a endimen o. Fila +Se i¸co =Sis ema N´ume o de clien es no sis ema (em cada ins an e) = es ado do sis ema Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 2 Slide 4 Fon e •Dimens˜ao da popula¸c˜ao –in ini a: quando a p obabilidade de oco e uma no a chegada n˜ao ´e in luenciada pelo n´ume o de clien es que j´a se encon am no sis ema; – ini a. •Dimens˜ao da chegada –clien es chegam um a um; –clien es chegam em g upo. •Con olo das chegadas –chegadas con ol´a eis (p.ex. insc i¸c˜oes em dias ixos); –chegadas incon ol´a eis (p.ex. u gˆencia de um hospi al). Slide 5 •Dis ibui¸c˜ao das chegadas O pad ˜ao das chegadas pode se desc i o pelo empo en e duas chegadas consecu i as ( empo en e chegadas) ou pelo n´ume o de chegadas po unidade de empo (dis ibui¸c˜ao das chegadas). –cons an e: in e alos de empo en e chegadas sucessi as ixos (p.ex. ilas de mon agem indus iais); –alea ´o io: os in e alos de empo en e chegadas sucessi as n˜ao podem se p e is os com ce eza ⇒dis ibui¸c˜oes de p obabilidade. •Taxa de chegada (λ) N´ume o m´edio de clien es que p ocu am o se i¸co po unidade de empo. –independen e do es ado do sis ema; –dependen e do es ado do sis ema: λn,n– n´ume o de clien es no sis ema. •A i ude dos clien es –pacien e: pe manecem na ila a ´e se em a endidos −→ boa ap oxima¸c˜ao quando h´a poucas desis ˆencias; –impacien e: desis em de espe a ou simplesmen e n˜ao se jun am `a ila se es a o mui o g ande ⇒u iliza¸c˜ao de modelos de simula¸c˜ao. Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 3 Slide 6 Fila •N´ume o de ilas – ila simples: uma ´unica ila mesmo que o se ido enha ´a ios pos os de a endimen o; – ila m´ul ipla: uma ila po pos o de a endimen o ⇒cada conjun o ila/pos o de a endimen o cons i ui um sis ema sepa ado de ila de espe a. ´ E usual epa i as chegadas igualmen e pelas ´a ias ilas. •Comp imen o da ila –in ini o: a capacidade m´axima da ila ´e mui o g ande quando compa ada com o n´ume o de elemen os que habi ualmen e a cons i uem; – ini o: a ila pode acolhe apenas um n´ume o pequeno de clien es. •Disciplina da ila –FIFO – “Fi s In Fi s Ou ”; –p io idades: p.ex. ese as, idade, eme gˆencia; –alea ´o ia. Slide 7 Se i¸co •Con igu a¸c˜ao do se i¸co N´ume o de se ido es em pa alelo (pos os de a endimen o) e n´ume o de ases de a endimen o: –um se ido , uma ase; –um se ido , m´ul iplas ases; –m´ul iplos se ido es, uma ase; –m´ul iplos se ido es, m´ul iplas ases; – edes de ilas de espe a. •Dimens˜ao do se i¸co –simples; –em g upo (p.ex. um ele ado a ende ´a ios clien es em simul ˆaneo). Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 4 Slide 8 •Dis ibui¸c˜ao do empo de se i¸co: –cons an e; –alea ´o io: dis ibui¸c˜ao exponencial nega i a, E lang, ou a. •Taxa de se i¸co (µ) N´ume o m´edio de clien es que podem se a endidos po cada se ido e po unidade de empo. 1 µ= du a¸c˜ao m´edia do se i¸co. N´ume o m´edio de clien es e ec i amen e a endidos ≤µ→pode ha e momen os de inac i idade. –dependen e do es ado do sis ema (µn, n – n´ume o de clien es no sis ema), p.ex. se i¸co de eclama¸c˜oes que a endesse mais dep essa as eclama¸c˜oes quando a ila ´e maio : maio p odu i idade ou deg ada¸c˜ao da qualidade do se i¸co? –independen e do es ado do sis ema. Slide 9 Modeliza¸c˜ao de sis emas de ilas de espe a – Objec i o “Op imiza ” o uncionamen o das ilas de espe a, encon ando solu¸c˜oes equilib adas en e dois ex emos: Conges ionamen o – os clien es ˆem que espe a demasiado empo na ila → axa de ocupa¸c˜ao dos se ido es p ´oxima dos 100%. S´o acei ´a el quando o cus o do se ido ´e mui o maio do que o cus o de espe a do clien e. Ra e ac¸c˜ao – os se ido es pe manecem inac i os du an e uma pe cen agem de empo ele ada (si ua¸c˜ao po ezes desej´a el, p.ex. se i¸cos de bombei os). Es abelecimen o de ade-o s en e o cus o do se i¸co e o “cus o” do empo pe dido pelos clien es na ila de espe a →c escimen o acen uado pa a empos de espe a ele ados. Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 5 Slide 10 Medidas de desempenho •comp imen o m´edio da ila (Lq) •n´ume o m´edio de clien es no sis ema (L) • empo m´edio de espe a na ila (Wq) • empo m´edio de espe a no sis ema (W) • axa m´edia de ocupa¸c˜ao (e desocupa¸c˜ao) do se i¸co (pe cen agem de empo du an e o qual o se i¸co es ´a ocupado) Ou as medidas (mais po meno izadas) ´u eis: •Pn= p obabilidade de exis i em nclien es no sis ema •P(n≥k) = P∞ n=kPn= p obabilidade de exis i em no sis ema kou mais clien es •P(Wq= 0) = p obabilidade de o empo de espe a na ila se ze o •P(Wq> ) = p obabilidade de o empo de espe a na ila excede •P(W > ) = p obabilidade de o empo gas o no sis ema excede Slide 11 Nomencla u a λ— axa de chegada (n´ume o m´edio de clien es que chegam po unidade de empo). 1 λ— in e alo m´edio en e duas chegadas consecu i as. λn— axa de chegada dependen e do es ado, is o ´e, quando exis em n clien es no sis ema. λ=P∞ n=0λnPn— axa m´edia de en ada no sis ema. µ— axa de se i¸co (n´ume o m´edio de clien es que cada se ido em capacidade pa a a ende po unidade de empo). 1 µ— empo m´edio de se i¸co. µn— axa de se i¸co dependen e do es ado, is o ´e, quando exis em n clien es no sis ema. s— n´ume o de se ido es. ρ— pa ˆame o auxilia , no malmen e designado po axa de ocupa¸c˜ao. Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 6 Slide 12 Ca ac e iza¸c˜ao das dis ibui¸c˜oes das chegadas e do a endimen o 1. Desc e e a in o ma¸c˜ao ecolhida, sob e chegadas de clien es e seu a endimen o, a a ´es de his og amas e pa ˆame os amos ais (m´edia, a iˆancia,...). 2. In e i dos pa ˆame os amos ais os pa ˆame os da popula¸c˜ao. 3. “Ajus a ” uma dis ibui¸c˜ao e´o ica ao his og ama expe imen al, i.e., escolhe uma dis ibui¸c˜ao es a ´ıs ica que desc e a “adequadamen e” o en´omeno analisado. A maio ia dos modelos anal´ı icos de ilas de espe a sup˜oe chegadas seguindo uma dis ibui¸c˜ao de Poisson e um empo de a endimen o ca ac e izado po uma dis ibui¸c˜ao exponencial nega i a – dis ibui¸c˜oes que mais equen emen e ca ac e izam as ilas de espe a eais. Slide 13 Dis ibui¸c˜ao exponencial nega i a Fun¸c˜ao densidade de p obabilidade de T: ( ) =    αe−α se ≥0 0 se < 0 Dis ibui¸c˜ao acumulada: F( ) = P(T≤ ) = 1 −eα ( ≥0) M´edia: E(T) = 1 α Va iˆancia: V a (T) = 1 α2 Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 7 Slide 14 Dis ibui¸c˜ao de Poisson Fun¸c˜ao dis ibui¸c˜ao de p obabilidade de X: (x) = (α )xe−α x!x= 0,1,2,... x (x) 0012345678 0.05 0.1 0.15 0.2 0.25 0.3 Função densidade de p obabilidade de uma a iá el com dis ibuição de Poisson (α =2) Pa ˆame o da dis ibui¸c˜ao: α α— n´ume o m´edio de acon ecimen os po unidade de empo; — comp imen o do in e alo de empo em an´alise; x— n´ume o de acon ecimen os du an e o in e alo . M´edia: E(X) = α Va iˆancia: V a (X) = α Slide 15 P op iedades •Se o empo en e dois acon ecimen os consecu i os segue uma dis ibui¸c˜ao exponencial nega i a com pa ˆame o α, en ˜ao o n´ume o de acon ecimen os po unidade de empo segue uma dis ibui¸c˜ao de Poisson com pa ˆame o α . •A dis ibui¸c˜ao exponencial nega i a n˜ao em mem´o ia, i.e., a p obabilidade de oco ˆencia de um acon ecimen o ´e independen e do ins an e de empo em que oco eu o acon ecimen o imedia amen e an e io . Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 8 Slide 16 •Sejam T1, T2,...,Tn a i´a eis alea ´o ias com dis ibui¸c˜ao exponencial nega i a e pa ˆame os α1, α2,...,αn. A a i´a el u= min{T1, T2,...,Tn}, que ep esen a o empo a ´e que o p imei o de en e nacon ecimen os oco a, segue uma dis ibui¸c˜ao exponencial nega i a com pa ˆame o α=Pn i=1 αi. Es a p op iedade pe mi e modeliza sis emas com kse ido es idˆen icos (mesma dis ibui¸c˜ao) com pa ˆame o µ, ope ando em pa alelo, como um ´unico se ido com pa ˆame o kµ (o p ´oximo clien e ´e a endido quando o p imei o se ido ica li e). •Desag ega¸c˜ao — se a chegada de clien es segui uma dis ibui¸c˜ao de Poisson com pa ˆame o λ, e esses clien es pude em se di ididos em di e en es ipos de al o ma que a p obabilidade pide o clien e se de um dado ipo iseja ixa e Pipi= 1, en ˜ao a chegada de cada um dos clien es segue ainda uma dis ibui¸c˜ao de Poisson com pa ˆame o λi=piλ. Slide 17 P ocessos de ida e mo e P ocessos es oc´as icos sem mem´o ia que, aplicados `as ilas de espe a, associam ida a uma chegada `a ila e mo e `a sa´ıda de um clien e depois de a endido, segundo as seguin es hip´o eses: •Dado que no ins an e o sis ema se encon a no es ado n, o empo que sepa a : –do p ´oximo nascimen o (chegada) segue uma dis ibui¸c˜ao exponencial nega i a com pa ˆame o λn; –da p ´oxima mo e (se i¸co e minado) segue uma dis ibui¸c˜ao exponencial nega i a com pa ˆame o µn. •Nunca podem oco e simul aneamen e mais do que um nascimen o ou uma mo e ( ansi¸c˜ao apenas pa a es ados adjacen es). Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 15 Slide 30 Modelo b´asico com Sse ido es – M/M/S 0312 λλλ µ2µ3µ nn-1 λ Sµ S-2 S+1S-1 S λλ (S-1)µSµ λ Sµ ... ... •Caso mais ge al de uma ila de espe a ´unica, baseada num p ocesso de ida e mo e, em que exis em Sse ido es em pa alelo. •A axa de chegada λ´e independen e do es ado do sis ema. •A axa de se i¸co µ´e igual pa a odos os se ido es, sendo a axa de a endimen o (conjun o dos Sse ido es) dada po Sµ. •A axa de ocupa¸c˜ao ´e igual a λ Sµ , que e ´a que se <1 pa a que o sis ema es eja em equil´ıb io. Slide 31 •A axa de en ada em cada es ado ´e semp e igual a λ. •A axa de sa´ıda a ia com o es ado: –pa a es ados onde os se ido es n˜ao es ejam odos ocupados, a dis ibui¸c˜ao exponencial nega i a do in e alo de empo en e sa´ıdas de clien es a endidos em pa ˆame o kµ (com k < S), sendo ko n´ume o de se ido es ocupados nesse es ado — quan o mais se ido es es i e em ocupados mais p o ´a el ´e sai um clien e a endido do sis ema. –pa a os es ados co esponden es a odos os se ido es ocupados (es ados com Sou mais clien es no sis ema), o empo en e sa´ıdas de clien es a endidos em pa ˆame o Sµ e n˜ao depende do n´ume o de clien es no sis ema. Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 16 Slide 32 Ca ac e ´ıs icas do modelo M/M/S Chegada: Poissoniana Tempo a endimen o: exponencial nega i o Taxa: λclien es / u. empo Taxa: µclien es / u. empo e se ido Popula¸c˜ao =∞Nose ido es: S Fila m´axima =∞ρ=λ Sµ ,com ρ < 1 Taxa de ocupa¸c˜ao =ρ Taxa de desocupa¸c˜ao = 1 −ρ Lq=∞ X n=S (n−S)Pn= P0³λ µ´Sρ S!(1 −ρ)2Wq=Lq λ L=∞ X n=0 nPn=Lq+λ µW=Wq+1 µ=L λ P0=1 S−1 X n=0 ³λ µ´n n!+³λ µ´S S! 1 1−ρ P(W > ) ≥0=e−µ   1 + P0³λ µ´S S!(1 −ρ) 1−e−µ (S−1−λ/µ) S−1−λ µ    Pn=     ³λ µ´n n!P0,se 0 ≤n≤S ³λ µ´n S!Sn−SP0,se n≥S P(Wq> ) ≥0= [1 −P(Wq= 0)]e−Sµ(1−ρ) P(Wq= 0) = S−1 X n=0 Pn Slide 33 Exemplo – Es a¸c˜ao de co eios Uma mode na es a¸c˜ao de co eios p e ende dimensiona e eo ganiza o seu a endimen o ao p´ublico, p e endendo, no en an o, man e o mesmo esquema de a endimen o em que odos os uncion´a ios a endem odo o ipo de clien es, pedidos de in o ma¸c˜ao, eclama¸c˜oes, aquisi¸c˜ao de selos, ales pos ais, e c. Pa a isso ecolheu in o ma¸c˜ao sob e o n´ume o de chegadas de clien es, bem como sob e os empos de a endimen o endo conclu´ıdo que as chegadas seguiam bas an e ap oximadamen e uma dis ibui¸c˜ao de Poisson com pa ˆame o λ= 1.56 chegadas po minu o, enquan o os empos de se i¸co seguiam uma dis ibui¸c˜ao nega i a com m´edia igual a 66.24 segundos, a que co esponde uma axa de a endimen o µ= 1/66.24 ×60 = 0.906 a endimen os po minu o. O cus o ho ´a io de cada uncion´a io ´e de 1 500$00. Quan o aos clien es a bi a-se um cus o ho ´a io independen e do empo de espe a e igual ao dos uncion´a ios dos co eios. Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 17 Slide 34 Resolu¸c˜ao – Es a¸c˜ao de co eios Compa ando as axas de chegada e de a endimen o conclui-se de imedia o que λ > µ pelo que se ´a necess´a io um n´ume o de se ido es supe io a 1. Fazendo c´alculos pa a 2, 3 e 4 se ido es, a pa i das exp ess˜oes do quad o ela i o ao modelo M/M/S, ob ´em-se a seguin e abela: Nose ido es ρ P0Wq S= 2 0.86 0.075 3.17 minu os S= 3 0.57 0.162 0.28 minu os S= 4 0.43 0.175 0.05 minu os No e-se que nas ilas M/M/S P0n˜ao ep esen a a axa de desocupa¸c˜ao mas apenas a p obabilidade de odos os se ido es es a em desocupados. No en an o, quando a axa de ocupa¸c˜ao (ρ) diminui, P0aumen a e, in e samen e, Wqdiminui. Uma ez que os clien es e ˜ao semp e que se se idos e o empo de se i¸co ´e cons an e (n˜ao depende do n´ume o de se ido es), o cus o depende do empo gas o na ila de espe a Wq. Slide 35 N´ume o de clien es chegados num pe ´ıodo de 8 ho as: λ×8×60 = 1.56 ×8×60 = 749 clien es Tempo pe dido na ila de espe a po dia: S= 2 →3.17 ×749 = 2374 min = 39.57 ho as S= 3 →0.28 ×749 = 210 min = 3.50 ho as S= 4 →0.05 ×749 = 37 min = 0.62 ho as Cus os po dia: (cus o o al = cus o de espe a dos u en es + cus o de se i¸co dos emp egados) S= 2 →39.57 ×1500$ + 2 ×8×1500$ = 59355$ + 24000$ = 83355$ S= 3 →3.50 ×1500$ + 3 ×8×1500$ = 5250$ + 36000$ = 41250$ S= 4 →0.62 ×1500$ + 4 ×8×1500$ = 930$ + 48000$ = 48930$ Op¸c˜ao que minimiza os cus os globais: 3 se ido es. Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 18 Slide 36 In o ma¸c˜ao adicional, po encialmen e ´u il nes e p ocesso de omada de decis˜ao, s˜ao os: Tempos de ac i idade/inac i idade dos emp egados: Ac i idade o al = 749 ×1 0.906 = 826min = 13.78h/dia Inac i idade: S= 2 →2×8−13.78 = 2.22h ( axa de inac i idade = 14%) S= 3 →3×8−13.78 = 10.22h ( axa de inac i idade = 43%) S= 4 →4×8−13.78 = 18.22h ( axa de inac i idade = 57%) Slide 37 Tabela p ´a ica pa a o c´alculo de P0em ilas M/M/S N´ume o de se ido es (S) λ µ2 3 4 5 0.15 0.8605 0.8607 0.8607 0.8607 0.20 0.8182 0.8187 0.8187 0.8187 0.25 0.7778 0.7788 0.7788 0.7788 0.30 0.7391 0.7407 0.7408 0.7408 0.35 0.7021 0.7046 0.7047 0.7047 0.40 0.6667 0.6701 0.6703 0.6703 0.45 0.6327 0.6373 0.6376 0.6376 0.50 0.6000 0.6061 0.6065 0.6065 0.55 0.5686 0.5763 0.5769 0.5769 0.60 0.5385 0.5479 0.5487 0.5488 0.65 0.5094 0.5209 0.5219 0.5220 0.70 0.4815 0.4952 0.4965 0.4966 0.75 0.4545 0.4706 0.4722 0.4724 0.80 0.4286 0.4472 0.4491 0.4493 0.85 0.4035 0.4248 0.4271 0.4274 0.90 0.3793 0.4035 0.4062 0.4065 0.95 0.3559 0.3831 0.3863 0.3867 Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 19 Slide 38 N´ume o de se ido es (S) λ µ2 3 4 5 1.00 0.3333 0.3636 0.3673 0.3678 1.20 0.2500 0.2941 0.3002 0.3011 1.40 0.1765 0.2360 0.2449 0.2463 1.60 0.1111 0.1872 0.1993 0.2014 1.80 0.0526 0.1460 0.1616 0.1646 2.00 0.1111 0.1304 0.1343 2.20 0.0815 0.1046 0.1094 2.40 0.0562 0.0831 0.0889 2.60 0.0345 0.0651 0.0721 2.80 0.0160 0.0521 0.0581 3.00 0.0377 0.0466 3.20 0.0273 0.0372 3.40 0.0186 0.0293 3.60 0.0113 0.0228 3.80 0.0051 0.0174 4.00 0.0130 4.20 0.0093 4.40 0.0063 4.60 0.0038 4.80 0.0017 Slide 39 Exemplo – Se i¸co de Ve e in´a ia da Coope a i a Ag ´ıcola de Belos A es Edmundo Te a ´e um dos c ´ı icos do uncionamen o do se i¸co de e e in´a ia da Coope a i a Ag ´ıcola de Belos A es – a i ma que semp e que chama um e e in´a io ele nunca em no mesmo dia. Ac ualmen e h´a dois e e in´a ios, cada um a endendo em m´edia 5 chamadas po dia – o se i¸co pode se conside ado M/M/2. Quan o aos pedidos de apoio a animais doen es e i ica-se que chegam alea o iamen e, seguindo um p ocesso de Poisson, `a az˜ao de 9 po dia. Sens´ı el `as c ´ı icas dos memb os da Coope a i a, a di ec¸c˜ao decidiu discu i o caso, admi indo mesmo con a a um no o e e in´a io. A alie a si ua¸c˜ao, con ibuindo com in o ma¸c˜ao que possa se ´u il pa a uma omada de decis˜ao sob e a e e ida con a a¸c˜ao. Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 20 Slide 40 Exemplo – Se i¸co de o oc´opias A sec¸c˜ao de o oc´opias duma emp esa, abe a 40 ho as po semana, disp˜oe de 2 o ocopiado as a endadas pelo alo o al de 12.0 con os cada po semana. Os u ilizado es chegam `a az˜ao de 33/ho a e o empo m´edio de se i¸co ´e de 3 minu os. Suponha e i icadas as condi¸c˜oes indicadas no es udo das ilas de espe a. 1. De e mine: •o nom´edio de pessoas agua dando a u iliza¸c˜ao duma o ocopiado a; •o empo m´edio duma pessoa na ila; •o empo m´edio duma pessoa no sis ema. 2. O cus o ho ´a io m´edio, pa a a emp esa, do pessoal que eco e ao se i¸co de o ocopias ´e de 1.8 con os/ho a, incluindo o e heads. Se ´a con enien e aumen a ao n´ume o de o ocopiado as a endadas? E pa a que n´ume o? Slide 41 Exemplo – Manu en¸c˜ao O supe iso ope acional duma emp esa de m´aquinas el´ec icas epa ou que o se i¸co de manu en¸c˜ao co en e de equipamen o ´e no malmen e a asado, de ido `a espe a na sec¸c˜ao de e amen as. Como qualque a aso na p odu¸c˜ao ob iga a uma al e a¸c˜ao das o dens de ab ico ou mesmo a abalho em ho as ex ao din´a ias, o supe iso eque eu um es udo sob e a iabilidade de ac escen a mais uncion´a ios `a sec¸c˜ao em ques ˜ao, pa a melho a a espos a `as necessidades do se i¸co de manu en¸c˜ao. O assun o oi es udado, concluindo-se que o empo m´edio en e-chegadas ´e de 80 segundos e que o empo m´edio de a endimen o, po pa e dum uncion´a io, ´e de 60 segundos. O cus o o al dum uncion´a io na sec¸c˜ao de e amen as ´e de $8.50 po ho a, enquan o que o cus o ela i o `a espe a (m´aquina pa ada) ´e de $15.00 po ho a. Conside a-se o dia de 8 ho as. A abela seguin e, pa cialmen e comple a, in o ma sob e o e ei o na ila de espe a de ac escen a mais uncion´a ios ( ila ipo M/M/s, s = 2, 3), `a sec¸c˜ao, incluindo a an´alise dos cus os di´a ios o ais en ol idos nas ´a ias op¸c˜oes. Comple e a abela. Na pe spec i a dos cus os o ais abelados, qual ´e a melho op¸c˜ao ? Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 21 Slide 42 Node uncion´a ios 1 2 3 Nom´edio equipamen os no sis ema (L) 3.00 Tempo m´edio no sis ema, em min.(W) 4.00 Nom´edio na ila de espe a (Lq) 2.25 Tempo m´edio na ila de espe a, em min. (Wq) 3.00 Pe cen agem de empo de desocupa¸c˜ao 0.25 Cus o ($)/dia dos uncion´a ios 68.00 Cus o ($)/dia de espe as 360.00 Cus o o al di´a io 428.00 Slide 43 Fila de espe a com comp imen o limi ado – M/M/1/K e M/M/S/K Fila de espe a com comp imen o limi ado — caso em que, po limi a¸c˜oes di e sas, o n´ume o m´aximo de elemen os no sis ema (a endimen o + ila de espe a) ´e K. ⇓ Taxa de chegada (λn) depende do es ado (n) do sis ema: λn=   λpa a n= 0,1,2,...,K−1 0 pa a n≥K Taxa de chegada −→ Taxa m´edia de en ada no sis ema λ(m´edia ponde ada das axas λe ze o pelas suas p obabilidades de oco ˆencia): λ= K−1 X n=0 λ×Pn=λ× K−1 X n=0 Pn=λ(1 −PK) No e-se que a p obabilidade de o sis ema es a em es ados n≥K+ 1 ´e nula (n˜ao se acei a ningu´em acima de K). Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 22 Slide 44 Consequˆencias •As ela¸c˜oes undamen ais en e Lq,L,WqeWman ˆem-se e dadei as, subs i uindo λpo λ. •λ µ ep esen a a axa de ocupa¸c˜ao. •ρ=λ µ ep esen a a axa de p ess˜ao. •O sis ema pode es a em equil´ıb io pa a alo es de ρsupe io es a 1. No en an o, nesse caso, ha e ´a um n´ume o po encialmen e ele ado de u en es do sis ema que chegam e n˜ao s˜ao se idos. •Pk ep esen a a p obabilidade de desis ˆencia po al a de capacidade do sis ema pa a a ende clien es que chegam quando o sis ema es ´a cheio. •Pa a S > 1 se ido es a axa de sa´ıda do sis ema con inua a depende do es ado do sis ema. Slide 45 Ca ac e ´ıs icas do modelo M/M/1/K Chegada: Poissoniana Tempo a endimen o: exponencial nega i o Taxa: λclien es / u. empo Taxa: µclien es / u. empo e se ido λn=   λpa a n= 0,1,2,...,K−1 0 pa a n≥KNose ido es: 1 λ= K−1 X n=0 λPn=λ(1 −PK)ρ=λ µ Popula¸c˜ao =∞Taxa de ocupa¸c˜ao =λ µ N0m´aximo de elemen os no sis ema =KTaxa de desocupa¸c˜ao = 1 −λ µ Fila m´axima K−1 Lq=∞ X n=1 (n−1)Pn=L−λ µWq=Lq λ L=∞ X n=0 nPn=ρ 1−ρ−(K+ 1)ρK+1 1−ρK+1 W=Wq+1 µ=L λ P0=1−ρ 1−ρK+1 (Taxa de desocupa¸c˜ao) Pn=   ρnP0,se n= 1,...,K 0,se n > K P(Wq= 0) = P0 Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 23 Slide 46 Ca ac e ´ıs icas do modelo M/M/S/K Chegada: Poissoniana Tempo a endimen o: exponencial nega i o Taxa: λclien es / u. empo Taxa: µclien es / u. empo e se ido λn=(λpa a n= 0,1,2,...,K−1 0 pa a n≥KNose ido es: S λ= K−1 X n=0 λPn=λ(1 −PK)ρ=λ Sµ Popula¸c˜ao =∞Taxa de ocupa¸c˜ao =λ Sµ N0m´aximo de elemen os no sis ema =KTaxa de desocupa¸c˜ao = 1 −λ Sµ Fila m´axima K−S Lq=∞ X n=S (n−S)Pn=Wq=Lq λ =P0³λ µ´Sρ S!(1−ρ)2×[1 −ρK−S−(K−S)ρK−S(1 −ρ)] L=∞ X n=0 nPn=Lq+λ µW=Wq+1 µ=L λ P0=1 S−1 X n=0 ³λ µ´n n!+³λ µ´S S! K X n=S ρn−S Pn=         ³λ µ´n n!P0,se n= 1, . . . , S ³λ µ´n S!Sn−SP0,se n=S,...,K 0,se n > K P(Wq= 0) = S−1 X n=0 Pn Slide 47 Exemplo – Po o de ma Um po o que ecebe na ios g anelei os em uma ´unica es a¸c˜ao de desca ga (m´o el) que pe mi e desca ega , em m´edia, 5 na ios po dia. O po o em um cais que pe mi e a acos agem de apenas 2 na ios, pelo que, quando o cais es ´a ocupado, na ios adicionais que p e endam acos a s˜ao des iados pa a ou o po o, aca e ando um cus o de 20000 con os po na io des iado. A imobiliza¸c˜ao de na ios no po o em um cus o de 12000 con os po dia e po na io. As chegadas dos na ios podem se conside adas Poissionianas, com uma axa de 3 na ios po dia, sendo os empos de desca ga exponenciais nega i os. P e ende-se a alia a iabilidade econ´omica de amplia o cais de modo a pode ecebe 3 na ios, amplia¸c˜ao essa a que co esponde ia um enca go adicional de 1000 con os po dia. Jos´e Fe nando Oli ei a – FEUP Filas de Espe a 24 Slide 48 Resolu¸c˜ao – Po o de ma A amplia¸c˜ao do cais jus i ica-se se a edu¸c˜ao de cus os (imobiliza¸c˜ao + des io) de na ios o maio que 1000 con os/dia. •Cus o de imobiliza¸c˜ao (CI): CI = 12000Wλ = 12000Lcon os/dia •Cus o de des io (CD): CD = 20000(3 −λ) con os/dia, em que 3 −λ ep esen a o n´ume o de na ios des iados po dia. Tomando en ˜ao: λ= 3 na ios/dia µ= 5 na ios/dia S= 1 ρ=3 5= 0.6 e eco endo `a abela com as ca ac e ´ıs icas do modelo an e io men e ap esen ada podemos calcula os cus os associados a K= 2 e a K= 3. Slide 49 Cus o com K= 2 P0= 0.510 P1= 0.306 P2= 0.184 1−P2= 0.816 (P obabilidade de o na io n˜ao se des iado) λ=λ(1 −P2) = 2.448 Taxa de ocupa¸c˜ao = λ µ= 0.49 L=0.6 1−0.6−3×0.63 1−0.63= 0.673 na ios Lq= 0.673 −0.49 = 0.183 na ios CI +CD = 12000 ×0.673 + 20000 ×(3 −2.448) = 8076 + 11040 = 19116 con os/dia Jos´e Fe nando Oli ei a – FEUP