Métodos de Simulación de Sucesos Discretos PDF

Máster Universitario en Inteligencia Artificial MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos ÍNDICE 1. Conceptos básicos de la SSD...

Máster Universitario en Inteligencia Artificial MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos ÍNDICE 1. Conceptos básicos de la SSD 2. SSD de sistemas de espera complejos - Modelo G/G/1 - Red de colas 3. SSD de un modelo de inventario probabilístico 4. Software de SSD 5. Referencias MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Existen distintos tipos de modelos de simulación: Los modelos continuos tratan con sistemas cuyo comportamiento cambia continuamente de forma con el tiempo (por ejemplo, el estudio de la dinámica de la población mundial). Normalmente se representan en la forma de ecuaciones diferenciales o en diferencias que describen las interacciones entre los diferentes elementos del sistema. Los modelos discretos tratan con sistemas cuyo comportamiento sólo cambia en instantes considerados. Un ejemplo típico ocurre en las líneas de espera, donde estamos interesados en la estimación de medidas como el tiempo de espera promedio o la longitud de la cola, las cuales sólo cambian cuando un cliente entra o sale del sistema. En todos los demás momentos no ocurre nada en el sistema desde el punto de vista de la inferencia estadística. Los momentos en los que ocurren los cambios en el sistema identifican los eventos o sucesos del modelo. El hecho de que estos sucesos ocurren en instantes discretos da lugar al nombre de simulación de sucesos discretos. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Por lo tanto, estudiaremos sistemas que evolucionan en el tiempo en forma discreta à el estado del sistema cambia sólo en ciertos instantes del tiempo, no de forma continua. Para su estudio construimos un modelo o representación simplificada del sistema real. En SSD podemos diferenciar tres tipos de variables: La variable tiempo t, que indica el tiempo transcurrido de la simulación. Las variables contadores, que llevan la cuenta del número de veces que se ha producido un evento. Las variables de estado, subconjunto mínimo de variables que describe el sistema en un instante particular del tiempo, y que permite predecir su comportamiento futuro. Los valores de las variables de estado en un instante t proporcionan el estado del sistema en ese instante. En general, el estado del sistema podría cambiar como resultado de actividades internas o endógenas, o bien actividades externas o exógenas. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos En SSD el estado del sistema cambiará cuando se produce un evento o suceso. Los sucesos que definen la evolución se generan en distintos instantes de tiempo y el paso del tiempo se controla mediante un mecanismo de reloj o reloj de la simula- ción. Básicamente, hay dos tipos de mecanismo de reloj: En la simulación síncrona u orientada a intervalos el incremento del reloj se fija en una cantidad t, al término de la cual se actualizan las estadísticas y se cambia el estado del sistema. El proceso se repite hasta que se cumpla una condición de finalización, momento en el cual se imprimen los resultados y se concluye la simulación. Este tipo de control del mecanismo del reloj de simulación tiene como inconve- niente la selección del incremento de tiempo t: Demasiado grande à podría producirse más de un suceso durante ese intervalo perdemos info de cuando se produce el y el orden en que se ha producido no se habría registrado evento y el orden de (se asume que han tenido lugar al final del mismo). estos sucesos MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Demasiado pequeño à puede que en la mayoría de intervalos de tiempo no ocu- rra ningún suceso, lo que llevará asociado una ineficien- cia computacional. la que mejor se ajusta En la simulación asíncrona u orientada a sucesos el reloj de simulación avanza hasta el instante en el que ocurre un nuevo suceso, se actualiza el estado del sis- tema y se recogen estadísticas. El proceso se repite hasta que su cumpla una con- asi no perdemos el dición de finalización, momento en el que se imprimen los resultados. instante ni el orden de los sucesos Debido a los inconvenientes de la simulación síncrona y a pesar de su sencilla implementación, en la SSD utilizaremos la segunda alternativa para el control del mecanismo del reloj de simulación, la simulación asíncrona. Nota: la simulación síncrona, sin embargo, es una estrategia valiosa para sistemas en tiempo continuo que se estudian, por ejemplo, en Neelamkavil (1987). MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Simulación síncrona Simulación asíncrona MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Al depender la evolución de la simulación del sistema de los instantes en los que suceden los eventos, debemos mantener una lista de éstos y de los instantes en que tendrán lugar, de forma que el mecanismo de reloj avanzará al instante en el que se produzca el primero de los eventos de la lista. Dado un tipo de evento determinado, el tiempo que transcurre entre ocurrencias consecutivas de dicho evento puede ser determinístico o aleatorio, en cuyo caso se deberán generar valores a partir de la distribución de probabilidad que describe dicho comportamiento aleatorio. libros de referencia Banks et al. (2000) especialmente orientado a lectores con poca base en cálculo, probabilidad y estadística, cubriendo de forma básica la SSD. Banks (1998) orientado a lectores interesados en los aspectos más prácticos y no- vedosos de la SSD. Referencias a los investigadores más destaca- dos y su aplicación en campos tan diversos como son el transporte, la sanidad o las aplicaciones militares. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos ÍNDICE 1. Conceptos básicos de la SSD 2. SSD de sistemas de espera complejos - Modelo G/G/1 - Red de colas 3. SSD de un modelo de inventario probabilístico 4. Software de SSD 5. Referencias MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos 3. SSD de sistemas de espera complejos Una de las posibles aplicaciones de la SSD son los sistemas de espera (colas) complejos, en los cuales: es difícil encontrar procedimientos analíticos para modelizar su comportamiento porque se violen las hipótesis de estacionariedad, independencia o ergodicidad. se trata de una red de colas muy grande con disciplinas caprichosas, tiempos de llegada o de servicio arbitrarios, capacidad limitada de ciertos nodos y otros con comportamiento no estable... Son muchos los libros sobre simulación en los que se incluyen ejemplos de simulación de sistemas de espera complejos, como: Ross (1997), que además del modelo G/G/1 incluye sistemas con dos servidores en serie y en paralelo. Karian y Dudewicz (1999), en el que se analizan los sistemas con disciplinas de colas con prioridades. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos 2.1. MODELO G/G/1 Sea un sistema de espera formado por un único servidor. Supongamos que los tiempos entre llegadas de clientes al sistema se modelizan mediante la variable aleatoria F. Si al llegar los clientes el sistema está vacío entonces pasan directamente a ser servidos, mientras que si ya hay algún cliente recibiendo servicio pasan a formar parte de la cola, en la que esperarán a que les llegue su turno. Los tiempos de servicio de los clientes siguen una distribución G, siendo independientes entre sí e independientes de las llegadas de clientes. La cola se supone de capacidad infinita (no se rechazan clientes) y disciplina FIFO (First In First Out), es decir, el cliente que llegó primero al sistema será servido en primer lugar. T: condicion de parada --> a partir de instante T ya no se permiten entradas al sistema. La simulacion finaliza cuando a partir de T ya no tenga clientes El sistema permite la entrada de clientes en el mismo hasta el instante T, momento en el cual no se permiten más entradas pero sí se sigue dando servicio a los clientes que están en el sistema hasta que todos ellos lo abandonan. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Para realizar la SSD en el sistema propuesto definimos las siguientes variables: - t ≡ tiempo transcurrido de simulación - n ≡ nº de clientes en el sistema en el instante t (var. de estado). - NLL, NS ≡ nº de llegadas y de salidas hasta el instante t (variables contador). - LISTA{tLL, tS} ≡ registro con dos elementos en los que guardamos los tiempos en guardar los instantes en los cuales se que sucederán los dos tipos de eventos. espera que sucedan los eventos - LL(i) ≡ instante en el que llega el cliente i-ésimo al sistema. - S(i) ≡ instante en el que sale del sistema el cliente i-ésimo. - Serv(i) ≡ tiempo de servicio recibido por el cliente i-ésimo. Estas tres últimas variables las utilizaremos para contabilizar los tiempos medios solicitados (en el sistema y en la cola). - T ≡ horizonte de la simulación. no entran mas clientes al sistema - Tp ≡ tiempo transcurrido desde T hasta que el último cliente abandona el sistema. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos int simul_main (float T, float ∗Tp, float ∗t_med_sistema, float ∗t_med_cola) { float t = tsuc = 0.0; float LISTA.tLL = LISTA.tS = -1; Ponemos el -1 para indicar que inicialmente no está previsto un servicio int NLL = NS = n = 0; -1 = no hay evento pendiente de ser tratado float LL(i) = S(i) = Serv(i) = 0.0 para todo i float X = GenerarDistribucionF(); tiempo que transcurre hasta que llega el 1º cliente if (X > T) { Tp = t_med_sistema = t_med_cola = 0.0; return -1; } else { rutina_llegada(X); while ((LISTA.tLL ≠ -1) | |(LISTA.tS ≠ -1)) { if (LISTA.tLL < LISTA.tS) { tsuc = LISTA.tLL; LISTA.tLL = -1; rutina_llegada(tsuc); } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos if (LISTA.tS < LISTA.tLL) { tsuc = LISTA.tS; LISTA.tS = -1; rutina_servidor(tsuc); } } //tiempo desde T hasta que el último cliente abandona el sistema Tp = max (0.0, t-T); //tiempos medios en la cola y en el sistema float acumulo1 = acumulo2 = 0.0; for (int ind = 0; ind < NLL; ind++){ acumulo1 += S(ind) - LL(ind); tiempo que ha pasado en sistema acumulo2 += S(ind) - LL(ind) - Serv(ind); tiempo que ha pasado en cola } t_med_sistema = acumulo1 / NLL; t_med_cola = acumulo2 / NLL; } return 0; } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos void rutina_llegada (int tsuc) { void rutina_servidor (int tsuc) { instante en el que se produce el evento t = tsuc; t = tsuc; n++; incremento nº clientes n--; NLL++; incremento llegadas NS++; LL(NLL) = t; registro momento de llegada S(NS) = t; float X = GenerarDistribucionF(); generar el tiempo que tarda en llegar el siguiente cliente if (n > 0) { sigenero todavia hay clientes en el sistema--> nuevo tiempo de servicio if (t + X < T) LISTA.tLL = t + X; float Y = GenerarDistribucionG(); solo lo genero si en la LISTA.tS = t + Y; cola hay clientes para el primer cliente if (n == 1) { Serv(NS ) = Y; float Y = GenerarDistribucionG(); } LISTA.tS = t + Y; } Serv(NS + 1) = Y; cada vez que el sistema quede vacio no se genera tiempo de } servicio nuevo } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos ÍNDICE 1. Conceptos básicos de la SSD 2. SSD de sistemas de espera complejos - Modelo G/G/1 - Red de colas 3. SSD de un modelo de inventario probabilístico 4. Software de SSD 5. Referencias MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos 2.2. RED DE COLAS Consideremos el siguiente sistema formado por tres nodos: hay solo 4 eventos: 1º. llegada del cliente al nodo 1 2º. Finalizacion servicio nodo 1 --> entrada al nodo 2 o nodo 3 3º. Finalizacion servicio nodo 2 --> entrada nodo 3 4º. Finalizacion servicio nodo 3 Se permite la entrada de clientes hasta el instante T, a partir del cual únicamente se sigue dando servicio a los clientes que están en el sistema hasta que todos ellos lo abandonan. Determinar el tiempo medio que pasan los clientes en el sistema, el número medio de clientes en cada nodo y el porcentaje de clientes que pasan por el nodo 2. Obtendremos también el tiempo transcurrido desde el instante T hasta que el último cliente abandona el sistema. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Para realizar la SSD en el sistema propuesto definimos las siguientes variables: - t ≡ tiempo transcurrido de simulación - n1, n2, n3 ≡ nº de clientes en el nodo 1, 2 y 3 (var. de estado). - NLL1, NLL2, NLL3 ≡ nº de llegadas al primer, segundo y tercer nodo hasta el instan- te t (variables contador). - NS1, NS2, NS3 ≡ nº de salidas del primer, segundo y tercer nodo hasta el instante t (variables contador). - LISTA{tLL1, tS1, tS2, tS3} ≡ registro con cuatro elementos en los que guardamos los tiempos en que sucederán los cuatro tipos de eventos. - LLj(i), Sj(i) ≡ instante en el que llega/sale el cliente i-ésimo al/del servidor j-ési- mo, j=1,2,3, respectivamente. Estas seis últimas variables las utilizaremos para contabilizar el tiempo medio que pasan los clientes en el sistema o en los nodos. - T ≡ horizonte de la simulación. - n_med_nj ≡ número medio de clientes en el servidor j-ésimo, j=1,2,3. - Tp ≡ tiempo transcurrido desde T hasta que el último cliente abandona el sistema. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos tasa de proceso de llegada int simul_main (float T, float λ, float μ1, float σ1, float μ2, float μ31, float σ31, float μ32, float σ32, float ∗t_med_sistema, float ∗%_clientes_n2, float ∗Tp, float ∗n_med_n1, float ∗n_med_n2, float ∗n_med_n3){ float t = tsuc = Tp = 0.0; float LISTA.tLL1 = LISTA.tS1 = LISTA.tS2 = LISTA.tS3 = -1; en principio no hay ningun evento pendiente int NLL1 = NLL2 = NLL3 = NS1 = NS2 = NS3 = 0; int n1 = n2 = n3 = 0; float LL1(i) = LL2(i) = LL3(i) = 0.0 para todo i float S1(i) = S2(i) = S3(i) = 0.0 para todo i float n_med_n1 = n_med_n2 = n_med_n3 = 0.0; float X = GenerarExponencial(λ); por el proceso de poisson tpos entre llegadas consecutivas son exponenciales if (X > T) { Tp = t_medio_sistema = %_clientes_n2 = 0.0; n_med_n1 = n_med_n2 = n_med_n3 = 0; return -1; } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos else { rutina_llegada_cliente(X); while ((LISTA.tLL1≠ -1) || (LISTA.tS1 ≠ -1) || (LISTA.tS2 ≠ -1 ) ||(LISTA.tS3 ≠ -1)) { if (min(LISTA) == LISTA.tLL1) { tsuc = LISTA.tLL1; LISTA.tLL1 = -1; rutina_llegada_cliente(tsuc); } if (min(LISTA) == LISTA.tS1) { tsuc = LISTA.tS1; LISTA.tS1 = -1; rutina_servicio_nodo1(tsuc); } if (min(LISTA) == LISTA.tS2) { tsuc = LISTA.tS2; LISTA.tS2 = -1; rutina_servicio_nodo2(tsuc); } if (min(LISTA) == LISTA.tS3) { tsuc = LISTA.tS3; LISTA.tS3 = -1; rutina_servicio_nodo3(tsuc); } } // fin del while } //fin del else MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos //tiempo desde T hasta que el último cliente abandona el sistema Tp = max(0.0, t - T); //porcentaje de clientes que pasa por el segundo nodo %_clientes_n2 = NLL2 / NLL1; //tiempo medio que pasan los clientes en el sistema float acumulo1, acumulo2, acumulo3 = 0.0; for (int ind = 0; ind < NLL1; ind++) acumulo1 += S1(ind) - LL1(ind); for (ind = 0; ind < NLL2; ind++) acumulo2 += S2(ind) - LL2(ind); for (ind = 0; ind < NLL3; ind++) acumulo3 += S3(ind) - LL3(ind); t_med_sistema = (acumulo1 / NLL1) + (%_clientes_nodo2 × acumulo2 / NLL2) + (acumulo3 / NLL3); tiempo del nodo x la probabilidad de pasar por ese nodo (%clientes) --> no todos los clientes pasan por el nodo 2 //número medio de clientes en cada nodo n_med_n1 = n_med_n1 / t; n_med_n2 = n_med_n2 / t; n_med_n3 = n_med_n3 / t; return 0; } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos void rutina_llegada_cliente (int tsuc) { n_med_n1 += n1 × (tsuc - t); n_med_n2 += n2 × (tsuc - t); n_med_n3 + =n3 × (tsuc - t); n1++; NLL1++; LL1(NLL1) = tsuc; t = tsuc; float Y = GenerarExponencial(λ); if (t + Y < T) LISTA.tLL1 = t + Y; if (n1 ==1 ) { Y = GenerarNormal(μ1, σ1); tiempo de servicio para el cliente que llega y el sistema esta vacio LISTA.tS1 = t + Y; } } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos void rutina_servicio_nodo1 (int tsuc) { else { //el cliente va al tercer nodo n_med_n1 + =n1 × (tsuc - t); n3++; NLL3++; n_med_n2 += n2 × (tsuc - t); LL3(NLL3) = t; n_med_n3 + =n3 × (tsuc - t); if (n3 == 1) { t = tsuc; float W = GenerarNormal(μ31, σ31); n1--; NS1++; LISTA.tS3 = t + W; S1(NS1) = tsuc; } } if (n2 < 9) { //el cliente va al segundo nodo n2++; NLL2++; if (n1 > 0) { LL2(NLL2) = t; float S = GenerarNormal(μ1, σ1); if (n2 == 1) { LISTA.tS1 = t + S; float Z = GenerarExponencial(μ2); } LISTA.tS2 = t + Z; } } } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos void rutina_servicio_nodo2 (int tsuc) { void rutina_servicio_nodo3 (int tsuc) { n_med_n1 + =n1 × (tsuc - t); n_med_n2 += n2 × (tsuc - t); float R; n_med_n3 + =n3 × (tsuc - t); n_med_n1 + =n1 × (tsuc - t); t = tsuc; n_med_n2 += n2 × (tsuc - t); n2--; NS2++; n_med_n3 + =n3 × (tsuc - t); S2(NS2) = t; t = tsuc ; if (n2 > 0) { n3--; NS3++; float Y = GenerarExponencial(μ2); S3(NS3) = t; LISTA.tS2 = t + Y; } if (n3 > 0) { //trato la entrada del cliente en el tercer nodo if (n3 < 5) R = GenerarNormal(μ31, σ31); n3++; NLL3++; else R = GenerarNormal(μ32, σ32); LL3(NLL3) = t; LISTA.tS3 = t + R; if (n3 == 1) { } float W = GenerarNormal(μ31, σ31); } LISTA.tS3 = t + W; } } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos ÍNDICE 1. Conceptos básicos de la SSD 2. SSD de sistemas de espera complejos - Modelo G/G/1 - Red de colas 3. SSD de un modelo de inventario probabilístico 4. Software de SSD 5. Referencias MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Proceso de Proveedor llegadas Realización Clientes de pedido Coste de preparación (K) Almacén Demanda de productos Coste por unidad Distribución discreta Descuento por cantidad Precio de venta (r) P Coste de almacenamiento (h) Llegada del pedido Tiempo líder (L) p es de caracter probabilistico cuando baje de la p --> (no es un tiempo exacto al hago un pedido: tantas 100%) unidades como necesite para alcanzar el nivel P (para política aperiódica) Política de pedidos clave: necesito saber valor de p y P ej: todos los viernes hago un pedido (mayor o menor Política periódica cantidad) Política aperiódica pido en funcion del inventario (no hay fecha determinada del pedido) MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos nota: la mayoria de llegadas reales siguen proceso de poisson no homogeneos Consideremos un almacén de un determinado producto cuyo precio de venta al público es de 2 euros la unidad (r). La llegada de clientes al almacén se distribuye según un proceso de Poisson de parámetro λ = 0.5 clientes por hora y la cantidad de productos demandados por cada uno de ellos tiene la siguiente distribución: Para satisfacer la demanda de sus clientes el dueño del almacén mantiene un stock de productos, de forma que cuando el nivel del inventario es bajo solicita al distribuidor más unidades. La política de pedidos al distribuidor es por lo tanto aperiódica, es decir, cuando el nivel del inventario es menor que una determinada cantidad (p=30) y no hay actualmente ningún pedido pendiente (esperando a que nos llegue), se solicitan unidades del producto para que el nivel del inventario llegue a P=100 unidades. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Asociado a cada pedido que realizamos al proveedor existe un coste fijo K (coste de preparación) de 10 euros, independientemente de las unidades demandadas. Adicionalmente, el coste por unidad incluida en el pedido depende de la cantidad solicitada, habiendo descuentos por cantidad, es decir, si el número de unidades demandadas es menor que 50 (n_descuent) el precio es de 1 euro la unidad (p1), mientras que si se piden más de 50 el precio desciende a 75 céntimos (p2). El tiempo que tarda en ser servido el pedido por los proveedores (tiempo líder), sigue una distribución normal de media μ=48 horas y desviación típica σ=0.8, pagándose en ese momento. Se ha llegado a un acuerdo con el proveedor de forma que, tomando como referencia las 48 horas que tarda en media un pedido en ser servido, si hay un retraso superior a las 3 horas (lim_penal) en la entrega del mismo se realizará un descuento del 0.01% del valor del pedido (%_penal), encareciéndose en la misma cantidad en el caso de que el pedido llegue de al menos esas 3 horas (lim_penal). MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos El dueño del almacén debe pagar h=0.0001 euros por unidad del producto y unidad de tiempo, asociado al almacenamiento físico de los productos (alquiler del local, refrigeración,...). En el caso de que al llegar un cliente éste solicite una cantidad mayor que la que hay en inventario, se le sirve lo que queda, perdiendo la venta restante. A.Simular el comportamiento de almacén durante un periodo de tiempo de T=5 meses para estimar el beneficio esperado, la proporción de clientes cuya demanda se satisface completamente y el porcentaje de tiempo que el nivel del inventario permanece a cero. Para ello, supondremos que el nivel del inventario inicial es de P0=70 unidades del producto. A.Representar gráficamente la evolución del nivel del inventario durante los 5 meses. B.Mediante replicaciones de simulación identificar qué cambios se podrían realizar para mejorar el comportamiento del modelo de inventario (mayor beneficio y mayor porcentaje de clientes servidos satisfactoriamente). MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Nota. El almacén permanece abierto 24 horas al día de lunes a domingo. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Consideramos las siguientes variables: - x ≡ número de unidades del producto en el inventario (variable de estado). - y ≡ nº de unidades incluidas en un pedido que está pendiente de llegar. Si es cero, entonces no hay ningún pedido pendiente (variable de estado). - t ≡ tiempo transcurrido de simulación. - LISTA{tC, tP} ≡ registro con dos elementos en los que guardamos los tiempos en que sucederán los dos tipos de eventos. Las variables contador, que usaremos para tomar estadísticas y responder a la preguntas sobre el comportamiento del sistema, son: - C ≡ coste total por pedidos hasta el instante t. - H ≡ coste total por almacenamiento hasta el instante t. - R ≡ beneficios por ventas a clientes hasta el instante t. - NC+ ≡ número de clientes servidos satisfactoriamente. - NC- ≡ número de clientes a los que no hemos podido satisfacer completamente su demanda. - t0 ≡ tiempo en el que el nivel del inventario está a cero. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos simul_main (70, 30, 100, 5×30×8 horas, 0.5, (1,2,3,4), (0.3,0.4,0.2,0.1), 2 euros, 0.0001, 48, 0.8, 10 euros, 30, 1 euro, 0.75 euros, 0.001%, 48 horas, 3 horas, ∗benef, *%_cl_satisf, ∗%_x_0) int simul_main (int P0, int p, int P, float T, float λ, int *dem, float *prob, float r, float h, float μ, float σ, float K, int n_descuent, float p1, float p2, float %_penal, float Lref, float lim_penal, float ∗benef, float ∗%_cl_satisfechos, float ∗%_x_0) { int x = P0; int y = NC+ = NC- = 0; float C = R = H = 0.0; float LISTA.tC = LISTA.tP = -1; float t = tsuc = t0 = 0.0; benef = %_cl_satisf= %_x_0= 0.0; float var_auxiliar = 0.0; (instante en que x se pone a 0) float Laux=0.0; (último L generado) float Z = GenerarExponencial(λ); if (Z > T) return -1; MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos else { rutina_llegada_cliente(Z); while ((LISTA.tP ≠ -1) | |(LISTA.tC ≠ -1)) { if (LISTA.tC < LISTA.tP) { tsuc = LISTA.tC; LISTA.tC = -1; rutina_llegada_cliente(tsuc); } if (LISTA.tP < LISTA.tC) { tsuc = LISTA.tP; LISTA.tP = -1; rutina_llegada_pedido(tsuc); } } //fin del else } //fin del while benef = R – C – H ; %_cl_satisf = NC+ / (NC+ + NC-); %_x_0 = t0 / t; return 0; } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos void rutina_llegada_cliente (int tsuc) { H += (tsuc - t) × h × x; t = tsuc; float demanda = GenerarDiscreta (dem, prob); if (demanda ≤ x) { R += demanda × r;r: preciox producto -= demanda; NC+++; if (x==0) var_auxiliar = t; instante en el que el inventario se queda a 0 --> se guarda en var_auxiliar } else { le doy lo que me queda R += x × r; x = 0; NC-++; if (var_auxiliar == 0) var_auxiliar = t; } if ((x ≤ p) && (y == 0)) { realizo pedido y = P - x; tiempo en el que llegará mi pedido Lauxgenero =L =tiempo GenerarNormal(μ,σ); lider LISTA.tP = t + L; } float Y = GenerarExponencial(λ); if (t + Y < T) LISTA.tC = t + Y; tiempo que tarda en llegar el siguiente cliente } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos void rutina_llegada_pedido (int tsuc) { H += (tsuc - t) × h × x; t = tsuc; float Cinit= 0 %Calcular coste pedido if (y < num_descuent) Cinit= K + y × p1 no aplico descuento (+50 unidades se hace descuento) else Cinit= K + y × p2 aplico descuento if (Laux – Lref ≥ lim_penal ) Cinit= Cinit × (1+ %_penal) prima si se adelanta o atrasa if (Lref −Laux ≥ lim_penal ) Cinit= Cinit × (1- %_penal) el pedido (lo de las 3 horas) C += Cinit; archivo el coste del pedido x += y; incremento unidades de inventario y = 0; ya no hay pedidos pendientes if (var_auxiliar > 0) { t0 += (t – var_auxiliar); var_auxiliar = 0; que este a 0 indica que el nivel de inventario ya no está a 0 } } MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Resultados de la simulación modelo de inventario el descenso es escalonado, si hacemos zoom se verian los "escalones" MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos llega un momento que aumentar p disminuye las ganancias Variación de los indicadores en función de p manteniendo P=100 jugar con p --> nivel de inventario que si lo paso por debajo realizo pedido valor de p Resultado de la simulación para p=50 y P=100 MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Variación de los indicadores en función de P manteniendo p=30 Resultado de la simulación para p=30 y P=317 MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos combinación de todos los valores (p y P)--> 12 horas aprox. Pentium Core 5 4 GB RAM Metaheurísticas? Ratio de clientes satisfechos en función de P (eje vertical) y de p (eje horizontal) MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Ratio de clientes satisfechos en el entorno del óptimo alcanzado MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Beneficio esperado en el entorno del óptimo alcanzado MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos soluciones eficientes para los dos objetivos del problema: beneficio y satisfacer clientes MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos ÍNDICE 1. Conceptos básicos de la SSD 2. SSD de sistemas de espera complejos - Modelo G/G/1 - Red de colas 3. SSD de un modelo de inventario probabilístico 4. Software de SSD 5. Referencias MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos 4. Software de SSD La implementación de modelos complejos con varios tipos de sucesos y procesos y numerosas interacciones puede resultar complicada à se han desarrollado numerosos productos de software específicos de la simulación. En cierto sentido son comparables a lenguajes generales como C, Pascal..., pero cuentan además con capacidades o herramientas específicas que facilitan el proceso de modelización. Esencialmente, tales capacidades evitan al analista crear herramientas y procedimientos que aparecen en casi todas las aplicaciones de simulación. Entre estas herramientas específicas suelen estar: Un marco general para la creación y descripción de un modelo en términos de procesos, sucesos, entidades, atributos, recursos e interacciones entre componentes del modelo. La inclusión de un mecanismo de reloj de simulación. La inclusión de métodos para secuenciar la ocurrencia de sucesos. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Generadores de números aleatorios y de las principales variables aleatorias. Herramientas para la recolección y el análisis de estadísticas relativas al uso de recursos y otras entidades. Herramientas para la descripción gráfica del modelo y de la simulación. Herramientas para la validación y la verificación del modelo. Los lenguajes de simulación presentan como inconvenientes que suelen ser caros, no están disponibles para todos los sistemas operativos y requieren mayor tiempo de ejecución que los lenguajes generales. Los lenguajes de simulación discreta disponibles entran en dos amplias categorías: Programación de eventos. El usuario detalla las acciones asociadas con la ocurrencia de cada evento. La contribución principal del lenguaje es automatizar el proceso de muestreo a partir de las distribuciones, el almacenamiento cronológico y recuperación de eventos, así como la recopilación de estadísticas del modelo. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos GASP (Pritsker, 1974; Rimvall y Cellier, 1982), SLAM (Pritsker y O'Reilly, 1999), SIMAN (Pegden et al. 1995) y SIMSCRIPT (Fayek, 1988). Orientados a procesos. Usan bloques o nodos que se pueden unir para formar una red que describa los movimientos, transacciones o entidades en el sistema. Se conducen internamente por las mismas acciones que se usan en los lenguajes de programación de eventos. La diferencia es que esas acciones están automatizadas para liberar al usuario de los tediosos detalles de cálculo. Están basados en el concepto de entrada-salida del enfoque de "caja negra”, proporcionando de esta forma una mayor simplicidad y facilidad de uso a costa de una menor flexibilidad. GPSS (Solomon, 1983; Karian y Dudewicz; 1999) fue el primero que se creó (en 1960 por IBM), está específicamente diseñado para la simulación de sistemas de espera, y requiere que el usuario domine el "trabajo interno” de aproximadamente 80 bloques diferentes. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Otros lenguajes que implementan esta estrategia son: SIMULA (Pooley, 1987; Holmevik, 1994) (http://www.engin.umd.umich.edu/CIS/course.des/cis400/simula/simula.html) SIMNET II (Taha, 1991) (http://web.ineg.uark.edu/simnet2/simnet.htm). Otros lenguajes, como SIMSCRIPT II.5 (Rusell, 1999) (http://www.simscript.com) o MODSIM (Belanger, 1993) (http://www.caci.com), permiten modelizar con am- bas estrategias. Los simuladores son paquetes de software de sencillo manejo que permiten desarrollar modelos para situaciones específicas. Obviamente su uso es más fácil y permiten un desarrollo rápido de modelos, pero su escasa generalidad limita su interés como herramientas generales. En la revista OR/MS Today se realiza bienalmente un estudio del software en el mercado para SSD (Swain, 2013). MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos También se han desarrollado simuladores de propósito general. Dos muy conocidos y utilizados, que permiten componentes discretos y continuos simultáneamente, son Extend Suite (Image, 2006) (http://www.imaginethatinc.com/prods_suite. html), que permite una descripción gráfica del modelo para facilitar la implementación mediante la importación de bloques de librerías, conectados para indicar el flujo de entidades a través del sistema y detallados mediante el uso cajas de diálogo; y Arena (Kelton et al., 2004) (http://www.arenasimulation.com/). Dias, L.M.S., Vieira, A.C.V., Pereira, G.A.B, Oliveira, J.A. (2016). Discrete simulation software ranking – A top list of the worldwide most popular and used tools, Proceedings of the 2016 Winter Simulation Conference, pp. 1060-1071. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos ÍNDICE 1. Conceptos básicos de la SSD 2. SSD de sistemas de espera complejos - Modelo G/G/1 - Red de colas 3. SSD de un modelo de inventario probabilístico 4. Software de SSD 5. Referencias MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos 5. Referencias Banks, J. (1998). Handbook of Simulation: Principles, Methodology, Application and Practice, Willey. Banks, J., Nelson, B. y Carson, J. (2000). Discrete-Event System Simulation, Prentice Hall. Belanger, R. (1993). MODSIM II: The High-Level Object-Oriented Language, CACI Products Company. Bryant, R.E. (1977) Simulation of Packet Communications Architecture Computer Systems, MIT- LCS-TR-188, Massachusetts Institute of Technology. Chandy, K.M. y Misra, J (1979) Distributed Simulation: a Case Study in Design and Verification of Distributed Programs, IEEE Trans. Software Engineering 5 (5), 440-452. (disponible en Aula Virtual) Dias, L.M.S., Vieira, A.C.V., Pereira, G.A.B, Oliveira, J.A. (2016). Discrete simulation software ranking – A top list of the worldwide most popular and used tools, Proceedings of the 2016 Winter Simulation Conference, pp. 1060-1071. (disponible en Aula Virtual) Fayek, A.M. (1988). Introduction to Combined Discrete-Continuous Simulation Using PC SIMSCRIPT II.5, CACI Products Company. Fujimoto, R.M. (1990). Parallel Discrete Event Simulation, Communications of the ACM 33 (10), 30- 53. (disponible en Aula Virtual) MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Holmevik (1994). Compiling SIMULA: A Historical Study of Technological Genesis, Annals of the History of Computing 16 (4), 25-37. (disponible en Aula Virtual) Imagine That, Inc. (2006) Extend User’s Manual, versión 7. Jefferson, D.R. (1985) Virtual Time, ACM Trans. Programming Languages and Systems 7 (3), 404- 425. (disponible en Aula Virtual) Karian, Z.A. y Dudewicz, E.J. (1999). Modern Statistical, Systems and GPSS Simulation, 2ª Ed., CRC Press. Kelton, W.D., Sadowski, R.P. y Sturrock, D.T. (2004) Simulation with Arena, McGraw-Hill. Lin Y.-B. y Fishwick, A. (1995). Asynchronous Parallel Discrete Event Simulation, IEEE Trans. Systems, Man and Cybernetics, vol. XX. Misra, J. (1986). Distributed Discrete-Event Simulation, Computing Surveys 18 (1), 40-65. (disponible en Aula Virtual) Neelamkavil, F. (1987). Computer Simulation and Modelling, Wiley. Pegden, C.D., Shannon, R.E. y Sadowski, R.P. (1995). Introduction to Simulation Using SIMAN, McGraw-Hill Inc. MÉTODOS DE SIMULACIÓN Capítulo 4. Simulación de sucesos discretos Pooley, R.J. (1987). An Introduction to Programming in SIMULA, Blackwell Scientific Publications. Pritsker, A.A. (1974). The GASP-V Simulation Language, Wiley. Pritsker, A.A. y O'Reilly, J.J. (1999). Simulation with Visual SLAM and AweSim, Wiley. Rimvall, C.M. y Cellier, F.E. (1982). The GASP-VI Simulation Package for Process-Oriented Combined Continuous and Discrete System Simulation, Proceedings of the 10th IMACS World Congress on Simulation and Scientific Computation, 413-416. Ross, S. (1997). Simulation, Academic Press. Russell, E.C. (1999). Building Simulation Models with SIMSCRIPT II.5, CACI Products Company. Solomon, S.L. (1983). Simulation of Waiting-Line Systems, Prentice Hall. Swain, J.J. (2013). Discrete Event Simulation Software Tools: A better reality, OR/MS Today, Vol. 40, No. 5, pp. 48-59. Taha, H.A. (1991). Simulation with SIMNET II, Proceedings of the 23rd Conference on Winter Simulation, 132-135. (disponible en Aula Virtual)