• Author / Uploaded
• nicolas reinaldo Armijo

Citation preview

Conceptos Fundamentales de la Simulación

Lo que haremos... • • •

Destacar ideas, métodos, y asuntos en simulación Independencia de Software Ejemplo de un Sistema de procesamiento simple    

•

Simulación de Planilla 

•

Descomponer el problema Terminología Simulación manual Algunos temas básicos de estadística Modelos estáticos y dinámicos simples

Análisis de un proyecto de simulación Slide 2 de 57

El Sistema: Un Sistema de Procesos Simple Máquina (Servidor)

llegada Partes iniciales

• Intención general:

7

6

5

Cola (FIFO)

4

Salida Partes Finalizadas Partes en Servicio

Estimar producción esperada  Tiempo de espera en cola, largo de cola, proporción de tiempo de máquina ocupado Unidades de Tiempo  Se pueden utilizar diferentes unidades en diferentes lugares… se deben declarar  Cuidado con chequear unidades cuando se define el input Declare unidades base de tiempo para output y cálculos internos  Sea razonable (interpretación, error de redondeo) 

•

Slide 3 de 57

Especificaciones del Modelo • • •

•

Inicialmente (tiempo 0) vacío y desocupado Unidades base de tiempo: minutos Input data (asumir dadas por ahora…), en minutos: Numbero de Partes Tiempo llegada Tiempo entre arribos 1 0.00 1.73 2 1.73 1.35 3 3.08 0.71 4 3.79 0.62 5 4.41 14.28 6 18.69 0.70 7 19.39 15.52 8 34.91 3.15 9 38.06 1.76 10 39.82 1.00 11 40.82 . . . . . . .

Tiempo de servicio 2.90 1.76 3.39 4.52 4.46 4.36 2.07 3.36 2.37 5.38 . . .

Para cuando han transcurrido 20 minutos de tiempo (simulado) Slide 4 de 57

Objetivo del Proyecto: Medidas de Rendimiento de Salida (OUTPUT)

• •

Producción total de partes de una corrida (P) Tiempo de espera promedio de partes en cola: N = no. de partes completando una fila de espera WQi = Tiempo de espera en la cola (waiting time in queue) para parte i Conocer: WQ1 = 0 (Por qué?) N > 1 (Por qué?)

N

 WQ

i

i 1

N

•

Máximo tiempo de espera de partes en la cola: max WQ

i

i  1,..., N

Slide 5 de 57

Objetivo del Proyecto: Medidas de Rendimiento de Salida (OUTPUT)

•

Tiempo promedio número de partes en cola: 20

0 Q ( t ) dt

• •

Q(t) = numero de partes en cola al tiempo t 20 Máximo numero de partes en cola: max Q ( t ) 0  t  20 Promedio y máximo tiempo total en el sistema de partes (a.k.a. tiempo de ciclo (cycle time)): P

 TS i 1

P

i

,

max TS i  1 ,..., P

i

TSi = tiempo en sistema de partes i Slide 6 de 57

Objetivo del Proyecto: Medidas de Rendimiento de Salida (OUTPUT)

•

Utilización de máquina(proporcion de tiempo en uso (time busy))



20

B (t ) d t 0

, 20

•



1 B (t )  0

if m a c h in e is b u s y a t tim e t if m a c h in e is id le a t tim e t

Muchas otras posibilidades (sobrecarga de información)

Slide 7 de 57

Opciones de Análisis •

Adivinar en forma informada   

  

Tiempo promedio entre llegadas (Average interarrival time) = 4.08 minutes Tiempo promedio de servicio (Average service time) = 3.46 minutes Por lo tanto (en promedio) las partes están siendo procesadas más rápido de lo que llegan – El Sistema tiene la oportunidad de operar en forma estable, en largas corridas; por ejemplo puede “que no explote” – Si todos los tiempos entre llegadas y de servicio estuvieran realmente a su promedio, nunca habría una cola. – Sin embargo la data exhibe claramente variabilidad, por lo que se puede formar una cola Si tuviésemos el average interarrival < average service time, y esto persistiese, entonces la cola explotaría La verdad — entre estos extremos El adivinar tiene sus límites has its limits … Slide 8 de 57

Opciones de Análisis •

Teoría de colas  

Requiere supuestos adicionales sobre el modelo Popular, modelo simple: M/M/1 queue – Interarrival times ~ exponencial – Service times ~ exponencial, indep. de interarrivals – Debe tener E(service) < E(interarrival) – Steady-state (long-run, para siempre) – Resultados analíticos exactos; ej., Tiempo de espera promedio en cola (average waiting time in queue) es 2

S

 A  S  

,

 A  E(interarr

ival time)

 S  E(service

time)

Problemas: validez, estimación de promedios, rango de tiempo (time frame) A menudo útil como una aproximación de primera instancia Slide 9 de 57

Simulación Mecanizada • • • • • •

Operaciones individuales (arrivals, service times) ocurrirán exactamente como en la realidad Movimientos, cambios ocurren en momentos “precisos”, y en el orden correcto Diferentes piezas interactúan Instalar “observadores” para obtener las medidas de rendimiento de salida (output performance measures) Concretar, aproximación de análisis de “fuerza-bruta Nada misterioso o sutil  Pero con mucho detalle, archivo  El software de simulación lleva el registro por Ud.

Slide 10 de 57

Componentes de un Modelo de Simulación •

Entidades (entities)      



“Jugadores” que se mueven alrededor, cambian status, afectan o son afectados por otras entidades Objetos dinámicos (Dynamic objects) — Se crean, mueven alrededor, y salen (quizás) Usualmente representan cosas “reales” – Nuestro modelo: entidades son partes Pueden crearse entidades falsas para modelar “trucos” – Breakdown demon, break angel Generalmente se tienen múltiples realizaciones flotando alrededor Se puede tener diferentes tipos de entidades en forma concurrente Generalmente el identificar los tipos de entidades es lo primero que se hace en la construcción de un modelo

Slide 11 de 57

Componentes de un Modelo de Simulación •

Atributos (Attributes)  

Características de todas las entidades: describen, diferencian Todas las entidades tienen los mismos atributos “espacios” pero valores diferentes para entidades diferentes, por ejemplo: – – –

–

  

Timpo de llegada (Time of arrival) Fecha de expiración (Due date) Prioridad (Priority) Color

El valor atributo está unido a una entidad en específico Como las variables “local” (para entidades) Algunas son automáticas, otras se asignan Slide 12 de 57

Componentes de un Modelo de Simulación •

Variables (Globales)  

Reflejan una característica del modelo complete, no de entidades en especifico Usado para muchas cosas – – –

   

Tiempo de viaje entre todas las estaciones pares Numero de partes del sistema Reloj de simulación

Nombre, valor que tiene una sola versión para todo el modelo No unido a entidades Entidades pueden acceder, cambiar variables Escritura en muralla (reescribible)

Slide 13 de 57

Componentes de un Modelo de Simulación •

Recursos (Resources) 

Por lo que las entidades compiten – – –

  

Las entidades toman un recurso (seize), lo usan y le sueltan (releases) Se debe pensar que los recursos son asignados a una entidad, más que una entidad “pertenece” a un recurso “Un” recurso puede tener varias unidades de capacidad – –



Gente (People) Equipo (Equipment) Espacio (Space)

Asientos en una mesa de restaurant Personal de atenci{on de tickets en un counter de aerolínea

Número de unidades de un recurso pueden ser modificados durante la simulación Slide 14 of 57

Componentes de un Modelo de Simulación •

Colas (Queues) 

 



Lugar en donde las entidades deben esperar cuando no se pueden mover o continuar (quizás porque en recurso que quieren utilizar no está disponible) Asigne nombre, a menudo amarrados al correspondiente recurso Puede tener una cantidad finita para modelar el espacio limitado – Se debe modelar que hacer en caso de que una entidad se presente en una cola que se encuentra llena Generalmente se debe observar el largo de una cola, y el tiempo de espera en ella

Slide 15 de 57

Componentes de un Modelo de Simulación •

Estadística de acumulación     

Variables que “ven” lo que está sucediendo Depende de las medidas deseadas de la performance de salida “Pasivo” en el modelo — No se anticipe, sólo observe Muchas son automáticas, pero algunas deben establecerse y mantenerse durante la simulación Al final de la simulación, se utilizó para computar el rendimiento final

Slide 16 de 57

Componentes de un Modelo de Simulación •

Acumuladores estadísticos para sistemas de procesamiento simple   

  

  

Numero de partes producidas hasta el momento Total of tiempos de espera en la cola hasta el momento Número de partes que han pasado por la cola Tiempo Max en la cola, que se ha visto hasta el momento Total de tiempo transcurrido en el sistema Tiempo Max en el sistema, que hemos visto hasta el momento Área bajo la curva de la cola Q(t), hasta el momento Max de Q(t) hasta el momento Área bajo la curva de servidor ocupado (server-busy), hasta el momento curve B(t) Slide 17 de 57

Dinámica de la Simulación: Event-Scheduling “World View” • Identificar eventos característicos • Decidir la lógica para cada tipo de evento para:   

Efectuar cambios de estado (state changes) para cada tipo de evento Observar la estadística Actualizar tiempos de eventos futuros(quizás de este tipo, o de otros tipos)

• Mantener un reloj (clock), y un calendario de eventos •

• •

futuros Saltar de un evento al siguiente, procesar, observar estadística, actualizar calendario de eventos Debe especificar una regla de detención apropiada Generalmente hecha con un lenguaje de programación de propósito general(C++, Java, Matlab, FORTRAN, etc.)

Slide 18 de 57

Eventos para el Sistema de Procesamiento Simple • Llegada (Arrival) de una nueva pieza al sistema 

 





Actualizar los acumuladores estadísticos persistentes en el tiempo (desde el último evento hasta ahora) – Área bajo Q(t) – Max de Q(t) – Área bajo B(t) “Marcar” partes que llegan con el tiempo presente (uso después) Si la máquina está desocupada: – Comenzar procesamiento (programa de partida - schedule departure), Mantener la máquina ocupada, Mantener la cuenta del tiempo de espera en la cola(0) Si no (la maquina está ocupada): – Ponga la parte al final de la cola, aumente el largo variable de la cola Programe el próximo evento de llegada Slide 19 de 57

Eventos para el Sistema de Procesamiento Simple • Partida o salida (Departure) (cuando un servicio es completado)   





Incrementar el numero producido del acumulador estadístico Computar & llevar el tiempo en el sistema (ahora – tiempo de llegada (arrival)) Actualizar estadística persistente en el tiempo (como en un evento de llegada) Si la cola no está vacía: – Tome la primera pieza fuera de la cola, compute y cuente el tiempo de espera en la cola, y el comienzo de servicio (programar departure time) Si no (la cola está vacía): – Mantenga la máquina desocupada (Notar: no habrá evento de salida programado para futuros eventos de, calendario, Lo que si se desea

Slide 20 de 57

Eventos para el Sistema de Procesamiento Simple • Finalización  



•

Actualizar las estadísticas persistentes en el tiempo (para finalizar la simulación) Computar las medidas de rendimiento de salida finales utilizando los valores actuales del acumulador de estadísticas Después de cada evento, el registro superior del calendario de eventos es removido para ver cual es el tiempo, y que hacer

También se debe reinicializar todo

Slide 21 de 57

Algunos puntos adicionales para el Sistema de Procesamiento Simple • Reloj de Simulación variable (interno en Arena) • Calendario de eventos : lista de eventos registrados: [Entity No., Event Time, Event Type]  Mantener rankeado en orden creciente en Event Time  Próximo evento siempre al comienzo del registro (record)  Inicialmente, programe la primera llegada (Arrival), la última (The End) (Dep.?) Variable de estado (State variables): describe el estatus actual  Estatus del Servidor B(t) = 1 ocupado (busy), 0 libre (idle)  Numero de clientes en cola Q(t)  Hora de llegada de cada cliente en la cola (una ista de largo aleatorio) 

•

Slide 22 de 57

Simulation Manual • •

• • •

Manualmente traquee las variables de estado, y los acumuladores estadísticos Use el interarrival (entre llegadas) “dado (given)”, y los tiempos de servicio Mantenga el registro del calendario de eventos “Avance” el reloj de un evento al siguiente Se omitirán el tiempo en el sistema, “maximiza” computación aqui

Slide 23 de 57

Simulación Manual: Setup S y s te m

C lo c k

B (t)

A r r iv a l t im e s o f

Q (t)

E v e n t c a le n d a r

c u s t s . in q u e u e

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le t e d w a it in g

w a it in g t im e s in q u e u e

Q (t)

B (t)

t im e s in q u e u e

4 3

Q (t) g ra p h

2 1 0

B (t) g ra p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u t e s ) I n t e r a r r iv a l t im e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e t im e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 24 de 57

Simulación Manual : t = 0.00, Inicializar S y s te m

C lo c k 0 .0 0

B (t)

Q (t)

0

A r r iv a l t im e s o f

E v e n t c a le n d a r

c u s t s . in q u e u e

[1 ,

0 .0 0 ,

A rr]

[– ,

2 0 .0 0 ,

End]

< e m p ty >

0

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le t e d w a it in g

w a it in g t im e s in q u e u e

Q (t)

B (t)

0 .0 0

0 .0 0

0 .0 0

t im e s in q u e u e 0

4 3

Q (t) g ra p h

2 1 0

B (t) g ra p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u t e s ) I n t e r a r r iv a l t im e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e t im e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 25 de 57

Simulación Manual : t = 10.00,Arrival (llegada) of Part 1(Pieza 1 ) S y s te m

C lo c k

1

0 .0 0

B (t)

Q (t)

1

A r r iv a l t im e s o f

E v e n t c a le n d a r

c u s t s . in q u e u e

[2 ,

1 .7 3 ,

A rr]

[1 ,

2 .9 0 ,

Dep]

[– ,

2 0 .0 0 ,

End]

< e m p ty >

0

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le t e d w a it in g

w a it in g t im e s in q u e u e

Q (t)

B (t)

0 .0 0

0 .0 0

0 .0 0

t im e s in q u e u e 1

4 3

Q (t) g ra p h

2 1 0

B (t) g ra p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u t e s ) I n t e r a r r iv a l t im e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e t im e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 26 de 57

Simulación Manual : t = 1.73, Arrival (llegada) of Part 2(Pieza 2) S y s te m

C lo c k

2

1

1 .7 3

B (t)

Q (t)

1

A r r iv a l t im e s o f

E v e n t c a le n d a r

c u s t s . in q u e u e

[1 ,

2 .9 0 ,

Dep]

[3 ,

3 .0 8 ,

A rr]

[– ,

2 0 .0 0 ,

End]

(1 .7 3 )

1

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le t e d w a it in g

w a it in g t im e s in q u e u e

Q (t)

B (t)

0 .0 0

0 .0 0

1 .7 3

t im e s in q u e u e 1

4 3

Q (t) g ra p h

2 1 0

B (t) g ra p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u t e s ) I n t e r a r r iv a l t im e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e t im e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 27 de 57

Simulación Manual : t = 2.90, Departure (salida) of Part 1 S y s te m

C lo c k

2

2 .9 0

B (t)

Q (t)

1

A r r iv a l t im e s o f

E v e n t c a le n d a r

c u s t s . in q u e u e

[3 ,

3 .0 8 ,

A rr]

[2 ,

4 .6 6 ,

Dep]

[– ,

2 0 .0 0 ,

End]

< e m p ty >

0

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le t e d w a it in g

w a it in g t im e s in q u e u e

Q (t)

B (t)

1 .1 7

1 .1 7

2 .9 0

t im e s in q u e u e 2

Q (t) g ra p h

B (t) g ra p h

2 1 0 0

5

10

15

20

T im e ( M in u t e s ) I n t e r a r r iv a l t im e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e t im e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 28 de 57

Simulación Manual : t = 3.08, Arrival of Part 3 S y s te m

C lo c k

3

2

3 .0 8

B (t)

Q (t)

1

A r r iv a l t im e s o f

E v e n t c a le n d a r

c u s t s . in q u e u e

[4 ,

3 .7 9 ,

A rr]

[2 ,

4 .6 6 ,

Dep]

[– ,

2 0 .0 0 ,

End]

(3 .0 8 )

1

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le t e d w a it in g

w a it in g t im e s in q u e u e

Q (t)

B (t)

1 .1 7

1 .1 7

3 .0 8

t im e s in q u e u e 2

4 3

Q (t) g ra p h

2 1 0

B (t) g ra p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u t e s ) I n t e r a r r iv a l t im e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e t im e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 29 de 57

Simulación Manual : t = 3.79, Arrival of Part 4 S y s te m

4

C lo c k

3

2

3 .7 9

B (t)

Q (t)

1

A r r iv a l t im e s o f

E v e n t c a le n d a r

c u s t s . in q u e u e

[5 ,

4 .4 1 ,

A rr]

[2 ,

4 .6 6 ,

Dep]

[– ,

2 0 .0 0 ,

End]

(3 .7 9 , 3 .0 8 )

2

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le t e d w a it in g

w a it in g t im e s in q u e u e

Q (t)

B (t)

1 .1 7

1 .8 8

3 .7 9

t im e s in q u e u e 2

4 3

Q (t) g ra p h

2 1 0

B (t) g ra p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u t e s ) I n t e r a r r iv a l t im e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e t im e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 30 de 57

Simulación Manual : t = 4.41, Arrival of Part 5 S y s te m

5

4

C lo c k

3

2

4 .4 1

B ( t)

Q ( t)

1

3

A r r iv a l tim e s o f

E v e n t c a le n d a r

c u s ts . in q u e u e

[2 ,

4 .6 6 ,

D ep]

[6 ,

1 8 .6 9 ,

A rr]

[– ,

2 0 .0 0 ,

End]

( 4 .4 1 , 3 .7 9 , 3 .0 8 )

N um ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le te d w a itin g

w a itin g tim e s in q u e u e

Q ( t)

B ( t)

1 .1 7

3 .1 2

4 .4 1

tim e s in q u e u e 2

4

Q ( t) g r a p h

3 2 1 0

B ( t) g r a p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u te s ) In te r a r r iv a l tim e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e tim e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 31 de 57

Simulación Manual : t = 4.66, Departure of Part 2 S y s te m

5

C lo c k

4

3

4 .6 6

B ( t)

Q ( t)

1

A r r iv a l tim e s o f

E v e n t c a le n d a r

c u s ts . in q u e u e

[3 ,

8 .0 5 ,

Dep]

[6 ,

1 8 .6 9 ,

A rr]

[– ,

2 0 .0 0 ,

End]

2

( 4 .4 1 , 3 .7 9 )

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le te d w a itin g

w a itin g tim e s in q u e u e

Q ( t)

B ( t)

2 .7 5

3 .8 7

4 .6 6

tim e s in q u e u e 3

4

Q ( t) g r a p h

3 2 1 0

B ( t) g r a p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u te s ) In te r a r r iv a l tim e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e tim e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 32 de 57

Simulación Manual : t = 8.05, Departure of Part 3 S y s te m

C lo c k

5

4

8 .0 5

B ( t)

Q ( t)

1

A r r iv a l tim e s o f

E v e n t c a le n d a r

c u s ts . in q u e u e

[4 ,

1 2 .5 7 ,

Dep]

[6 ,

1 8 .6 9 ,

A rr]

[– ,

2 0 .0 0 ,

End]

1

( 4 .4 1 )

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le te d w a itin g

w a itin g tim e s in q u e u e

Q ( t)

B ( t)

7 .0 1

1 0 .6 5

8 .0 5

tim e s in q u e u e 4

4

Q ( t) g r a p h

3 2 1 0

B ( t) g r a p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u te s ) In te r a r r iv a l tim e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e tim e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 33 ode 57

Simulación Manual : t = 12.57, Departure of Part 4 S y s te m

C lo c k

5

1 2 .5 7

B ( t)

Q ( t)

1

A r r iv a l tim e s o f

E v e n t c a le n d a r

c u s ts . in q u e u e

[5 ,

1 7 .0 3 ,

Dep]

[6 ,

1 8 .6 9 ,

A rr]

[– ,

2 0 .0 0 ,

End]

0

()

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le te d w a itin g

w a itin g tim e s in q u e u e

Q ( t)

B ( t)

1 5 .1 7

1 5 .1 7

1 2 .5 7

tim e s in q u e u e 5

4

Q ( t) g r a p h

3 2 1 0

B ( t) g r a p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u te s ) In te r a r r iv a l tim e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e tim e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 34 de 57

Simulación Manual : t = 17.03, Departure of Part 5 S y s te m

C lo c k 1 7 .0 3

B ( t)

Q ( t)

0

0

A r r iv a l tim e s o f

E v e n t c a le n d a r

c u s ts . in q u e u e

[6 ,

1 8 .6 9 ,

A rr]

()

[– ,

2 0 .0 0 ,

End]

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le te d w a itin g

w a itin g tim e s in q u e u e

Q ( t)

B ( t)

1 5 .1 7

1 5 .1 7

1 7 .0 3

tim e s in q u e u e 5

4

Q ( t) g r a p h

3 2 1 0

B ( t) g r a p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u te s ) In te r a r r iv a l tim e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e tim e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 35 de 57

Simulación Manual : t = 18.69, Arrival of Part 6 S y s te m

C lo c k

6

1 8 .6 9

B ( t)

Q ( t)

1

0

A r r iv a l tim e s o f

E v e n t c a le n d a r

c u s ts . in q u e u e

[7 ,

1 9 .3 9 ,

A rr]

()

[– ,

2 0 .0 0 ,

End]

[6 ,

2 3 .0 5 ,

Dep]

Num ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le te d w a itin g

w a itin g tim e s in q u e u e

Q ( t)

B ( t)

1 5 .1 7

1 5 .1 7

1 7 .0 3

tim e s in q u e u e 6

4

Q ( t) g r a p h

3 2 1 0

B ( t) g r a p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u te s ) In te r a r r iv a l tim e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e tim e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 36 de 57

Simulación Manual : t = 19.39, Arrival of Part 7 S y s te m

C lo c k

7

6

1 9 .3 9

B ( t)

Q ( t)

1

A r r iv a l tim e s o f

E v e n t c a le n d a r

c u s ts . in q u e u e

[– ,

2 0 .0 0 ,

End]

[6 ,

2 3 .0 5 ,

D ep]

[8 ,

3 4 .9 1 ,

A rr]

1

( 1 9 .3 9 )

N um ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le te d w a itin g

w a itin g tim e s in q u e u e

Q ( t)

B ( t)

1 5 .1 7

1 5 .1 7

1 7 .7 3

tim e s in q u e u e 6

4

Q ( t) g r a p h

3 2 1 0

B ( t) g r a p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u te s ) In te r a r r iv a l tim e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e tim e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 37 de 57

Simulación Manual : t = 20.00, The End (Término de la Simulación) S y s te m

C lo c k

7

6

2 0 .0 0

B ( t)

Q ( t)

1

A r r iv a l tim e s o f

E v e n t c a le n d a r

c u s ts . in q u e u e

[6 ,

2 3 .0 5 ,

D ep]

[8 ,

3 4 .9 1 ,

A rr]

1

( 1 9 .3 9 )

N um ber of

T o ta l o f

A re a u n d e r

A re a u n d e r

c o m p le te d w a itin g

w a itin g tim e s in q u e u e

Q ( t)

B ( t)

1 5 .1 7

1 5 .7 8

1 8 .3 4

tim e s in q u e u e 6

4

Q ( t) g r a p h

3 2 1 0

B ( t) g r a p h

0

5

10

15

20

0

5

10

15

20

2 1 0

T im e ( M in u te s ) In te r a r r iv a l tim e s

1 .7 3 , 1 .3 5 , 0 .7 1 , 0 .6 2 , 1 4 .2 8 , 0 .7 0 , 1 5 .5 2 , 3 .1 5 , 1 .7 6 , 1 .0 0 , ...

S e r v ic e tim e s

2 .9 0 , 1 .7 6 , 3 .3 9 , 4 .5 2 , 4 .4 6 , 4 .3 6 , 2 .0 7 , 3 .3 6 , 2 .3 7 , 5 .3 8 , ...

Slide 38 de 57

Simulación Manual : Terminando • Average waiting time in queue: Total of times No. of times

•



15 . 17

in queue

 2 . 53 minutes

per part

6

Time-average number in queue: Area under

Q ( t ) curve

Final clock

•

in queue



15 . 78

value

 0 . 79 part

20

Utilization of drill press: Area under Final clock

B ( t ) curve value



18 . 34

 0 . 92 (dimension

less)

20

Slide 39 de 57

Complete Record of the Hand Simulation

Slide 40 de 57

Event-Scheduling Logic via Programación • •

•

Claramente se adecuan a lenguajes de programación estándar (C, C++, Java, etc.) A menudo se utiliza librerías “utility” para:  Listas de procesamiento  Generación de números aleatorios (Random-number generation)  Generación de variables aleatorias (Random-variate generation)  Recolección estadística  Listas de eventos y administración del reloj  Resumen y output Programa principal lo une, ejecuta eventos en orden Slide 41 de 57

Dinámica de la Simulación : Process-Interaction World View • • • •

• • •

Identificar entidades características en el sistema Copias múltiples de entidades co-existen, interactúan, compiten “Codificar” no es procedimental Cuente una historia de lo que le pasa a una entidad “típica” Puede tener muchos tipos de entidades, entidades falsas (fake) para cosas como falla de maquinas Generalmente requiere software de simulación especializado  Por debajo, todavía ejecutado como event-scheduling La vista es manejada por el software (Arena, Simio)  Arena traduce la descripción de su modelo en un programa en lenguaje de simulación SIMAN para su ejecución Slide 42 de 57

Aleatoriedad en la Simulación • •

Anteriormente sólo fue una “replica” — una muestra de tamaño uno (no vale mucho) Ahora 5 réplicas (IID):

Variabilidad substancial a lo largo de las replicas

•

Intervalo de confianza para valores esperados:  

En general, X  t n  1,1   / 2 s / n (Supuesto normal?) Para producción total esperada 3 . 80  ( 2 . 776 )( 1 . 64 / 3 . 80  2 . 04

5)

Precisión? Slide 43 de 57

Comparando Alternativas • •

•

Generalmente, la simulación es usada para la “configuración” de mas de un solo modelo A menudo se quiere comparar alternativas, seleccionar o buscar la mejor (vía algún criterio) Sistema de Procesamiento Simple: ¿Que pasaría si la frecuencia de llegada se duplica?   

Se corta el tiempo entre llegada en la mitad Echar a correr nuevamente el modelo para llegadas de tiempo duplicado Hacer 5 replicas

Slide 44 de 57

Resultados: Original vs. Double-Time Arrivals • Original – círculos • Double-time – triángulos • Replication 1 – Relleno • Replications 2-5 – Vacío • Notar variabilidad • Peligro en tomar decisiones • •

basado en una (primera) réplica Difícil ver diferencias reales Se necesita: Análisis Estadístico de Output data de Simulación (Statistical analysis of simulation output data)

Slide 45 de 57

Simulación con Planillas: Introducción • Herramienta popular, ubicua • Puede usarse para modelos simples de simulación 

Típico, solo modelos estadísticos –



•

Análisis de riesgo, escenarios financieros/inversión

Sólo modelos dinámicos (muy) simples

Dos ejemplos  

Newsvendor problem (estático) Tiempos de espera en single-server queue (cola) (dinámico) –

Repercusión especial válida sólo para este caso

Slide 46 de 57

Simulación con Planillas : Newsvendor Problem – Setup • • • •

• •

Rupert vende periódicos en la calle  Rupert compra por c = $0.55 c/u, vende por r = $1.00 c/u Cada mañana, Rupert compra q copias  q es un número fijo, el mismo cada día Demanda durante un dia: D = max (X, 0)  X ~ normal ( = 135.7, s = 27.1), de data histórica  X redondea a X al entero más cercano Si D  q, satisface toda la demanda, y q – D  0 lo que sobra, vende por desecho a s = $0.03 c/u Si D > q, vende todo (vende todas las q copias), No hay desecho  Pero se le pasó que las ventas D – q > 0 Cuanto debe ser q? Slide 47 de 57

Simulación con Planillas : Newsvendor Problem – Formulación • Elegir q para maximizar la ganancia esperada por día q demasiado pequeño– vende todo, pierde $0.45 de ganancia por periódico  q demasiado grande– tiene sobras, desecho a una pérdida de $0.52 por periódico Problema clásico de Investigación Operacional  Muchas versiones, variantes, extensiones, aplicaciones  Mucha investigación en soluciones exactas en ciertos casos  Pero fácil de simular, incluso en una planilla Ganancia en un día, como función de q: W(q) = r min (D, q) + s max (q – D, 0) – cq 

•

•

Ganancia venta

Ganancia desecho Costo

W(q) es una variable aleatoria– la ganancia varía de un día a otro Maximizar E(W(q)) sobre enteros positivos q 

•

Slide 48 de 57

Simulación con Planillas : Newsvendor Problem – Simulación • Establecer valor de prueba para q, generar demanda D, computar

•

ganancia para ese día  Luego repetir esto por muchos días, independientemente, promediar para estimar E(W(q)) – También obtener intervalo de confianza, estimar P (pérdida), histograma de W(q)  Probar para un rango de valores de q Necesario generar demanda D = max (X, 0)  Se necesita generar X ~ normal ( = 135.7, s = 27.1)  (Mucho) por delante – Sec. 12.2, generating random variates 1  En este caso, generar X = F,s(U) U es un número aleatorio uniformemente distribuido en [0, 1] (Sec. 12.1) F,s es una función de distribución acumulativa de la distribución normal (, s) Slide 49 de 57

Simulación con Planillas : Newsvendor Problem – Excel • File Newsvendor.xls • Parámetros de ingreso en celdas B4 – B8 (azul) • Valores de prueba para q en fila 2 (roza) • Número de día (1, 2, ..., 30) en columna D • Demanda en columna E para cada día: = MAX(ROUND(NORMINV(RAND(), $B$7, $B$8), 0), 0) Función redondeo

RAND() es “volatil” por lo que se regenera con cualquier tecka edit o F9

F

1

U(0, 1) Número aleatorio



s

X ~ normal (, s) Redondear al entero próximo

MAX 2nd argument Slide 50 de 57

Simulación con Planillas : Newsvendor Problem – Excel (cont’d.) • Para cada q:   

•



columna“Sold” : numero de periódicos vendidos ese día column“Scrap” : numero de periódicos desechados ese día column“Profit” : ganancia (+, –, 0) de ese día Ubicación de“$” en formulas para facilitar la copia

Al final de las columnas “Profit” columns (verde):  

Promedi de ganancia sobre 30 días Half-width de 95% intervalo de confianza E(W(q)) –

–



•

Valor 2.045 es superior a 0.975 punto critico de distribución t con 29 d.f. Plotear intervalo de confianza como “I-beams” en borde izquierdo

Estimación de P(W(q) < 0) –

Use función COUNTIF

Histogramas de W(q) al final 

Línea roja vertical en 0, separata ganancias, pérdidas Slide 51 de 57

Simulación con Planillas : Newsvendor Problem – Resultados • Afinando– Se uso la misma demanda diaria (columna E) para cada

•

día, por sobre todos los valores de prueba de q  Habría sido válido para generarlos independientemente  Porqué es mejor usar la misma demanda para todos los q? Resultados  El mejor q es cerca de140, quizás un poco menos  Aleatoriedad (Randomness) en todos los resultados (F9) – Todas las demandas, ganancias, cambios gráficos – Cambio en intervalo de confianza y ploteos de histogramas – Recuerde que estos son outputs aleatorios, ploteos aleatorios  Mayor q  más variabilidad en la demanda – Histogramas al final son mas anchos para mayores q – Mayor probabilidad de grandes ganancias, y mayor probabilidad de pérdidas a su vez – Razón riesgo/retorno puede ser cuantificado– risk taker vs. riskaverse Slide 52 de 57

Simulación con Planillas : Single-Server Queue – Setup • Como la Simulación Manual, pero: Tiempo entre llegadas (Interarrival times) ~ exponencial con media 1/l = 1.6 min.  Service times ~ uniform en [a, b] = [0.27, 2.29] min.  Parar cuando 50th waiting time en la cola sea observado – Ej., cuando el cliente 50th comience su servicio, no sale del sistema Observar waiting times en cola (in queue) WQ1, WQ2, ..., WQ50  Importante – No mirar nada más, a diferencia de antes Si = service time de cliente i, Ai = interarrival time entre clientes. i – 1 e i Lindley’s recursion (1952): Initializar WQ1 = 0, WQi = max (WQi – 1 + Si – 1 – Ai, 0), i = 2, 3, ... 

• •

•

Slide 53 de 57

Simulación con Planillas : Single-Server Queue – Simulación • Necesidad de generar variables aleatorias (random variates): Sea U ~ U[0, 1] 

• • • •



Exponencial (media 1/l): Uniform on [a, b]:

Ai = –(1/l) ln(1 – U) Si = a + (b – a) U

File MU1.xls Input parameters en celdas B4 – B6 (azul) 

Algunos outputs teóricos en celdas B8 – B10

Número de cliente (i = 1, 2, ..., 50) en columna D 5 IID replicas (3 columnas para cada una)  

IA = interarrival times, S = service times WQ = waiting times in queue (ploteo, curvas delgadas) –

1ro. Inicializado en 0, remanentes usan Lindley’s recursion Curvas se elevan desde 0, variación aumenta hacia la derecha

–

Creata autocorrelació´n positiva en columnas WQ Curvas tienen menos cambios abruptos que si los WQi’s fueran independientes Slide 54 de 57

Simulación con Planillas : Single-Server Queue – Resultados • Promedio de columnas (verde) Promedio interarrival, service times cercano a expectativas  Promedio WQi dentro de cada réplica – No muy lejos de expectativa steady-state – Variación considerable – Muchas están bajo ella (Porqué?) Promedio Cross-replication (Del cliente) (verde)  Columna T, línea gruesa en el ploteo para bajar el ruido Porqué no muestra de la varianza, histogramas de WQi’s?  Podría haber computado a los dos, como en newsvendor; dos temas: – Nonstationarity – Cual es el “típico” WQi aquí? – Autocorrelación – estimación de la desviación de la varianza , puede desviar histograma si replica no es suficientemente larga 

• •

Slide 55 de 57

Simulating with Spreadsheets: Recap • Popular for static models 

•

Add-ins – @RISK, Crystal Ball

Inadequate tool for dynamic simulations if there’s any complexity  

Extremely easy to simulate single-server queue in Arena – Chapter 3 main example Can build very complex dynamic models with Arena – most of rest of book

Slide 56 de 57

Vistazo a un Proyecto de Simulación • • • • • • • • •

Entender el Sistema Estar claro sobre los objetivos Formular la representación del modelo Traducir a software de modelación Verificar el “programa” Validar el modelo Diseñar experimentos Hacer replicas (corridas) Analizar, sacar conclusiones, documentar resultados Slide 57 de 57