AM2. Tema 3. Teoria de cues

Tema 3. Teoria de cues Lali Barri`ere Departament de Matem`atiques - UPC Enginyeria de Sistemes Aeroespacials EETAC Lali Barri`ere - AM2 Tema 3. Teoria de cues 1 / 23 Continguts Continguts 3.1 Proc´es de Poisson 3.2 Introducci´o a la teoria de cues 3.3 Poblaci´o infinita (N=∞) 3.4 Poblaci´o finita (N < ∞) Lali Barri`ere - AM2 Tema 3. Teoria de cues 2 / 23 3.1 Proc´es de Poisson 3.1 Proc´es de Poisson Definici´o Un proc´es ´es una col·lecci´o de variables aleat`ories X(t), on t∈R, si el proc´es ´es continu; t∈N, si el proc´es ´es discret. La variable t representa el temps. En un proc´es de naixement,X(t)compta arribades independents amb una certa intensitat. X(0) = 0, i en certs instants de temps tenim un “naixement” o “arribada”, de manera que X(t)s’incrementa en 1. Exemples IX(t) = # cotxes que han passat per un peatge fins a l’instant t. IX(t) = # trucades rebudes per una centraleta a l’instant t. X(ta, tb) = X(tb)−X(ta)compta el nombre d’arribades entre taitb. Lali Barri`ere - AM2 Tema 3. Teoria de cues 3 / 23 3.1 Proc´es de Poisson Proc´es de Poisson Definici´o Un proc´es de Poisson d’intensitat λ´es un proc´es que compleix alguna de les propietats equivalents seg¨uents: 1. En intervals dt (diferencial de temps) arriben Po(λ·dt)elements. 2. X(t)∼Po(λ·t)per a tota t∈R. A m´es, si t1< t2< t3< t4,X(t1, t2)iX(t3, t4)s´on independents. E(X(t)) = λ·t. 3. El temps Tentre dues arribades ´es independent i es distribueix seguint una Exp(λ). T∼Exp(λ),E(T) = 1 λ. Observaci´o Els processos de Poisson s´on un cas particular de proc´es de naixements. Lali Barri`ere - AM2 Tema 3. Teoria de cues 4 / 23 3.1 Proc´es de Poisson Propietats 1. Els processos de Markov no tenen mem`oria (Memoryless). Un proc´es de Poisson ´es un proc´es de Markov. Paradoxa de l’autoestopista Suposem que en una carretera passen cotxes seguint un proc´es de Poisson amb par`ametre λ= 6. En mitjana, passen 6 cotxes cada hora, ´es a dir, un cada 10 minuts. Quin ´es el temps que haur`a d’esperar, en mitjana, un autoestopista que arriba a la carretera en un instant qualsevol? Proc´es de Poisson: el temps d’espera, T, t´e una esperan¸ca E(T) = 10 minuts. Intu¨ıci´o Mitjana del temps d’espera: 5 minuts. Realitat ´ Es m´es probable arribar entre dues arribades molt distants, que entre dues arribades molt properes. Per tant, haur`a d’esperar m´es. Lali Barri`ere - AM2 Tema 3. Teoria de cues 5 / 23 3.1 Proc´es de Poisson Suposem que els cotxes arriben exactament cada 10 minuts. Mitjana del temps d’espera: 5 minuts. Proc´es de Poisson. Mitjana del temps d’espera: 10 minuts. Observaci´o Els processos de Poisson no tenen mem`oria (Memoryless). Lali Barri`ere - AM2 Tema 3. Teoria de cues 6 / 23 3.1 Proc´es de Poisson 2. Si condicionem que X(t) = n, aleshores les arribades s´on uniformes en l’interval [0, t]. 3. Merge X1(t),X2(t)processos de Poisson amb intensitats λ1iλ2, respectivament. Aleshores: X(t) = X1(t) + X2(t)´es un proc´es de Poisson amb intensitat λ1+λ2. 4. Split X(t)proc´es de Poisson amb intensitat λ. Seleccionem cada element que arriba amb probabilitat p∈[0,1]. Aleshores, les arribades seleccionades formen un proc´es de Poisson amb intensitat λ·p. 5. Diagrama d’estats Ei´es l’estat (esdeveniment) en qu`e X(t) = i(hi ha iarribades). E0E1E2E3· · · λλλλ El temps de saltar d’un estat al seg¨uent ´es Exp(λ). Lali Barri`ere - AM2 Tema 3. Teoria de cues 7 / 23 3.2 Introducci´o a la teoria de cues 3.2 Introducci´o a la teoria de cues Una cua ´es un proc´es de naixement i mort: arribades i sortides. El sistema t´e dues parts: els servidors i la cua. | {z } servidors | {z } cua | {z } sistema ISempre suposarem que hi ha una ´unica cua. IPot haver-hi m´es d’un servidor. Lali Barri`ere - AM2 Tema 3. Teoria de cues 8 / 23 3.2 Introducci´o a la teoria de cues Notaci´o de Kendall M / M / s / k // N ↓ ↓ ↓ ↓ ↓ 1 2 3 4 5 1. Distribuci´o d’arribada. Proc´es de Poisson amb intensitat λ > 0. 2. Distribuci´o de sortida (o de servei). Proc´es de Poisson amb intensitat µ > 0. El temps mitj`a de servei ´es 1/µ. 3. Nombre de servidors: s≥1. 4. Capacitat del sistema: k≥s. Pot ser finita o infinita. Si no es posa la k, vol dir que la capacitat ´es infinita. 5. Poblaci´o. Pot ser finita o infinita. Si no es posa la N, vol dir que la poblaci´o ´es infinita. M vol dir “Memoryless”, ´es a dir, proc´es de Poisson. Hi poden haver cues amb altres distribucions, que no estudiarem. Pol´ıtica de cua FIFO (First In, First Out) Hip`otesi de treball Per evitar l’efecte de les condicions inicials: esperem un temps perqu`e la cua s’estabilitzi, llavors l’estudiem. Diem que estudiem les cues en r`egim estacionari od’equilibri. Lali Barri`ere - AM2 Tema 3. Teoria de cues 9 / 23 3.3 Poblaci´o infinita (N=∞) Par`ametres relacionats amb el temps d’espera IW=temps esperat d’un usuari al sistema Llei de Little: L=λ·W⇒W=L λ=1 µ−λ IWs=temps esperat d’un usuari al servidor =temps de servei =1 µ IWq=temps esperat d’un usuari a la cua = =W−Ws=1 µ−λ−1 µ=λ µ(λ−µ) Lali Barri`ere - AM2 Tema 3. Teoria de cues 16 / 23 3.3 Poblaci´o infinita (N=∞) 3.3.2 M / M / s (s > 1,k=N=∞) Diagrama d’estats E0E1E2· · · Es−1EsEs+1 · · · λ λ λλλλ λ sµ sµ sµ (s−1)µ 3µ 2µ µ Intensitat ρ=λ sµ S’ha de complir ρ < 1per tal que la cua sigui estable. Observaci´o Per a aquest model i els seg¨uents no calcularem els par`ametres, utilitzarem el Formulari. Observaci´o Per a aquest model tamb´e es compleix que ρ´es la fracci´o de temps que un servidor est`a ocupat. Lali Barri`ere - AM2 Tema 3. Teoria de cues 17 / 23 3.3 Poblaci´o infinita (N=∞) 3.3.3 M / M / 1 / k (s= 1,kfinita, N=∞) Diagrama d’estats E0E1E2· · · Ek−1Ek λ λ λλλ µ µ µ µµ Intensitat ρ=λ µ ILes arribades a l’estat Ekes perden. ISi ρ≥1perdem entrades, per`o la cua no ser`a mai massa gran. Iρ∈R+. Si ρ6= 1, utilitzem el Formulari; si ρ= 1 es fan els c`alculs a m`a, tenint en compte que, en aquest cas, pk+1 = 0 (i,per tant, pi= 0 si i>k. Lali Barri`ere - AM2 Tema 3. Teoria de cues 18 / 23 3.3 Poblaci´o infinita (N=∞) IIntensitat d’arribades: λper unitat de temps. IIntensitat d’entrades: λper unitat de temps: λ= k X i=0 λi·pi=λ·p0+λ·p1+· · · +λ·pk−1+ 0 ·pk= =λ(p0+p1+· · · +pk−1) = λ(1 −pk) IIntensitat de p`erdues: λ−λ IL,Wamb λ: mitjanes sobre el nombre d’entrades. Observaci´o En algun cas ens podem preguntar quant valen LiW, sobre el nombre d’arribades. Els c`alculs s´on semblants, amb λen lloc de λ. Lali Barri`ere - AM2 Tema 3. Teoria de cues 19 / 23 3.3 Poblaci´o infinita (N=∞) 3.3.3 M / M / s / k (s≥1,kfinita, N=∞) Diagrama d’estats E0E1E2· · · Es−1EsEs+1 · · · Ek−1Ek λ λ λλλλλλλ sµ sµ sµ sµ sµ (s−1)µ 3µ 2µ µ Intensitat ρ=λ sµ Lali Barri`ere - AM2 Tema 3. Teoria de cues 20 / 23 3.4 Poblaci´o finita (N < ∞) 3.4 Poblaci´o finita (N < ∞) Exemple Una companyia de taxis t´e 10 taxis. Quan algun taxi s’espatlla, entra a la cua de reparaci´o. La probabilitat que entri un taxi a la cua de reparaci´o ´es m´es petita, com m´es gran sigui la cua. Observaci´o En aquest model, cada usuari t´e la seva λ. Lali Barri`ere - AM2 Tema 3. Teoria de cues 21 / 23 3.4 Poblaci´o finita (N < ∞) 3.4.1 M / M / 1 // N (s= 1,k=∞,Nfinita) Diagrama d’estats E0E1E2· · · EN−1EN Nλ (N−1)λ(N−2)λ2λλ µ µ µ µ µ Intensitat mitjana d’entrada λ= N X i=0 λi·pi= N X i=0 λ(N−i)·pi=Nλ N X i=0 pi−λ N X i=0 i·pi= (N−L)λ Exlicaci´o La intensitat d’entrada en mitjana, λ, ´es la intensitat d’arribada particular, λ, pel nombre mitj`a d’usuaris fora del sistema, (N−L). Lali Barri`ere - AM2 Tema 3. Teoria de cues 22 / 23 3.4 Poblaci´o finita (N < ∞) 3.4.2 M / M / s / / N (s≥1,k=∞,Nfinita) Diagrama d’estats E0E1E2· · · Es−1EsEs+1 · · · EN−1EN Nλ (N−1)λ(N−2)λ(N−s+ 2)λ(N−s+ 1)λ(N−s)λ(N−s−1)λ2λλ sµ sµ sµ sµ sµ (s−1)µ 3µ 2µ µ Lali Barri`ere - AM2 Tema 3. Teoria de cues 23 / 23