mm1 por lotes

8/16/2019 MM1 por Lotes

http://slidepdf.com/reader/full/mm1-por-lotes 1/52

Solución Analítica M (x )/M /1

25 de julio de 2015

Nicolás Hernández R.Profesor: Reinaldo Vallejos

Procesos EstocásticosUniversidad Técnica Federico Santa María

Valparaíso–Chile



24

Solución AnalíticaM (x ) /M /1

Nicolás Hernández R.

Introducción

Descripción de la Fila

Kendall

Grafo

Solución EspacialRecurrente

EBG

Solución

Solución EspacialAnalítica

Primera Aproximación

Grafo de la Ecuación

Recurrente

Solución Analítica

Caso Particular L = 1

Comparación de lasSoluciones

Implementación

Computacional

Resultados

Tiempos de Ejecución

Referencias

Procesos Estocásticos

Universidad TécnicaFederico Santa María

Valparaíso–Chile

Contenido

Introducción

Descripción de la FilaKendallGrafo

Solución Espacial RecurrenteEBGSolución

Solución Espacial AnalíticaPrimera AproximaciónGrafo de la Ecuación RecurrenteSolución Analítica


Comparación de las SolucionesImplementación ComputacionalResultadosTiempos de Ejecución

Referencias



24



2Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile

Introducción

Motivación (G. Jensen 1977)

Considérese una industria de producción de planchas demadera.





2Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile

Introducción



Si una plancha posee más de L defectos es rechazada, delo contrario se envía a reparación.





2Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile

Introducción




Las plachas defectuosas arriban al centro de reparacióncon tasa λ. Con probabilidad αi , siendo 1 ≤ i ≤ L, unaplacha tiene i defectos.





2Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile

Introducción




Las plachas defectuosas arriban al centro de reparacióncon tasa λ. Con probabilidad αi , siendo 1 ≤ i ≤ L, unaplacha tiene i defectos.

Los defectos arriban en lotes, pero sólo pueden repararsede uno a la vez.





Introducción


3Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile

Descripción de la FilaKendall

M (x )/M /1 Bulk Arrival

Tiempo entre arribos de lotes: exp (λ).

λi = λαi 1 ≤ i ≤ L0 e .o .c

(1)

αi : probabilidad de que el lote sea de i clientes.

Tiempo de servicio: exp (µ).

Servidores: 1. Capacidad sistema: ∞.

Tamaño Población: ∞.





Introducción


Kendall

4Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile

Descripción de la FilaGrafo

0 1 2 i L-1 L L+1. . . . . . . . .λα1

λα2 λαi λαL−1 λαL

λα1λαi −1 λαL−2 λαL−1 λαL

µ µ µ µ





Introducción


Kendall

Grafo


5EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile

Solución Espacial RecurrenteEBG i + 1 ≤ L

0 1 2 i i + 1 L-1 L L+1. . . . . . . . .

λα1 λα2 λαi

λαi +1 λαL−1 λαL

λα1 λαi −1 λαi λαL−2 λαL−1 λαL

µ µ µ µ µ

µπi +1 = πh

Lk =i +1−h

λαk





Introducción


Kendall

Grafo


5EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile


0 1 2 i i + 1 L-1 L L+1. . . . . . . . .

λα1 λα2 λαi



µ µ µ µ µ

µπi +1 = πh

Lk =i +1−h

λαk



24



Introducción


Kendall

Grafo


5EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile


0 1 2 i i + 1 L-1 L L+1. . . . . . . . .

λα1 λα2 λαi



µ µ µ µ µ

µπi +1 =

i h =0

πh

Lk =i +1−h

λαk



24



Introducción


Kendall

Grafo


5EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile


0 1 2 i i + 1 L-1 L L+1. . . . . . . . .

λα1 λα2 λαi



µ µ µ µ µ

µπi +1 =

i h =0

πh

Lk =i +1−h

λαk

πi +1 = ρ

i h =0

πh Ai −h (2)



24



Introducción


Kendall

Grafo


6EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile

Solución Espacial RecurrenteEBG i + 1 > L

L-1 L L+1 i i+1. . . . . . . . .

λα1λα2 λαi +1−L

λαi +2−L

λα1 λαi −L λαi +1−L

µµ µ

µπi +1 = πh

Lk =i +1−h

λαk



24



Introducción


Kendall

Grafo


6EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile


L-1 L L+1 i i+1. . . . . . . . .


λαi +2−L


µµ µ

µπi +1 = πh

Lk =i +1−h

λαk



24



Introducción


Kendall

Grafo


6EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile


L-1 L L+1 i i+1. . . . . . . . .


λαi +2−L


µµ µ

µπi +1 =

i h =i −L+1

πh

Lk =i +1−h

λαk



24



Introducción


Kendall

Grafo


6EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile


L-1 L L+1 i i+1. . . . . . . . .


λαi +2−L


µµ µ

µπi +1 =

i h =i −L+1

πh

Lk =i +1−h

λαk

πi +1 = ρi

h =i −L+1

πh Ai −h (3)



24



Introducción


Kendall

Grafo


7EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile

Solución Espacial Recurrenteπ0

Utilizando la Ley de Little, que relaciona la tasa media de

llegada de individuos λ, número medio de clientes en elservidor N s y el tiempo medio de servicio 1

µse calcula π0.

λ = N s

1µ

(4)



24



Introducción


Kendall

Grafo


7EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile




µse calcula π0.

λ = N s

1µ

(4)

Se sabe que

λ =

Lk =1

λαk k



24



Introducción


Kendall

Grafo


7EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile




µse calcula π0.

λ = N s

1µ

(4)

Se sabe que

λ =

Lk =1

λαk k

y

N s = 0π0 + 1(1 − π0)



24



Introducción


Kendall

Grafo


7EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias



Valparaíso–Chile




µse calcula π0.

λ = N s

1µ

(4)

Se sabe que

λ =

Lk =1

λαk k

y

N s = 0π0 + 1(1 − π0)

Reemplazando en la ecuación (4)

λL

k =1

αk k = (1 − π0)

1µ

S l ió E i l R



24



Introducción


Kendall

Grafo


8EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias


Universidad Técnica

Federico Santa María

Valparaíso–Chile


π0 = 1 − ρL (5)

donde L representa el número medio de clientes por lote, estoes

L = λL

k =1

αk k

S l ió E i l R



24



Introducción


Kendall

Grafo


EBG

9Solución




Recurrente




Implementación

Computacional

Resultados


Referencias




Valparaíso–Chile

Solución Espacial RecurrenteSolución

En general, la solución recurrente que permite calcular πi +1 es

πi +1 =

1 − ρL i + 1 = 0

ρi

h =0 πh Ai −h 1 ≤ i + 1 ≤ L

ρi

h =i −L+1 πh Ai −h i + 1 > L

(6)

donde

Ai −h =L

k =i −h +1

αk

S l ió E i l A líti



24



Introducción


Kendall

Grafo


EBG

Solución


10Primera Aproximación


Recurrente




Implementación

Computacional

Resultados


Referencias




Valparaíso–Chile

Solución Espacial AnalíticaPrimera Aproximación

Para guiar la búsqueda se calculan los primero πi +1

π0

π0 = 1 − ρL

S l ió E i l A líti



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias




Valparaíso–Chile


Para guiar la búsqueda se calculan los primero πi +1

π0

π0 = 1 − ρL

π1

π1 = ρ0

h =0

πh A(0 − h )

= ρπ0A0

Solución Espacial Analítica



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias




Valparaíso–Chile


π2

π2 = ρ1

h =0

πh A(1 − h )

= ρπ0A1 + π1A0

= π0

ρ2A

2

0 + ρA1




24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias




Valparaíso–Chile


π2

π2 = ρ1

h =0

πh A(1 − h )

= ρπ0A1 + π1A0

= π0

ρ2A

2

0 + ρA1

π3

π3 = ρ2

h =0

πh A(2 − h )

= ρπ0A2 + π1A1 + π2A0

= π0 ρ3A

3

0 + 2ρ2A1A0 + ρA2




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente




Implementación

Computacional

Resultados


Referencias




Valparaíso–Chile


Parece cumplir la siguiente relación

πi +1 = π0 ρi +1Ai +1

0 + i ρi Ai

0A1 + (i − 1)ρi −1Ai −1

0 A2+

· · · + ρ0A0

0Ak −1

= π0

ρi +1A

i +1

0 +

i h =1

(i + 1 − h )ρi +1−h Ai −h

0 Ah




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente




Implementación

Computacional

Resultados


Referencias




Valparaíso–Chile


Parece cumplir la siguiente relación

πi +1 = π0 ρi +1Ai +1

0 + i ρi Ai

0A1 + (i − 1)ρi −1Ai −1

0 A2+

· · · + ρ0A0

0Ak −1

= π0

ρi +1A

i +1

0 +

i h =1

(i + 1 − h )ρi +1−h Ai −h

0 Ah

Sin embargo desde π4 en adelante no cumple estarelación, se debe buscar un método fiable para establecerla solución analítica.




24



Introducción


Kendall

Grafo


EBGSolución



13Grafo de la Ecuación

Recurrente




Implementación

Computacional

Resultados


Referencias




Valparaíso–Chile

Solución Espacial AnalíticaGrafo de la Ecuación Recurrente

0 1 2 3 L-1 L L+1. . . . . .

ρA1ρA2

ρAL−2 ρAL−1

ρA1 ρAL−3 ρAL−2 ρAL−1

ρA0 ρA0 ρA0 ρA0 ρA0




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente

14Solución Analítica



Implementación

Computacional

Resultados


Referencias



Federico Santa MaríaValparaíso–Chile

Solución Espacial AnalíticaSolución Analítica

Cada πn puede ser calculado como la suma de lasprobabilidades asociadas a cada camino que llega al nodon .




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente




Implementación

Computacional

Resultados


Referencias






La probabilidad de cada camino es el producto de π0 porlas probabilidades de transición.




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente




Implementación

Computacional

Resultados


Referencias







Estrategia:




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente




Implementación

Computacional

Resultados


Referencias







Estrategia:

Determinar todos los caminos que parten desde el nodo 0 y

llegan al nodo n .




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente




Implementación

Computacional

Resultados


Referencias







Estrategia:

Determinar todos los caminos que parten desde el nodo 0 y

llegan al nodo n . Calcular la probabilidad de cada camino.




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente




Implementación

Computacional

Resultados


Referencias





k j : cantidad de pasos de largo j con 1 ≤ j ≤ L .




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente




Implementación

Computacional

Resultados


Referencias






s : total de cantidad de pasos.

mínima cantidad total de pasos: cuando se da la mayor

cantidad de pasos de largo L, luego s =

n L

máxima cantidad total de pasos: cuando todos los pasos

son de largo 1, luego s = n




24



Introducción


Kendall

Grafo


EBGSolución




Recurrente




Implementación

Computacional

Resultados


Referencias




So uc ó spac a a t caSolución Analítica


s : total de cantidad de pasos.

mínima cantidad total de pasos: cuando se da la mayor

cantidad de pasos de largo L, luego s =

n L

máxima cantidad total de pasos: cuando todos los pasos

son de largo 1, luego s = n

n : distancia o largo a recorrer.




24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias




pSolución Analítica

Un camino de total de pasos s se puede secuenciar demúltiples formas. Si posee k 1 pasos de largo 1, k 2 pasosde largo 2, etc. el número de secuencias distintas es

s

k 1, k 2, k 3,..., k L

(7)




24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias





Un camino de total de pasos s se puede secuenciar demúltiples formas. Si posee k 1 pasos de largo 1, k 2 pasosde largo 2, etc. el número de secuencias distintas es

s

k 1, k 2, k 3,..., k L

(7)

Notar que el paso de largo j tiene una probabilidad detransición

ρA j −1

. Luego la probabilidad asociada a cada

camino es

(1 − ρL)ρA0

k 1 ρA1

k 2...ρAL−1

k L(8)




24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias





Considerando las definiciones de k j , s y n es necesario

que se cumpla

0 ≤ k j ≤ s 1 ≤ j ≤ Lk 1 + k 2 + ... + k L = s k 1 + 2k 2 + ... + Lk L = n

(9)




24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias





Considerando las definiciones de k j , s y n es necesario

que se cumpla

0 ≤ k j ≤ s 1 ≤ j ≤ Lk 1 + k 2 + ... + k L = s k 1 + 2k 2 + ... + Lk L = n

(9)


πn =

n

s =

n

L0≤k 1,...,k L≤s

k 1+k 2+...+k L=s k 1+2k 2+...+Lk L=n

s

k 1, k 2, ...,k L

(1 − ρL)ρs

L−1

i =0

Ak i +1

i

(10)

Solución Espacial AnalíticaS l ió A lí i



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias





La solución analítica encontrada puede reescribirse como

πn =

n L

k L=0

n −Lk L

L−1

k L−1=0

...

n −

L

j =3 jk j

2

k 2=0

s

k 1, k 2,...,k L

(1 − ρL)ρs

L−1i =0

Ak i +1

i

(11)

donde k 1 queda inmediatamente determinado pork 1 = n − 2k 2 − 3k 3 − ...− Lk L

y s inmediatamente determiando por

s = k 1 + k 2 + ... + k L

Solución Espacial AnalíticaC P ti l L 1



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente


19Caso Particular L = 1


Implementación

Computacional

Resultados


Referencias





Si L = 1 la fórmula general se transforma en

πn =

n s = n

1

0≤k 1≤s

k 1=s k 1=n

s

k 1

(1 − ρ)ρs

0i =0

Ak i +1

i

Solución Espacial AnalíticaC P ti l L 1



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias






πn =

n s = n

1

0≤k 1≤s

k 1=s k 1=n

s

k 1

(1 − ρ)ρs

0i =0

Ak i +1

i

=n

s =n

0≤k 1≤s

k 1=s k 1=n

s

k 1

(1 − ρ)ρs

0i =0

Ak i +1

i

Solución Espacial AnalíticaCaso Particular L 1



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias






πn =

n s = n

1

0≤k 1≤s

k 1=s k 1=n

s

k 1

(1 − ρ)ρs

0i =0

Ak i +1

i

=n

s =n

0≤k 1≤s

k 1=s k 1=n

s

k 1

(1 − ρ)ρs

0i =0

Ak i +1

i

=n

n

(1 − ρ)ρ

n

A

n

0

Solución Espacial AnalíticaCaso Particular L 1



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


Referencias






πn =

n s = n

1

0≤k 1≤s

k 1=s k 1=n

s

k 1

(1 − ρ)ρs

0i =0

Ak i +1

i

=n

s =n

0≤k 1≤s

k 1=s k 1=n

s

k 1

(1 − ρ)ρs

0i =0

Ak i +1

i

=n

n

(1 − ρ)ρ

n

A

n

0

Solución Analítica para caso M/M/1 (llegadas individuales)

πn = (1 − ρ)ρ

n

(12)

Comparación de las SolucionesImplementación Computacional



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




20Implementación

Computacional

Resultados


Referencias




Implementación Computacional

πn =

n 5

k 5=0

n −5k 54

k 4=0

...

n −5k 5−4k 4−3k 32

k 2 =0

s

k 1 , k 2 , ..., k 5

(1 − ρL)ρ

s

4i =0

Ak i +1i

Implementación en MATLAB.

sumatoria=0;

for k5=0:floor(n/5)

for k4=0:floor((n-5*k5)/4)

for k3=0:floor((n-5*k5-4*k4)/3)

for k2=0:floor((n-5*k5-4*k4-3*k3)/2)

k1=n-2*k2-3*k3-4*k4-5*k5;

s=k1+k2+k3+k4+k5;

ft=factorial(s);

f1=factorial(k1);

f2=factorial(k2);

f3=factorial(k3); f4=factorial(k4);

f5=factorial(k5);

PAc=Ac(1,1)^k1*Ac(2,1)^k2*Ac(3,1)^k3*Ac(4,1)^k4*Ac(5,1)^k5;

sumatoria=sumatoria+(ft/(f1*f2*f3*f4*f5))*p(1,1)*rho^s*PAc;

end

end

end

end

Comparación de las SolucionesResultados



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

21Resultados


Referencias




Resultados

Parámetros y Resultados

n Pi_nR Pi_nA

__ _________ _________

1 0.0695 0.0695 20 3.556e-05 3.556e-05

40 5.652e-09 5.652e-09 80 1.425e-16 1.425e-16

120 3.596e-24 3.596e-24

160 9.071e-32 9.071e-32 170 1.143e-33 1.143e-33

171 7.382e-34 NaN 10e+6 2.488e-191 NaN

%PARAMETROS

n=1;

lambda=1;

mu=10;

rho=lambda/mu;

%LOTE MEDIO

alfa=[0.15; 0.3; 0.1; 0.25; 0.2];

L=5;

Lmedio=mtimes(transpose([1; 2; 3; 4; 5]), alfa);

p(1,1)=1-rho*Lmedio; %Pi_0

Comparación de las SolucionesResultados



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

22Resultados


Referencias




Resultados

Comparación de las SolucionesTiempos de Ejecución



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados

23Tiempos de Ejecución

Referencias




p j

ReferenciasPublicaciones



24



Introducción


Kendall

Grafo


EBG

Solución




Recurrente




Implementación

Computacional

Resultados


24Referencias




G. Jensen, A. Paulson & P. Sullo, 1977. Explicit steady state solutions for a particular M (x )/M /1 queueing system .

Naval Research Logistics Quarterly 24, 651-659.

J. Martínez V., R. Vallejos C. & M. Barría M., 2014. On the limiting probabilities of the M /E r /1 queueing system .Statistics and Probability Letters 88, 56–61.



Gracias por su atención.

mm1 por lotes

Documents